Exploring Structural Diversity in Evolutionary Algorithms
Tamara Ulrich · Repository for Publications and Research Data (ETH Zurich) · 2012
Optimization problems arise in many different contexts and applications. For each optimization problem, there is a so-called decision space that contains all feasible solutions to the problem. Additionally there are one or several objective functions that quantify how well each solution satisfies the given objectives. The goal of optimization algorithms for single-objective problems is to find the global optimum, i.e. one or several solutions that have the best objective value. In multi-objective problems, on the other hand, there is no single best solution, but a set of tradeoff solutions, the so-called Pareto-front. Multi-objective optimizers therefore aim at finding that front, or a subset of it. To find the global optimum or the Pareto-front, either analytical methods or exhaustive search can be employed. Sometimes though, the decision space is too large for exhaustive search, and the type of problem is not suitable for analytical methods. In such cases, Evolutionary Algorithms (EAs) are often used to approximate the best solutions. EAs mimic natural evolution by evolving sets of solutions in iterations, where in each iteration, new solutions are created by combining or modifying the current solutions, and the best solutions are kept and enter the next iteration. When optimizing real-world problems, a model is needed that presents the optimization problem in such a way that an EA can optimize it. Often, there are simplifications and uncertainties in these models. Therefore, not only optimal, but also close-to-optimal solutions are of interest. Moreover, a user may not be satisfied with a single solution, but instead wants to gain insights into the problem. In this case it is advantageous to present the user with structurally diverse solutions, i.e. solutions which are diverse in decision space. Therefore, this thesis tackles the problem of generating a set of solutions which has a high structural diversity, but whose solutions at the same time have acceptable objective values. Also, it is useful to have methods that support analyzing the optimized set, in order to help the user to identify the characteristics that lead to high