@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}}, } @article{48854, abstract = {{We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. The (1+1) Evolutionary Algorithm and RLS operate in a setting where the number of colors is bounded and we are minimizing the number of conflicts. Iterated local search algorithms use an unbounded color palette and aim to use the smallest colors and, consequently, the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i.e., starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. We further show that tailoring mutation operators to parts of the graph where changes have occurred can significantly reduce the expected reoptimization time. In most settings the expected reoptimization time for such tailored algorithms is linear in the number of added edges. However, tailored algorithms cannot prevent exponential times in settings where the original algorithm is inefficient.}}, author = {{Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}}, issn = {{0178-4617}}, journal = {{Algorithmica}}, keywords = {{Dynamic optimization, Evolutionary algorithms, Running time analysis}}, number = {{10}}, pages = {{3148–3179}}, title = {{{Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem}}}, doi = {{10.1007/s00453-021-00838-3}}, volume = {{83}}, year = {{2021}}, } @inproceedings{48847, abstract = {{Dynamic optimization problems have gained significant attention in evolutionary computation as evolutionary algorithms (EAs) can easily adapt to changing environments. We show that EAs can solve the graph coloring problem for bipartite graphs more efficiently by using dynamic optimization. In our approach the graph instance is given incrementally such that the EA can reoptimize its coloring when a new edge introduces a conflict. We show that, when edges are inserted in a way that preserves graph connectivity, Randomized Local Search (RLS) efficiently finds a proper 2-coloring for all bipartite graphs. This includes graphs for which RLS and other EAs need exponential expected time in a static optimization scenario. We investigate different ways of building up the graph by popular graph traversals such as breadth-first-search and depth-first-search and analyse the resulting runtime behavior. We further show that offspring populations (e. g. a (1 + {$\lambda$}) RLS) lead to an exponential speedup in {$\lambda$}. Finally, an island model using 3 islands succeeds in an optimal time of {$\Theta$}(m) on every m-edge bipartite graph, outperforming offspring populations. This is the first example where an island model guarantees a speedup that is not bounded in the number of islands.}}, author = {{Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference}}, isbn = {{978-1-4503-7128-5}}, keywords = {{dynamic optimization, evolutionary algorithms, running time analysis, theory}}, pages = {{1277–1285}}, publisher = {{Association for Computing Machinery}}, title = {{{More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization}}}, doi = {{10.1145/3377930.3390174}}, year = {{2020}}, } @inproceedings{48851, abstract = {{Several important optimization problems in the area of vehicle routing can be seen as variants of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the Traveling Thief Problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour.}}, author = {{Bossek, Jakob and Casel, Katrin and Kerschke, Pascal and Neumann, Frank}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference}}, isbn = {{978-1-4503-7128-5}}, keywords = {{dynamic optimization, evolutionary algorithms, running time analysis, theory}}, pages = {{1286–1294}}, publisher = {{Association for Computing Machinery}}, title = {{{The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics}}}, doi = {{10.1145/3377930.3390243}}, year = {{2020}}, } @inproceedings{48845, abstract = {{In practice, e.g. in delivery and service scenarios, Vehicle-Routing-Problems (VRPs) often imply repeated decision making on dynamic customer requests. As in classical VRPs, tours have to be planned short while the number of serviced customers has to be maximized at the same time resulting in a multi-objective problem. Beyond that, however, dynamic requests lead to the need for re-planning of not yet realized tour parts, while already realized tour parts are irreversible. In this paper we study this type of bi-objective dynamic VRP including sequential decision making and concurrent realization of decisions. We adopt a recently proposed Dynamic Evolutionary Multi-Objective Algorithm (DEMOA) for a related VRP problem and extend it to the more realistic (here considered) scenario of multiple vehicles. We empirically show that our DEMOA is competitive with a multi-vehicle offline and clairvoyant variant of the proposed DEMOA as well as with the dynamic single-vehicle approach proposed earlier.}}, author = {{Bossek, Jakob and Grimme, Christian and Trautmann, Heike}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference}}, isbn = {{978-1-4503-7128-5}}, keywords = {{decision making, dynamic optimization, evolutionary algorithms, multi-objective optimization, vehicle routing}}, pages = {{166–174}}, publisher = {{Association for Computing Machinery}}, title = {{{Dynamic Bi-Objective Routing of Multiple Vehicles}}}, doi = {{10.1145/3377930.3390146}}, year = {{2020}}, } @inproceedings{48841, abstract = {{We tackle a bi-objective dynamic orienteering problem where customer requests arise as time passes by. The goal is to minimize the tour length traveled by a single delivery vehicle while simultaneously keeping the number of dismissed dynamic customers to a minimum. We propose a dynamic Evolutionary Multi-Objective Algorithm which is grounded on insights gained from a previous series of work on an a-posteriori version of the problem, where all request times are known in advance. In our experiments, we simulate different decision maker strategies and evaluate the development of the Pareto-front approximations on exemplary problem instances. It turns out, that despite severely reduced computational budget and no oracle-knowledge of request times the dynamic EMOA is capable of producing approximations which partially dominate the results of the a-posteriori EMOA and dynamic integer linear programming strategies.}}, author = {{Bossek, Jakob and Grimme, Christian and Meisel, Stephan and Rudolph, Günter and Trautmann, Heike}}, booktitle = {{Evolutionary Multi-Criterion Optimization (EMO)}}, editor = {{Deb, Kalyanmoy and Goodman, Erik and Coello Coello, Carlos A. and Klamroth, Kathrin and Miettinen, Kaisa and Mostaghim, Sanaz and Reed, Patrick}}, isbn = {{978-3-030-12598-1}}, keywords = {{Combinatorial optimization, Dynamic optimization, Metaheuristics, Multi-objective optimization, Vehicle routing}}, pages = {{516–528}}, publisher = {{Springer International Publishing}}, title = {{{Bi-Objective Orienteering: Towards a Dynamic Multi-objective Evolutionary Algorithm}}}, doi = {{10.1007/978-3-030-12598-1_41}}, year = {{2019}}, } @inproceedings{48843, abstract = {{We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical graph coloring problem and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. This includes the (1+1) EA and RLS in a setting where the number of colors is bounded and we are minimizing the number of conflicts as well as iterated local search algorithms that use an unbounded color palette and aim to use the smallest colors and - as a consequence - the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i. e. starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. Furthermore, we show how to speed up computations by using problem specific operators concentrating on parts of the graph where changes have occurred.}}, author = {{Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}}, booktitle = {{Proceedings of the Genetic and Evolutionary Computation Conference}}, isbn = {{978-1-4503-6111-8}}, keywords = {{dynamic optimization, evolutionary algorithms, running time analysis, theory}}, pages = {{1443–1451}}, publisher = {{Association for Computing Machinery}}, title = {{{Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring}}}, doi = {{10.1145/3321707.3321792}}, year = {{2019}}, }