@inproceedings{48869,
  abstract     = {{Evolutionary algorithms have been shown to obtain good solutions for complex optimization problems in static and dynamic environments. It is important to understand the behaviour of evolutionary algorithms for complex optimization problems that also involve dynamic and/or stochastic components in a systematic way in order to further increase their applicability to real-world problems. We investigate the node weighted traveling salesperson problem (W-TSP), which provides an abstraction of a wide range of weighted TSP problems, in dynamic settings. In the dynamic setting of the problem, items that have to be collected as part of a TSP tour change over time. We first present a dynamic setup for the dynamic W-TSP parameterized by different types of changes that are applied to the set of items to be collected when traversing the tour. Our first experimental investigations study the impact of such changes on resulting optimized tours in order to provide structural insights of optimization solutions. Afterwards, we investigate simple mutation-based evolutionary algorithms and study the impact of the mutation operators and the use of populations with dealing with the dynamic changes to the node weights of the problem.}},
  author       = {{Bossek, Jakob and Neumann, Aneta and Neumann, Frank}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{9798400701191}},
  keywords     = {{dynamic optimization, evolutionary algorithms, re-optimization, weighted traveling salesperson problem}},
  pages        = {{248–256}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{On the Impact of Basic Mutation Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem}}},
  doi          = {{10.1145/3583131.3590384}},
  year         = {{2023}},
}

@inproceedings{48872,
  abstract     = {{Quality diversity (QD) is a branch of evolutionary computation that gained increasing interest in recent years. The Map-Elites QD approach defines a feature space, i.e., a partition of the search space, and stores the best solution for each cell of this space. We study a simple QD algorithm in the context of pseudo-Boolean optimisation on the "number of ones" feature space, where the ith cell stores the best solution amongst those with a number of ones in [(i - 1)k, ik - 1]. Here k is a granularity parameter 1 {$\leq$} k {$\leq$} n+1. We give a tight bound on the expected time until all cells are covered for arbitrary fitness functions and for all k and analyse the expected optimisation time of QD on OneMax and other problems whose structure aligns favourably with the feature space. On combinatorial problems we show that QD finds a (1 - 1/e)-approximation when maximising any monotone sub-modular function with a single uniform cardinality constraint efficiently. Defining the feature space as the number of connected components of a connected graph, we show that QD finds a minimum spanning tree in expected polynomial time.}},
  author       = {{Bossek, Jakob and Sudholt, Dirk}},
  booktitle    = {{Proceedings of the Genetic and Evolutionary Computation Conference}},
  isbn         = {{9798400701191}},
  keywords     = {{quality diversity, runtime analysis}},
  pages        = {{1546–1554}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Runtime Analysis of Quality Diversity Algorithms}}},
  doi          = {{10.1145/3583131.3590383}},
  year         = {{2023}},
}

@inproceedings{48886,
  abstract     = {{Generating new instances via evolutionary methods is commonly used to create new benchmarking data-sets, with a focus on attempting to cover an instance-space as completely as possible. Recent approaches have exploited Quality-Diversity methods to evolve sets of instances that are both diverse and discriminatory with respect to a portfolio of solvers, but these methods can be challenging when attempting to find diversity in a high-dimensional feature-space. We address this issue by training a model based on Principal Component Analysis on existing instances to create a low-dimension projection of the high-dimension feature-vectors, and then apply Novelty Search directly in the new low-dimension space. We conduct experiments to evolve diverse and discriminatory instances of Knapsack Problems, comparing the use of Novelty Search in the original feature-space to using Novelty Search in a low-dimensional projection, and repeat over a given set of dimensions. We find that the methods are complementary: if treated as an ensemble, they collectively provide increased coverage of the space. Specifically, searching for novelty in a low-dimension space contributes 56% of the filled regions of the space, while searching directly in the feature-space covers the remaining 44%.}},
  author       = {{Marrero, Alejandro and Segredo, Eduardo and Hart, Emma and Bossek, Jakob and Neumann, Aneta}},
  booktitle    = {{Proceedings of the Genetic} and Evolutionary Computation Conference}},
  isbn         = {{9798400701191}},
  keywords     = {{evolutionary computation, instance generation, instance-space analysis, knapsack problem, novelty search}},
  pages        = {{312–320}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{{Generating Diverse and Discriminatory Knapsack Instances by Searching for Novelty in Variable Dimensions of Feature-Space}}},
  doi          = {{10.1145/3583131.3590504}},
  year         = {{2023}},
}