Large-scale multi-objective optimisation : new approaches and a classification of the state-of-the-art

Abstract

Many problems occurring in nature or technical applications can be formulated as optimisation problems with multiple, conflicting goals that need to be optimised simultaneously. Solving such problems requires a search for the optimal input parameters to the problem, called decision variables. This kind of problems is often solved with metaheuristic approaches such as evolutionary algorithms. In this field of multi-objective optimisation, the topic of solving large-scale problems has become increasingly popular in recent years. Large-scale optimisation in general deals with the optimisation of problems that contain large numbers of decision variables, objective functions or both. The performance of classical algorithms in the optimisation area often deteriorates when faced with large-scale problems. The topic of this thesis is the optimisation of such large-scale problems, with a focus on high-dimensional search spaces, i.e. problems that contain multiple hundreds or thousands of decision variables. Several approaches have been proposed in the literature which use different strategies, in many cases to reduce the dimensionality of the problem and thus make traditional algorithms applicable to such high-dimensional problems. These approaches are theoretically analysed and compared, and a classification scheme is proposed based on the different techniques used in the related literature. Moreover, many of the related mechanisms require the division of variables into groups. Several mechanisms to do so are described in this thesis, and these are formally categorised based on three proposed classes of grouping methods. The algorithmic contributions of this thesis include three proposed optimisation techniques for large-scale multi-objective optimisation. Each of these three methods is designed to be used with arbitrary metaheuristics from the literature, and to enable existing algorithms to search efficiently in high-dimensional decision spaces. The proposed mechanisms are theoretically described and analysed. They are further compared to each other and categories based on the proposed classification scheme. Finally, this thesis provides an extensive experimental evaluation, including the proposed approaches as well as various methods from the literature. Several interesting advantages and disadvantages of the tested algorithms are described and compared, including the dependency on variable groups, and the performances in terms of convergence behaviour and final solution quality. The results show that the proposed approaches are able to heavily increase the performance of existing algorithms for large-scale problems, and that they are competitive and in many cases superior to the state-of-the-art approaches in this field.

Viele Probleme in realen Anwendungen lassen sich mathematisch als Optimierungsprobleme mit mehreren, in Konflikt stehenden Zielen formulieren. Die Lösung solcher Probleme erfordert die Suche nach den optimalen Kombinationen der Designparameter des Prob-lems, sogenannte Entscheidungsvariablen. Neben exakten Methoden werden hierfür in der Praxis oft sogenannte Metaheuristiken wie etwa evolutionäre Algorithmen angewen-det. In diesem Forschungsfeld der mehrkriteriellen Optimierung hat das Lösen von hochdimensionalen, sogenannten “large-scale” Optimierungsproblemen in den letzten Jahren immer mehr an Bedeutung gewonnen. Large-scale Optimierung befasst sich mit der Optimierung von Problemen mit mehreren Zielfunktionen und hunderten bis tausenden von Entscheidungsvariablen. Klassische Algorithmen aus dem Bereich der mehrkriteriellen Optimierung sind oft ungeeignet für die Optimierung in solch hochdi-mensionalen Suchräumen. Die vorliegende Dissertation befasst sich mit der Optimierung von solch hochdimensionalen Problemen. Existierende Methoden werden in der Arbeit theoretisch untersucht, neue Methoden vorgestellt, und eine experimentelle Evaluation durchgeführt. Verschiedene Ansätze sind in der Literatur zu diesem Thema publiziert worden, oftmals mit dem Ziel durch verschiedene Techniken den Suchraum zu verkleinern, um so klas-sische Algorithmen anwendbar zu machen. Die Methoden werden theoretisch analysiert und verglichen, und basierend auf den Eigenschaften der Algorithmen aus der Literatur wird ein Klassifizierungsschema vorgestellt. Viele der verwandten Methoden verwenden außerdem einen Mechanismus, um die Variablen in Gruppen einzuteilen. Verschiedene dieser Techniken werden in dieser Arbeit beschrieben und in drei vorgeschlagene Kate-gorien eingeordnet. Die algorithmischen Beiträge dieser Arbeit umfassen drei vom Autor entwickelte Optimierungstechniken für hochdimensionale mehrkriterielle Probleme. Jede dieser drei Methoden ist so gestaltet, dass beliebige existierende Algorithmen in die Lage versetzt werden, hochdimensionale Suchräume effizient zu durchsuchen. Die drei entwickelten Methoden werden analysiert, verglichen und schließlich in die vorgestellten Klassen von Algorithmen eingeordnet. Die experimentelle Evaluation dieser Arbeit umfasst die entwickelten Algorithmen sowie verschiedene der verwandten Methoden aus der Literatur. In der Analyse werden verschiedene Vor- und Nachteile der Algorithmen beschrieben und verglichen, wie beispielsweise die Abhängigkeit von Variablengruppen und die Leistung in Bezug auf Konvergenzgeschwindigkeit und finale Lösungsqualität. Die Ergebnisse zeigen, dass die entwickelten Methoden in der Lage sind, die Leistung existierender Algorithmen für hochdimensionale Probleme stark zu verbessern. Weiterhin zeigen die vorgestellten Techniken eine vergleichbare und in vielen Fällen überlegene Lösungsqualität im Vergleich mit anderen aktuellen large-scale Methoden.