Direkte Suchverfahren unter Rauschen II: Analyse und Design

Der Bedarf an effizienten direkten Suchverfahren für verrauschte Optimierung ist in den letzten Jahren gestiegen. Dies liegt an dem wachsenden Einsatz dieser Verfahren bei simulations-basierten Optimierungsproblemen und im Feld der robusten Optimierung. Allerdings gibt es noch viele unbeantwortete Fragen in Hinblick auf das dynamische Verhalten dieser Verfahren. Ein erster Schritt in dieser Richtung wurde im Projekt "Evaluation von Evolutionären und anderen direkten Suchverfahren unter dem Einfluss von Rauschen" getan. Der nächste Schritt ist jetzt, die Entwicklung von effizienten Verfahren voranzubringen. Dabei sollen diese Verfahren automatisch erkennen, ob Rauschen vorliegt und gegebenenfalls den Einfluss des Rauschens reduzieren. Das Ziel ist es, Methoden zu entwickeln, welche mit möglichst wenig zusätzlichen Funktionsevaluationen auskommen. Diese Methoden können dann bei unterschiedlichsten Optimierungsverfahren benutzt werden. In Hinblick auf die Minimierung des Rauschens werden wir uns hauptsächlich mit Evolutionsstrategien (ES) beschäftigen. Bei diesen Verfahren kann der Einfluss des Rauschens durch eine Anpassung der Populationsgrössen erreicht werden. Dafür werden zweistufige ES (Meta-ES) benutzt, welche in der äusseren Stufe die Populationsgrössen steuern und in der inneren Stufe das Optimierungsproblem lösen. Erste Untersuchungen dieser Verfahren sind vielversprechend, allerdings sind weitere detailierte Untersuchungen notwendig (insbesondere im Hinblick auf Rauschen), bevor diese Verfahren als hinreichend praxistauglich bezeichnet werden können. Neben diesen Zielen soll die Analyse von direkten Suchverfahren weitergeführt werden. Wie auch im Vorprojekt werden die Optimierungsstrategien mit Hilfe des von uns entwickelten Analyseverfahrens evaluiert; der Fokus liegt auf Pattern Search Verfahren und Response Surface Verfahren. Die Analyse anhand von verrauschten Testfunktionen wird ein tieferes Verständnis ermöglichen und gleichzeitig die Möglichkeit zum direkten Vergleich mit anderen Verfahren eröffnen. Weiterhin soll die Analyse bereits untersuchter Verfahren auf komplexere Testfunktionen, wie Gratfunktionen und ellipsoide Testfunktionen, ausgedehnt werden. Dies wird unser Wissen über das Verhalten dieser Verfahren erweitern und kann bei der Verbesserung der Verfahren helfen. Ein weiteres Ziel ist, Empfehlungen für den Einsatz der Verfahren zu entwickeln, welche hilfreich für Anwender im Bereich der verrauschten Optimierung sein werden.

Das Forschungsprojekt zielte auf die Analyse und die Entwicklung von sogenannten direkten Suchverfahren unter der Anwesenheit von Rauschen und Unsicherheiten. Insbesondere sind Evolutionsstrategien untersucht worden, aber auch sogenannte Mustersuchverfahren (pattern search methods) und response surface basierende Strategien wurden betrachtet. Neben umfangreichen theoretischen Analysen, die die Basis für ein tieferes Verständnis der Funktionsweise und Leistungsfähigkeit dieser Verfahren bilden, wurden Techniken entwickelt, die die Performance dieser Algorithmen unter Rauschen verbessern.Rauschen und Unsicherheiten treten oft bei Optimierungsproblemen aus der Praxis auf und können nicht immer verhindert werden. Typische Beispiele sind die Optimierung von realen physikalischen Objekten (Maschinen, Komponenten, usw.), die Optimierung von Monte-Carlo Simulationen und das zunehmend wichtiger werdende Feld des robusten Systemdesigns. Oft sind diese Probleme so komplex, dass eine komplette (mathematische) Analyse nicht mit erträglichem Aufwand durchführbar ist und das zu optimierende System daher als Blackbox behandelt werden muss.Direkte Suchverfahren sind dann das Mittel der Wahl, um derartige Systeme, die es in allen Bereichen der Technik, Wissenschaft und Wirtschaft gibt, zur verbessern oder zu optimieren. Der Hauptvorteil dieser direkten Suchverfahren liegt in der Einfachheit ihrer Anwendung und der allgemeinen Verwendbarkeit speziell im Fall der Blackbox-Optimierung. Die Suchverfahren manipulieren auf direkte Weise die Eingabeparameter der Blackbox mit dem Ziel, die Ausgaben der Blackbox bezüglich vordefinierter Designziele zu optimieren.Im Fall von Rauschen sind die Ausgaben der Blackbox (d.h. die des zu optimierenden Systems) jedoch gestört. Das heißt, wird das System mehrmals mit den gleichen Eingaben getestet, ändert sich die Systemausgabe in probabilistischer Weise (typische Bespiele: Beobachtungsfehler, Messfehler usw.). Eine scheinbar gute Systemausgabe kann zu einer unpassenden Systemeingabe gehören und umgekehrt. Um direkte Suchverfahren bei derartigen Szenarien einzusetzen, bedarf es Gegenmaßnahmen, die sicherstellen, dass am Ende des Optimierungsprozesses eine brauchbare robuste Lösung erhalten wird. Zusätzlich und das war eine Hauptintention dieser Forschung sollte der Aufwand, der erforderlich ist, um einer Optimallösung näher zu kommen, so klein wie möglich sein. Das heißt, es war ein Ziel, direkte Suchalgorithmen zu entwickeln bzw. zu verbessern, so dass diese mit einem Minimum an Blackbox-Bewertungen auskommen (die Evaluation der Blackbox, also die Bestimmung der Systemausgabe ist in der Regel mit Kosten und Zeit verbunden). Als Ergebnis der Forschung konnte eine Evolutionsstrategie entwickelt werden, die mit variabler Populationsgrößensteuerung auch Blackbox-Optimierungen unter starkem Rauschen ermöglicht.