[{"title":"Evolving Diverse Sets of Tours for the Travelling Salesperson Problem","date_created":"2023-11-14T15:58:58Z","publisher":"Association for Computing Machinery","year":"2020","language":[{"iso":"eng"}],"keyword":["diversity maximisation","evolutionary algorithms","travelling salesperson problem"],"abstract":[{"lang":"eng","text":"Evolving diverse sets of high quality solutions has gained increasing interest in the evolutionary computation literature in recent years. With this paper, we contribute to this area of research by examining evolutionary diversity optimisation approaches for the classical Traveling Salesperson Problem (TSP). We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions when adopting these measures. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches. Furthermore, we compare our approaches in terms of theoretical properties and the final set of tours obtained by the evolutionary diversity optimisation algorithm."}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","doi":"10.1145/3377930.3389844","author":[{"full_name":"Do, Anh Viet","last_name":"Do","first_name":"Anh Viet"},{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob"},{"full_name":"Neumann, Aneta","last_name":"Neumann","first_name":"Aneta"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"date_updated":"2023-12-13T10:48:50Z","page":"681–689","citation":{"short":"A.V. Do, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 681–689.","mla":"Do, Anh Viet, et al. “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 681–689, doi:<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>.","bibtex":"@inproceedings{Do_Bossek_Neumann_Neumann_2020, place={New York, NY, USA}, series={GECCO’20}, title={Evolving Diverse Sets of Tours for the Travelling Salesperson Problem}, DOI={<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Do, Anh Viet and Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={681–689}, collection={GECCO’20} }","apa":"Do, A. V., Bossek, J., Neumann, A., &#38; Neumann, F. (2020). Evolving Diverse Sets of Tours for the Travelling Salesperson Problem. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 681–689. <a href=\"https://doi.org/10.1145/3377930.3389844\">https://doi.org/10.1145/3377930.3389844</a>","ama":"Do AV, Bossek J, Neumann A, Neumann F. Evolving Diverse Sets of Tours for the Travelling Salesperson Problem. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO’20. Association for Computing Machinery; 2020:681–689. doi:<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>","ieee":"A. V. Do, J. Bossek, A. Neumann, and F. Neumann, “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 681–689, doi: <a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>.","chicago":"Do, Anh Viet, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 681–689. GECCO’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3389844\">https://doi.org/10.1145/3377930.3389844</a>."},"place":"New York, NY, USA","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"extern":"1","department":[{"_id":"819"}],"user_id":"102979","series_title":"GECCO’20","_id":"48879","status":"public","type":"conference"},{"abstract":[{"lang":"eng","text":"Performance comparisons of optimization algorithms are heavily influenced by the underlying indicator(s). In this paper we investigate commonly used performance indicators for single-objective stochastic solvers, such as the Penalized Average Runtime (e.g., PAR10) or the Expected Running Time (ERT), based on exemplary benchmark performances of state-of-the-art inexact TSP solvers. Thereby, we introduce a methodology for analyzing the effects of (usually heuristically set) indicator parametrizations - such as the penalty factor and the method used for aggregating across multiple runs - w.r.t. the robustness of the considered optimization algorithms."}],"status":"public","publication":"Proceedings of the Genetic and Evolutionary Computation Conference Companion","type":"conference","keyword":["algorithm selection","optimization","performance measures","transportation","travelling salesperson problem"],"language":[{"iso":"eng"}],"extern":"1","_id":"48885","department":[{"_id":"819"}],"user_id":"102979","series_title":"GECCO’18","year":"2018","place":"New York, NY, USA","page":"1737–1744","citation":{"apa":"Kerschke, P., Bossek, J., &#38; Trautmann, H. (2018). Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers. <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 1737–1744. <a href=\"https://doi.org/10.1145/3205651.3208233\">https://doi.org/10.1145/3205651.3208233</a>","bibtex":"@inproceedings{Kerschke_Bossek_Trautmann_2018, place={New York, NY, USA}, series={GECCO’18}, title={Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers}, DOI={<a href=\"https://doi.org/10.1145/3205651.3208233\">10.1145/3205651.3208233</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion}, publisher={Association for Computing Machinery}, author={Kerschke, Pascal and Bossek, Jakob and Trautmann, Heike}, year={2018}, pages={1737–1744}, collection={GECCO’18} }","mla":"Kerschke, Pascal, et al. “Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers.” <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, Association for Computing Machinery, 2018, pp. 1737–1744, doi:<a href=\"https://doi.org/10.1145/3205651.3208233\">10.1145/3205651.3208233</a>.","short":"P. Kerschke, J. Bossek, H. Trautmann, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, New York, NY, USA, 2018, pp. 1737–1744.","ieee":"P. Kerschke, J. Bossek, and H. Trautmann, “Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 2018, pp. 1737–1744, doi: <a href=\"https://doi.org/10.1145/3205651.3208233\">10.1145/3205651.3208233</a>.","chicago":"Kerschke, Pascal, Jakob Bossek, and Heike Trautmann. “Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 1737–1744. GECCO’18. New York, NY, USA: Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3205651.3208233\">https://doi.org/10.1145/3205651.3208233</a>.","ama":"Kerschke P, Bossek J, Trautmann H. Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>. GECCO’18. Association for Computing Machinery; 2018:1737–1744. doi:<a href=\"https://doi.org/10.1145/3205651.3208233\">10.1145/3205651.3208233</a>"},"publication_identifier":{"isbn":["978-1-4503-5764-7"]},"title":"Parameterization of State-of-the-Art Performance Indicators: A Robustness Study Based on Inexact TSP Solvers","doi":"10.1145/3205651.3208233","date_updated":"2023-12-13T10:48:38Z","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:59Z","author":[{"full_name":"Kerschke, Pascal","last_name":"Kerschke","first_name":"Pascal"},{"full_name":"Bossek, Jakob","id":"102979","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"}]},{"volume":26,"date_created":"2023-11-14T15:58:58Z","author":[{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"},{"full_name":"Kotthoff, Lars","last_name":"Kotthoff","first_name":"Lars"},{"last_name":"Bossek","orcid":"0000-0002-4121-4668","id":"102979","full_name":"Bossek, Jakob","first_name":"Jakob"},{"full_name":"Hoos, Holger H.","last_name":"Hoos","first_name":"Holger H."},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"}],"date_updated":"2023-12-13T10:51:26Z","doi":"10.1162/evco_a_00215","title":"Leveraging TSP Solver Complementarity through Machine Learning","issue":"4","publication_identifier":{"issn":["1063-6560"]},"intvolume":"        26","page":"597–620","citation":{"ieee":"P. Kerschke, L. Kotthoff, J. Bossek, H. H. Hoos, and H. Trautmann, “Leveraging TSP Solver Complementarity through Machine Learning,” <i>Evolutionary Computation</i>, vol. 26, no. 4, pp. 597–620, 2018, doi: <a href=\"https://doi.org/10.1162/evco_a_00215\">10.1162/evco_a_00215</a>.","chicago":"Kerschke, Pascal, Lars Kotthoff, Jakob Bossek, Holger H. Hoos, and Heike Trautmann. “Leveraging TSP Solver Complementarity through Machine Learning.” <i>Evolutionary Computation</i> 26, no. 4 (2018): 597–620. <a href=\"https://doi.org/10.1162/evco_a_00215\">https://doi.org/10.1162/evco_a_00215</a>.","ama":"Kerschke P, Kotthoff L, Bossek J, Hoos HH, Trautmann H. Leveraging TSP Solver Complementarity through Machine Learning. <i>Evolutionary Computation</i>. 2018;26(4):597–620. doi:<a href=\"https://doi.org/10.1162/evco_a_00215\">10.1162/evco_a_00215</a>","bibtex":"@article{Kerschke_Kotthoff_Bossek_Hoos_Trautmann_2018, title={Leveraging TSP Solver Complementarity through Machine Learning}, volume={26}, DOI={<a href=\"https://doi.org/10.1162/evco_a_00215\">10.1162/evco_a_00215</a>}, number={4}, journal={Evolutionary Computation}, author={Kerschke, Pascal and Kotthoff, Lars and Bossek, Jakob and Hoos, Holger H. and Trautmann, Heike}, year={2018}, pages={597–620} }","mla":"Kerschke, Pascal, et al. “Leveraging TSP Solver Complementarity through Machine Learning.” <i>Evolutionary Computation</i>, vol. 26, no. 4, 2018, pp. 597–620, doi:<a href=\"https://doi.org/10.1162/evco_a_00215\">10.1162/evco_a_00215</a>.","short":"P. Kerschke, L. Kotthoff, J. Bossek, H.H. Hoos, H. Trautmann, Evolutionary Computation 26 (2018) 597–620.","apa":"Kerschke, P., Kotthoff, L., Bossek, J., Hoos, H. H., &#38; Trautmann, H. (2018). Leveraging TSP Solver Complementarity through Machine Learning. <i>Evolutionary Computation</i>, <i>26</i>(4), 597–620. <a href=\"https://doi.org/10.1162/evco_a_00215\">https://doi.org/10.1162/evco_a_00215</a>"},"year":"2018","department":[{"_id":"819"}],"user_id":"102979","_id":"48884","language":[{"iso":"eng"}],"keyword":["automated algorithm selection","machine learning.","performance modeling","Travelling Salesperson Problem"],"publication":"Evolutionary Computation","type":"journal_article","status":"public","abstract":[{"lang":"eng","text":"The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers\\textemdash namely, LKH, EAX, restart variants of those, and MAOS\\textemdash on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement."}]}]