Beuth Hochschule für Technik, Berlin

University of Applied Sciences Berlin, Germany Bionic Research Unit, FB Maschinenbau, Umwelt- und Verfahrenstechnik

Lokale Suche. In der Entwicklung von Optimierungsstrategien für komplexe hochdimensionale Qualitätenräume stellen lokale Suchalgorithmen mit generationsübergreifender Informationsausnutzung 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 für Algorithmen zur Lösung hochdimensionaler numerischer Optimierungsprobleme in der Technik [Her-00][Her-05][Kah-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ätenrä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.

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

Beuth Hochschule für Technik, Berlin

University of Applied Sciences Berlin, Germany Bionic Research Unit, FB Maschinenbau, Umwelt- und Verfahrenstechnik

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 „Entstochastisierung“ 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 Fouriertrans-

formierte 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

Für Strategienentwickler stellt das Präzisieren der Optimierungsalgorithmen im Konvergenz-grund und damit die Resorption der absoluten Zahlenwerte des rezenten Progresses p ein unbedingtes Gut dar. Die Beobachtung der materiellen Zahlenwerte der hochdimensionalen Qualitätsfunktion während der Optimierungslaufzeit liefert die Information für eine Kontrolle der Entwicklung des rezenten Progress p(n). Eine Lösung dieses Problems bietet nun folgender Ansatz: Die materielle, vektorielle Änderung des Fortschrittspektrums der Generation (n), die ∆Sp(n) ist ein spektraler Gradient, also Fouriertransformierte ∆ ∆

∆Sp(n) = Sp(n-1) - Sp(n) = ∆ [ FT{ (Vb(n-1)) } , FT{ (Ve(n)) } ] ( 2 ) ∆ ∆ ∆

In Optimierungsstrategien, die Varianten über lokale (Ähnlichkeits-) Variationen generieren, kommen entweder eine individuelle vektorielle Variationsschrittweite δ(n) der Generation (n)

δ oder eine skalare, global für alle Vektorkomponenten gleiche Variationsschrittweite δ(n) mit der δ

der Zufallszahlenvektor gewichtet wird, zur Anwendung.

V(n+1) = V(n) + δ(n) Z ( 3 ) δ

Der Term δ(n) Z ist der mit der individuellen vektoriellen Variationsschrittweite δ(n) der δ δ

Generation (n) gewichtete Zufallszahlenvektor Z der Dimension (m). Das (vektorielle) Spektrum der Zufallszahlenverteilung ist:

Sr(n) = FT{ (Z(n)) } = Sr(n,m) ( 4 )

∆Sp(n) und der vektorielle Zufallsspektrum Sr(rn) besitzen beide die Der spektrale Gradient ∆ ∆

Dimension des Objektvariablenvektors der Optimierungsaufgabe. Auf spektraler Ebene sind sie superponierbar und einer Weiterverarbeitung zugänglich.

+ γ ( 5 ) Svar(n,m) γr Sr(n,m) = γ = γp ∆Sp(n,m) = γ = γ ∆ γ

^{VARIATION PROGRESS RANDOM} In einem ersten einfachen Ansatz bilden wir die (spektrale) Variation Svar(n,m) aus der Summe ∆Sp(n,m) und der vektoriellen Verteilung Sr(n,m). der spektralen Intensitäten des Gradienten ∆ ∆

Um die Gewichtung dieser Summe zu einem späteren Zeitpunkt einem Selektionsdruck auszusetzen, lässt sich der Term mit den Formfaktoten γp und γr parametrisieren. Hier, auf der γ γ

Ebene der (Frequenz-) Spektren, sind die Signale einer informationellen Weiterverarbeitung zugänglich. Die Gleichwertigkeit der allgemeinen Signalbeschreibung in einem Originalbereich und einem Spektralbereich lässt sich aus der rezibroken Natur orthogonaler Transformation ableiten [Mef -04].

Fouriertransformation S(n,m) = FT{ ( V(n,m) ) } ( 6 ) inverse Transformation v(n,m) = iFT{

( S(n,m) ) } Mit einer orthogonalen Rücktransformationen wird das Signal vom Spektralbereich (Transformationsbereich) in den Ortsbereich (Objektbereich) rückübertragen: var(n,m)=iFT{(Svar(n,m))}. In der Nomenklatur der Lokalen Suchalgorithmen [Die09-6] [Die09-7] folgt die Variantenbildung:

V(n+1) = V(n) + δ (n) iFT{ ( Svar(n,m) ) } ( 7 ) δ