Analysis and Applications of Evolutionary Multiobjective Optimization Algorithms


Abstract

This thesis deals with the analysis and applications of evolutionary algorithms for optimization problems with multiple objectives. Many application problems involve (i) a system model that is not given in a close analytical form and (ii) multiple, often conflicting optimization criteria. Both traits hamper the application of classical optimization techniques, which require a certain structure of the problem and are mostly designed to handle only a single objective. For this problem domain, the class of randomized search heuristics, to which evolutionary algorithms also belong, have become popular. Due to their population concept, evolutionary algorithms can process multiple solutions in parallel and can therefore cope with different objectives more naturally. Like most randomized search algorithms, evolutionary algorithms are easy to describe and implement, but hard to analyze theoretically. Despite much empirical knowledge and successful application, only few theoretical results concerning their effectiveness and efficiency are available. This holds especially in the multiobjective case where these questions have not been investigated yet. However, even from a practical point of view is important to distinguish: * whether a given algorithm is capable of solving a given problem (effectiveness); and * the computational complexity (measured in computation time and memory requirements) of an algorithm to solve a given problem (efficiency). The aim of this work is to contribute to the understanding of evolutionary algorithms for multiobjective optimization problems with respect to these questions. Specifically, the following topics are covered: * Based on known concepts from decision theory, the topic of quality measurement is addressed, with respect to single solutions (via fitness functions) and sets of solutions (via quality indicators). The common mathematical framework allows us to compactly describe existing fitness functions and quality indicators as well as to analyze them theoretically. * Convergence properties are investigated for the limit case of inifinite running time, but finite memory resources. Based on the concept of e-approximations, new selection operators are proposed that guarantee the convergence of randomized search strategies to a well- defined discrete solution set with simultaneous consideration of diversity. * In order to facilitate a running time analysis, simple model algorithms and problems are proposed and suitable proof techniques developed and applied. The results achieved concerning the expected running time show that through special selection operators, population-based approaches can be advantageous over multistart-strategies. * Three case studies from the field of automotive engineering demonstrate how evolutionary algorithms can systematically be exploited in the design process. The applications underline the practical relevance of some results from the previous theoretical investigations.