---
_id: '48842'
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.'
author:
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Pascal
  full_name: Kerschke, Pascal
  last_name: Kerschke
- first_name: Aneta
  full_name: Neumann, Aneta
  last_name: Neumann
- first_name: Markus
  full_name: Wagner, Markus
  last_name: Wagner
- first_name: Frank
  full_name: Neumann, Frank
  last_name: Neumann
- first_name: Heike
  full_name: Trautmann, Heike
  last_name: Trautmann
citation:
  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>'
  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>
  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}
    }'
  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>.'
  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>.
  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.'
date_created: 2023-11-14T15:58:52Z
date_updated: 2023-12-13T10:42:57Z
department:
- _id: '819'
doi: 10.1145/3299904.3340307
extern: '1'
keyword:
- benchmarking
- instance features
- optimization
- problem generation
- traveling salesperson problem
language:
- iso: eng
page: 58–71
place: New York, NY, USA
publication: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic
  Algorithms
publication_identifier:
  isbn:
  - 978-1-4503-6254-2
publication_status: published
publisher: Association for Computing Machinery
series_title: FOGA ’19
status: public
title: Evolving Diverse TSP Instances by Means of Novel and Creative Mutation Operators
type: conference
user_id: '102979'
year: '2019'
...
---
_id: '48870'
abstract:
- lang: eng
  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.
author:
- first_name: Jakob
  full_name: Bossek, Jakob
  id: '102979'
  last_name: Bossek
  orcid: 0000-0002-4121-4668
- first_name: Dirk
  full_name: Sudholt, Dirk
  last_name: Sudholt
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>'
  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>
  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}
    }'
  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>.'
  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.'
date_created: 2023-11-14T15:58:56Z
date_updated: 2023-12-13T10:46:12Z
department:
- _id: '819'
doi: 10.1145/3299904.3340311
extern: '1'
keyword:
- edge coloring problem
- runtime analysis
language:
- iso: eng
page: 102–115
place: New York, NY, USA
publication: Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic
  Algorithms
publication_identifier:
  isbn:
  - 978-1-4503-6254-2
publication_status: published
publisher: Association for Computing Machinery
series_title: FOGA ’19
status: public
title: Time Complexity Analysis of RLS and (1 + 1) EA for the Edge Coloring Problem
type: conference
user_id: '102979'
year: '2019'
...