Evolutionary algorithms for multiobjective optimization: methods and applications

Many real-world problems involve two types of problem difficulty: i) multiple, conflicting objectives and ii) a highly complex search space. On the one hand, instead of a single optimal solution competing goals give rise to a set of compromise solutions, generally denoted as Pareto-optimal. In the absence of preference information, none of the corresponding trade-offs can be said to be better than the others. On the other hand, the search space can be too large and too complex to be solved by exact methods. Thus, efficient optimization strategies are required that are able to deal with both difficulties. Evolutionary algorithms possess several characteristics that are desirable for this kind of problem and make them preferable to classical optimization methods. In fact, various evolutionary approaches to multiobjective optimization have been proposed since 1985, capable of searching for multiple Paretooptimal solutions concurrently in a single simulation run. However, in spite of this variety, there is a lack of extensive comparative studies in the literature. Therefore, it has remained open up to now: • whether some techniques are in general superior to others, • which algorithms are suited to which kind of problem, and • what the specific advantages and drawbacks of certain methods are. The subject of this work is the comparison and the improvement of existing multiobjective evolutionary algorithms and their application to system design problems in computer engineering. In detail, the major contributions are: • An experimental methodology to compare multiobjective optimizers is developed. In particular, quantitative measures to assess the quality of trade-off fronts are introduced and a set of general test problems is defined, which are i) easy to formulate, ii) represent essential aspects of real-world problems, and iii) test for different types of problem difficulty. • On the basis of this methodology, an extensive comparison of numerous evolutionary techniques is performed in which further aspects such as the influence of elitism and the population size are also investigated. • A novel approach to multiobjective optimization, the strength Pareto evolutionary algorithm, is proposed. It combines both established and new techniques in a unique manner. • Two complex multicriteria applications are addressed using evolutionary algorithms: i) the automatic synthesis of heterogeneous hardware/systems and ii) the multidimensional exploration of software implementations for digital signal processors. Zusammenfassung Viele praktische Optimierungsprobleme sind durch zwei Eigenschaften charakterisiert: a) mehrere, teilweise im Konflikt stehende Zielfunktionen sind involviert, und b) der Suchraum ist hochgradig komplex. Einerseits f ̈ uhren widersprüchliche Optimierungskriterien dazu, dass es statt eines klar definierten Optimums eine Menge von Kompromissl ̈ o ungen, allgemein als Pareto-optimal bezeichnet, gibt. Insofern keine Gewichtung der Kriterien vorliegt, m ̈ ussen die entsprechenden Alternativen als gleichwertig betrachtet werden. Andererseits kann der Suchraum eine bestimmte Gr ̈ osse und Komplexit ̈ at überschreiten, so dass exakte Optimierungsverfahren nicht mehr anwendbar sind. Erforderlich sind demnach effiziente Suchstrategien, die beiden Aspekten gerecht werden. Evolutionäre Algorithmen sind aufgrund mehrerer Merkmale f ̈ ur diese Art von Problem besonders geeignet; vor allem im Vergleich zu klassischen Methoden weisen sie gewisse Vorteile auf. Doch obwohl seit 1985 verschiedenste evolutionäre Ansätze entwickelt wurden, die mehrere Pareto-optimale L ̈ osungen in einem einzigen Simulationslauf generieren k ̈ onnen, mangelt es in der Literatur an umfassenden Vergleichsstudien. Folglich blieb bislang ungekl ̈ art, • ob bestimmte Techniken anderen Methoden generell  ̈ ub rlegen sind, • welche Algorithmen f ̈ ur welche Art von Problem geeignet sind und • wo die spezifischen Vorund Nachteile einzelner Verfahren liegen. Die vorliegende Arbeit hat zum Gegenstand, bestehende evolution ̈ are Mehrzieloptimierungsverfahren zu vergleichen, zu verbessern und auf Entwurfsprobleme im Bereich der Technischen Informatik anzuwenden. Im Einzelnen werden folgende Themen behandelt: • Eine Methodik zum experimentellen Vergleich von Mehrzieloptimierungsverfahren wird entwickelt. Unter anderem werden quantitative Qualit ̈ atsmasse für Mengen von Kompromissl ̈ osungen eingef ̈ uhrt und mehrere Testfunktionen definiert, die a) eine einfache Problembeschreibung besitzen, b) wesentliche Merkmale realer Optimierungsprobleme repr ̈ asentieren und c) erlauben, verschiedene Einflussfaktoren separat zu  ̈ uberprüfen. • Auf der Basis dieser Methodik wird ein umfangreicher Vergleich diverser evolutionärer Techniken durchgef ̈ uhrt, wobei auch weitere Aspekte wie die Auswirkungen von Elitism und der Populationsgr ̈ osse auf den Optimierungsprozess untersucht werden. • Ein neues Verfahren, der Strength-Pareto-Evolutionary-Algorithm, wird vorgestellt. Es kombiniert auf spezielle Art und Weise bew ̈ ahrte und neue Konzepte miteinander. • Zwei komplexe Mehrzielprobleme werden auf der Basis evolution ̈ arer Methoden untersucht: a) die automatische Synthese von heterogenen Hardware/Software-Systemen und b) die mehrdimensionale Exploration von Softwareimplementierungen f ̈ ur digitale Signalverarbeitungsprozessoren. I would like to thank Prof. Dr. Lothar Thiele for the valuable discussions concerning this research, Prof. Dr. Kalyanmoy Deb for his willingness to be the co-examiner of my thesis,