Co-Evolutionary Diversity Optimisation for the Traveling Thief Problem - Nikfarjam, Adel; Neumann, Aneta; Bossek, Jakob; Neumann, Frank (Parallel Problem Solving from Nature (PPSN XVII))
Recently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to explore niches in behavioural space (quality diversity) or 2) to increase the structural differences of solutions (evolutionary diversity optimisation). In this study, we introduce a co-evolutionary algorithm to simultaneously explore the two spaces for the multi-component traveling thief problem. The results show the capability of the co-evolutionary algorithm to achieve significantly higher diversity compared to the baseline evolutionary diversity algorithms from the literature.
Keywords: Co-evolutionary algorithms; Evolutionary diversity optimisation; Quality diversity; Traveling thief problem

Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem - Nikfarjam, Adel; Bossek, Jakob; Neumann, Aneta; Neumann, Frank (Proceedings of the Genetic and Evolutionary Computation Conference)
Computing diverse sets of high-quality solutions has gained increasing attention among the evolutionary computation community in recent years. It allows practitioners to choose from a set of high-quality alternatives. In this paper, we employ a population diversity measure, called the high-order entropy measure, in an evolutionary algorithm to compute a diverse set of high-quality solutions for the Traveling Salesperson Problem. In contrast to previous studies, our approach allows diversifying segments of tours containing several edges based on the entropy measure. We examine the resulting evolutionary diversity optimisation approach precisely in terms of the final set of solutions and theoretical properties. Experimental results show significant improvements compared to a recently proposed edge-based diversity optimisation approach when working with a large population of solutions or long segments.
Keywords: evolutionary algorithms; evolutionary diversity optimisation; high-order entropy; traveling salesperson problem

Diversifying Greedy Sampling and Evolutionary Diversity Optimisation for Constrained Monotone Submodular Functions - Neumann, Aneta; Bossek, Jakob; Neumann, Frank (Proceedings of the Genetic and Evolutionary Computation Conference)
Submodular functions allow to model many real-world optimisation problems. This paper introduces approaches for computing diverse sets of high quality solutions for submodular optimisation problems with uniform and knapsack constraints. We first present diversifying greedy sampling approaches and analyse them with respect to the diversity measured by entropy and the approximation quality of the obtained solutions. Afterwards, we introduce an evolutionary diversity optimisation (EDO) approach to further improve diversity of the set of solutions. We carry out experimental investigations on popular submodular benchmark problems and analyse trade-offs in terms of solution quality and diversity of the resulting solution sets.
Keywords: evolutionary algorithms; evolutionary diversity optimisation; sub-modular functions

Computing Diverse Sets of High Quality TSP Tours by EAX-based Evolutionary Diversity Optimisation - Nikfarjam, Adel; Bossek, Jakob; Neumann, Aneta; Neumann, Frank (Proceedings of the 16th ACM}/SIGEVO Conference on Foundations of Genetic Algorithms)
Evolutionary algorithms based on edge assembly crossover (EAX) constitute some of the best performing incomplete solvers for the well-known traveling salesperson problem (TSP). Often, it is desirable to compute not just a single solution for a given problem, but a diverse set of high quality solutions from which a decision maker can choose one for implementation. Currently, there are only a few approaches for computing a diverse solution set for the TSP. Furthermore, almost all of them assume that the optimal solution is known. In this paper, we introduce evolutionary diversity optimisation (EDO) approaches for the TSP that find a diverse set of tours when the optimal tour is known or unknown. We show how to adopt EAX to not only find a high-quality solution but also to maximise the diversity of the population. The resulting EAX-based EDO approach, termed EAX-EDO is capable of obtaining diverse high-quality tours when the optimal solution for the TSP is known or unknown. A comparison to existing approaches shows that they are clearly outperformed by EAX-EDO.
Keywords: edge assembly crossover (EAX); evolutionary algorithms; evolutionary diversity optimisation (EDO); traveling salesperson problem (TSP)