In the classical setting evolutionary algorithms (EAs) are used to compute a single solution of high quality with respect to the objective function or a set of trade-off solutions in the field multi-objective optimization where one deals with multiple, usually conflicting objectives. Here, diversity preservation is usually introduced as a means to prevent premature convergence.
In many engineering applications and in the field of algorithm selection / configuration however, it is beneficial to produce a set of solutions that is (1) of high quality and (2) diverse with respect to the search space and/or some features of the given problem. Evolutionary Diversity Optimization enables the computation of a large variety of new and innovative solutions that are unlikely to be produced by traditional evolutionary computation methods for single-objective or multi-objective optimization. Related to evolutionary diversity optimization is the concept of novelty search. Here EAs are used to discover new designs/solutions without focusing on explicit objectives as a driver for the search process. The goal of novelty search is to explore solutions that are different to the ones previously obtained.
In this tutorial, we will give a detailed overview on evolutionary diversity optimization which is a new important research area within evolutionary computation that aims to provide sets of diverse solutions. Apart from that, we give a brief introduction into novelty search, highlight similarities and differences to evolutionary diversity optimization and give an outlook how both fields can benefit from each other.
Scope:
Designing evolutionary computation techniques for diversity optimisation is highly beneficial to many industrial application areas as it provides a large variety of high quality and innovative design choices. Evolutionary diversity optimisation aims to construct a diverse set of solutions that all meet given quality criteria. Moreover, diversity optimisation in terms of features on the underlying problem allows to obtain a better understanding of possible solutions to the problem and can be used for algorithm selection when dealing with combinatorial optimisation problems such as the Traveling Salesperson Problem.
This tutorial gives an overview on this relatively new research area within evolutionary computation. We will point out design principles for evolutionary diversity optimisation and discuss important components such as the design of mutation operators, features of solutions, and the impact of different diversity measures. Furthermore, we report on theoretical investigations that lay the foundations for a better understanding on the working principles of evolutionary diversity optimisation methods.
Tutorial outline:
• Introduction and Motivation
• Definition: Evolutionary Diversity Optimisation
• Application Areas
• Diverse TSP Instances and Images
• Discrepancy for Evolutionary Diversity Optimisation
• Indicators for Evolutionary Diversity Optimisation
• Operators for Creating Diverse Sets of Solutions
• Jakob Bossek received his bachelor degree in Statistics and diploma in Computer Science from the TU Dortmund University (Germany) in 2013 and 2014, respectively. In 2018 he finished his PhD in Information Systems at the University of Münster, Germany. He held postdoc positions at the University of Münster, Germany and the University of Adelaide, Australia. Currently, he is affiliated at his alma mater, the Department for Information Systems at the University of Münster.
His broad research topics include practical and theoretical aspects of bio-inspired problem solving, in particular evolutionary algorithms for NP-hard combinatorial optimisation problems.
• Aneta Neumann graduated in Computer Science from the Christian-Albrechts-University of Kiel, Germany and received her PhD from the University of Adelaide, Australia. She presented invited talks at UCL London, Goldsmiths, University of London, University of Nottingham, University of Sheffield, Hasso Plattner Institut University of Potsdam, Sorbonne University, University of Melbourne, University of Sydney in 2016-19. She received the ACM Women scholarship, sponsored by Google, Microsoft, and Oracle, the Hans-Juergen and Marianna Ohff Research Grant in 2018, and the Best Paper Nomination at GECCO 2019 in the track “Genetic Algorithms”. Her main research interest focuses on bio-inspired computation, evolutionary diversity optimisation, submodular functions, and optimisation under uncertainty in practice. She serves as the co-chair of the Real-World Applications track at GECCO 2021.
• Frank Neumann received his diploma and Ph.D. from the Christian-Albrechts-University of Kiel in 2002 and 2006, respectively. Currently, he is a full Professor and leader of the Optimisation and Logistics Group at the School of Computer Science, The University of Adelaide, Australia. Frank has been the general chair of the ACM Genetic and Evolutionary Computation Conference (GECCO) 2016 and has given several tutorials at GECCO and PPSN over the last 10 years. He co-organised ACM Foundations of Genetic Algorithms (FOGA) 2013 and is an author of the textbook "Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity" published by Springer. Currently, he is an Associate Editor of the journals "Evolutionary Computation” and "ACM Transactions on Evolutionary Learning and Optimization". In his work, he considers algorithmic approaches in particular for combinatorial and multi-objective optimization problems and focuses on theoretical aspects of evolutionary computation as well as high impact applications in the areas of creativity, renewable energy, logistics, and mining.
