[{"title":"Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:52Z","year":"2019","keyword":["benchmarking","instance features","optimization","problem generation","traveling salesperson problem"],"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Evolutionary algorithms have successfully been applied to evolve problem instances that exhibit a significant difference in performance for a given algorithm or a pair of algorithms inter alia for the Traveling Salesperson Problem (TSP). Creating a large variety of instances is crucial for successful applications in the blooming field of algorithm selection. In this paper, we introduce new and creative mutation operators for evolving instances of the TSP. We show that adopting those operators in an evolutionary algorithm allows for the generation of benchmark sets with highly desirable properties: (1) novelty by clear visual distinction to established benchmark sets in the field, (2) visual and quantitative diversity in the space of TSP problem characteristics, and (3) significant performance differences with respect to the restart versions of heuristic state-of-the-art TSP solvers EAX and LKH. The important aspect of diversity is addressed and achieved solely by the proposed mutation operators and not enforced by explicit diversity preservation."}],"publication":"Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","doi":"10.1145/3299904.3340307","date_updated":"2023-12-13T10:42:57Z","author":[{"first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979","orcid":"0000-0002-4121-4668","last_name":"Bossek"},{"last_name":"Kerschke","full_name":"Kerschke, Pascal","first_name":"Pascal"},{"first_name":"Aneta","full_name":"Neumann, Aneta","last_name":"Neumann"},{"first_name":"Markus","full_name":"Wagner, Markus","last_name":"Wagner"},{"last_name":"Neumann","full_name":"Neumann, Frank","first_name":"Frank"},{"last_name":"Trautmann","full_name":"Trautmann, Heike","first_name":"Heike"}],"place":"New York, NY, USA","page":"58–71","citation":{"apa":"Bossek, J., Kerschke, P., Neumann, A., Wagner, M., Neumann, F., &#38; Trautmann, H. (2019). Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators. <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 58–71. <a href=\"https://doi.org/10.1145/3299904.3340307\">https://doi.org/10.1145/3299904.3340307</a>","mla":"Bossek, Jakob, et al. “Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators.” <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, Association for Computing Machinery, 2019, pp. 58–71, doi:<a href=\"https://doi.org/10.1145/3299904.3340307\">10.1145/3299904.3340307</a>.","bibtex":"@inproceedings{Bossek_Kerschke_Neumann_Wagner_Neumann_Trautmann_2019, place={New York, NY, USA}, series={FOGA ’19}, title={Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators}, DOI={<a href=\"https://doi.org/10.1145/3299904.3340307\">10.1145/3299904.3340307</a>}, booktitle={Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Kerschke, Pascal and Neumann, Aneta and Wagner, Markus and Neumann, Frank and Trautmann, Heike}, year={2019}, pages={58–71}, collection={FOGA ’19} }","short":"J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, H. Trautmann, in: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, New York, NY, USA, 2019, pp. 58–71.","chicago":"Bossek, Jakob, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. “Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators.” In <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 58–71. FOGA ’19. New York, NY, USA: Association for Computing Machinery, 2019. <a href=\"https://doi.org/10.1145/3299904.3340307\">https://doi.org/10.1145/3299904.3340307</a>.","ieee":"J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, and H. Trautmann, “Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators,” in <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 2019, pp. 58–71, doi: <a href=\"https://doi.org/10.1145/3299904.3340307\">10.1145/3299904.3340307</a>.","ama":"Bossek J, Kerschke P, Neumann A, Wagner M, Neumann F, Trautmann H. Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators. In: <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>. FOGA ’19. Association for Computing Machinery; 2019:58–71. doi:<a href=\"https://doi.org/10.1145/3299904.3340307\">10.1145/3299904.3340307</a>"},"publication_identifier":{"isbn":["978-1-4503-6254-2"]},"publication_status":"published","extern":"1","_id":"48842","department":[{"_id":"819"}],"user_id":"102979","series_title":"FOGA ’19","status":"public","type":"conference"},{"publication":"Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms","abstract":[{"text":"The edge coloring problem asks for an assignment of colors to edges of a graph such that no two incident edges share the same color and the number of colors is minimized. It is known that all graphs with maximum degree {$\\Delta$} can be colored with {$\\Delta$} or {$\\Delta$} + 1 colors, but it is NP-hard to determine whether {$\\Delta$} colors are sufficient. We present the first runtime analysis of evolutionary algorithms (EAs) for the edge coloring problem. Simple EAs such as RLS and (1+1) EA efficiently find (2{$\\Delta$} - 1)-colorings on arbitrary graphs and optimal colorings for even and odd cycles, paths, star graphs and arbitrary trees. A partial analysis for toroids also suggests efficient runtimes in bipartite graphs with many cycles. Experiments support these findings and investigate additional graph classes such as hypercubes, complete graphs and complete bipartite graphs. Theoretical and experimental results suggest that simple EAs find optimal colorings for all these graph classes in expected time O({$\\Delta\\mathscrl$}2m log m), where m is the number of edges and {$\\mathscrl$} is the length of the longest simple path in the graph.","lang":"eng"}],"keyword":["edge coloring problem","runtime analysis"],"language":[{"iso":"eng"}],"year":"2019","publisher":"Association for Computing Machinery","date_created":"2023-11-14T15:58:56Z","title":"Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem","type":"conference","status":"public","_id":"48870","user_id":"102979","series_title":"FOGA ’19","department":[{"_id":"819"}],"extern":"1","publication_status":"published","publication_identifier":{"isbn":["978-1-4503-6254-2"]},"place":"New York, NY, USA","citation":{"ama":"Bossek J, Sudholt D. Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem. In: <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>. FOGA ’19. Association for Computing Machinery; 2019:102–115. doi:<a href=\"https://doi.org/10.1145/3299904.3340311\">10.1145/3299904.3340311</a>","chicago":"Bossek, Jakob, and Dirk Sudholt. “Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem.” In <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 102–115. FOGA ’19. New York, NY, USA: Association for Computing Machinery, 2019. <a href=\"https://doi.org/10.1145/3299904.3340311\">https://doi.org/10.1145/3299904.3340311</a>.","ieee":"J. Bossek and D. Sudholt, “Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem,” in <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 2019, pp. 102–115, doi: <a href=\"https://doi.org/10.1145/3299904.3340311\">10.1145/3299904.3340311</a>.","apa":"Bossek, J., &#38; Sudholt, D. (2019). Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem. <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, 102–115. <a href=\"https://doi.org/10.1145/3299904.3340311\">https://doi.org/10.1145/3299904.3340311</a>","mla":"Bossek, Jakob, and Dirk Sudholt. “Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem.” <i>Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms</i>, Association for Computing Machinery, 2019, pp. 102–115, doi:<a href=\"https://doi.org/10.1145/3299904.3340311\">10.1145/3299904.3340311</a>.","short":"J. Bossek, D. Sudholt, in: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Association for Computing Machinery, New York, NY, USA, 2019, pp. 102–115.","bibtex":"@inproceedings{Bossek_Sudholt_2019, place={New York, NY, USA}, series={FOGA ’19}, title={Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem}, DOI={<a href=\"https://doi.org/10.1145/3299904.3340311\">10.1145/3299904.3340311</a>}, booktitle={Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Sudholt, Dirk}, year={2019}, pages={102–115}, collection={FOGA ’19} }"},"page":"102–115","date_updated":"2023-12-13T10:46:12Z","author":[{"first_name":"Jakob","orcid":"0000-0002-4121-4668","last_name":"Bossek","id":"102979","full_name":"Bossek, Jakob"},{"first_name":"Dirk","last_name":"Sudholt","full_name":"Sudholt, Dirk"}],"doi":"10.1145/3299904.3340311"}]