Optimierung mit Fortschritt Spektren Adaption

Abstract. Komplexe Simulationsumgebungen, wie die computerunterstützte Strukturanalyse und numerische Strömungssimulation bedürfen robuster, leistungsstarker und gleichzeitig universell einsetzbarer Optimierungsalgorithmen. Soll die Effizienz der Variantenbildung verbessert werden, ist eine möglichst vollständige Evaluation aller Simulationsprozessinformationen von Bedeutung. In der frühen Phase der Strategieentwicklung dienen hochdimensionale Modell- funktionen als Prüfmarken für innovative Verfahrensansätze. Der Aufsatz führt in die algorithmischen Mechanismen einer lokalen Optimierungsstrategie mit adaptiver mutativer Schrittweitenregelung und generationsübergreifender Informationsausnutzung von Simulations- prozessinformationen auf spektraler Ebene ein und diskutiert an ausgewählten Beispielen die Leistungsfähigkeit des Algorithmus unter der Bedingung minimalen Variationsaufwands.

Intro. Bei der Entwicklung von Optimierungsstrategien steht der Einsatz der Algorithmen in komplexen Simulationsumgebungen, wie beispielsweise der Strukturanalyse mit der Methode der Finiten Elemente (FEM) und der computerunterstützten Strömungssimulation (computational fluid dynamics, CFD) im Fokus industrieller Anwender. Im Wissenschaftsbereich allgemein und insbesondere in der Bionikforschung gewinnt das „Physical Modelling“ im Sinne computerunterstützter Vorgehensweisen bei der Übertragung biologischer Phänomene in Technik an Bedeutung [Die-09-2]. Darüber hinaus bleibt in der Optimierungspraxis die Berechnungszeit kritische Größe bei der Strukturanalyse und der Strömungssimulation. Ein übergeordnetes Forschungsziel ist daher, die Reduzierung der Anzahl relevanter Simulations- Funktionsaufrufe. Bei Algorithmen zur lokalen Untersuchung einer komplexen Qualitäts- landschaft ist die Größe des Variantenensembles das einen Fortschritt in der Entwicklung der Objektvariablen der Optimierungsaufgabe hervorbringt, von strategischem Einfluss. Um für die industrielle Optimierungspraxis überhaupt interessant zu sein, ist die Anzahl von Variationen um einen temporären (Best-) Zustand herum zu minimieren.

Die Entwicklung effizienter Optimierungsstrategien für Programmsysteme zur Simulation komplexer Systeme und Prozesse ist Gegenstand rezenter Forschung der Bionic Research Unit der Beuth Hochschule für Technik, Berlin [Die-05][Die-06][Die-07][Die09-8].

Lokale Suche. In der Entwicklung von Optimierungsstrategien für komplexe hochdimensionale Qualitätenräume stellen lokale Suchalgorithmen mit generationsübergreifender Informations- ausnutzung den gegenwärtigen Höhepunkt der Entwicklung dar [Ost-97][Han-98][Rec- 94][Schw-95]. Der Deklarations- und Datenaufwand derartiger Verfahren wächst etwa beim Richtungslernen (Schwefel) und der Präteritum- Strategie (Rechenberg) linear, bei der „Covarianz-Matrix-Adaption, CMA“ (Hansen) quadratisch und bei der „Erzeugendensystem- Adaption, ESA“ (Ostermeier) kubisch mit der Dimension der Optimierungsaufgabe. Zu den robustesten und leistungsfähigsten lokal arbeitenden Optimierungsstrategien gehören die Evolutionären Algorithmen: Genetischen Algorithmen (GA) und die Evolutionsstrategien (ES).

Evolutionäre Algorithmen.

Die Mechanismen der biologischen Evolution sind Vorbild hochdimensionaler numerischer Optimierungsprobleme in der 91][Kos-03][Rec-94][Schw95][Die-09].

In einem einfachen Evolutionären Algorithmus (EA) werden zunächst Kopien eines artifiziellen Startsystems erstellt. Zufällige Modifizierungen führen auf eine Schar von Varianten des Elter- Systems (Variation). MUTANTEN und ELTER bilden ein gemeinsames Selektionsensemble. In jeder Generation werden alle Variationen des aktuellen Elter mittels einer Zielfunktion bewertet und die Qualität aller Systeme ermittelt (Evaluation). Aus der Schar bewerteter Systeme wird ein neuer, aktueller Elter für die folgende Generation erwählt (Selektion). Mit der Variation dieses Elter-Systems setzt sich die Kampagne fort. Auf diese Weise kann die Qualität des Ensembles von Generation zu Generation steigen. Evolutionäre Algorithmen sind lokale Suchverfahren für hochdimensionale Qualitäten- räume und untersuchen den Phänotyp eines Zielsystems. Der Code dieser Algorithmen ist sehr kompakt. Zu den Evolutionären Algorithmen (EA) zählen die Genetischen Algorithmen (GA) und die Evolutionsstrategien (ES). Letztere sind Gegenstand der weiteren Beachtungen.

Abbildung in dieser Leseprobe nicht enthalten

Lokale Suchalgorithmen mit Adaption solidierter Fortschrittspektren umgehen das Problem der exponierten Datenhaltung mit einer bemerkenswerten Eleganz. Den operativen Kern des „Fortschritt-Spektren-Adaptation (FSA)“ genannten Verfahrens bilden …

- Transformation von Prozessdaten in ihren Spektralbereich, ihre …
- Weiterverarbeitung, Analyse und Kompression und eine …
- nachfolgende Rücktransformation in den Funktionsbereich des Optimierungsprozesses.

Die Filterung eines Signals im Spektralbereich entspricht einer Faltung im Funktionsbereich [Mef-04]. In der Praxis der Regelungstechnik zielt eine spektrale Filteung darauf ab, eine höhere Signifikanz des Signals zu erreichen. In Simulationsexperimenten mit hochdimensionalen Qualitätsfunktionen kann gezeigt werden, dass in einem Optimierungsprozess sich Operationen im Spektralbereich, beispielsweise die Datenkompression oder Filterung, das Unterdrücken der hochfrequenten Anteile des solidierten spektralen Fortschritts, positiv auf die Konvergenz im Optimierungsverlauf auswirken. Einer Theorie der Fortschritt-Spektren-Adaptation wird die Aufgabe zukommen zu erklären, weshalb dem so ist. Im Vorfeld einer Theorienbildung sind jedoch Surveystudien qualitativer Art und erste quantitative Aussagen über das Konvergenzverhalten von lokalen Suchalgorithmen mit Fortschritt-Spektren-Adaptation nützlich. Auf dem heutigen Stand der Entwicklung der FSA-Strategieentwicklung können wir lediglich vermuten, dass es sich strategisch auszahlt, mit der Weiterverarbeitung des vektoriellen Fortschritts in dessen Spektralbereich eine Art Generalisierung der Zufallszahlenverteilung bei der Variantenbildung im Funktionsbereich anzustoßen.

Ausentwicklung des Kernalgorithmus. Gegenstand rezenter Forschung an der Beuth Hochschule für Technik Berlin auf dem Gebiet der FSA- Algorithmen (Fortschritt-Spektren- Adaptation) sind erste Optimierungsexperimente und Konvergenzuntersuchungen an ausgewählten Modellfunktionen. In den Voruntersuchungen legten Testläufe den Schluss nahe, dass eine Generalisierung der Zufallszahlenverteilung des vektoriellen Fortschritts offenbar zu einer Trajektierung der Variantenbildung während der Optimierung führt (dazu weiter unten mehr). Anfangs war keineswegs klar, dass das hin- und hertransformieren von Prozessdaten, das Weiterverarbeiten im Spektralbereich und letztendlich die fortschreitende „Entstochasti- sierung“ der Zufallszahlenverteilung während der Optimierung hinsichtlich des Deklarations- und Algorithmischen Aufwands zu rechtfertigen ist. Als ein unbeabsichtigt guter Griff stellt sich dabei die verwendete Programmiersprache heraus, in der die rezenten Algorithmen der Weiterverarbeitung des vektoriellen Fortschritts in seinem Spektralbereich entwickelt werden. In der c-basierten Programmiersprache SciLab, einem freeware-MATLAB-Derivat, sind die „Kosten“ der Variablendeklararition, der Datenhaltung und des Programieraufwands einer Konditionierung und Variantenverteilung über Spektral-Trajektorien gering, denn für die Transformation des Fortschrittsvektors in den Spektralbereich und eine in jeder Generation stattfindende Rücktransformation in seinen jeweiligen Funktionsbereich stehen bis auf die Ebene numerischer Machbarkeit hin optimierte Algorithmen zur Verfügung.

Des Weiteren erwarten wir für Algorithmen in dieser Programmierumgebung in näherer Zukunft einen veritablen Geschwindigkeitszuwachs. Neuste Entwicklungen bei der Verschränkung von Grafikkartenhardware und Optimalcode (CUDA, openGL, GPGPU-Verfahren) setzen genau hier an: Künftig sollen leistungsstarke Grafik-Prozessoren zur Berechnung von grafikfremden Inhalten intensiv genutzt werden. Der Code (C, Matlab) der Fouriertransformationen ist in besonderem Maße einer Parallelisierung und Verarbeitung in vielkernigen Grafikkarten zugänglich und stellt damit eine erhebliche Reduzierung der Berechnungszeit in Aussicht. Derzeit sind die parallelisierenden Algorithmen allerdings noch nicht Stand der Programmierpraxis (Freakphase der Algorithmenentwicklung).

Konventionelle Algorithmen. Dennoch ist, auch ohne Zugriff auf die GPU-Rechenkapazität, das hier vorgestellte Verfahren der Integration der Variablenvergangenheit für das lokale Suchverfahren sehr effizient: die Ähnlichkeitsvariation der Objektvariablen ist komplementär gegenüber der diskreten Variablenvergangenheit in einer Generation.

Eine möglichst effiziente Evaluation aller Simulationsprozessinformationen gelingt, weil jeder Generation in einer iterativen Optimierungskampagne der Optimierungsfortschritt (Progress (p)) inhärent ist. Dieser Vektor ist temporär und kann ohne zusätzlichen Speicherbedarf aus der Differenz der vorangegangenen und der rezenten Vektoren der Objektvariablen zweier erfolgreicher Optimierungsschritte gewonnen werden:

p(n) = Vb(n-1) - Ve(n) (1)

Nach der Qualitätsermittlung, der Evaluation und Selektion, wird der rezente Progress p aus der Differenz des besten Nachkommen Vb und dem aktuellen Elter Ve ermittelt. Der Vektor Vb geht in der Generation (n-1) aus der Nominierung des besten Nachkommen zum Elter Ve der neuen Generation hervor; der Algorithmus ist in [Die09-6] näher beschrieben.

In der Optimierungspraxis taucht genau hier ein für Untersuchungen an Modellproblemen mit hochdimensionalen Qualitätslandschaften typisches Verhalten auf: Das Optimierungsproblem konvergiert, der Algorithmus präzisiert und folgerichtig können die absoluten Zahlenwerte des rezenten Progresses p sehr klein werden [Die09-7]. In diesen Fällen liefert die Fouriertransformierte S`(n) über den rezenten Progress p(n) keine stabilen Werte mehr; also:

S`(n) = FT{ p(ΔV(n)) }, mit (ΔV(n) = Vb(n-1)-Ve(n) ~ 0

[...]