Abstract. Lokale Suchalgorithmen in Optimierungsstrategien sind robust, deklaratorisch genügsam und arbeiten schnell. Jedoch besitzen sie keine Erinnerung an ihre eigene Variablenvorgeschichte. Dies ist ein großer Nachteil gegenüber anderen konkurrierenden Optimierungsalgorithmen. Der Aufsatz beschreibt den Stand der Entwicklung eines lokalen Suchalgorithmus der dadurch Zugriff auf die eigene Variablenvergangenheit erhält, dass ein in den Spektralbereich transformiertes Forschrittsmuster adaptiert wird.

Der Kernmechanismus eines lokalen Suchalgorithmus ist die Ähnlichkeitsvariation von Objektvariablen der Qualitätsfunktion der gestellten Optimierungsaufgabe. Ähnlich ist der Datensatz der Objektvariablen dann, wenn er gering von jenem Erzeugendensystem abweicht, dem er entstammt. Lokal werden solche Suchalgorithmen für Optimierungsaufgaben genannt, wenn eine von einer komplexen Qualitätsfunktion aufgespannte Topologie in einem begrenztem Gebiet um den aktuellen Arbeitspunkt herum untersucht wird. Lokale Suchalgorithmen sind robust, benötigen geringen strukturellen, deklatorischen Aufwand und arbeiten schnell. Ihr Einsatzgebiet ist das vieldimensionale Qualitätsgelände. Die Ähnlichkeitsvariation der Objektvariablen ist komplementär gegenüber ihrer eigenen Variablenvergangenheit. Als Kernmechanismus eines lokalen

Suchalgorithmus ergänzt sie den rezenten Status des Vektors V der Objektvariablen zu einem vorangegangenen Zustand:

V(n+1) = V(n) + ∆V(n) (1)

Betrachten wir den lokalen Suchvorgang als eine Entwicklung von Zustandseigenschaften im Zeitbereich, dann ist mit fortschreitenden diskreten (n) eine Ahnenfolge der Systemzustände, beschrieben durch den Vektor der Objektvariablen. Wir sehen, dass die Variation zeitlich dem „herkünftigen“ Vektor zugeordnet und diesem gleich indiziert ist. Bei der Suche nach einem Minimum der Qualitätsfunktion in einer Optimierungsaufgabe existieren zuversichtlich und

unglücklich tastende Variationen des rezenten Zustands. Es besteht Gestaltungsbedarf hinsichtlich der Entwicklung einfacher und robuster Strategien, die die Anzahl nichtzuversichtlicher Variationen minimieren aber nicht die Vorteile eines kompakten Codes aufgeben. Zu den leistungsfähigsten lokal arbeitenden Optimierungsstrategien gehören die Evolutionären Algorithmen: Genetischen Algorithmen und die Evolutionsstrategien. Bei der Evolutionsstrategie wird die Ähnlichkeitsvariation als Addition eines durch die rezente Variationsschrittweite d(n) gewichteten Zufallszahlenvektors bestimmt:

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

Evolutionäre Algorithmen simulieren das biologische Wechselspiel von Variation und Selektion und wenden es auf mathematisch modellierte Optimierungsaufgaben an. Dabei werden in einem einfachsten Szenario m Kopien eines artifiziellen Startsystems erstellt (Mutation). Zufällige Modifizierungen führen auf eine Schar von m Variationen des Elter-Systems. In jeder Generation werden alle Variationen des aktuellen Elter (in bestimmten Strategien einschließlich dem Elter, siehe [Rec-94]) mittels einer Zielfunktion einer Bewertung unterzogen, die Qualität aller Systeme wird ermittelt (Selektion). MUTANTEN und ELTER, respektive ihre Qualitäten, bilden somit ein gemeinsames Selektionsensemble. Aus der Schar bewerteter Systeme wird ein neuer, aktueller Elter für die folgende Generation erwählt. Mit der Variation dieses Elter-Systems setzt sich die Kampagne fort. Auf diese Weise steigt die Qualität des Ensembles von Generation zu Generation, bzw. fällt nicht hinter die des aktuellen Elter zurück. Evolutionäre Algorithmen sind lokale Suchverfahren für komplexe, hochdimensionale Qualitätenräume. Aus biologistischer Sicht betrachtet untersuchen tradierte Evolutionsstrategien den Phänotyp eines Zielsystems und zielen somit auf das „äußere Evolutionsgeschehen“.

Der Variation kommt bei evolutionären Algorithmen eine besondere Bedeutung zu. In unserem Szenario sollen gleichverteilt zufällige Variationen den Objektvariablen-Vektor des Nachkommen von dem des ELTER unterscheiden. Neben den Merkmalen des als ELTER der nächsten Generation bestellten Nachkommen wird ein Strategieparameter vererbt: die Variations-Schrittweite δ δ (siehe Form (2)). Sie ist δ δ

in einfachen Optimierungsstrategien für alle Komponenten des Objektvariablen-Vektors gleich.

Ein einfachster evolutionärer Algorithmus besteht wenigstens aus den formalen Elementen:

Mit dem Grad der Nachahmung der biologischen Evolution nimmt die Güte der Algorithmen zu. Effiziente Evolutionsstrategien und Genetische Algorithmen waren und sind aktuell Ziel intensiver Forschung und Entwicklung [Kos-03][Her-00][Her-05] [Rec-94][Sche-85][Schw-95][Die-09][Die-07][Die-06][Die-05]. Nachfolgend soll immer von (einfachsten) Evolutionsstrategien mit einem Elter und einer globalen (auf alle Varianten angewendeten) Variationsschrittweite die Rede sein.

Optimierungsfortschritt. Trotz oder gerade wegen ihrer von totaler Einfachheit getragenen Kompaktheit tritt bei Evolutionsstrategien und Genetischen Algorithmen nun folgendes Problem auf: Wie alle lokalen Strategien sind Evolutionsstrategien per se amnestisch; sie besitzen keine Erinnerung an ihre eigene (Variablen-) Vorgeschichte. Dies ist ein großer Nachteil gegenüber anderen konkurrierenden Optimierungsalgorithmen. In der Vergangenheit wurden deshalb zahlreiche Strategien entwickelt, die die Integration der Variablenvorgeschichte leisten. Richtungslernen (Schwefel) und Präteritum- Strategie (Rechenberg) führen auf korrelierte Mutationen und untersuchen hierzu die Variablenvergangenheit. Extrahiert werden den Optimierungsprozess steuernde Strategieparameter aus dem aktuellen Optimierungsfortschritt p, sofern ∆V(n) eine Erfolgreiche unter den rezenten Variationen ist.

p = F(∆V(n))

Die Integration Variablenvergangenheit in eine Evolutionsstrategie ist effizient. Ursache ist die Komplemetarität der Ähnlichkeitsvariation der Objektvariablen gegenüber deren Variablenvergangenheit. Jeder Generation in einer iterativen Optimierungskampagne ist der Optimierungsfortschritt (Progress (p) ) inhärent. Er 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) (3)

In der Form (3) wird nach der Analyse und Qualitätsermittlung der rezente Progress p aus der Differenz des besten Nachkommen Vb und dem aktuellen Elter Ve ermittelt. Der Vektor Vb ging in der Generation (n-1) aus der Nominierung des besten Nachkommen zum Elter Ve der neuen Generation hervor.

Variablenvergangenheit. In der Entwicklung der lokalen Suchalgorithmen stellten Strategien, die den Progress während der Laufzeit der Optimierung analysieren und statistisch auswerten einen entscheidenden Fortschritt und gleichzeitig den gegenwärtigen Endpunkt der Entwicklung dar [Ost-97][Han-98]. Jedoch hat die gegebene Effizienz dieser Verfahren einen hohen Preis: der Deklarationsaufwand für beispielsweise wächst beim Richtungslernen (Schwefel) und der Präteritum-