[{"abstract":[{"text":"In recent years, Evolutionary Algorithms (EAs) have frequently been adopted to evolve instances for optimization problems that pose difficulties for one algorithm while being rather easy for a competitor and vice versa. Typically, this is achieved by either minimizing or maximizing the performance difference or ratio which serves as the fitness function. Repeating this process is useful to gain insights into strengths/weaknesses of certain algorithms or to build a set of instances with strong performance differences as a foundation for automatic per-instance algorithm selection or configuration. We contribute to this branch of research by proposing fitness-functions to evolve instances that show large performance differences for more than just two algorithms simultaneously. As a proof-of-principle, we evolve instances of the multi-component Traveling Thief Problem (TTP) for three incomplete TTP-solvers. Our results point out that our strategies are promising, but unsurprisingly their success strongly relies on the algorithms’ performance complementarity.","lang":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference Companion","language":[{"iso":"eng"}],"keyword":["evolutionary algorithms","evolving instances","fitness function","instance hardness","traveling thief problem (TTP)"],"year":"2021","title":"Generating Instances with Performance Differences for More than Just Two Algorithms","date_created":"2023-11-14T15:58:57Z","publisher":"Association for Computing Machinery","status":"public","type":"conference","extern":"1","department":[{"_id":"819"}],"user_id":"102979","series_title":"GECCO’21","_id":"48876","page":"1423–1432","citation":{"apa":"Bossek, J., &#38; Wagner, M. (2021). Generating Instances with Performance Differences for More than Just Two Algorithms. <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 1423–1432. <a href=\"https://doi.org/10.1145/3449726.3463165\">https://doi.org/10.1145/3449726.3463165</a>","bibtex":"@inproceedings{Bossek_Wagner_2021, place={New York, NY, USA}, series={GECCO’21}, title={Generating Instances with Performance Differences for More than Just Two Algorithms}, DOI={<a href=\"https://doi.org/10.1145/3449726.3463165\">10.1145/3449726.3463165</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Wagner, Markus}, year={2021}, pages={1423–1432}, collection={GECCO’21} }","short":"J. Bossek, M. Wagner, in: Proceedings of the Genetic and Evolutionary Computation Conference Companion, Association for Computing Machinery, New York, NY, USA, 2021, pp. 1423–1432.","mla":"Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences for More than Just Two Algorithms.” <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, Association for Computing Machinery, 2021, pp. 1423–1432, doi:<a href=\"https://doi.org/10.1145/3449726.3463165\">10.1145/3449726.3463165</a>.","ama":"Bossek J, Wagner M. Generating Instances with Performance Differences for More than Just Two Algorithms. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>. GECCO’21. Association for Computing Machinery; 2021:1423–1432. doi:<a href=\"https://doi.org/10.1145/3449726.3463165\">10.1145/3449726.3463165</a>","ieee":"J. Bossek and M. Wagner, “Generating Instances with Performance Differences for More than Just Two Algorithms,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 2021, pp. 1423–1432, doi: <a href=\"https://doi.org/10.1145/3449726.3463165\">10.1145/3449726.3463165</a>.","chicago":"Bossek, Jakob, and Markus Wagner. “Generating Instances with Performance Differences for More than Just Two Algorithms.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference Companion</i>, 1423–1432. GECCO’21. New York, NY, USA: Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3449726.3463165\">https://doi.org/10.1145/3449726.3463165</a>."},"place":"New York, NY, USA","publication_identifier":{"isbn":["978-1-4503-8351-6"]},"doi":"10.1145/3449726.3463165","author":[{"first_name":"Jakob","id":"102979","full_name":"Bossek, Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"last_name":"Wagner","full_name":"Wagner, Markus","first_name":"Markus"}],"date_updated":"2023-12-13T10:47:41Z"},{"extern":"1","user_id":"102979","series_title":"Lecture Notes in Computer Science","department":[{"_id":"819"}],"_id":"48873","status":"public","editor":[{"first_name":"Paola","last_name":"Festa","full_name":"Festa, Paola"},{"last_name":"Sellmann","full_name":"Sellmann, Meinolf","first_name":"Meinolf"},{"last_name":"Vanschoren","full_name":"Vanschoren, Joaquin","first_name":"Joaquin"}],"type":"conference","doi":"10.1007/978-3-319-50349-3_4","author":[{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"}],"date_updated":"2023-12-13T10:47:05Z","citation":{"ama":"Bossek J, Trautmann H. Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers. In: Festa P, Sellmann M, Vanschoren J, eds. <i>Learning and Intelligent Optimization</i>. Lecture Notes in Computer Science. Springer International Publishing; 2016:48–59. doi:<a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">10.1007/978-3-319-50349-3_4</a>","ieee":"J. Bossek and H. Trautmann, “Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers,” in <i>Learning and Intelligent Optimization</i>, 2016, pp. 48–59, doi: <a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">10.1007/978-3-319-50349-3_4</a>.","chicago":"Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers.” In <i>Learning and Intelligent Optimization</i>, edited by Paola Festa, Meinolf Sellmann, and Joaquin Vanschoren, 48–59. Lecture Notes in Computer Science. Cham: Springer International Publishing, 2016. <a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">https://doi.org/10.1007/978-3-319-50349-3_4</a>.","apa":"Bossek, J., &#38; Trautmann, H. (2016). Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers. In P. Festa, M. Sellmann, &#38; J. Vanschoren (Eds.), <i>Learning and Intelligent Optimization</i> (pp. 48–59). Springer International Publishing. <a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">https://doi.org/10.1007/978-3-319-50349-3_4</a>","mla":"Bossek, Jakob, and Heike Trautmann. “Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers.” <i>Learning and Intelligent Optimization</i>, edited by Paola Festa et al., Springer International Publishing, 2016, pp. 48–59, doi:<a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">10.1007/978-3-319-50349-3_4</a>.","short":"J. Bossek, H. Trautmann, in: P. Festa, M. Sellmann, J. Vanschoren (Eds.), Learning and Intelligent Optimization, Springer International Publishing, Cham, 2016, pp. 48–59.","bibtex":"@inproceedings{Bossek_Trautmann_2016, place={Cham}, series={Lecture Notes in Computer Science}, title={Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-50349-3_4\">10.1007/978-3-319-50349-3_4</a>}, booktitle={Learning and Intelligent Optimization}, publisher={Springer International Publishing}, author={Bossek, Jakob and Trautmann, Heike}, editor={Festa, Paola and Sellmann, Meinolf and Vanschoren, Joaquin}, year={2016}, pages={48–59}, collection={Lecture Notes in Computer Science} }"},"page":"48–59","place":"Cham","publication_status":"published","publication_identifier":{"isbn":["978-3-319-50349-3"]},"language":[{"iso":"eng"}],"keyword":["Algorithm selection","Feature selection","Instance hardness","TSP"],"abstract":[{"lang":"eng","text":"Despite the intrinsic hardness of the Traveling Salesperson Problem (TSP) heuristic solvers, e.g., LKH+restart and EAX+restart, are remarkably successful in generating satisfactory or even optimal solutions. However, the reasons for their success are not yet fully understood. Recent approaches take an analytical viewpoint and try to identify instance features, which make an instance hard or easy to solve. We contribute to this area by generating instance sets for couples of TSP algorithms A and B by maximizing/minimizing their performance difference in order to generate instances which are easier to solve for one solver and much harder to solve for the other. This instance set offers the potential to identify key features which allow to distinguish between the problem hardness classes of both algorithms."}],"publication":"Learning and Intelligent Optimization","title":"Evolving Instances for Maximizing Performance Differences of State-of-the-Art Inexact TSP Solvers","date_created":"2023-11-14T15:58:57Z","publisher":"Springer International Publishing","year":"2016"},{"author":[{"last_name":"Bossek","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob","id":"102979","first_name":"Jakob"},{"first_name":"Heike","full_name":"Trautmann, Heike","last_name":"Trautmann"}],"date_created":"2023-11-14T15:58:57Z","date_updated":"2023-12-13T10:47:11Z","publisher":"Springer-Verlag","doi":"10.1007/978-3-319-49130-1_1","title":"Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference","publication_identifier":{"isbn":["978-3-319-49129-5"]},"publication_status":"published","page":"3–12","citation":{"apa":"Bossek, J., &#38; Trautmann, H. (2016). Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference. <i>Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>, 3–12. <a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">https://doi.org/10.1007/978-3-319-49130-1_1</a>","mla":"Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.” <i>Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>, Springer-Verlag, 2016, pp. 3–12, doi:<a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">10.1007/978-3-319-49130-1_1</a>.","bibtex":"@inproceedings{Bossek_Trautmann_2016, place={Berlin, Heidelberg}, series={AI*IA 2016}, title={Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference}, DOI={<a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">10.1007/978-3-319-49130-1_1</a>}, booktitle={Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037}, publisher={Springer-Verlag}, author={Bossek, Jakob and Trautmann, Heike}, year={2016}, pages={3–12}, collection={AI*IA 2016} }","short":"J. Bossek, H. Trautmann, in: Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037, Springer-Verlag, Berlin, Heidelberg, 2016, pp. 3–12.","ieee":"J. Bossek and H. Trautmann, “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference,” in <i>Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>, 2016, pp. 3–12, doi: <a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">10.1007/978-3-319-49130-1_1</a>.","chicago":"Bossek, Jakob, and Heike Trautmann. “Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference.” In <i>Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>, 3–12. AI*IA 2016. Berlin, Heidelberg: Springer-Verlag, 2016. <a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">https://doi.org/10.1007/978-3-319-49130-1_1</a>.","ama":"Bossek J, Trautmann H. Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance Difference. In: <i>Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037</i>. AI*IA 2016. Springer-Verlag; 2016:3–12. doi:<a href=\"https://doi.org/10.1007/978-3-319-49130-1_1\">10.1007/978-3-319-49130-1_1</a>"},"year":"2016","place":"Berlin, Heidelberg","user_id":"102979","series_title":"AI*IA 2016","_id":"48874","extern":"1","language":[{"iso":"eng"}],"keyword":["Combinatorial optimization","Instance hardness","Metaheuristics","Transportation","TSP"],"publication":"Proceedings of the XV International Conference of the Italian Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 10037","type":"conference","status":"public","abstract":[{"text":"State of the Art inexact solvers of the NP-hard Traveling Salesperson Problem TSP are known to mostly yield high-quality solutions in reasonable computation times. With the purpose of understanding different levels of instance difficulties, instances for the current State of the Art heuristic TSP solvers LKH+restart and EAX+restart are presented which are evolved using a sophisticated evolutionary algorithm. More specifically, the performance differences of the respective solvers are maximized resulting in instances which are easier to solve for one solver and much more difficult for the other. Focusing on both optimization directions, instance features are identified which characterize both types of instances and increase the understanding of solver performance differences.","lang":"eng"}]}]