2 Numerische Optimierungsverfahren

2 Numerische Optimierungsverfahren

2.1 Überblick

Optimierungsprobleme treten heute in immer mehr Anwendungsbereichen auf. Ziel der Optimierung ist die Verbesserung der Qualität eines technischen Systems durch Veränderung der Systemparameter. Dies kann z. B. unter wirtschaftlichen Gesichtspunkten zur Senkung von Produktionskosten erfolgen. Über eine Erhöhung des Wirkungsgrades lässt sich z. B. der Energieverbrauch senken, was nicht nur zu verringerten Kosten, sondern auch zu vermindertem Schadstoffausstoß führt. Auch zeitliche Probleme können eine Optimierung erfordern. So kann die Produktionszeit verringert oder der Durchsatz erhöht werden.

Einen weiteren wichtigen Bereich stellen multimediale Anwendungen dar. Die dort verwendeten Algorithmen müssen zur Verbesserung der Bild- und Tonqualität optimal an die audiovisuellen Eigenschaften der menschlichen Wahrnehmung angepasst werden [BlFrSch98].

In der Vergangenheit wurden Optimierungen größtenteils auf experimentelle Art durchgeführt. Dies erfordert langjährige Erfahrung und „Fingerspitzengefühl”. Zudem sind Experimente an realen Systemen sehr kostspielig und zeitaufwendig, wenn sie zur Bewertung der Optimierungsfortschritte den Bau und das Austesten von Prototypen erfordern. In Bereichen wie dem Flugzeugbau sind solche Tests häufig mit Risiken verbunden. Gewünschtes Ziel ist daher, möglichst wenige Versuche durchzuführen.

Im Gegensatz zu diesen heuristischen Verfahren steht die mathematische Optimierung. Ausgangspunkt ist ein mathematisches Modell, welches das System oder einen Prozess nachbildet und so eine Behandlung mittels mathematischer Methoden ermöglicht bzw. Simulationen auf digitalen Rechnern zulässt. Ein Modell kann nie alle Parameter eines realen Prozesses repräsentieren, daher erfordert die Modellbildung eine gründliche Analyse des zu optimierenden Systems. Für Systeme wie die menschliche Wahrnehmung, die sich aufgrund ihrer Komplexität nicht analytisch beschreiben lassen, werden stark vereinfachte Signalmodelle verwendet. Es müssen relevante Variablen von zu vernachlässigenden Einflüssen getrennt werden, um das Modell nicht unnötig zu verkomplizieren, da jeder Freiheitsgrad die Dimension des Optimierungsproblems erhöht. Von entscheidender Bedeutung ist die Vorgabe einer Zielgröße für den Optimierungsvorgang. Diese Zielfunktion ist von den Modellvariablen abhängig. Die Schwierigkeit besteht darin, eine geeignete Zielfunktion zu finden, da die vorgegebenen Ziele oft widersprüchlich sind, wie z. B. hohe Bildauflösung bei geringer Datenübertragungsrate.

Um das Optimum zu erhalten, wird nach dem Minimum oder Maximum der Zielfunktion F(x) gesucht. Maximierungsprobleme können durch

max {F(x)} = - min {- F(x)}

leicht in die in der Literatur häufiger erwähnten Minimierungsprobleme umgewandelt werden [Schwefel95].

Da die Zielfunktion in vielen Fällen nicht analytisch darstellbar und insbesondere nicht differenzierbar ist, lassen sich die aus der Analysis bekannten Verfahren zum Auffinden von Extremwerten nicht anwenden. Deshalb wird eine numerische Optimierung als iterativer Suchprozess über dem Parameterraum durchgeführt.

Eine Schwierigkeit besteht darin, dass neben unimodalen Problemen auch multimodale Optimierungsprobleme existieren. Unimodal bedeutet, dass die Funktion nur ein einziges und damit globales Optimum besitzt. Bei multimodalen Problemen existieren mehrere lokale Optima. Anschaulich verhält sich die Zielfunktion im zweidimensionalen Fall wie ein Gebirge mit mehreren unterschiedlich hohen Berggipfeln. Dies ist in den Abbildungen 2.1 und 2.2 dargestellt. Sicher kann das globale Optimum von multimodalen Funktionen nur durch vollständiges Enumerieren, dem Austesten aller Parametervariationen, gefunden werden. Das ist aber nur in den seltensten Fällen realisierbar, da der mögliche Parameterbereich im Allgemeinen zu groß ist, um in akzeptabler Zeit komplett durchlaufen zu werden.


Unimodal Multimodal
Abbildung 2.1: Unimodale Funktion Abbildung 2.2: Multimodale Funktion

Das Fehlen einer universellen Optimierungsmethode hat zur Entwicklung verschiedenster Strategien geführt, von denen einige nur in sehr begrenzten Bereichen eingesetzt werden können. Daher spielt die Auswahl der für das vorliegende Problem geeignetsten Methode eine wichtige Rolle. Bewertungskriterien für die Qualität einer Optimierungsstrategie sind z. B. Effektivität und Effizienz. Die Effektivität ist ein Maß für die Zuverlässigkeit der Suche nach dem Optimum. Eine robuste Strategie findet selbst unter ungünstigen Startparametern ein Optimum. Auch die Effizienz der Strategie, also die Zeit bzw. die Anzahl der Iterationsschritte bis zum Auffinden eines Optimums, ist nicht zu vernachlässigen [Schwefel95].

Zunächst werden einige Optimierungsverfahren kurz vorgestellt. Im Anschluss erfolgt eine ausführlichere Vorstellung der in dieser Studienarbeit verwendeten Strategien.

2.1.1 Direkte Suchverfahren

Direkte Suchverfahren benötigen kein Modell der Bewertungsfunktion, sondern testen den Parameterraum schrittweise in unterschiedlichen Richtungen ab. Ausgehend von der Parameterbelegung im Iterationsschritt p(k) nähert man sich mit der Schrittweite s(k) in Richtung v(k) dem Optimum:

p(k+1) = p(k) + s(k) · v(k) .

Durch einen Vergleich der Zielfunktion F(x) an der aktuellen Position mit den Funktionswerten an den abgetasteten Stellen findet eine Adaption der Suchrichtung und Schrittweite statt. Erfolgreiche Tastschritte haben eine Verbesserung des Zielfunktionswertes zur Folge. Auch durch schlechtere Werte können Rückschlüsse über den Verlauf der Zielfunktion gezogen werden. Daher werden direkte Suchverfahren auch als trial-and-error-Methoden bezeichnet. Zum sicheren Auffinden des globalen Optimums, benötigt man wenigstens einen Weg zum Ziel, auf dem die Zielfunktion sich je nach Problemtyp monoton steigend oder fallend verhält.

Direkte Suchverfahren werden aufgrund ihrer einfachen Realisierbarkeit häufig erfolgreich in der Praxis angewendet. Da diese Verfahren schnell in den Einfluss lokaler Optima gelangen, ist die Wahl des richtigen Startpunktes entscheidend. Zur Lösung multimodaler Probleme müssen daher viele Optimierungsläufe mit unterschiedlichen Startparametern realisiert werden.

Zu den ältesten Suchverfahren gehört das Koordinatenverfahren (coordinate strategy) von Gauß und Seidel, bei dem die Suche parallel zu den Koordinatenachsen verläuft. Ein häufig verwendetes Verfahren ist das pattern search von Hooke und Jeeves (1961). Dabei erfolgt nach einem Testschritt (exploratory move) eine Extrapolation entlang der bevorzugten Richtung (pattern move). Um die Beschränkung durch Koordinatenachsen zu entfernen, hatte Rosenbrock 1960 die Idee, das Koordinatensystem jeweils in die aussichtsreichste Richtung zu drehen (rotating coordinates). Eine ausführliche Beschreibung der direkten Suchverfahren ist in [Schwefel95] gegeben.

2.1.2 Zufallsmethoden

Anders als die zuvor beschriebenen Suchverfahren arbeiteten Zufallsstrategien mit Wahrscheinlichkeiten. Kennzeichen dieser Optimierungsstrategien ist, dass der Parameterraum dabei durch zufällige Parameterbelegungen abgesucht wird. Aufgrund des nicht deterministischen Verhaltens können Zufallsmethoden auch dann zum Ziel führen, wenn andere Verfahren nicht den gewünschten Erfolg haben. Nachteilig ist, dass sich keine Aussagen über den Erfolg der Suche machen lassen, da Optima nur durch Zufall gefunden werden können. Zudem ist der Rechenaufwand enorm groß, weil gute Ergebnisse erst nach vielen untersuchten Punkten des Parameterraums zu erwarten sind. Auch besteht die Wahrscheinlichkeit, dass schon getestete Punkte noch einmal untersucht werden.

Reine Zufallsmethoden werden auch als Monte-Carlo-Strategien bezeichnet. Neben dieser „blinden” einfachen Strategie wurden auch kompliziertere Varianten entwickelt, z. B. mit Einbeziehung eines Informationsspeichers und einer Zielrichtung [Schwefel95].

Obwohl der Anwendungsbereich von Zufallsmethoden eingeschränkt ist, werden Zufallselemente in fast jeder Optimierungsstrategie verwendet. So lässt sich beispielsweise die Wahl der Suchrichtung beim Koordinatenverfahren durch zufällige Entscheidungen treffen. Auch bei Evolutionsstrategien spielt der Zufall eine wichtige Rolle.

2.2 Gradientenstrategien

Gradientenstrategien sind eine Untergruppe von direkten Suchverfahren. Eine Gradientenstrategie schreitet von einem Punkt des Parameterraums in die aussichtsreichste Richtung der Zielfunktion voran. Diese Richtung ist der Gradient, der steilste Anstieg bzw. Abfall der Bewertungsfunktion an der untersuchten Position. Um den Gradienten zu ermitteln, müssen die ersten partiellen Ableitungen der Zielfunktion nach allen n Variablen des n-dimensionalen Problems gebildet werden. Die Ableitungen können nach [Schwefel95] auch über einen Differenzenquotienten approximiert werden:

Formel

p(k) entspricht einem Punkt der k-ten Iteration im Parameterraum, δ ist die Schrittweite des Differenzenquotienten, F(p) bezeichnet die Ziel- oder Bewertungsfunktion und ei ist der Einheitsvektor in Richtung der i-ten Koordinatenachse.

Formal lautet die Iterationsvorschrift nach [Schwefel95]

Formel

Nach einem Schritt mit Schrittweite s(k) in Richtung des Gradienten wird der neue Funktionswert überprüft. Falls F(p(k+1)) besser als der vorangegangene F(p(k)) ist, läuft das Verfahren von diesem Punkt p(k+1) mit derselben Schrittweite weiter. Bei einem schlechteren Wert von F(p(k+1)) muss die Schrittweite um einen Reduktionsfaktor r verringert werden, da das Optimum schon überschritten worden ist. Dies ist in den Abbildungen 2.3 und 3.4 dargestellt. Hat die Schrittweite eine bestimmte Größe unterschritten, ist im Rahmen der durch die Abbruchschrittweite gegebenen Genauigkeit ein Optimum der Funktion gefunden. Der Algorithmus wird in Abbildung 2.5 noch einmal ausführlich beschrieben.


Schrittweite Schrittweite
Abbildung 2.3: Richtige Schrittweite Abbildung 2.4: Zu große Schrittweite

Algorithmus
Abbildung 2.5: Algorithmus der Gradientenstrategie

Entscheidend ist die richtige Wahl des Startpunktes p, da der Suchprozess in das nächste lokale Optimum läuft. Um das globale Optimum bei multimodalen Problemen zu finden, muss von vielen unterschiedlichen Punkten gestartet werden.

Gradientenstrategien sind einfach zu implementierende Verfahren, die sich zur Lösung von unimodalen Aufgaben bewährt haben. Sie können auch zu Kontrollzwecken verwendet werden, um einen Anhaltspunkt über zu erwartende Optima zu erhalten. Da das Versagen bei multimodaler Problemstellung zu erwarten ist, müssen hierfür andere Verfahren genutzt werden. [Schwefel95] enthält einen Überblick weiterer Gradientenstrategien.

2.3 Simulated Annealing

Das Grundprinzip des Simulated Annealing wurde aus physikalischen Vorgängen übernommen. Der Begriff „Annealing” stammt aus der Metallurgie und bezeichnet den Aushärtungsvorgang von Stahl. Das Optimierungsverfahren verläuft analog zu diesem physikalischen Aushärtungsprozess, bei dem das Metall nahe an den Schmelzpunkt erhitzt wird. Würde das Metall zu rasch abgekühlt, blieben die Atome in einem hohen zufälligen Energieniveau eingeschlossen. Fällt die Temperatur jedoch langsam genug, haben die Atome genügend Zeit, sich auf stabileren und geordneten Positionen einzufinden. Am Ende bleibt ein kristalliner Zustand mit einem sehr niedrigen Energieniveau. Die gleiche Erscheinung tritt bei Phasenübergängen von gasförmigen Stoffen zu flüssigen und von flüssigen zu festen Zuständen auf.

Beim Simulated-Annealing-Prozess entspricht der Wert der Zielfunktion dem Energiezustand des Metalls. Das globale Minimum entspricht dem Zustand der höchsten Ordnung oder kleinsten Entropie. Ein weiterer Parameter, welcher mit der Temperatur korrespondiert, wird langsam abgesenkt, um den Abkühlungsvorgang zu simulieren. Falls die „Temperatur” zu schnell abgesenkt wird, kann der Prozess in einem lokalen Minimum gefangen bleiben, bei zu langsamem Abkühlen kann die Berechnungszeit unnötig verlängert werden.

Das Simulated-Annealing-Verfahren startet mit einem zufälligen Anfangszustand. Neue Konfigurationen werden mit Monte-Carlo-Methoden generiert, wobei die Zufallswerte aus dem Intervall [-½, ½] gleichverteilt oder einer Normalverteilung entnommen sein können. Der neue Energiezustand bzw. Wert der Zielfunktion wird mit dem alten verglichen. Ist der neue Wert besser, wird er übernommen. Er kann andererseits aber auch übernommen werden, falls Eneu < Ealt, allerdings nur mit einer Wahrscheinlichkeit Formel, wobei k für die Boltzmannkonstante und T für die Temperatur stehen. Dies entspricht der aus der Thermodynamik bekannten Boltzmannverteilung. Wurde nach einer bestimmten Anzahl von Schritten keine Verbesserung erzielt, ein Zustand der auch als Equilibrium bezeichnet wird, wird die Temperatur abgesenkt [Schwefel95]. Dies geschieht solange, bis die Zieltemperatur erreicht ist. Der vollständige Algorithmus ist in Abbildung 2.6 dargestellt.


Algorithmus
Abbildung 2.6: Algorithmus des Simulated Annealing

Die Simulation muss bei jeder Temperatur genügend Testschritte durchführen, um eine für diese Temperatur typische Konfiguration zu finden. Diese Optimierungsstrategie läuft durch das Absenken der Temperatur einem Optimum entgegen, kann aber anhand des gelegentlichen Akzeptierens von „schlechteren” Positionen den Bereich eines lokalen Extremums wieder verlassen.

2.4 Evolutionsstrategien

Evolutionsstrategien (ES) besitzen die Mechanismen der biologischen Evolution als Vorbild. Durch die Evolution haben sich im Laufe der Zeit optimal an den sie umgebenden Lebensraum angepasste Lebewesen entwickelt. Außerdem ist im Verlauf der Evolution eine Entwicklung zu immer komplexeren und intelligenteren Arten erkennbar, wie der Ablauf der Evolution von einzelligen Lebensformen hin zu vielzelligen hochentwickelten Säugetieren zeigt. Daher ist zu vermuten, dass der Evolutionsprozess, der als Ergebnis optimale Lebewesen liefert, auch in seinen Mechanismen sehr effektiv ist. Deshalb bieten sich Evolutionsmechanismen auch zu Lösung technischer Optimierungsprobleme an [Franzen96].

In der Natur erhalten die Nachkommen einer Art durch sexuelle Fortpflanzung eine Kombination der Gene und damit der Eigenschaften ihrer Vorfahren. Dieser Vorgang wird als Rekombination bezeichnet. Zusätzlich können beim Kopieren der Erbinformationen Veränderungen auftreten, die Mutation genannt werden. Letztendlich wird sich das Individuum durchsetzen und weitere Nachkommen generieren, welches den Anforderungen an seine Umwelt am besten gewachsen ist. Schlechtere Individuen haben selten Möglichkeiten zur Fortpflanzung, daher werden ihre Gene nicht an nachfolgende Generationen weitergegeben. Nach einer großen Anzahl Generationen haben sich die besten Eigenschaften durchgesetzt. Ein Phänomen das Selektion genannt wird.

Die erste technische Anwendung der Evolutionsstrategie fand 1963 an der Technischen Universität Berlin statt. Rechenberg und Schwefel setzten die Prinzipien der Evolution ein, um die Form von Gegenständen im Windkanal zu optimieren. Bei diesem Vorgang ist eine analytische Optimierung nicht möglich. Evolutionsstrategien haben sich zur Lösung von Optimierungsaufgaben in vielen anderen Anwendungsbereichen als sehr effektiv und effizient erwiesen. Aufgrund ihrer Mechanismen können Evolutionsstrategien den Bereich schlechterer lokaler Extremwerte der Zielfunktion verlassen und so mit größerer Wahrscheinlichkeit als die Gradientenstrategien gute Optima erreichen. Dies zeichnet sie als robuste Optimierungsverfahren aus. Nach der ursprünglich entwickelten (1+1)-Strategie entstanden die als (μ + λ)- und (μ , λ)-Strategie (Plus- bzw. Komma-Strategie) bezeichneten Verfahren [Schwefel95]. Später wurde der Begriff zur (μ , κ, λ, ρ)-Strategie verallgemeinert.

Im Folgenden sollen nun die im Zusammenhang mit Evolutionsstrategien wichtigen Begriffe näher erläutert werden.

2.4.1 Grundbegriffe der Evolutionsstrategie

Individuum

In der biologischen Evolution wird ein Individuum durch seine Gene gekennzeichnet. Die Erbinformationen, die den Bauplan und das instinktive Verhalten eines Lebewesens enthalten, sind in jeder Körperzelle in den aus Desoxyribonukleinsäure (DNS) bestehenden Chromosomen codiert.

Auf ähnliche Weise lassen sich die veränderbaren Parameter in technischen Prozessen auch als Gene auslegen. Während die biologische DNS nur vier verschiedenen Nukleotidbasen benötigt, können in technischen Systemen sowohl reellwertige, ganzzahlige als auch boolsche Werte verwendet werden. Zusätzlich zu den Objektvariablen xi, die die Eigenschaften eines Individuums repräsentieren, können noch Strategieparameter σi eingeführt werden. Während die Objektvariablen für den Optimierungsprozess wichtige Parameter wie z. B. bei digitalen Filtern die einzelnen Filterkoeffizienten enthalten, sind die Strategieparameter nur für die Mechanismen der Evolution notwendig. Für die Evolution ist ein Individuum durch die sich aus den Objektparametern gemäß der Optimierungsaufgabe bestimmten „Fitness” charakterisiert. Ihr kommt eine wichtige Aufgabe bei der Selektion zu. Der Aufbau eines Individuums ist in Abbildung 2.7 zu erkennen.


Fitness x1 x2 ... xn
σ1 σ2 σn
Objektvariablen
Strategieparameter
Abbildung 2.7: Schematischer Aufbau eines Individuums

Population

Anders als bei den vorab beschriebenen Optimierungsverfahren werden bei Evolutionsstrategien nicht nur einzelne Individuen sondern ganze Gruppen oder Populationen von Individuen verwendet. Das hat den Vorteil, dass der Parameterraum von mehreren Startpunkten aus gleichzeitig durchsucht werden kann. Zudem kann, falls ein einzelnes Individuum in ein lokales Optimum läuft, die Restpopulation die Suche in anderen Bereichen des Parameterraumes fortsetzen. Die Anzahl der Elternindividuen einer Generation wird bei Evolutionsstrategien mit μ bezeichnet, die Zahl der Nachkommen wird λ genannt. Die ursprüngliche (1+1)-Strategie von Rechenberg umfasst nur jeweils ein Eltern- und Kindindividuum. Neuere Strategien benutzen weitaus größere Populationen.

Mutation

Im Verlauf der natürlichen Mutation werden einzelne Gene bei der Weitergabe der Erbinformation zufällig verändert. In einem technischen System wird dies durch die zufällige Änderung mehrerer Parameter realisiert. Dabei bringen geringfügige Änderungen an bewährten Individuen in der Regel geeignetere Individuen mit sich als große Veränderungen vieler Parameter. Zu große Sprünge im Parameterraum führen zu einer reinen Zufallsstrategie. Andererseits ist aber auch eine größere Schrittweite wünschenswert, um schneller Fortschritte im Evolutionsprozess zu erzielen. Damit diese widersprüchlichen Anforderungen vereint werden können, wird daher jedem Parameter xi des Individuums ein Streuwerte σi zugewiesen. Dieser Strategieparameter gibt die Halbwertsbreite einer normal (gauß)-verteilten Zufallszahl an, die zur Mutation der Objektvariablen verwendet wird. Durch die Verwendung der Normalverteilung finden kleinere Änderungen der Gene häufiger statt als große. Normalverteilte Zufallswerte z1, z2 können durch

Formel

aus den gleichverteilten Zufallszahlen y1 und y2 erzeugt werden [Schwefel95].

Innerhalb jedes Iterationsschrittes werden sowohl die Parameter xi eines Individuums als auch die Streuparameter σi gemäß folgender Gleichung mutiert [Franzen96]:

Formel

Die Funktion gauss(x) erzeugt dabei eine nach Gleichung (2.5) normalverteilte Zufallszahl der Halbwertsbreite x. Da die mittlere Streuwertgröße σmittel nahezu konstant bleibt, wird für alle Mutationen der Streuweite ein gleicher Anteil τ´ benutzt, τ ist eine frei zu wählende Konstante. Nach der Veränderung der Streuwerte werden die Objektparameter dann mit ihrer Hilfe mutiert. Dieser Vorgang wird in Abbildung 2.8 noch einmal verdeutlicht.


Schema
Abbildung 2.8: Schema der Mutation

Durch die Weitergabe der Streuwerte an die nachfolgenden Generationen sind auch sie dem Evolutionsprozess unterworfen. Im Verlauf des Optimierungsprozesses setzen sich diejenigen Streuwerte durch, welche das schnellste Fortschreiten in Richtung des Optimums ermöglichen. Dieses Verfahren der lernenden Population wurde von Rechenberg entwickelt [Schwefel 95].

Das oben dargestellte Mutationsschema wird gemäß [Schwefel95] nur bei kontinuierlichen Parameterräumen verwendet. Ein für diskrete Parameter geeignetes Verfahren wird in Kapitel 4 vorgestellt.

Rekombination

Die Rekombination ahmt den Vorgang der sexuellen Fortpflanzung in der Natur nach. Mit Ausnahme sehr weniger primitiver Organismen wird dieser Mechanismus von allen Lebewesen verwendet. Durch die Kombination der Eigenschaften beider Elternteile in den Nachfahren lassen sich größere Abstände im Parameterraum überwinden als durch die infolge ihrer Streuwerte beschränkte Mutation. Trotz der beträchtlichen Parameteränderung sind erfolgreiche Individuen zu erwarten, da sich die Eigenschaften des neuen Individuums aus den schon bewährten der Eltern ableiten.

Nach [Schwefel95] lassen sich zwei gegensätzliche Modi der Rekombination unterscheiden:

Bei der intermediären Rekombination werden die Parameter des neuen Individuums aus dem arithmetischen Mittel der entsprechenden Parameter beider Elternteile erzeugt. Zur diskreten Rekombination wird die Komponente eines mit gleicher Wahrscheinlichkeit zufällig ausgewählten Elternteils an das neuerzeugte Individuum weitergegeben. Entsprechend werden auch die vorhandenen Streuwerte weitergegeben. Die Unterschiede werden durch die Abbildungen 2.9 und 2.10 verdeutlicht.


Rekombination
Abbildung 2.9: Intermediäre Rekombination

Rekombination
Abbildung 2.10: Diskrete Rekombination

Selektion

Mit der Selektion wird ein weiterer wesentlicher Bestandteil der biologischen Evolution nachgebildet. Natürliche Lebewesen sind einem immerwährenden Überlebenskampf unterworfen. Nur die besten Individuen einer Art können gegen ihre Fressfeinde bestehen und erfolgreich einen Partner zur Fortpflanzung finden. Dieser Auslesevorgang wird auch bei technischen Systemen angewendet. Hier wird, anders als in der Natur, die eine fast beliebige Anzahl von Individuen zulässt, eine konstante Populationsgröße benutzt, um den programmiertechnischen Aufwand bzw. die Speichergröße in einem begrenzten Rahmen zu halten.

Dieser „Kampf ums Überleben”, von Darwin „Struggle for Life” genannt, gestaltet sich derart, dass aus der Elterngeneration die μ besten Individuen gesucht und aus ihnen anhand von Mutations- und Rekombinationsmechanismen λ neue Individuen erzeugt werden. Auch aus dieser neuen Generation setzen sich wieder die besten Individuen durch und generieren wiederum Nachfahren.

2.4.2 Verschiedene Evolutionsstrategien im Detail

Es existieren unterschiedliche Formen der Evolutionsstrategie. Allen gemeinsam ist der in Abbildung 2.11 dargestellte Algorithmus. Nach der Erzeugung einer Startpopulation wird eine Kindgeneration gebildet, aus der die Eltern der neuen Generation selektiert werden.


Algorithmus
Abbildung 2.11: Algorithmus der Evolutionsstrategie

Bei der Selektion werden zwei wesentliche Strategien unterschieden: Die (μ + λ)-Strategie und die (μ , λ)-Strategie.

Zur Erzeugung der Elternindividuen der n+1-ten Generation bei der (μ + λ)-Strategie werden die μ besten Individuen aller μ+λ Individuen der n-ten Generation bestimmt. Die (μ , λ)-Strategie hingegen generiert die nachfolgende Generation nur aus den λ besten Kindern der aktuellen Generation. Im Gegensatz zur (μ + λ)-Strategie, bei der „gute&tdquo; Individuen eine unendlich lange Lebensspanne erreichen können, „sterben” hier alle Individuen nach jeweils einer Generation. Dies entspricht eher dem Vorbild der natürlichen Evolution, da hier das Konzept einer begrenzten Lebensspanne berücksichtigt wird. Die unterschiedliche Funktionsweise beider Strategien wird durch Abbildung 2.12 verdeutlicht.


Strategie
Abbildung 2.12: Unterschiede zwischen (μ + λ)- und (μ , λ)-Strategie bei der Selektion

Die (μ , λ)-Strategie lässt eine schnellere Konvergenz erwarten, da die Individuen nur eine kurze „Lebenserwartung” haben und schlechtere Individuen nicht, wie bei der (μ + λ)-Strategie, auch einen längeren Zeitraum überleben können. Allerdings sind sogar Rückschritte möglich, weil die neu generierten Kinder nicht zwangsläufig besser als die Eltern sein müssen. Auch können besonders gute Individuen nur eine Generation lang Einfluss auf die Gesamtpopulation nehmen. Daher sollte das beste im Verlauf des Evolutionsprozesses gefundene Individuum abgespeichert werden, um nach dem Erreichen des Evolutionsendes die beste ermittelte Parameterkonfiguration zu erhalten.

Mit Hilfe des Verhältnisses von μ zu λ, dem Selektionsdruck, kann die Geschwindigkeit der Evolutionsstrategie eingestellt werden. Bei zu großem μ schreitet die Population nur langsam voran. Durch zu hohen Selektionsdruck, also bei kleinem μ, kann die Suche in einem lokalen Optimum enden, da schlechtere Individuen, die den Einflussbereich des Optimums verlassen können, von den besseren verdrängt werden.

Diese beiden Standardstrategien werden häufig modifiziert. Erwähnenswert ist die Einführung zweier neuer Parameter κ und ρ. κ bestimmt dabei die Anzahl der Generationen, die ein Individuum überlebt. Ist κ = 1, entspricht dies der (μ , λ)-Strategie, die (μ + λ)-Strategie wird durch den Extremwert κ = ∞ beschrieben. Durch den Parameter ρ wird festgelegt, wie viele Elternteile an der Generierung eines neuen Individuums beteiligt sind. Am verbreitetsten sind die übliche bisexuelle Rekombination mit ρ = 2 und die multisexuelle globale Rekombination für ρ = μ.

2.5 Differential Evolution

Das parallel arbeitende direkte Suchverfahren der Differential Evolution (DE) wurde 1995 von Rainer Storn und Kenneth Price entwickelt. Ihr Ziel war die Bildung einer robusten, leicht zu benutzenden und schnellen Optimierungsstrategie.

Ebenso wie bei Evolutionsstrategien wird bei der Differential Evolution eine Population von Individuen verwendet. Die Populationsgröße NP bleibt auch bei diesem Optimierungsverfahren konstant. Jedes Individuum stellt einen Parametervektor dar. Außer den Objektparametern werden keine weiteren Strategieparameter benötigt [Storn95].

Der Grundgedanke der Differential Evolution ist, die nächste Generation nicht durch Mutation und Rekombination zu bilden, sondern neue Individuen durch die Verwendung von Differenzen zwischen vorhandenen Vektoren zu generieren. Jedes neue Individuum der Population wird durch die Addition eines gewichteten Differenzvektors zweier (oder mehrerer) erfolgreicher Individuen pr2 und pr3 zu einem anderen Vektor pr1 gebildet. Der Mechanismus der Individuengenerierung ist in Abbildung 2.13 für den zweidimensionalen Fall veranschaulicht.


Erzeugung
Abbildung 2.13: Erzeugung eines neuen Individuums vneu

Erlangt das neugebildete Individuum eine bessere Fitness als das alte, ersetzt es dieses. Zur Verdeutlichung ist der Algorithmus in Abbildung 2.14 dargestellt.


Algorithmus
Abbildung 2.14: Algorithmus der Differential Evolution

2.5.1 Unterschiedliche Methoden der Individuengenerierung

Die Parametervektoren der neuen Individuen können auf verschiedene Weisen gebildet werden. Im einfachsten Fall wird ein neues Individuum erzeugt, indem der mit einer Konstante F gewichtete Differenzvektor zweier zufällig aus der Population gewählter Individuen pr2 und pr3 zu einem weiteren Vektor pr1 hinzuaddiert wird [Storn95]:

vneu = pr1 + F · (pr2 - pr3) .

Die Auswahl der mit p bezeichneten zufällig bestimmten Individuen erfolgt mittels einer Gleichverteilung. Der aktuelle Vektor wird mit v bezeichnet. Diese Methode der Individuengenerierung wird (DE/rand/1)-Strategie genannt.

Bei der (DE/best/1)-Strategie wird anstelle des zufällig ausgewählten Vektors pr3 das beste im bisherigen Verlauf bestimmte Individuum verwendet:

vneu = pbest + F · (pr2 - pr3) .

Zur Generierung des neuen Parametervektors können noch weitere zufällig ausgewählte Vektoren hinzugezogen werden:

vneu = pr5 + F · (pr1 + pr2 - pr3 - pr4) .

Storn bezeichnet diese Methode als (DE/rand/2)-Strategie. Auch in diesem Fall kann anstelle von pr5 der bisher beste Vektor pbest verwendet werden. Dies führt zur (DE/best/2)-Strategie:

vneu = pbest + F · (pr1 + pr2 - pr3 - pr4) .

Bei den vorausgehend beschriebenen Verfahren wurde entweder ein zufälliger oder der beste Vektor zur Addition verwendet. Eine weitere aussichtsreiche Strategie hat die Verwendung des bislang vorhandenen Vektors valt als Ausgangspunkt:

vneu = valt + F · (pbest + valt) + F · (pr1 - pr2) .

Durch die Verwendung sowohl des besten als auch eines Paares zufälliger Parametervektoren trägt diese Methode zur Bildung neuer Individuen die Bezeichnung (DE/rand-to-best/1).

Die Komponenten der Vektoren können über zwei verschiedene Zufallsverfahren (Crossover) gewählt werden:

Bei der exponentiellen Auswahlmethode wird eine zufällige Anzahl aufeinanderfolgender Komponenten des alten Parametervektors durch die neu erzeugten ersetzt. Die binominale Crossover-Methode verändert mit der Wahrscheinlichkeit CR eine Komponente des Vektors oder belässt sie im Originalzustand [Storn95].


Kapitel1 Zurück Kapitel3