[{"date_created":"2023-11-14T15:58:53Z","keyword":["dynamic optimization","evolutionary algorithms","running time analysis","theory"],"type":"conference","department":[{"_id":"819"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","extern":"1","abstract":[{"lang":"eng","text":"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."}],"language":[{"iso":"eng"}],"series_title":"GECCO ’20","doi":"10.1145/3377930.3390174","year":"2020","title":"More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"author":[{"first_name":"Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob","id":"102979"},{"last_name":"Neumann","first_name":"Frank","full_name":"Neumann, Frank"},{"last_name":"Peng","first_name":"Pan","full_name":"Peng, Pan"},{"last_name":"Sudholt","first_name":"Dirk","full_name":"Sudholt, Dirk"}],"publication_status":"published","date_updated":"2023-12-13T10:43:41Z","place":"New York, NY, USA","citation":{"ieee":"J. Bossek, F. Neumann, P. Peng, and D. Sudholt, “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 1277–1285, doi: <a href=\"https://doi.org/10.1145/3377930.3390174\">10.1145/3377930.3390174</a>.","apa":"Bossek, J., Neumann, F., Peng, P., &#38; Sudholt, D. (2020). More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1277–1285. <a href=\"https://doi.org/10.1145/3377930.3390174\">https://doi.org/10.1145/3377930.3390174</a>","chicago":"Bossek, Jakob, Frank Neumann, Pan Peng, and Dirk Sudholt. “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1277–1285. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390174\">https://doi.org/10.1145/3377930.3390174</a>.","short":"J. Bossek, F. Neumann, P. Peng, D. Sudholt, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 1277–1285.","mla":"Bossek, Jakob, et al. “More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 1277–1285, doi:<a href=\"https://doi.org/10.1145/3377930.3390174\">10.1145/3377930.3390174</a>.","bibtex":"@inproceedings{Bossek_Neumann_Peng_Sudholt_2020, place={New York, NY, USA}, series={GECCO ’20}, title={More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390174\">10.1145/3377930.3390174</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Neumann, Frank and Peng, Pan and Sudholt, Dirk}, year={2020}, pages={1277–1285}, collection={GECCO ’20} }","ama":"Bossek J, Neumann F, Peng P, Sudholt D. More Effective Randomized Search Heuristics for Graph Coloring through Dynamic Optimization. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:1277–1285. doi:<a href=\"https://doi.org/10.1145/3377930.3390174\">10.1145/3377930.3390174</a>"},"page":"1277–1285","_id":"48847","publisher":"Association for Computing Machinery","user_id":"102979","status":"public"},{"place":"New York, NY, USA","citation":{"ieee":"J. Bossek, K. Casel, P. Kerschke, and F. Neumann, “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 1286–1294, doi: <a href=\"https://doi.org/10.1145/3377930.3390243\">10.1145/3377930.3390243</a>.","apa":"Bossek, J., Casel, K., Kerschke, P., &#38; Neumann, F. (2020). The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1286–1294. <a href=\"https://doi.org/10.1145/3377930.3390243\">https://doi.org/10.1145/3377930.3390243</a>","chicago":"Bossek, Jakob, Katrin Casel, Pascal Kerschke, and Frank Neumann. “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 1286–1294. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390243\">https://doi.org/10.1145/3377930.3390243</a>.","short":"J. Bossek, K. Casel, P. Kerschke, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 1286–1294.","mla":"Bossek, Jakob, et al. “The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 1286–1294, doi:<a href=\"https://doi.org/10.1145/3377930.3390243\">10.1145/3377930.3390243</a>.","bibtex":"@inproceedings{Bossek_Casel_Kerschke_Neumann_2020, place={New York, NY, USA}, series={GECCO ’20}, title={The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390243\">10.1145/3377930.3390243</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Casel, Katrin and Kerschke, Pascal and Neumann, Frank}, year={2020}, pages={1286–1294}, collection={GECCO ’20} }","ama":"Bossek J, Casel K, Kerschke P, Neumann F. The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:1286–1294. doi:<a href=\"https://doi.org/10.1145/3377930.3390243\">10.1145/3377930.3390243</a>"},"publisher":"Association for Computing Machinery","_id":"48851","page":"1286–1294","user_id":"102979","status":"public","date_created":"2023-11-14T15:58:53Z","department":[{"_id":"819"}],"keyword":["dynamic optimization","evolutionary algorithms","running time analysis","theory"],"type":"conference","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","abstract":[{"lang":"eng","text":"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."}],"extern":"1","language":[{"iso":"eng"}],"series_title":"GECCO ’20","doi":"10.1145/3377930.3390243","author":[{"last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob","full_name":"Bossek, Jakob","id":"102979"},{"last_name":"Casel","first_name":"Katrin","full_name":"Casel, Katrin"},{"first_name":"Pascal","last_name":"Kerschke","full_name":"Kerschke, Pascal"},{"full_name":"Neumann, Frank","first_name":"Frank","last_name":"Neumann"}],"publication_identifier":{"isbn":["978-1-4503-7128-5"]},"title":"The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics","year":"2020","date_updated":"2023-12-13T10:43:33Z","publication_status":"published"},{"department":[{"_id":"819"}],"type":"conference","keyword":["decision making","dynamic optimization","evolutionary algorithms","multi-objective optimization","vehicle routing"],"date_created":"2023-11-14T15:58:52Z","extern":"1","abstract":[{"text":"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.","lang":"eng"}],"publication":"Proceedings of the Genetic and Evolutionary Computation Conference","doi":"10.1145/3377930.3390146","series_title":"GECCO ’20","language":[{"iso":"eng"}],"publication_status":"published","date_updated":"2023-12-13T10:43:24Z","author":[{"full_name":"Bossek, Jakob","last_name":"Bossek","first_name":"Jakob","orcid":"0000-0002-4121-4668","id":"102979"},{"full_name":"Grimme, Christian","first_name":"Christian","last_name":"Grimme"},{"last_name":"Trautmann","first_name":"Heike","full_name":"Trautmann, Heike"}],"publication_identifier":{"isbn":["978-1-4503-7128-5"]},"title":"Dynamic Bi-Objective Routing of Multiple Vehicles","year":"2020","place":"New York, NY, USA","citation":{"ama":"Bossek J, Grimme C, Trautmann H. Dynamic Bi-Objective Routing of Multiple Vehicles. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:166–174. doi:<a href=\"https://doi.org/10.1145/3377930.3390146\">10.1145/3377930.3390146</a>","bibtex":"@inproceedings{Bossek_Grimme_Trautmann_2020, place={New York, NY, USA}, series={GECCO ’20}, title={Dynamic Bi-Objective Routing of Multiple Vehicles}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390146\">10.1145/3377930.3390146</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Grimme, Christian and Trautmann, Heike}, year={2020}, pages={166–174}, collection={GECCO ’20} }","mla":"Bossek, Jakob, et al. “Dynamic Bi-Objective Routing of Multiple Vehicles.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 166–174, doi:<a href=\"https://doi.org/10.1145/3377930.3390146\">10.1145/3377930.3390146</a>.","short":"J. Bossek, C. Grimme, H. Trautmann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 166–174.","chicago":"Bossek, Jakob, Christian Grimme, and Heike Trautmann. “Dynamic Bi-Objective Routing of Multiple Vehicles.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 166–174. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390146\">https://doi.org/10.1145/3377930.3390146</a>.","apa":"Bossek, J., Grimme, C., &#38; Trautmann, H. (2020). Dynamic Bi-Objective Routing of Multiple Vehicles. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 166–174. <a href=\"https://doi.org/10.1145/3377930.3390146\">https://doi.org/10.1145/3377930.3390146</a>","ieee":"J. Bossek, C. Grimme, and H. Trautmann, “Dynamic Bi-Objective Routing of Multiple Vehicles,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 166–174, doi: <a href=\"https://doi.org/10.1145/3377930.3390146\">10.1145/3377930.3390146</a>."},"user_id":"102979","publisher":"Association for Computing Machinery","_id":"48845","page":"166–174","status":"public"},{"date_updated":"2023-12-13T10:44:01Z","publication_status":"published","year":"2020","title":"Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB","publication_identifier":{"isbn":["978-1-4503-7128-5"]},"author":[{"id":"102979","full_name":"Bossek, Jakob","last_name":"Bossek","orcid":"0000-0002-4121-4668","first_name":"Jakob"},{"full_name":"Doerr, Carola","last_name":"Doerr","first_name":"Carola"},{"full_name":"Kerschke, Pascal","first_name":"Pascal","last_name":"Kerschke"}],"doi":"10.1145/3377930.3390155","language":[{"iso":"eng"}],"series_title":"GECCO ’20","abstract":[{"lang":"eng","text":"Sequential model-based optimization (SMBO) approaches are algorithms for solving problems that require computationally or otherwise expensive function evaluations. The key design principle of SMBO is a substitution of the true objective function by a surrogate, which is used to propose the point(s) to be evaluated next. SMBO algorithms are intrinsically modular, leaving the user with many important design choices. Significant research efforts go into understanding which settings perform best for which type of problems. Most works, however, focus on the choice of the model, the acquisition function, and the strategy used to optimize the latter. The choice of the initial sampling strategy, however, receives much less attention. Not surprisingly, quite diverging recommendations can be found in the literature. We analyze in this work how the size and the distribution of the initial sample influences the overall quality of the efficient global optimization (EGO) algorithm, a well-known SMBO approach. While, overall, small initial budgets using Halton sampling seem preferable, we also observe that the performance landscape is rather unstructured. We furthermore identify several situations in which EGO performs unfavorably against random sampling. Both observations indicate that an adaptive SMBO design could be beneficial, making SMBO an interesting test-bed for automated algorithm design."}],"extern":"1","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","type":"conference","keyword":["continuous black-box optimization","design of experiments","initial design","sequential model-based optimization"],"department":[{"_id":"819"}],"date_created":"2023-11-14T15:58:53Z","status":"public","user_id":"102979","page":"778–786","_id":"48850","publisher":"Association for Computing Machinery","citation":{"ieee":"J. Bossek, C. Doerr, and P. Kerschke, “Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 778–786, doi: <a href=\"https://doi.org/10.1145/3377930.3390155\">10.1145/3377930.3390155</a>.","apa":"Bossek, J., Doerr, C., &#38; Kerschke, P. (2020). Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 778–786. <a href=\"https://doi.org/10.1145/3377930.3390155\">https://doi.org/10.1145/3377930.3390155</a>","chicago":"Bossek, Jakob, Carola Doerr, and Pascal Kerschke. “Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 778–786. GECCO ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390155\">https://doi.org/10.1145/3377930.3390155</a>.","short":"J. Bossek, C. Doerr, P. Kerschke, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 778–786.","mla":"Bossek, Jakob, et al. “Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 778–786, doi:<a href=\"https://doi.org/10.1145/3377930.3390155\">10.1145/3377930.3390155</a>.","bibtex":"@inproceedings{Bossek_Doerr_Kerschke_2020, place={New York, NY, USA}, series={GECCO ’20}, title={Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390155\">10.1145/3377930.3390155</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Bossek, Jakob and Doerr, Carola and Kerschke, Pascal}, year={2020}, pages={778–786}, collection={GECCO ’20} }","ama":"Bossek J, Doerr C, Kerschke P. Initial Design Strategies and Their Effects on Sequential Model-Based Optimization: An Exploratory Case Study Based on BBOB. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO ’20. Association for Computing Machinery; 2020:778–786. doi:<a href=\"https://doi.org/10.1145/3377930.3390155\">10.1145/3377930.3390155</a>"},"place":"New York, NY, USA"},{"place":"New York, NY, USA","citation":{"ama":"Do AV, Bossek J, Neumann A, Neumann F. Evolving Diverse Sets of Tours for the Travelling Salesperson Problem. In: <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>. GECCO’20. Association for Computing Machinery; 2020:681–689. doi:<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>","bibtex":"@inproceedings{Do_Bossek_Neumann_Neumann_2020, place={New York, NY, USA}, series={GECCO’20}, title={Evolving Diverse Sets of Tours for the Travelling Salesperson Problem}, DOI={<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>}, booktitle={Proceedings of the Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Do, Anh Viet and Bossek, Jakob and Neumann, Aneta and Neumann, Frank}, year={2020}, pages={681–689}, collection={GECCO’20} }","mla":"Do, Anh Viet, et al. “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem.” <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 681–689, doi:<a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>.","chicago":"Do, Anh Viet, Jakob Bossek, Aneta Neumann, and Frank Neumann. “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem.” In <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 681–689. GECCO’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3389844\">https://doi.org/10.1145/3377930.3389844</a>.","short":"A.V. Do, J. Bossek, A. Neumann, F. Neumann, in: Proceedings of the Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 681–689.","apa":"Do, A. V., Bossek, J., Neumann, A., &#38; Neumann, F. (2020). Evolving Diverse Sets of Tours for the Travelling Salesperson Problem. <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 681–689. <a href=\"https://doi.org/10.1145/3377930.3389844\">https://doi.org/10.1145/3377930.3389844</a>","ieee":"A. V. Do, J. Bossek, A. Neumann, and F. Neumann, “Evolving Diverse Sets of Tours for the Travelling Salesperson Problem,” in <i>Proceedings of the Genetic and Evolutionary Computation Conference</i>, 2020, pp. 681–689, doi: <a href=\"https://doi.org/10.1145/3377930.3389844\">10.1145/3377930.3389844</a>."},"user_id":"102979","_id":"48879","publisher":"Association for Computing Machinery","page":"681–689","status":"public","department":[{"_id":"819"}],"keyword":["diversity maximisation","evolutionary algorithms","travelling salesperson problem"],"type":"conference","date_created":"2023-11-14T15:58:58Z","abstract":[{"text":"Evolving diverse sets of high quality solutions has gained increasing interest in the evolutionary computation literature in recent years. With this paper, we contribute to this area of research by examining evolutionary diversity optimisation approaches for the classical Traveling Salesperson Problem (TSP). We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions when adopting these measures. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches. Furthermore, we compare our approaches in terms of theoretical properties and the final set of tours obtained by the evolutionary diversity optimisation algorithm.","lang":"eng"}],"extern":"1","publication":"Proceedings of the Genetic and Evolutionary Computation Conference","doi":"10.1145/3377930.3389844","language":[{"iso":"eng"}],"series_title":"GECCO’20","date_updated":"2023-12-13T10:48:50Z","author":[{"full_name":"Do, Anh Viet","last_name":"Do","first_name":"Anh Viet"},{"id":"102979","last_name":"Bossek","first_name":"Jakob","orcid":"0000-0002-4121-4668","full_name":"Bossek, Jakob"},{"last_name":"Neumann","first_name":"Aneta","full_name":"Neumann, Aneta"},{"first_name":"Frank","last_name":"Neumann","full_name":"Neumann, Frank"}],"publication_identifier":{"isbn":["978-1-4503-7128-5"]},"year":"2020","title":"Evolving Diverse Sets of Tours for the Travelling Salesperson Problem"},{"user_id":"102979","_id":"48895","publisher":"Association for Computing Machinery","page":"551–559","status":"public","place":"New York, NY, USA","citation":{"ieee":"V. Roostapour, J. Bossek, and F. Neumann, “Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem,” in <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>, 2020, pp. 551–559, doi: <a href=\"https://doi.org/10.1145/3377930.3390168\">10.1145/3377930.3390168</a>.","apa":"Roostapour, V., Bossek, J., &#38; Neumann, F. (2020). Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem. <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>, 551–559. <a href=\"https://doi.org/10.1145/3377930.3390168\">https://doi.org/10.1145/3377930.3390168</a>","short":"V. Roostapour, J. Bossek, F. Neumann, in: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, New York, NY, USA, 2020, pp. 551–559.","chicago":"Roostapour, Vahid, Jakob Bossek, and Frank Neumann. “Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem.” In <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>, 551–559. {GECCO} ’20. New York, NY, USA: Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3377930.3390168\">https://doi.org/10.1145/3377930.3390168</a>.","mla":"Roostapour, Vahid, et al. “Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem.” <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>, Association for Computing Machinery, 2020, pp. 551–559, doi:<a href=\"https://doi.org/10.1145/3377930.3390168\">10.1145/3377930.3390168</a>.","bibtex":"@inproceedings{Roostapour_Bossek_Neumann_2020, place={New York, NY, USA}, series={{GECCO} ’20}, title={Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem}, DOI={<a href=\"https://doi.org/10.1145/3377930.3390168\">10.1145/3377930.3390168</a>}, booktitle={Proceedings of the 2020 Genetic and Evolutionary Computation Conference}, publisher={Association for Computing Machinery}, author={Roostapour, Vahid and Bossek, Jakob and Neumann, Frank}, year={2020}, pages={551–559}, collection={{GECCO} ’20} }","ama":"Roostapour V, Bossek J, Neumann F. Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem. In: <i>Proceedings of the 2020 Genetic and Evolutionary Computation Conference</i>. {GECCO} ’20. Association for Computing Machinery; 2020:551–559. doi:<a href=\"https://doi.org/10.1145/3377930.3390168\">10.1145/3377930.3390168</a>"},"doi":"10.1145/3377930.3390168","series_title":"{GECCO} ’20","language":[{"iso":"eng"}],"date_updated":"2023-12-13T10:49:38Z","author":[{"full_name":"Roostapour, Vahid","first_name":"Vahid","last_name":"Roostapour"},{"full_name":"Bossek, Jakob","last_name":"Bossek","first_name":"Jakob","orcid":"0000-0002-4121-4668","id":"102979"},{"full_name":"Neumann, Frank","last_name":"Neumann","first_name":"Frank"}],"publication_identifier":{"isbn":["978-1-4503-7128-5"]},"year":"2020","title":"Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem","department":[{"_id":"819"}],"keyword":["biased mutation","evolutionary algorithms","minimum spanning tree problem","runtime analysis"],"type":"conference","date_created":"2023-11-14T15:59:00Z","abstract":[{"text":"Evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more knowledge about the structure of optimal solutions is given, which can be leveraged by means of biased search operators. We consider the Minimum Spanning Tree (MST) problem in a single- and multi-objective version, and introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We present example graphs where the biased mutation can significantly speed up the expected runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate that bias can lead to exponential runtime if \"heavy\" edges are necessarily part of an optimal solution. However, on general graphs in the single-objective setting, we show that a combined mutation operator which decides for unbiased or biased edge selection in each step with equal probability exhibits a polynomial upper bound - as unbiased mutation - in the worst case and benefits from bias if the circumstances are favorable.","lang":"eng"}],"extern":"1","publication":"Proceedings of the 2020 Genetic and Evolutionary Computation Conference"}]