%----------------------------------------------------------------
%
% implicit.tex
% Implizite Modellierung
%
%----------------------------------------------------------------
%
\chapter[Diskretisierung der Evolutionsstrategie]{Strategien zur Diskretisierung der Evolutionsstrategie}
\label{chap:DES}
% chapter E
%%%%%%%%
Im direkt folgenden Abschnitt \ref{chap:E_Motivation} wird
zunächst motiviert, weshalb eine Modifikation herkömmlicher
Evolutionsstrategien durch Diskretisierung des Suchraums sinnvoll
ist. In Abschnitt \ref{chap:E_Implementierung} werden dann
entsprechende diskretisierte Evolutionsstrategien konzipiert. Die
Ergebnisse dieser implementierten Strategie belegen die
Aufrechterhaltung einer ausreichend großen Diversität der
Population während des gesamten Optimierungsprozesses. Hierdurch
wird für eine ausgiebige Breitensuche gesorgt und die Neigung zur
Terminierung in lokalen Minima verringert.

\section{Motivation diskretisierter Suchräume}
\label{chap:E_Motivation}

\subsection{Vorzeitige Konvergenz in lokalen Optima }
Jede Evolutionsstrategie steht vor dem prinzipiellen Problem die
beiden gegenläufigen Ziele Exploration und Exploitation in
sinnvoller Weise zu unterstützen. Tendiert das Suchverhalten nur
zu einer Breitensuche, werden zwar Gebiete mit globalen Optima
gefunden, die globalen Optima an sich können aber nur schwer
entdeckt werden. Andererseits konvergiert ein
Optimierungsverfahren mit rein exploitativem Suchverhalten schnell
gegen ein Optimum. Meist handelt es sich jedoch um ein lokales
Optimum, das aufgrund der Tiefensuche auch nicht mehr verlassen
wird. Oft ist in konventionellen Evolutionsstrategien durch die
Verwendung der selbstadaptiven Schrittweitenanpassung nach
\Schwefel{} \cite{Sch77} eine Kombination zwischen beiden
Suchcharakteristiken umgesetzt. Der Anteil beider Charakteristiken
am Gesamtsuchverhalten ändert sich im Laufe der Optimierung. Nach
einer Phase mit dem Hauptgewicht auf der Breitensuche geht dieser
Anteil später gegen Null und das Verhalten ändert sich zu einer
Tiefensuche. Der Anteil der Tiefensuche ist jedoch auch am Anfang
nicht gleich Null. Dies führt dazu, dass das globale Optimum in
einer \glqq freundlichen\grqq{} (z.~B. muldenförmigen)
Fitnesslandschaft zwar schnell gefunden, aber bei einer
Fitnesslandschaft mit vielen lokalen Optima nur selten oder gar
nicht entdeckt wird.

\subsection{Bedeutung der Diversität einer Population}

Ein weiterer Nachteil herkömmlicher Evolutionsstrategien besteht
meistens darin, dass die Diversität der Population im Laufe der
Optimierung verloren geht. Dabei hat der Begriff der Diversität
mehrere Facetten: Diversität kann beispielsweise bedeuten, dass
die Fitnesswerte der Individuen einer Population möglichst
unterschiedlich sind. Eine andere -- auch in dieser Arbeit zu
Grunde gelegte -- Auffassung der Diversität basiert auf der
Verteilung der Individuen im Parameterraum, charakterisiert durch
Aufsummierung aller paarweisen Abstände aller Individuen. Hiernach
ist die Diversität umso größer, je gleichmäßiger die Individuen im
gesamten Parameterraum verteilt sind.

Eine hohe Diversität verhindert eine schnelle ungewollte
Konvergenz \cite{Wei02}. Deshalb ist es günstig die Diversität
durch geeignete Maßnahmen auf einem hohen Niveau zu halten.
Beginnt man die evolutionäre Optimierung mit einer zufällig
initialisierten Startpopulation, kann man von einer hohen
Diversität zu diesem Zeitpunkt ausgehen. Doch bereits nach wenigen
Generation kann sich die Diversität stark verringert haben.
Verantwortlich hierfür ist in der Regel der verwendete Mechanismus
zur Selektion. Ein hoher Selektionsdruck verringert die Diversität
stärker als ein niedriger Selektionsdruck, weil in letzterem Fall
auch schlechtere Individuen mit in die Folgepopulation übernommen
werden. Diese liegen in der Regel nicht in unmittelbarer
Nachbarschaft von guten Individuen.

Die Bedeutung der Diversität für den Erfolg der Optimierung kann
man vereinfacht wie folgt beschreiben: Je größer die vorgesehenen
Mutationen sind, desto größer kann -- abhängig von der Selektion
-- die Diversität in der Population werden. Ist die Diversität
groß, kann die Rekombination ebenfalls einen explorativen
Charakter bekommen. Dies bedeutet, dass ein erforschendes
Verhalten der Mutation ein ebensolches der Rekombination
begünstigt, falls die Selektion nicht zu kontrahierend wirkt.
Umgekehrt bewirkt eine geringe Mutation die Verringerung der
Diversität, die im Extremfall dazu führt, dass die Rekombination
nahezu nutzlos wird. Ein für konventionelle Evolutionsstrategien
bekanntes Phänomen ist, dass sich die Individuen im Laufe der
Optimierung immer weiter einander annähern, d.~h. die Diversität
immer mehr verloren geht. Sollte es sich bei dem gefundenen
Optimum nicht um das globale Optimum, sondern nur um ein lokales
handeln, wird dies aufgrund der fehlenden Diversität dann nur noch
schwer oder gar nicht mehr verlassen.

\subsection{Motivation der Diskretisierung von Suchräumen}

Während \cite{Wei02} den besten Weg zur aktiven Erhaltung der
Diversität in der Verwendung eines geeigneten
Selektionsmechanismus sieht, wird in dieser Arbeit ein anderer Weg
vorgeschlagen und ausgebaut. Dieser basiert auf der Intention,
eine Mehrfachbesetzung sowie eine erneute Besetzung von Punkten im
Parameterraum durch Individuen auszuschließen. Diese Intention ist
allerdings nicht mit vertretbarem Aufwand im reellwertigen
Parameterraum realisierbar. Daher wird hier eine Diskretisierung
des Suchraums eingeführt. Hierzu wird entlang jeder
Koordinatenachse eine Rasterung vorgenommen, so dass der Suchraum
letztendlich aus Gitterpunkten besteht. Eine solche
Diskretisierung erlaubt sowohl die Mehrfachbesetzung eines Punktes
im Suchraum als auch die Wiederbesetzung durch ein Individuum
einer späteren Generation auszuschließen. Zudem bleibt die Anzahl
der Individuen, die sich in einem günstigen Gebiet versammeln
können, in jeder Generation beschränkt. Damit wird zugleich auch
die Möglichkeit eröffnet, lokale Optima wieder zu verlassen.



Zusätzlich erlaubt der Diskretisierung das Ergebnis der
Optimierung zu beurteilen. Im Gegensatz zur konventionellen
Evolutionsstrategie, bei der in der Regel am Ende alle Individuen
den gleichen Punkt besetzen, kann jetzt die erhaltene
Endpopulation dahingehend untersucht werden, inwieweit größere
Suchraumgebiete von Individuen mit annähernd gleich guten
Fitnesswerten aufgefunden wurden. Dies ist in vielen praktischen
Anwendungsfällen von großem Interesse, denn hier besteht das
Suchbestreben nicht darin, nur ein sehr begrenztes Gebiet mit
guten Fitnesswerte zu finden. Vielmehr ist ein ausgedehntes Gebiet
mit guten Fitnesswerten im Sinne der Robustheit einer Lösung
deutlich zu bevorzugen: Bei Kenntnis eines solchen ausgedehnten
Gebietes mit guten Fitnesswerten wird man die Lösung so auswählen,
dass sie in der Mitte dieses Gebietes liegt. Handelt es sich bei
der Lösung beispielsweise um einen Regler, so gewährleistet diese
Wahl, dass das Regelungsverhalten robust gegenüber gewissen
Parametervariationen des Regelungssystems ist.

%%%
\section{Statische Diskretisierung des Suchraums}

\label{chap:E_Implementierung} Wie vorab beschrieben, liegen die
Vorteile eines diskretisierten Suchraums in einer Betonung des
explorativen Charakters des Suchverhaltens. Zudem eröffnet die
Diskretisierung den erfolgreichen Einsatz von zusätzlichen
Maßnahmen zur Aufrechterhaltung einer günstigen Diversität, so
dass lokale Optima wieder verlassen werden. Im Folgenden werden
zunächst die Änderungen beschrieben, die zur Einführung einer
statischen Diskretisierung an einer konventionellen
Evolutionsstrategie vorgenommen werden müssen. Daran anschließend
werden zusätzliche Strategieelemente zur adaptiven Diskretisierung
des Suchraums vorgestellt.

\subsection{Evolutionäre Suche in statisch diskretisierten Suchräumen}

Die Änderungen zur Einführung einer statischen Diskretisierung
werden durch Abbildung \ref{chap:E_Abb_Diskret_Mass} im Überblick
veranschaulicht.
\begin{figure}[ht]  \centering
\ingraph{15}{0}{../Bilder/des/Ablaufdiskretisiert}
\caption{\label{chap:E_Abb_Diskret_Mass} Modifizierter Ablauf der
Evolutionsstrategie in diskretisierten Suchräumen.}
\end{figure}

Zur Diskretisierung des Parameterraums wird eine Rasterung entlang
der Koordinatenachsen vorgenommen. Prinzipiell könnte die
Rasterung in jeder Dimension des Parameterraums unterschiedlich
gewählt werden. Aus Aufwandsgründen wird aber im Folgenden die
Rasterung in jeder Dimension gleich gewählt. Die eigentliche
Diskretisierung wird durch Runden auf bestimmte Werte erreicht.
Gemäß einer vom Anwender vorgegebenen Rasterweite können die
Individuen nur noch bestimmte Punkte in jeder Dimension besetzen.
So entsteht aus dem gesamten Parameterraum ein äquidistantes
Gitter. Die Individuen können nur noch die Gitterpunkte besetzen.

Die Rasterweite wird in normierter Form durch den Anwender
eingestellt. Sie bezieht sich auf die Wertebereichsbreite in der
jeweiligen Dimension. Eine eingestellte Rasterweite von $r=0,01$
führt bei einer Wertebereichsbreite von 1000 zu einer realen
Rasterweite von $r=10$. Dies bedeutet, dass Individuen im
Parameterraum nur noch Gitterpunkte mit einem Abstand von 10
entlang einer Koordinatenachse besetzen können.

Ein wichtiger Aspekt ist die Wahl einer geeigneten Rasterweite
$r$. Wird eine große Rasterweite ausgewählt, birgt sie zwar den
Vorteil einer Parameterraumabdeckung mit wenigen Schritten, aber
möglicherweise können gewisse Details der Fitnesslandschaft nicht
erkannt werden. Dieser Fall ist in Abbildung
\ref{chap:E_Abb_Diskretisierung} dargestellt. Im Gegenzug sollte
die Rasterweite aber auch nicht zu klein gewählt werden, da sonst
die gleichen Nachteile auftreten, wie sie herkömmlichen
kontinuierlich arbeitenden Verfahren eigen sind. Der Vorteil einer
kleinen Rasterweite ist allerdings ein kleiner
Diskretisierungsfehler, den wir hier als Differenz zwischen dem
betrachteten Minimum und dem nächstgelegen Rasterpunkt verstehen.
Besser als mit diesem Fehler kann das Minimum nicht gefunden
werden.
\begin{figure}[ht] \centering
\ingraph{8}{0}{../Bilder/des/Diskretisierung} \caption{
\label{chap:E_Abb_Diskretisierung} Beispiel für eine ungünstig
gewählte Rasterweite  $r$.}
\end{figure}

Durch empirische Ermittlung optimaler Rasterweiten für die
Testbeispiele aus Abschnitt \ref{chap:E_Testbeispiele} wurden die
Werte von $r=0,1$ und $r=0,0001$ als kleinster bzw. größter Wert
ermittelt. Als bester Kompromiss für die Wahl einer festen
Rasterweite für alle betrachteten Testbeispiele stellte sich der
Wert $r=0,01$ heraus.

Ferner ist ein Abbruchmechanismus vorgesehen, der den
Optimierungsvorgang abbricht, bevor die Anzahl der
Funktionsaufrufe die Anzahl der Gitterpunkte erreicht: Die Anzahl
$g$ der Gitterpunkte für ein $n$-dimensionales Optimierungsproblem
mit der normierten Rasterweite $r$  ist durch
\begin{equation} \label{chapE:_eq AnzGitterpunkte}
g =  \left( \frac {1} {r} + 1 \right)^{n}\;.
\end{equation}

bestimmt. Ohne Abbruchmechanismus würde der Algorithmus bei
Überschreitung der Anzahl vorhandener Gitterpunkt in eine
Endlosschleife übergehen, weil es aufgrund der ausgeschlossenen
Mehrfach- oder Wiederbesetzung nicht möglich ist, weitere Punkte
zu besetzen. Daher ist ein Abbruchmechanismus implementiert
worden, der die Optimierung beendet, falls ein bestimmter
Prozentsatz, typischerweise 25\%, aller Rasterpunkte besetzt ist
bzw. besetzt war.

\subsection{Diversifizierung der Population}
Entscheidend für den Erfolg der diskretisierten
Evolutionsstrategie sind geeignete Maßnahmen zur
Populationsdiversifizierung. Wie einführend erläutert, ist der
Erhalt der Diversität für den Erfolg der evolutionären Optimierung
wesentlich. Im Folgenden wird eine Strategie zur
Populationsdiversifizierung beschrieben, die auch im Rahmen dieser
Arbeit eingesetzt wird. Diese ist prinzipiell für kontinuierliche,
als auch für diskretisierte Suchräume einsetzbar, verspricht aber
nur bei diskretisierten Suchräumen wirkliche Vorteile.

Die Maßnahme basiert auf einem einfachen Prinzip: Jeder besuchte
Punkt im diskretisierten Suchraum wird in einer entsprechenden
Liste markiert. Anschaulich entspricht das Verfahren einer
Kennzeichnung besuchter Punkte in einer Karte des Suchraums
(\emph{Map}). Jeder dort verzeichnete Punkt kann nicht wieder
besetzt werden. Somit wird sowohl eine Mehrfachbesetzung von
Punkten im Suchraum, als auch das Wiederbesetzen von Punkten in
zukünftigen Generationen verhindert.

Technisch wird die \emph{Map} durch den Aufbau einer Tabelle mit
den entsprechenden Einträgen realisiert. Wird während der
Rekombination oder der Mutation ein neues Individuum erzeugt, wird
zunächst ein Abgleich mit der \emph{Map} durchgeführt. Ist der
Punkt, an dem sich das Individuum im Suchraum befindet, bereits in
der \emph{Map} vorhanden, wird das Individuum verworfen und ein
neues erzeugt. Nach einer bestimmten Anzahl von vergeblichen
Versuchen ein neues Individuum zu erzeugen, das noch nicht in der
\emph{Map} verzeichnet ist, wird mittels eines Zufallsgenerators
ein neues Individuum erzeugt. Der Zufallsgenerator erzeugt dazu
Individuen gleichverteilt über den gesamten Suchraum. Die so
erzeugten Individuen werden ebenfalls mit der \emph{Map}
abgeglichen und gegebenenfalls erneut gebildet.

Um Performanceverlusten durch Abgleiche mit einer sehr großen
\emph{Map} entgegenzuwirken, ist es vorgesehen, die \emph{Map} als
Speicher nach dem FIFO-Prinzip (First-In-First-Out) zu verwenden.
In diesem Fall wirkt sie nur als Aufzeichnung der letzten $k$
Generationen. Bei Erreichen der Generation $k+1$ werden die Daten
der ersten Generation gelöscht. Durch eine geeignete Wahl von $k$
kann die Performance bei Optimierungsproblemen, für die eine große
Anzahl von Funktionsaufrufe zu erwarten ist, verbessert werden,
ohne dass durch Löschen der Daten die Diversität verloren geht.
Durch regelmäßiges Sichern der \emph{Map}--Daten in Dateien kann
nach Ende der Optimierung der Inhalt der kompletten \emph{Map}
wiederhergestellt werden. Die Informationen können dann
beispielsweise als Grundlage für die später beschriebenen
Bewertungen genutzt werden.



\subsection{Rekombination bei diskreten Suchräumen}

Dieser Abschnitt erläutert die Änderungen, die an dem
ursprünglichen Rekombinationsmechanismus vorgenommen werden
müssen, wenn die Diskretisierung eingeführt wird. Die in dieser
Arbeit verwendete Standard--Evolutionsstrategie verfügt über zwei
verschiedene Rekombinationsmechanismen (vergl. Kapitel
\ref{chap:B_ES}). Im Fall der diskreten Rekombination ist keine
Anpassung erforderlich. Wenn vorausgesetzt wird, dass sich die
Eltern auf einem Gitterpunkt befinden, müssen sich die Nachkommen
ebenfalls auf Gitterpunkten befinden. Eine andere Situation ergibt
sich, falls die Rekombination intermediär durchgeführt wird. In
diesem Fall wird der Nachkomme analog zur kontinuierlichen
Variante erzeugt. Danach wird die Position des Nachkommen auf den
nächstliegenden Gitterpunkt gerundet. Wird eine Rasterweite $r$
angenommen, die den Abstand zwischen zwei Gitterpunkten
beschreibt, dann kann die durch Rundung entstehende Abweichung $a$
durch
\begin{equation} \label{chapE:_eq Rundung}
0 \leq |a| \leq \frac {r} {2}\;
\end{equation}

abgeschätzt werden. Durch den Einsatz der \emph{Map} zur
Diversifizierung der Population besteht die Möglichkeit, dass
erzeugte Individuen als ungültig ausgeschieden werden. In diesem
Fall wird der entsprechende Rekombinationsvorgang wiederholt. Um
unter Umständen eine Endlosschleife zu vermeiden, wird
gleichzeitig ein Zählmechanismus initialisiert. Sollte dieser
Zähler einen oberen Grenzwert erreichen, weil während der
wiederholten Rekombination stets ungültige Individuen erzeugt
wurden, wird das neue Individuum zufällig erzeugt. Hierzu wird
zufällig eine durch die \emph{Map} nicht verbotene Position im
Parameterraum ausgewählt.


\subsection{Mutation bei diskreten Suchräumen}

Die Mutation der diskretisierten Evolutionsstrategie weicht
ebenfalls von der kontinuierlichen Version ab. Der Unterschied
besteht hier in der Bedeutung der Schrittweite. Im
kontinuierlichen Fall wird ein zufälliger Schritt auf Basis der
mutierten Schrittweite ausgeführt. Technisch wird dies durch
Addition eines Zufallsvektors zum Positionsvektor des Individuums
realisiert. Die diskretisierte Evolutionsstrategie interpretiert
den zufälligen Schritt bezogen auf Rasterpunkte. Realisiert wird
dies durch eine Multiplikation des Zufallsvektors mit der
Rasterweite und der dann folgenden Addition zum Positionsvektor.

Die Betrachtung der Schrittlänge, bezogen auf die Rasterweite,
bewirkt  bei unterschiedlichen Rasterweiten einen deutlichen
Unterschied im Suchverhalten. Große Rasterweiten führen zu einem
wesentlich schnelleren Durchschreiten des Suchraums. Da sich das
Individuum vor der Mutation auf einem Gitterpunkt befunden hat,
wird es sich auch nach der Mutation auf einem Gitterpunkt
befinden, da durch die Mutation nur ganzzahlige Rasterschritte
durchgeführt werden. Auch bei der Mutation können ungültige
Individuen entstehen. Um dennoch gültige Mutationen durchführen zu
können, wird der gleiche Mechanismus wie bei der Rekombination
eingesetzt.
\subsection{Selektion bei diskreten Suchräumen}

Der Selektionsmechanismus wird nur insofern geändert, als dass die
Möglichkeit vorgesehen wird, die Populationsgröße während der
Optimierung situationsabhängig zu ändern.

In der Literatur finden sich verschiedene Arbeiten, die sich mit
dynamischen Populationsgrößen befassen. Beispielsweise empfiehlt
\cite{CTR99} für den Fall, dass keine weiteren Informationen über
das Optimierungsproblem vorhanden sind, die Verwendung einer
zufallsgesteuerten Variation der Populationsgröße gegenüber einer
willkürlich festgelegten festen Populationsgröße. Die in dieser
Arbeit verwendete Art der Populationsgrößenvariation bezieht sich
in erster Linie auf eine \emph{Vergrößerung} der Population.


Im Folgenden wird eine Strategie zur Erhöhung der Populationsgröße
bei Vorliegen nur einer Fitnessfunktion beschrieben. Eine
konventionelle Fitness-Selektion wählt aus einer Menge von $\mu +
\lambda$ Individuen die besten $\lambda$ Individuen als Eltern für
die nächste Generation aus. Dabei gilt üblicherweise $\mu
\leq\lambda$. Technisch wird die Selektion durch eine Sortierung
der Individuen nach ihren Fitnesswerten und Auswahl der ersten
$\mu$ Individuen umgesetzt. Im Rahmen des
Populationsvergrößerungsmechanismus wird die Fitness des
Individuums $\Ind_\mu$  mit der Fitness der Individuen
$\Ind_{\mu+1}$ bis $\Ind_{\mu + \lambda}$ verglichen. An den
Fitnesswert des Individuums $\Ind_\mu$ wird ein Toleranzbereich
der Breite $+ \varepsilon$ angelegt. Alle Individuen, deren
Fitnesswerte innerhalb dieses Toleranzbereichs liegen, werden
zusätzlich in die Population übernommen. Abbildung
\ref{chap:E_Abb_Popgroeser} zeigt exemplarisch eine Erhöhung der
Populationsgröße um ein weiteres Individuum.

\begin{figure}[ht]  \centering
\ingraph{10}{0}{../Bilder/des/Populationsvergroesserung}
\caption{\label{chap:E_Abb_Popgroeser} Prinzip der Erhöhung der
Populationsgröße.}
\end{figure}

Bei skalaren Optimierungsproblemen bewirkt die
Populationsvergrößerung, dass Plateaus der Fitnesslandschaft, also
Suchraumgebiete mit gleichen Fitnesswerten, \emph{vollständig}
besetzt werden. \emph{Vollständig} bedeutet in diesem
Zusammenhang, dass alle Gitterpunkte, die das Plateau einschließt,
besetzt sind. Die Verwendung der Populationsvergrößerung für ein
Optimierungsproblem mit mehr als einer Fitnessbewertungsfunktion
wirkt sich erfahrungsgemäß stärker aus als bei einem skalaren
Optimierungsproblem. Das entscheidende Kriterium zur Vergrößerung
der Population ist dabei die Anzahl der Pareto--optimalen
Lösungen. Ist diese größer als die ursprünglich gewünschte
Elternzahl, wird die Population entsprechend vergrößert. Während
das Kontinuum Pareto--optimaler Lösungen bei einer
kontinuierlichen Evolutionsstrategie zu einer unendlich großen
Population führt, wird durch die Diskretisierung des Suchraums die
mögliche Anzahl Pareto--optimaler Lösungen begrenzt und somit eine
endliche Populationsgröße garantiert.

Unabhängig von der Anzahl der Fitnessfunktionen des
Optimierungsproblems wird für die Populationsvergrößerung die
Möglichkeit vorgesehen, den Selektionsdruck auf den ursprünglichen
Wert zurückzusetzen. Hierzu wird die Anzahl der Nachkommen pro
Generation auf die geänderte Elternzahl angepasst. Unter Umständen
ist es jedoch wünschenswert, den Selektionsdruck nicht konstant zu
halten, sondern die Erhöhung des Selektionsdrucks durch die
Populationsvergrößerung gezielt dafür einzusetzen, dass das
Suchverhalten  einen explorativeren Charakter bekommt. Der
allgemein bekannte Eigenschaft kontinuierlicher
Evolutionsstrategien im Laufe des Optimierungsprozesses unter
Umständen zu schnell von einer Breitensuche zur einer Tiefensuche
überzugehen, wird hierdurch entgegengewirkt.


\section{Adaptive Diskretisierung des Suchraums}
Die bisherige statische Diskretisierung des Suchraums basierend
auf einer festen Rasterweite wird im Folgenden durch einen
Mechanismus zur Adaption der Rasterweite erweitert. Hierzu werden
nach einer einleitenden Motivation zur Einführung adaptiv
diskretisierter Suchräume entsprechende Strategien und Maßnahmen
zur Implementierung beschrieben.

\subsection{Motivation adaptiv diskretisierter Suchräume}
Ein zentrales Problem bei der bisher beschriebenen diskretisierten
Evolutionsstrategie ist eine geeignete Wahl der Rasterweite. Dies
ist ähnlich gelagert wie das Problem der Wahl einer günstigen
Schrittweite bis \Schwefel{} \cite{Sch77} die adaptive
Schrittweitenanpassung entwickelte. Eine konstante Rasterweite
während des gesamten Optimierungsdurchlaufs bringt Nachteile
bezüglich der Performance (Schnelligkeit des
Optimierungsvortschritts) oder bezüglich der Genauigkeit der
gefundenen Lösung. Eine sehr ungünstig gewählte Rasterweite kann
auch bei beiden Kriterien  zu deutlich schlechteren Ergebnissen
führen. Sowohl grobe als auch sehr feine Rasterweiten lassen sich
jeweils nur bezüglich eines der Kriterien rechtfertigen.

Daher wird im Folgenden ein Mechanismus eingeführt, der die
Rasterweite vergröbert und verfeinert. Dies führt zu einem Gewinn
an Performance und der Anwender wird von der Wahl einer geeigneten
festen Rasterweite befreit. Stattdessen wählt er nur eine obere
und untere Schwelle, zwischen denen der Adaptionsmechanismus die
Rasterweite variiert. Der obere Schwellwert der Rasterweite wird
abhängig von der Dimensionszahl des Optimierungsproblems gewählt.
In einem zweidimensionalen Testproblem hat sich ein Wert von etwa
$1/10$ bewährt. Die untere Schwellwert ist in Abhängigkeit der
gewünschten Genauigkeit bzw. der erwarteten Robustheit zu wählen.

Man kann die Rasteradaption als ein Analogon zur Methode der
Finiten Elemente auffassen. Dort wird das zu berechnende Objekt
z.~B. für eine Feldberechnung mit einem Gitterpunktenetz überzogen
und innerhalb der Netzmaschen das Feld bestimmt. Ausschließlich in
den Gebieten mit einer starken Feldänderung wird dieses Gitter
sukzessive verfeinert. Würde das Gitter auch in Gebieten mit
geringer Feldänderung verfeinert, stiege der Rechenaufwand, ohne
dass sich die Genauigkeit des Ergebnisses dort verbessern würde.

Eine Übertragung dieses Mechanismus zur Schaffung einer adaptiv
diskretisierten Evolutionsstrategie in völlig anderer Form, dass
nämlich das Raster nur an bestimmten Stellen verfeinert wird,
bringt allerdings keinen Vorteil in Bezug auf die Rechenleistung.
Eine Rasterverfeinerung bei diskretisierten Suchräumen bedeutet ja
nur, dass die Individuen in einem Gebiet mehr Möglichkeiten zur
Besetzung eines Gitterpunktes erhalten. Es muss jedoch nicht ein
Individuum an all diesen Position entstehen, so dass dadurch auch
keine zusätzliche Fitnessauswertung und damit einhergehender
zusätzlicher Rechenaufwand entsteht. Zudem ist das Erstellen und
Verwalten eines Gitters mit verschiedenen Rasterweiten in
verschiedenen Bereichen sehr aufwändig. Deshalb wird die
Rasteradaption in anderer Weise eingeführt.


\subsection{Adaption der Suchraumdiskretisierung durch Gitterebenen}
Der andersgearteter Ansatz für die adaptive Diskretisierung von
Evolutionsstrategien basiert auf der Einführung einer Schar
mehrerer parallel existierender Raster unterschiedlicher Teilung,
den Gitterebenen. Ein Individuum befindet sich immer auf einer
dieser Ebenen. Durch die Rekombination oder die Mutation wird ein
Individuum erzeugt, das sich auf einer anderen Ebene befinden kann
als das Ursprungsindividuum. Durch die verschiedenen Rasterweiten
der Ebenen resultiert der Schritt eines Individuums mit einer
bestimmten Schrittweite   in einer vollkommen anderen Position je
nachdem, auf welcher Ebene das Individuum sich befindet. Im
Folgenden wird zuerst das Prinzip der Gitterebenen dargestellt.
Danach folgt die Beschreibung, wie die Individuen andere Ebenen
erreichen.


Die Diskretisierung des Suchraums entlang der Koordinatenachsen
führt zu einem Gitter, das den Parameterraum ausfüllt. Pro
Koordinatenachse können verschiedene Rasterungen vorgenommen
werden. Betrachtet man alle unterschiedlichen Rasterungen entlang
der Koordinatenachsen parallel, entstehen Gitterebenen. Es wird
vorausgesetzt, dass für alle Koordinatenachsen jeweils die gleiche
Anzahl verschiedener Rasterungen existiert. Die Anzahl der
Rasterungen sei $b$. In einem $n$--dimensionalen Suchraum
existieren folglich Gitterebenen.
\begin{figure}[t]  \centering
\ingraph{13}{0}{../Bilder/des/Rasterebenen_schritt}
\caption{\label{chap:E_Abb_Gitterebenen} Gitterebenen bei
symmetrischer Rasterung in allen Dimensionen.}
\end{figure}
In Abbildung \ref{chap:E_Abb_Gitterebenen} ist ein Ausschnitt der
Gitterebenen für ein zweidimensionales vereinfachtes Beispiel
dargestellt. Die Vereinfachung besteht darin, dass die Rasterung
entlang aller Koordinatenachsen gleich angenommen wird, also
symmetrisch ist. In diesem Fall existieren nur $b$ Gitterebenen
parallel. Jeder Schnittpunkt der Gitter- bzw. Randlinien stellt
einen Gitterpunkt dar. Die verschiedenen Rasterungen der
Koordinatenachsen sollten so gewählt werden, dass die daraus
resultierenden Gitterebenen bezüglich der Gitterpunktlage
zueinander kompatibel sind. Seien die Gitterebenen untereinander
derart sortiert, dass der Ebene $i$ eine Ebene $i+1$ folgt, deren
Rasterung entlang aller Koordinatenachsen gleich oder feiner als
in der Ebene $i$ ist und  sei $G_i$ die Menge der Gitterpunkte der
Ebene $i$, so gilt:
\begin{equation}
G_i \subseteq G_j \quad \forall j \in \{i+1, \ldots, b^{n}\}\:.
\end{equation}

Ein Ansatz zur Wahl der verschiedenen Rasterweiten, der die obige
Forderung erfüllt, ist im Folgenden dargestellt. Wird beim
Übergang von der gröbsten Rasterung zur nächstfeineren Rasterung
die Rasterweite $t$ mal geteilt ($t \in \mathbb{N}$), dann muss
der Wert $t$ auch bei allen übrigen Übergängen verwendet werden.
Für die Rasterweite gilt dann:
\begin{equation}
r_{i+1}= \frac {r_i} {t+1}\:.
\end{equation}

In Rahmen dieser Arbeit wird immer $t=1$  gewählt. Dies führt also
bei absolut gleichmäßiger Abdeckung des Suchraums zu einer
Halbierung der Rasterweite innerhalb der Rasterungen.

Die Bedeutung der verschiedenen Gitterebenen wird am folgenden
Beispiel deutlich: Abbildung \ref{chap:E_Abb_Gitterebenen} zeigt,
wie sich ein Schritt bei der Mutation eines Individuums auswirkt,
wenn verschiedene Rasterebenen zugrunde gelegt werden. Angenommen
werden ein zweidimensionaler Parameterraum und eine Auswahl von
fünf Gitterebenen mit symmetrischer Rasterung. Die Rasterweiten
halbieren sich von einer Ebene zur nächsten. Wird nun ein Schritt
um einen Gitterpunkt in jeder Dimension des Parameterraums
ausgeführt, ist leicht ersichtlich, dass je nach Ebene vollkommen
andere Positionen im Parameterraum erreicht werden.



\subsection{Evolutionäre Suche in adaptiv diskretisierten Suchräumen} Für die
Implementierung der durch Gitterebenen adaptiv diskretisierten
Suchräume nach Abbildung
\ref{chap:E_Abb_Ablauf_adativ_diskretisiert} werden die
zugehörigen Rasterweiten $\omega_i$, die ein Individuum aktuell
verwendet, im genetischen Material des Individuums abgelegt.
\begin{figure}[ht]  \centering
\ingraph{15}{0}{../Bilder/des/Ablauf_adativ_diskretisiert}
\caption{\label{chap:E_Abb_Ablauf_adativ_diskretisiert}
Ablaufschema der adaptiv diskretisierten Evolutionsstrategie.}
\end{figure}

Dieser Vektor wird mit $\bar{\Omega}$ bezeichnet. Die einzelnen
Elemente dieses Vektors $\omega_1$  bis $\omega_n$ enthalten
jedoch nicht direkt einen Wert für die Rasterweite, sondern einen
Index, der sich auf den Vektor $\bar{R}$ bezieht, der die realen
Rasterweiten $r_1$ bis $r_b$ der $b$ verschiedenen Rasterungen
entlang der Koordinatenachsen enthält. Die Elemente $\omega_1$ bis
$\omega_n$  werden als reellwertige Zahlen angegeben. Die
Auswertung als Index auf den Vektor $\bar{R}$ erfolgt erst nach
Runden auf einen ganzzahligen Wert. Der gesamte reellwertige
Ausdruck spielt erst bei der Adaption des Vektors $\bar{\Omega}$
eine Rolle. Die Elemente des Vektors können Werte im Bereich $1
\leq \omega_i < b+1$ annehmen.



Sobald ein neues Individuum durch den Mutationsmechanismus erzeugt
wird, stellt sich die Frage, welche Rasterweite in jeder Dimension
zugrunde gelegt werden soll. Im Konzept der Gitterebenen soll
diese Eigenschaft der Individuen ebenfalls durch den Mechanismus
der Evolution selbst eingestellt werden, so dass die Information
über die Rasterweite genauso behandelt wird, wie die Position des
Individuums im Suchraum. Durch die Mutation in Abhängigkeit von
einer bestimmten Schrittweite wird die Position des Individuums
neu festgelegt. Dieser Mechanismus gilt analog für die
Rasterweite. Hierzu wird das genetische Material des Individuums
um einen zweiten Schrittweitensatz erweitert --- die
Rastermutationsschrittweiten  $\sigma_{r,i}$. Zur Einstellung
einer geeigneten Rastermutationsschrittweite wird die von
\Schwefel \cite{Sch77} entwickelte selbstadaptive
Schrittweitenanpassung verwendet (Abschnitt
\ref{chap:B_ES_Schwefel}).

Abbildung \ref{chap:E_Abb_Individuumerweitert} zeigt das
erweiterte genetische Material eines Individuums, das neben den
konventionell vorhandenen Zielvariablen $s_i$ und den
Strategieparametern $\sigma_i$, welche die Position und die
Schrittweiten im Suchraum darstellen, die weiteren
Strategieparametersätze der Rasterweiten $\omega_i$ und der
Rastermutationsschrittweiten $\sigma_{r,i}$ beinhaltet.

\begin{figure}[ht]  \centering
\ingraph{12}{0}{../Bilder/des/Individuumerweitert}
\caption{\label{chap:E_Abb_Individuumerweitert} Individuum mit
erweitertem genetischem Material.}
\end{figure}

Das genetische Material des Individuums besteht nun aus vier
Parametersätzen mit jeweils $n$ Elementen. Die hohe Zahl an
Freiheitsgraden verbessert die Anpassungsfähigkeit der adaptiv
diskretisierten Evolutionsstrategie  an komplexe
Optimierungsprobleme, führt aber auch zu einer Erhöhung des
Suchaufwandes.

Die Rastermutationsschrittweiten werden als reellwertige Zahlen
angegeben. Wenn $b$ die Anzahl der Rasterungen entlang jeder
Koordinatenachse bezeichnet, liegen die
Rastermutationsschrittweiten  $\sigma_{r,i}$ im Bereich

\begin{equation}
\frac {b} {1000} \leq  \sigma_{r,i} \leq  \frac {b} {10} \quad
\text{für}\;\;\;i=1, \dots, n \;.
\end{equation}

Die o.~a. oberen und unteren Schwellwerte wurden entsprechend zum
Verfahren der selbstadaptiven Schrittweitenanpassung angenommen.
Die Mutation des Rastervektors $\bar{\Omega}$  läuft analog zur
Mutation der Problemparameter ab. Äquivalent zum Ansatz zur
selbstadaptiven Schrittweitenanpassung nach \Schwefel{} aus
Gleichung~\ref{equ:schritt_schwefel} werden die
Rastermutationsschrittweiten des Vektors $\Vgr{\sigma}_r$  des zu
mutierenden Individuums gemäß

\begin{equation} \label{eq: Rasterschrittmut}
\sigma_{r,i}^{mut}=\sigma_{r,i} \cdot
e^{N(0,\tau_3)+N_i(0,\tau_4)}\;\;\;\text{für}\;\;\;i=1, \dots, n
\;
\end{equation}

mutiert. Die so erhaltene neue Rastermutationsschrittweite wird
als Standardabweichung für die eigentliche Mutation der
Rasterebenen verwendet. Die darauf folgenden weiteren Schritte
werden analog Kapitel \ref{chap:B_ES_Schwefel} durchgeführt, wobei

\begin{equation}
\tau_3= \tau_1 = \frac{c}{\sqrt{2 \cdot n}}\;, \; \; \; \tau_4=
\tau_2 = \frac{c}{\sqrt{2 \cdot \sqrt{n}}}\; \; \;\text{und} \; \;
\; c=1 \;
\end{equation}

gesetzt werden.


\subsection{Steuerung der adaptiven Suchraumdiskretisierung} In
simulativen Untersuchungen zum beschriebenen Konzept zur adaptiven
Suchraumdiskretisierung zeigte sich, dass die Rasterschrittweiten
nach der Schrittweitenanpassung analog \Schwefel{} \cite{Sch87}
unter Umständen zu schnell zu kleine Werte annehmen. Bei der
Übertragung der selbstadaptiven Schrittweitenanpassung auf die
Rastermutationsschrittweiten sollte dieser Effekt im Interesse
einer ausgewogenen Auswahl der Rasterweiten vermieden werden.

Zur Schaffung einer Eingriffsmöglichkeit zur Ausnutzung aller
Gitterebenen wird zusätzlich eine Wahrscheinlichkeit $p_i$ für
jede einzelne der $b$ Gitterebenen eingeführt, die die
Wahrscheinlichkeit der Verwendung dieser Gitterebene für ein
Individuum angibt. Für den Fall dass jede Gitterebene die
Wahrscheinlichkeit $p_i = \frac {1} {b}$ erhält, ist die
Verwendung aller Gitterebenen gleichwahrscheinlich.

Der Wahrscheinlichkeitsvektor $\Vgr{p}=(p_1, p_2, \ldots,p_b)$
erlaubt eine Steuerung der Rastermutation, hebelt aber den
Mechanismus der selbstadaptiven Anpassung der
Rastermutationsschrittweite nicht aus. Im Interesse einer
verstärkten Breitensuche wird zu Beginn des evolutionären
Optimierungsprozesses zuerst die Suche auf gröberen Gitterebenen
präferiert. Mit zunehmendem Optimierungsfortschritt wird die Suche
dann auf feineren Ebenen fortgesetzt. Mithilfe des eingeführten
Vektors $\Vgr{p}$, der die Auswahlwahrscheinlichkeiten für jede
der $b$ Rasterungen pro Koordinatenachse enthält, wird eine derart
wirkende Steuerung implementiert.

Ein weiterer Nutzen des Wahrscheinlichkeitsvektors  $\Vgr{p}$
liegt in der Steuermöglichkeit der Abdeckung in den einzelnen
Gitterebenen. Für den Fall, dass bezüglich der Maßnahme zur
Diversifizierung der Population eine zunehmend höhere Abdeckung in
einer Gitterebene erzielt wird, wird die Wahrscheinlichkeit für
die entsprechende Rasterung entsprechend herabgesetzt. Die
gröberen Gitterebenen werden ebenfalls derart mit niedrigeren
Wahrscheinlichkeitswerten versehen werden, da gröbere Gitterebenen
immer eine Teilmenge der Gitterpunkte der betrachteten Ebene
enthalten. Details hierzu sind in \cite{Sch02} zu finden.




%%%%%%%%
\section{Effizienzvergleich anhand analytischer Testfunktionen}
\label{chap:E_Testbeispiele} Dieser Abschnitt beschreibt fünf
ausgewählte Testprobleme, die in der Literatur üblicherweise
verwendet werden. Mit Ausnahme der Six--Hump--Funktion sind die
Testfunktionen aller Probleme $n$-dimensional definiert, also als
Optimierungsprobleme mit einstellbarer Komplexität verwendbar. Die
Testprobleme werden in dieser Arbeit zunächst zweidimensional
untersucht, um entsprechende Vorteile und Wirkungsweisen graphisch
zu illustrieren. Zu einigen ausgewählten Testproblemen werden
darüber hinaus hochdimensionale Varianten analysiert. Bei den
ersten vier verwendeten Testfunktionen handelt es sich um skalare
Optimierungsprobleme, das fünfte hingegen ist ein
multikriterielles Optimierungsproblem mit zwei unabhängig
voneinander zu minimierenden Bewertungsfunktionen. Eine große
Auswahl multikriterieller Optimierungsprobleme, die in der
Literatur oft verwendet werden, findet sich in [Veld99]. Dort ist
zu jedem Optimierungsproblem eine Approximation der Pareto--Front
angegeben, so dass eine Einordnung der erzielten Ergebnisse leicht
vorgenommen werden kann.

\subsection{Testfunktionen}

\subsubsection{Six--Hump--Camel--Back--Funktion \cite{DS78}}
\label{sec:shcbf}

Diese Testfunktion wurde von Dixon und Szego vorgeschlagen.
Innerhalb der Bereichsgrenzen befinden sich sechs lokale Minima,
von denen zwei auch globale Minima sind. Die Funktion ist
zweidimensional definiert. Die globalen Minima befinden sich in
den Punkten $\Vx_1=(-0,0898 , 0,7126)$  und  $\Vx_2=(0,0898 ,
-0,7126)$ mit $Q(\Vx_1)=Q(\Vx_2)= -1,0316$. Um einen Funktionswert
von Null im globalen Minimum der Funktion zu erreichen, wird die
Funktion durch Addition des konstanten Wertes $1,0316$ angepasst:
\begin{equation}\label{equ:shcbf_q}
Q(\Vx)=4 \cdot {x_1}^2 - 2,1 \cdot {x_1}^4 + \frac{1}{3} \cdot
{x_1}^6 + x_1 \cdot x_2 - 4 \cdot {x_2}^2 + 4 \cdot {x_2}^4 +
1,0316 \;.
\end{equation}

\begin{figure}[h]
\subfigure[]{
\begin{minipage}[b]{0.5\textwidth}
\centering
%\ingraph{16.5}{0.4}{../Bilder/efs/SchemaRelevanz}
\ingraph{6.8}{0}{../Bilder/des/Six_hump_1}
\end{minipage}}%
\subfigure[]{ \label{yschlange:mean}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{5}{0}{../Bilder/des/Six_hump_2}
\end{minipage}}\\[5pt]
\caption{Testfunktion Six--Hump--Camel--Back, (a): $Q(x_1,x_2)$,
(b): Höhenlinien, d.~h.
   Linien gleicher Funktionswerte $Q(x_1,x_2)$.}
   \label{fig:Six_hump}
\end{figure}

Bei Verwendung dieser Testfunktion werden die Zielvariablen im
folgenden Suchraum optimiert:
\[-2,5 \leq x_1 \leq 2,5 \quad \quad -1,5 \leq x_2 \leq 1,5.\]

Als Fitness-Schwellwert für den Abbruch des Optimierungsprozesses
wird bei dieser Funktion ein Wert von $\rho=10^{-5}$ verwendet.
Aufgrund der Genauigkeit von $10^{-4}$ des additiven Terms
$1,0316$ können bei dieser Funktion auch negative Funktionswerte
erreicht werden, die ebenfalls zum Abbruch des
Optimierungsprozesses führen. Im Allgemeinen wird in der Literatur
als Ziel des Optimierungsprozesses angegeben, mindestens eines
dieser beiden globalen Optima mit der angegebenen Genauigkeit
$\rho$ zu ermitteln. Für die im Rahmen dieser Arbeit vorgestellte
diskretisierte Evolutionsstrategie wird die Anforderung deutlich
verschärft. Der Optimierungsprozess soll beide globalen Minima
ermitteln.  Die Funktion ist in Abbildung \ref{fig:Six_hump}
dargestellt.




\subsubsection{Rastrigin--Funktion \cite{SHF94}} \label{sec:rastrf}

Rastrigins Testfunktion basiert auf einer $n$-dimensional
definierten einfachen quadratischen Funktion, die um einen
Cosinus--Modulationsterm erweitert wurde. Die Funktion ist
multimodal. Die Modulation führt zu einer Vielzahl lokaler Minima.
Das globale Minimum liegt, unabhängig von der gewählten Dimension
$n$, immer im Ursprung:

\begin{equation}\label{equ:rastnf_q}
Q(\Vx)=n \cdot A + \sum_{i=1}^{n} ({x_i}^2 - A \cdot cos (2 \cdot
\pi \cdot x_i)) \;\;\; \text{mit} \;\;\; A=10 \;.
\end{equation}

Für $n=2$ ergibt sich:
\begin{equation}\label{equ:rastzf_q}
Q(\Vx)=20 + ({x_1}^2 - 10 \cdot cos (2 \cdot \pi \cdot
x_1))+({x_2}^2 - 10 \cdot cos (2 \cdot \pi \cdot x_2))\;.
\end{equation}

\begin{figure}[h]
\subfigure[]{
\begin{minipage}[b]{0.5\textwidth}
\centering
%\ingraph{16.5}{0.4}{../Bilder/efs/SchemaRelevanz}
\ingraph{7.7}{0}{../Bilder/des/Rastrigin_1.eps}
\end{minipage}}%
\subfigure[]{ \label{yschlange:mean}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{6}{0}{../Bilder/des/Rastrigin_2.eps}
\end{minipage}}\\[5pt]
   \caption{Testfunktion Rastrigin bei Verwendung zweier Eingangsgrößen $x_1$ und $x_2$,
   (a): $Q(x_1,x_2)$, (b): Höhenlinien, d.~h.
   Linien gleicher Funktionswerte $Q(x_1,x_2)$.}
   \label{fig:Rastrigin}
\end{figure}
Der Suchraum wird dabei in folgendem Bereich festgelegt:
\[-5,12 \leq x_i \leq 5,12  \;\;\; \text{für} \;\;\; i=1,\dots,n.\]

Als Schwellwert für den Abbruch des Optimierungsprozesses wird bei
dieser Funktion ebenfalls ein Wert von $\rho=10^{-5}$ verwendet.
Abbildung \ref{fig:Rastrigin} illustriert die Schwierigkeit des
Optimierungsproblems für $n=2$.



\subsubsection{Rosenbrock--Funktion  \cite{Poh00}} \label{sec:rosf}
Die Rosenbrock--Funktion \cite{Ros60} ist in der Literatur sehr
weit verbreitet. Aufgrund ihrer optischen Eigenschaften wird sie
dort oft als \emph{banana function} bezeichnet. Es handelt sich um
eine unimodale bi--quadratische Funktion, die $n$-dimensional
definiert ist. Obwohl diese Funktion keine lokalen Minima hat, ist
es wesentlich schwieriger, das globale Minimum, zu finden als bei
der Testfunktion von Rastrigin oder der Six--Hump--Funktion. Dies
liegt an einem schmalen parabelförmigen Tal mit steil ansteigenden
Rändern, das einen sehr flachen Boden hat.

\begin{figure}[h]
\subfigure[]{
\begin{minipage}[b]{0.5\textwidth}
\centering
%\ingraph{16.5}{0.4}{../Bilder/efs/SchemaRelevanz}
\ingraph{6.8}{0}{../Bilder/des/Rosenbrock_1.eps}
\end{minipage}}%
\subfigure[]{ \label{yschlange:mean}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{5}{0}{../Bilder/des/Rosenbrock_2.eps}
\end{minipage}}\\[5pt]
   \caption{Testfunktion Rosenbrock bei Verwendung zweier Eingangsgrößen $x_1$ und $x_2$,
   (a): $Q(x_1,x_2)$, (b): Höhenlinien, d.~h.
   Linien gleicher Funktionswerte $Q(x_1,x_2)$.}
   \label{fig:Rosenbrock}
\end{figure}

Während das Auffinden des Tales an sich trivial ist, gestaltet
sich die Konvergenz gegen das globale Minimum sehr schwierig, da
der Gradient innerhalb des Tales extrem schwach abfällt, welches
zudem auch noch diagonal zu den Koordinatenachsen verläuft:
\begin{equation}\label{equ:rosnf_q}
Q(\Vx)=\sum_{i=1}^{n-1} (100 \cdot ({x_i}^2 - x_{i+1})^2 +
(1-x_i)^2)\;.
\end{equation}

Der Suchraum wird dabei in folgendem Bereich festgelegt:
\[-2.048 \leq x_i \leq 2.048  \;\;\; \text{für} \;\;\;
i=1,\dots,n\;.\]

Als Schwellwert für den Abbruch des Optimierungsprozesses wird
auch bei dieser Funktion ein Wert von $\rho=10^{-5}$ verwendet.
Die Funktion ist in Abbildung \ref{fig:Rosenbrock} für $n=2$
dargestellt.




\subsubsection{Schwefel--Funktion  \cite{SHF94}} \label{sec:schwf}
\Schwefel{} hat die schwierigste Testfunktion im Rahmen der hier
betrachteten Probleme vorgeschlagen. Seine Funktion ist ebenfalls
$n$-dimensional definiert. Sie ist multimodal und besitzt sehr
viele lokale Minima sowie ein globales Minimum für
$\breve{x}_i=420,9687$ für $i=1,\ldots,n$ mit
$Q(\breve{\Vx})=-837,9658 \cdot \frac {n} {2}$:
\begin{equation}\label{equ:schwnf_q}
Q(\Vx)=\sum_{i=1}^{n} (-x_i \cdot sin(\sqrt{|x_i|}))\;.
\end{equation}
\begin{figure}[h]
\subfigure[]{
\begin{minipage}[b]{0.5\textwidth}
\centering
%\ingraph{16.5}{0.4}{../Bilder/efs/SchemaRelevanz}
\ingraph{7.7}{0}{../Bilder/des/Schwefel_1.eps}
\end{minipage}}%
\subfigure[]{ \label{yschlange:mean}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{5.8}{0}{../Bilder/des/Schwefel_2.eps}
\end{minipage}}\\[5pt]
   \caption{Testfunktion nach Schwefel bei Verwendung zweier Eingangsgrößen $x_1$ und $x_2$,
   (a): $Q(x_1,x_2)$, (b): Höhenlinien, d.~h.
   Linien gleicher Funktionswerte $Q(x_1,x_2)$.}
   \label{fig:Schw}
\end{figure}

Um einen minimalen Funktionswert bei Null zu erhalten, wird die
Funktion in dieser Arbeit durch Addition des konstanten Wertes
$-837,9658$ für die Abbruchbedingung $10^{-6}$ angepasst.  Für
$n=2$ ergibt sich entsprechend
\begin{equation}\label{equ:schwzf_q}
Q(\Vx)=-837,9658 -{x_1} \cdot sin (\sqrt{|x_1|}) -{x_2} \cdot sin
(\sqrt{|x_2|})\;.
\end{equation}

Die einzustellenden Zielvariablen werden in folgendem Suchbereich
variiert:
\[-500 \leq x_i \leq 500  \;\;\; \text{für} \;\;\; i=1,\dots,n\;.\]


Diese Testfunktion gehört zu einer Gruppe von \glqq boshaften\grqq
Testfunktionen, die ausschließlich dazu konzipiert sind, Schwächen
von Optimierungsverfahren zu offenbaren. Viele
Optimierungsverfahren konvergieren daher in der Regel vorzeitig
gegen ein lokales Minimum dieser Funktion.


\subsubsection{Kursawe--Funktion} \label{sec:kursf}
Diese Testfunktion beinhaltet als multikriterielles
Optimierungsproblem zwei zu minimierende Fitnessfunktionen:
\begin{equation}\label{equ:kursw1_q}
Q_1(\Vx)=\sum_{i=1}^{n-1} -10 \cdot e ^{-0,2 \cdot \sqrt{x_i^2 +
w_{i+1}^2}}\;
\end{equation}
und
\begin{equation}\label{equ:kursw1_q}
Q_2(\Vx)=\sum_{i=1}^{n} |x_i|^{0,8} +5 \cdot sin ^{3}(x_i)\;.
\end{equation}
\begin{figure}[ht]
\subfigure[]{
\begin{minipage}[b]{0.5\textwidth}
\centering
%\ingraph{16.5}{0.4}{../Bilder/efs/SchemaRelevanz}
\ingraph{6.8}{0}{../Bilder/des/Kursawe1.eps}
\end{minipage}}%
\subfigure[]{ \label{yschlange:mean}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{6.8}{0}{../Bilder/des/Kursawe2.eps}
\end{minipage}}\\[5pt]
   \caption{Höhenlinien der Testfunktion nach Kursawe bei Verwendung zweier Eingangsgrößen $x_1$ und $x_2$,
   (a): $Q_1(x_1,x_2)$, (b): $Q_2(x_1,x_2)$.}
   \label{fig:kursaw}
\end{figure}

Die einzustellenden Zielvariablen werden in folgendem Suchbereich
variiert:
\[-5 \leq x_i \leq 5  \;\;\; \text{für} \;\;\; i=1,\dots,n\;.\]

Die Funktion $Q_1$ hat ihr globales Minimum bei $\breve{x}_i=0$
für $i=1,\ldots,n$ mit $Q_1(\breve{\Vx})=-10$. Das globale Minimum
der Funktion $Q_2$ liegt bei $\breve{x}_i=-1,5216$ für
$i=1,\ldots,n$ mit $Q_2(\breve{\Vx})=-7,1656$. In Abbildung
\ref{fig:kursaw} sind die Höhenlinien beider Funktionen
dargestellt.


Aufgrund der unterschiedlichen Lage der minimalen Funktionswerte
für $Q_1$ und $Q_2$ im Parameterraum gibt es keine einzelne
optimale Lösung, sondern es entsteht eine pareto--optimale
Lösungsmenge. In Abbildung \ref{fig:kursawpareto} ist eine aus der
Literatur bekannte Approximation der Pareto--Menge dargestellt.

\begin{figure}[h]  \centering
\ingraph{8.5}{0}{../Bilder/des/KursawePareto.eps}
\caption{\label{fig:kursawpareto} Approximation der Pareto--Front
für Kursawes Testfunktion.}
\end{figure}

\subsection{Bewertungskriterien}

Im Folgenden werden wesentliche Kriterien beschrieben, die zur
Bewertung der Effizienz der verschiedenen getesteten
Evolutionsstrategien  herangezogen werden können.

\subsubsection{Anzahl der Fitnessfunktionsauswertungen} Ein sehr
wichtiges und zugleich sehr einfaches Bewertungskriterium ist das
Zählen der Fitnessfunktionsaufrufe. Um ein vergleichbares Maß über
die Dauer der Suche eines Optimierungsdurchlaufs zu erhalten, ist
es nicht sinnvoll, die Generationen zu zählen, nach denen das
Optimum gefunden wurde. Diese Zahl wird stark beeinflusst von der
Größe der Population, der Zahl der Nachkommen, der Zahl der
Mutanten pro Nachkommen und weiteren Faktoren. Eine verlässlichere
Aussage kann über das Zählen der Fitnessauswertungen getroffen
werden. Bei der Optimierung eines technischen Problems ist die
Fitnessfunktion in der Regel nicht bekannt. Die Fitness wird durch
das Verhalten des technischen Systems auf die optimierten
Parameter bestimmt. Dieser Vorgang dauert in der Regel länger als
die Auswertung einer explizit gegebenen Funktion. Daher ist die
Anzahl von Fitnessauswertungen, die zum Finden des Optimums
notwendig sind, eine wichtige Größe bei der Bewertung von
Optimierungsverfahren. Üblicherweise zieht man sie als wichtigstes
Bewertungskriterium heran, was sinnvoll ist, wie folgendes
Beispiel zeigt: Hat ein Optimierungsverfahren den Suchraum sehr
gleichmäßig und breit abgesucht, ist dies nur dann als positiv zu
werten, falls dafür nicht um ein Vielfaches mehr
Fitnessfunktionsaufrufe durchgeführt wurden als bei einem anderen
Optimierungsverfahren.


\subsubsection{Entfernungen zu allen lokalen Minima} Dieses
Bewertungskriterium bewertet den Abstand der im Suchraum
\glqq{}erforschten\grqq{} Punkte zu den lokalen und globalen
Minima. Dieses Maß ist sehr gut zur Effizienzbewertung der
Suchraumabdeckung durch das Optimierungsverfahren geeignet.
Allerdings kann es nur bei Optimierungsproblemen verwendet werden,
bei denen die Lage aller Minima bekannt ist. Dies ist nur bei den
hier vorgestellten analytischen Testproblemen gegeben. Doch trotz
dieser Einschränkung der Allgemeinheit ist das Maß ein geeignetes
Mittel zur Beurteilung des Suchverhaltens von
Optimierungsverfahren. Im Folgenden werden die Einzelheiten der
Bewertung erläutert. Aus der Menge aller aufgezeichneten
Fitnessfunktionsaufrufe eines vollständigen Optimierungsverlaufs
wird zu jedem Minimum derjenige ausgewählt, der minimalen Abstand
zu diesem besitzt. Die Abstandswerte $d_i$ werden gemäß
\begin{equation}\label{equ:gewAbst}
d'_i= e^{\lambda \cdot d'_i }\;
\end{equation}
nichtlinear umskaliert, wobei $\lambda$  problemabhängig gewählt
wird. Zusätzlich wird eine Gewichtung nach der Fitness der Minima
vorgenommen. Das globale Minimum erhält das höchste Gewicht, alle
anderen Minima erhalten linearverteilt schwächere Gewichte.

\begin{figure}[h]  \centering
\ingraph{6}{0}{../Bilder/des/BewertAbstand.eps}
\caption{\label{chap E:pic_Abstande} Abstandsbestimmung an einer
Beispielfunktion.}
\end{figure}

Schließlich wird das Verhältnis zwischen der Summe der gewichteten
umskalierten Abstandswerte und der Summe der Werte für einen
Fitnessfunktionsaufruf in jedem Minimum gebildet. In der folgenden
Gleichung wird $g_i$ als umskalierter Fitnesswert des $i$-ten
Minimums und $d'_i$ als kleinster gewichteter Abstand eines
Fitnessfunktionsaufrufs zu diesem Minimum gewählt.


Für $n$ Minima gilt:
\begin{equation}\label{equ:gewAbst}
C_e= \frac {\sum_{i=1}^{n} g_i \cdot d'_i} {\sum_{i=1}^{n} g_i}\;
\end{equation}
Das Ergebnis der Bewertung $C_e$  wird den Wert 1 annehmen, wenn
genau in jedem Minimum eine Fitnessfunktionsauswertung
durchgeführt wurde. Abbildung \ref{chap E:pic_Abstande} zeigt ein
Beispiel im zweidimensionalen Raum. Die Orte der
Fitnessfunktionsauswertungen sind durch Punkte gekennzeichnet. Die
Abstände der ausgewählten Punkte zu den Minima sind durch
Verbindungslinien dargestellt. \pagebreak


\subsection{Ergebnisse}

Dieser Abschnitt präsentiert die Ergebnisse, die bei simulativen
Untersuchungen an den Testproblemen zu verschiedenen
Fragestellungen erzielt wurden. Abschließend erfolgt eine
Interpretation der vorgestellten Ergebnisse.


\subsubsection{Effizienz zweidimensional}
\begin{figure}[ht]
\subfigure[\textsl{Six-Hump}]{ \label{sixhump2d}
\begin{minipage}[b]{0.5\textwidth}
\centering
%\ingraph{16.5}{0.4}{../Bilder/efs/SchemaRelevanz}
\ingraph{6}{0}{../Bilder/des/sixhump2d.eps}
\end{minipage}}%
\subfigure[\textsl{Rastrigin}]{ \label{rastrigin2d}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{6}{0}{../Bilder/des/rastrigin2d.eps}
\end{minipage}}\\[0pt]
\subfigure[\textsl{ Rosenbrock}]{ \label{rosenbrock2d}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{6}{0}{../Bilder/des/rosenbrock2d.eps}
\end{minipage}}
\subfigure[\textsl{ Schwefel}]{ \label{schwefel2d}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{6}{0}{../Bilder/des/schwefel2d.eps}
\end{minipage}}
\caption{Vergleich der Effizienz der Varianten $ES$,
 $DES^{stat}$ und $DES^{adap}$ anhand zweidimensionaler
Testfunktionen.\label{erg2d}}
\end{figure}
Die Ergebnisse dieser Untersuchung untermauern die Erwartungen in
Bezug auf die Effizienzsteigerung.  In Abbildung \ref{erg2d}  ist
die Anzahl der Fitnessfunktionsaufrufe bis zum Erreichen des
Minimums der vorgestellten skalaren Testfunktionen mit aktivierter
Populationsdiversifizierung für die Standard--Evolutionsstrategie
$ES$, der statisch diskretisierten Variante $DES^{stat}$ sowie der
adaptiv diskretisierten Variante $DES^{adap}$ dargestellt. Dabei
sind die jeweils benötigte Anzahl von Funktionsaufrufen zur
Ermittlung des Optimums im zweidimensionalen Suchraum von $1000$
Optimierungsdurchläufen der Testfunktionen in Boxplots für die
drei Varianten dargestellt. Die Anzahl der Elternindividuen wurde
dabei jeweils auf $15$ und die der Nachkommen auf $100$
eingestellt. In jeweils einem der $1000$ Durchläufe wurde zur
Erhaltung der Vergleichbarkeit die gleiche Startpopulation für die
getesteten Varianten der Evolutionsstrategie verwendet. Die
Startpopulation ist immer  im vollständigen Suchraum zufällig
verteilt erzeugt worden. Die statisch diskretisierte
Evolutionsstrategie $DES^{stat}$ wurde mit einer Rasterweite von
$0,001$ durchgeführt. Die Grenzwerte der Rasterweiten im Fall der
adaptiv diskretisierten Evolutionsstrategie $DES^{adap}$ wurden
auf $0,0008$ und $0,01$ festgelegt.



\subsubsection{Effizienz $24$-dimensional}
In analoger Weise sind in Anlehnung an ein industrielles
Anwendungsproblem \cite{NKB01} die entsprechend ausgelegten
analytischen Testfunktionen im $24$-dimensionalen Suchraum
analysiert worden.
\begin{figure}[h]
\subfigure[\textsl{Rastrigin}]{ \label{rastrigin24d}
\begin{minipage}[b]{0.32\textwidth}
\centering \ingraph{5.3}{0}{../Bilder/des/rastrigin24d.eps}
\end{minipage}}%\\[5pt]
\subfigure[\textsl{ Rosenbrock}]{ \label{rosenbrock24d}
\begin{minipage}[b]{0.32\textwidth}
\centering \ingraph{5.3}{0}{../Bilder/des/rosenbrock24d.eps}
\end{minipage}}
\subfigure[\textsl{ Schwefel}]{ \label{schwefel24d}
\begin{minipage}[b]{0.32\textwidth}
\centering \ingraph{5.3}{0}{../Bilder/des/schwefel24d.eps}
\end{minipage}}
\caption{Vergleich der Effizienz der Varianten $ES$,
 $DES^{stat}$ und $DES^{adap}$ anhand 24--dimensionaler
Testfunktionen.\label{erg24d}}
\end{figure}

Jeder einzelne der $1000$ Testläufe ist zur Erhaltung der
Vergleichbarkeit wie vorher mit gleicher Startpopulation für die
getesteten Varianten $ES$, $DES^{stat}$ und $DES^{adap}$
durchgeführt worden. In Abbildung \ref{erg24d} sind in Boxplots
die Fitnesswerte $Q(\Ind_{end}^{best})$ des jeweils besten
Individuums eines Optimierungsdurchlaufs dargestellt, wobei jeder
Optimierungsdurchlauf nach $10000$ Fitnessauswertungen abgebrochen
wurde.

\subsubsection{Effizienz multikriteriell}
In diesem Abschnitt wird ein Vergleich der adaptiv diskretisierten
Evolutionsstrategie $DES^{adap}$ und der kontinuierlichen
Evolutionsstrategie $ES$ anhand des multikriteriellen Testproblems
von Kursawe im dreidimensionalen Suchraum vorgenommen. Die
Effizienz der Varianten zeigt sich in der Approximationsgüte, mit
der die Pareto--Front des Testproblems nach $2000$
Fitnessfunktionsaufrufen in zwei exemplarischen
Optimierungsdurchläufen dargestellt wird.
\begin{figure}[h]  \centering
\ingraph{16}{0}{../Bilder/des/VergleichParetoFronten.eps}
\caption{\label{ergpareto} Gegenüberstellung der erzielten
Approximationen der Pareto-Front.}
\end{figure}

Für diesen Fall wird ein qualitativer Vergleich gemäß Abbildung
\ref{ergpareto} vorgenommen, worin die erzielte Approximation der
Pareto--Front durch die adaptiv diskretisierte Evolutionsstrategie
$DES^{adap}$ im linken Diagramm der Approximation durch die
kontinuierliche Variante $ES$ im rechten Diagramm
gegenübergestellt wird. Es ist leicht ersichtlich, dass die
Approximation durch die adaptiv diskretisierte Evolutionsstrategie
Vorteile sowohl in der Gleichmäßigkeit der Verteilung als auch in
den Fitnesswerten der einzelnen Pareto--Punkte bietet.

\subsubsection{Gleichmäßigkeit der Abdeckung des Suchraums}
Die Ergebnisse dieser Untersuchung zeigen die Gleichmäßigkeit mit
der die Varianten $ES$ und $DES^{adap}$ den Suchraum abgesucht
haben. Abbildung \ref{fig:ergabd} zeigt die Orte der
Fitnessauswertungen für einen exemplarischen Optimierungsdurchlauf
mit der gleichen Startpopulation in beiden Fällen. Es ist leicht
ersichtlich, dass die Fitnessfunktionsauswertungen der adaptiv
diskretisierten Evolutionsstrategie $DES^{adap}$ wesentlich
gleichmäßiger über den Parameterraum verteilt sind. Durch die
bessere Verteilung im Parameterraum erreicht die adaptiv
diskretisierte Variante auch bei der Bewertung der Entfernung der
zu den lokalen Minima jeweils nächsten durchgeführten
Fitnessauswertungen einen besseren Wert.
\begin{figure}[ht]
\subfigure[]{
\begin{minipage}[b]{0.5\textwidth}
\centering
%\ingraph{16.5}{0.4}{../Bilder/efs/SchemaRelevanz}
\ingraph{6.8}{0}{../Bilder/des/AbdSchwefel_disk.eps}
\end{minipage}}%
\subfigure[]{ \label{abdschw_}
\begin{minipage}[b]{0.5\textwidth}
\centering \ingraph{6.8}{0}{../Bilder/des/AbdSchwefel_cont3.eps}
\end{minipage}}\\[5pt]
   \caption{Illustration der erzielten Abdeckung im zweidimensionalen
   Suchraum, \quad \quad \quad
   (a): $DES^{adap}$ erreicht Optimum nach $975$ Fitnessauswertungen,
   (b): $ES$ erreicht Optimum nach $2361$ Fitnessauswertungen.}
   \label{fig:ergabd}
\end{figure}




\subsubsection{Schlussfolgerungen}
Die vorgestellten Untersuchungsergebnisse  bestätigen, dass die
diskretisierten Evolutionsstrategien der kontinuierlichen Variante
in Bezug auf die Effizienz sowohl in nieder- als auch in
hochdimensionalen Suchräumen überlegen sind. Dies bedeutet, dass
sie entweder das gleiche Ziel mit weniger Aufwand oder mit
gleichem Aufwand einen besseren Fitnessendwert erreichen.

Im Fall der multikriteriellen Optimierungsprobleme zeigt sich
zudem, dass bei gleichem Aufwand in Form der Anzahl von
Fitnessfunktionsaufrufen durch die adaptiv diskretisierte
Evolutionsstrategie eine bessere Approximation der Pareto--Front
erreicht wird.

Die Gleichmäßigkeit der Abdeckung des Suchraums ist wesentlich
höher, wenn eine diskretisierte Evolutionsstrategie verwendet
wird. Damit steigt die Wahrscheinlichkeit, weitere und unter
Umständen bessere Optima der Fitnessfunktion zu finden. Darüber
hinaus ergibt sich, dass der Aufwand für die Adaption der
Diskretisierung einen Vorteil der adaptiv diskretisierten
Evolutionsstrategie gegenüber der statisch diskretisierten
Variante bei niederdimensionalen Optimierungsproblemen verhindert.
Ein plausibler Grund dafür ist, dass die feste Rasterweite bei der
statisch diskretisierten Evolutionsstrategie im Laufe der Zeit
empirisch auf einen sehr günstigen Wert eingestellt wurde. Da ein
großer Aufwand für das Finden einer geeigneten Rasterweite in der
Regel nicht betrieben wird, relativiert sich die vorherige
Aussage. Bei höherdimensionalen Problemen ergibt sich zudem
ohnehin ein deutlich erkennbarer Effizienzvorteil für die adaptiv
diskretisierte Variante.


%
%----------------------------------------------------
% Ende von implicit.tex
