Hypervolume-Based Search for Multiobjective Optimization: Theory and Methods


Most problems encountered in practice involve the optimization of multiple criteria. Usually, some of them are conflicting such that no single solution is simultaneously optimal with respect to all criteria, but instead many incomparable compromise solutions exist. At the same time, the search space of such problems is often very large and complex, so that traditional optimization techniques are not applicable or cannot solve the problem within reasonable time. In recent years, evidence has accumulated showing that Evolutionary Algorithms (EAs) are effective means of finding good approximate solutions to such problems. Apart from being applicable to complex problems, EAs offer the additional advantage of finding multiple compromise solutions in a single run. One of the crucial parts of EAs consists of repeatedly selecting suitable solutions. The aim thereby is to improve the current set of solutions by cleverly replacing old solutions by newly generated ones. In this process, the two key issues are as follows: first, a solution that is better than another solution in all objectives should be preferred over the latter. Second, the diversity of solutions should be supported, whereby often user preference dictates what constitutes a good diversity. The hypervolume offers one possibility to achieve the two aspects; for this reason, it has been gaining increasing importance in recent years as selection criterion in EAs. The present thesis investigates three central topics of the hypervolume that are still unsolved: • Although more and more EAs use the hypervolume as selection criterion, the resulting distribution of points favored by the hypervolume has scarcely been investigated so far. Many studies only speculate about this question, and in parts contradict one another. • The computational load of the hypervolume calculation sharply increases the more criteria are considered. This hindered so far the application of the hypervolume to problems with more than about five criteria. • Often a crucial aspect is to maximize the robustness of solutions, which is characterized by how far the properties of a solution can degenerate when implemented in practice—for instance when manufacturing imprecisions do not allow to build perfectly the solution. So far, no attempt has been made to consider robustness of solutions within hypervolume-based search. First, the present thesis examines how hypervolume-based search can be formalized, by proposing a new perspective on EAs which emphasizes the importance of sets rather than single solutions. Different factors are stated that need to be considered when selecting and comparing sets of solutions. In this context, a new algorithm based on this formalism is proposed. A visual comparison illustrates the different outcomes with respect to the underlying set selection method; these differences are confirmed by a new statistical procedure. This observation leads to a rigorous mathematical investigation of the set of solutions, obtained when optimizing according to the hypervolume. A concise description of the distribution of solutions in terms of a density function not only allows to predict the outcome of hypervolume-based methods, but also enables to implement precisely user preference within the hypervolume itself. While the foundation to articulate user preference by means of hypervolume had already be laid by previous works, no study so far considered the integration of robustness issues in hypervolume-based search. The present thesis closes this gap by extending the definition of the hypervolume to also enabling the consideration of robustness properties. Finally, to make the hypervolume applicable to problems with many criteria a new algorithm is proposed based on a fast approximation of the hypervolume values. Thereby, importance is attached to maintain the possibility for user preference articulation, as well as the consideration or robustness issues.