Hypervolume-Based Search for Multiobjective Optimization: Theory and Methods

PhD Thesis

Abstract

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. In recent years, evidence has accumulated showing that Evolutionary Algorithms (EAs) are effective means of finding good approximate solutions to such problems. One of the crucial parts of EAs consists of repeatedly selecting suitable solutions. 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. The present thesis investigates three central topics of the hypervolume that are still unsolved:

  1. 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.
  2. 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.
  3. 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. So far, no attempt has been made to consider robustness of solutions within hypervolume-based search.

PDF Download with Cover (12.8 MB), or

Defense Talk

Download Presentation