Evolutionsstrategien zur Optimierung unter Nebenbedingungen

Evolutionsstrategien (ES), insbesondere die sogenannten Kovarianz-Matrix-Adaptations-ES (CMA-ES), sind nachweislich die zur Zeit am leistungsfähigsten universalen direkten Suchverfahren für nicht-restringierte reell-parametrische Blackbox-Optimierung, wie man sie im Bereich der Simulationsoptimierung und anderer Felder der Ingenieuroptimierung findet. Dieser Erfolg ist derzeit noch im Wesentlichen auf den Fall der nicht-restringierten Probleme (d.h, Probleme ohne Nebenbedingungen) beschränkt. Die Einbeziehung von Gleichungs- und Ungleichungsnebenbedingungen beim Design von ES ist - im Vergleich zu anderen Evolutionären Algorithmen - derzeit noch nicht so weit vorangeschritten, wie beispielsweise beim Differential-Evolutions-Verfahren. Es ist das Ziel dieses Projektes, die Entwicklung von ES für restringierte Optimierung, d.h. Optimierung unter Nebenbedingungen, auf theoretisch basierter Grundlage voranzutreiben. Dies wird durch eine enge Verzahnung im Forschungsprogramm, welches theoretisch motivierte Algorithmenentwicklung mit der Analyse und der Evaluation der Suchstrategien verbindet, erreicht werden. Basierend auf dem Erkenntnisgewinn dieses Projektes ist ein tieferes Verständnis der Funktionsprinzipien von direkten Suchstrategien in restringierten Suchräumen zu erwarten. Daraus werden sowohl besser performende ES, als auch allgemeine Design-Prinzipien für Evolutionäre Algorithmen resultieren.

Dieses Forschungsprojekt zielte auf die Analyse und den Entwurf von Algorithmen für Optimierungsprobleme in reellwertigen Suchräumen, wie sie in vielen Anwendungen in der Technik, den Naturwissenschaften und der Wirtschaft vorkommen. Während es verschiedenste Lösungsansätze zur Optimierung derartiger Probleme gibt, haben sich Evolutionsstrategien (ES) als gut geeignete Alternative insbesondere bei schwierigen nichtlinearen Problemen erwiesen. Die ES-Algorithmen wurden der Natur abgeschaut. Sie ahmen den Prozeß der Darwinschen Evolution nach, indem sie initiale Ausgangslösungen schrittweise - wie in der Natur - durch Anwendung von kleinen Mutationen, der Rekombination von Lösungen und Selektion bessere und bessere Lösungen generieren. Jedoch war bis jetzt die Einbeziehung von Restriktionen, also Einschränkungen bei der Wahl der Lösungsmöglichkeiten, wie sie oft in der Praxis vorkommen, eher die Ausnahme und die Realisierung derartiger Algorithmen erfolgte auf nicht-systematischem Weg. Dieses Projekt hat die Situation for Evolutionsstrategien signifikant geändert. Basierend auf einer tiefgehenden theoretisch begründeten Analyse wurden Evolutionsstrategien entwickelt, die in der Lage sind, sowohl Gleichungs- als auch Ungleichungsnebenbedingungen während des Evolutionsprozesses zu erfüllen. Anders als die meisten anderen Evolutionären Algorithmen sind die im Projekt entwickelten Algorithmen in der Lage als innere-Punkt-Methoden zu funktionieren. Das heißt, die Lösungen, die während des evolutionären Verbesserungsprozesses generiert werden, sind immer gültige Lösungen, d.h., sie verletzen nicht die Gleichungs- und Ungleichungsbedingungen. Ein derartiges Verhalten ist besonders wünschenswert bei simulationsbasierten Optimierungsproblemen, bei denen das Verlassen des zulässigen Bereichs (die Verletzung der Nebenbedingungen) zu einem Versagen der Simulationssoftware führen kann. Dies ist auch ein Problem im Bereich der Finanzmathematik, wo Bilanz(gleichung)en exakt erfüllt werden müssen. Neben der Entwicklung der ES Algorithmen, die algorithmisch einfacher, von ihrer Performance gleichwertig und oft besser als der Stand der Wissenschaft sind, wurde auch die Theorie dieser probabilistischen Algorithmen vorangebracht. Dies ist wichtig, da das Verständnis der Funktionsweise dieser Algorithmen, die schwierig zu analysieren sind, eine Voraussetzung für die weitere Verbesserung dieser Algorithmen ist.