More Web Proxy on the site http://driver.im/

research-article

Evolutionary diversity optimization and the minimum spanning tree problem

Authors:

Frank NeumannAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 198 - 206

https://doi.org/10.1145/3449639.3459363

Published: 26 June 2021 Publication History

Abstract

In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Theoretical insights into the working principles of baseline evolutionary algorithms for diversity optimization are still rare. In this paper we study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization where population diversity is measured by the sum of pairwise edge overlaps. Theoretical results provide insights into the fitness landscape of the MST diversity optimization problem pointing out that even for a population of μ = 2 fitness plateaus (of constant length) can be reached, but nevertheless diverse sets can be calculated in polynomial time. We supplement our theoretical results with a series of experiments for the unconstrained and constraint case where all solutions need to fulfill a minimal quality threshold. Our results show that a simple (μ + 1)-EA can effectively compute a diversified population of spanning trees of high quality.

References

[1]

Bradley Alexander, James Kortman, and Aneta Neumann. 2017. Evolution of artistic image variants through feature based diversity optimisation. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO (GECCO '17), Peter A. N. Bosman (Ed.). ACM, 171--178.

Digital Library

[2]

Brian Alspach, Jean-Claude Bermond, and Dominique Sotteau. 1990. Decomposition into cycles I: Hamilton decompositions. Springer Netherlands, 9--18.

[3]

Jakob Bossek, Christian Grimme, and Frank Neumann. 2019. On the benefits of biased edge-exchange mutation for the multi-criteria spanning tree problem. In Proceedings of the 2019 Genetic and Evolutionary Computation Conference (GECCO '19). ACM Press, New York, New York, USA, 516--523.

Digital Library

[4]

Jakob Bossek, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. 2019. Evolving diverse TSP instances by means of novel and creative mutation operators. In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA XV). ACM Press, New York, New York, USA, 58--71.

Digital Library

[5]

Gary Chartrand and Linda Lesniak. 1986. Graphs & Digraphs (2nd Ed.). Wadsworth Publ. Co., USA.

[6]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2001. Introduction to Algorithms (2nd ed.). The MIT Press.

Digital Library

[7]

Duc-Cuong Dang, Thomas Jansen, and Per Kristian Lehre. 2017. Populations Can Be Essential in Tracking Dynamic Optima. Algorithmica 78, 2 (2017), 660--680.

Digital Library

[8]

Anh Viet Do, Jakob Bossek, Aneta Neumann, and Frank Neumann. 2020. Evolving Diverse Sets of Tours for the Travelling Salesperson Problem. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO '20). Association for Computing Machinery, New York, NY, USA, 681--689.

Digital Library

[9]

Doerr, B., Neumann, F. (Eds.). 2020. Theory of Evolutionary Computation - Recent Developments in Discrete Optimization. Springer.

[10]

Tobias Friedrich and Frank Neumann. 2015. Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms. Evolutionary Computation 23, 4 (2015), 543--558.

Digital Library

[11]

Wanru Gao, Samadhi Nallaperuma, and Frank Neumann. 2016. Feature-based diversity optimization for problem instance classification. In Parallel Problem Solving from Nature, PPSN (LNCS), Vol. 9921. Springer, 869--879.

[12]

Wanru Gao and Frank Neumann. 2014. Runtime analysis for maximizing population diversity in single-objective optimization. In Proceedings of the 2014 Genetic and Evolutionary Computation Conference (GECCO '14). ACM, 777--784.

Digital Library

[13]

Wanru Gao, Mojgan Pourhassan, and Frank Neumann. 2015. Runtime Analysis of Evolutionary Diversity Optimization and the Vertex Cover Problem. In Proceedings of the 2015 Genetic and Evolutionary Computation Conference (Companion) (GECCO '15). ACM, 1395--1396.

Digital Library

[14]

Luis Gouveia and Thomas L. Magnanti. 2003. Network flow models for designing diameter-constrained minimum-spanning and Steiner trees. Networks 41, 3 (2003), 159--173. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.10069

[15]

Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer. 1--236 pages.

Digital Library

[16]

Pascal Kerschke, Holger H. Hoos, Frank Neumann, and Heike Trautmann. 2019. Automated Algorithm Selection: Survey and Perspectives. Evolutionary Computation 27, 1 (2019), 3--45.

Digital Library

[17]

Joseph B. Kruskal. 1956. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proc. Amer. Math. Soc. 7, 1 (1956), 48--50.

[18]

Michel Lang, Bernd Bischl, and Dirk Surmann. 2017. batchtools: Tools for R to work on batch systems. The Journal of Open Source Software 2, 10 (feb 2017).

[19]

Joel Lehman and Kenneth O Stanley. 2011. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 2011 Genetic and Evolutionary Computation Conference. ACM, 211--218.

Digital Library

[20]

Aneta Neumann, Wanru Gao, Carola Doerr, Frank Neumann, and Markus Wagner. 2018. Discrepancy-based evolutionary diversity optimization. In Proceedings of the 2018 Genetic and Evolutionary Computation Conference (GECCO '18). ACM, 991--998.

Digital Library

[21]

Aneta Neumann, Wanru Gao, Markus Wagner, and Frank Neumann. 2019. Evolutionary diversity optimization using multi-objective indicators. In Proceedings of the 2019 Genetic and Evolutionary Computation Conference (GECCO '19). ACM, 837--845.

Digital Library

[22]

Aneta Neumann and Frank Neumann. 2020. Optimising Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-objective Algorithms. In Proceedings of the Parallel Problem Solving from Nature, PPSN 2020 (Lecture Notes in Computer Science), Vol. 12269. Springer, 404--417.

Digital Library

[23]

Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization. Springer.

[24]

R. C. Prim. 1957. Shortest Connection Networks And Some Generalizations. Bell System Technical Journal 36, 6 (1957), 1389--1401.

[25]

Justin K Pugh, Lisa B Soros, and Kenneth O Stanley. 2016. An Extended Study of Quality Diversity Algorithms. In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion. ACM, 19--20.

Digital Library

[26]

Chao Qian, Jing-Cheng Shi, Yang Yu, and Ke Tang. 2017. On Subset Selection with General Cost Constraints. In Proceedings of the 2017 International Joint Conference on Artificial Intelligence (IJCAI '19). 2613--2619.

[27]

Chao Qian, Yang Yu, and Zhi-Hua Zhou. 2015. Subset Selection by Pareto Optimization. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1, NIPS 2015. 1774--1782.

[28]

R Core Team. 2019. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. https://www.R-project.org/

[29]

Günther R Raidl, Gabriele Koller, and Bryant A Julstrom. 2006. Biased Mutation Operators for Subgraph-Selection Problems. IEEE Transactions on Evolutionary Computation 10, 2 (2006), 145--156.

Digital Library

[30]

Vahid Roostapour, Aneta Neumann, Frank Neumann, and Tobias Friedrich. 2019. Pareto Optimization for Subset Selection with Dynamic Cost Constraints. In Proceedings of the 2019 AAAI Conference on Artificial Intelligence (AAAI '19). AAAI Press, 2354--2361.

Digital Library

[31]

Tobias Storch. 2008. On the Choice of the Parent Population Size. Evolutionary Computation 16, 4 (2008), 557--578.

Digital Library

[32]

Tamara Ulrich and Lothar Thiele. 2011. Maximizing population diversity in single-objective optimization. In Proceedings of the 2011 Genetic and Evolutionary Computation Conference (GECCO '11). ACM, 641--648.

Digital Library

Cited By

Nikfarjam ANeumann ANeumann F(2024)On the Use of Quality Diversity Algorithms for the Travelling Thief ProblemACM Transactions on Evolutionary Learning and Optimization10.1145/36411094:2(1-22)Online publication date: 8-Jun-2024
https://dl.acm.org/doi/10.1145/3641109
Gounder SNeumann FNeumann ALi XHandl J(2024)Evolutionary Diversity Optimisation for Sparse Directed Communication NetworksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654184(1237-1245)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654184
Schmidbauer MOpris ABossek JNeumann FSudholt DLi XHandl J(2024)Guiding Quality Diversity on Monotone Submodular Functions: Customising the Feature Space by Adding Boolean ConjunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654160(1614-1622)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654160
Show More Cited By

Index Terms

Evolutionary diversity optimization and the minimum spanning tree problem
1. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Discrepancy-based evolutionary diversity optimization
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Diversity plays a crucial role in evolutionary computation. While diversity has been mainly used to prevent the population of an evolutionary algorithm from premature convergence, the use of evolutionary algorithms to obtain a diverse set of solutions ...
Approximation guarantees of evolutionary optimization on the minimum crossing spanning tree problem

The minimum crossing spanning tree (MCST) problem is to find a spanning tree in a given graph G and a family of subsets of vertices S such that the maximum number of edges crossing any set in S reaches minimum value. Evolutionary algorithms (EAs) have ...
The choice of the offspring population size in the (1,λ) evolutionary algorithm

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,@l) EA. We establish a sharp threshold at @l=log"e"e"-"1n~5log"1"0n between exponential and polynomial running times on OneMax. For ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

June 2021

1219 pages

ISBN:9781450383509

DOI:10.1145/3449639

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Australian Research Council

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
151
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)3

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikfarjam ANeumann ANeumann F(2024)On the Use of Quality Diversity Algorithms for the Travelling Thief ProblemACM Transactions on Evolutionary Learning and Optimization10.1145/36411094:2(1-22)Online publication date: 8-Jun-2024
https://dl.acm.org/doi/10.1145/3641109
Gounder SNeumann FNeumann ALi XHandl J(2024)Evolutionary Diversity Optimisation for Sparse Directed Communication NetworksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654184(1237-1245)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654184
Schmidbauer MOpris ABossek JNeumann FSudholt DLi XHandl J(2024)Guiding Quality Diversity on Monotone Submodular Functions: Customising the Feature Space by Adding Boolean ConjunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654160(1614-1622)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654160
Antipov DNeumann ANeumann FLi XHandl J(2024)A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMaxProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654082(467-475)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654082
Ngo HGuo MNguyen HLi XHandl J(2024)Optimizing Cyber Response Time on Temporal Active Directory Networks Using DecoysProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654035(1309-1317)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654035
Do AGuo MNeumann ANeumann F(2024)Evolutionary Multi-objective Diversity OptimizationParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70085-9_8(117-134)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70085-9_8
Antipov DNeumann ANeumann FSutton A(2024)Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) ProblemParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_2(19-35)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_2
Antipov DNeumann ANeumann F(2024)Local Optima in Diversity Optimization: Non-trivial Offspring Population is EssentialParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_12(181-196)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_12
Gadea Harder JNeumann ANeumann F(2024)Analysis of Evolutionary Diversity Optimisation for the Maximum Matching ProblemParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_10(149-165)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70071-2_10
Antipov DNeumann ANeumann F(2023)Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMaxProceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3594805.3607135(3-14)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3594805.3607135
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents