%--------------------------------------------
%
% basics.tex
% enthält die Grundlagen
%
%----------------------------------------------------------------
%
\chapter{Methodische Grundlagen}
\label{chap:B_fuzzy}
% chapter B


In diesem Kapitel wird auf die wesentlichen methodischen
Grundlagen eingegangen, die inhaltlich für diese Arbeit einen
zentralen Stellenwert einnehmen.

Für die Grundlagen zur datenbasierten Fuzzy--Modellierung wird
zunächst dabei in Abschnitt \ref{sec:B_logik} eine kurze
Einführung in die von \Zadeh{} im Jahre $1965$ eingeführte
Fuzzy--Logik gegeben. Die darauf basierenden gängigsten Typen von
Fuzzy--Systeme werden in Abschnitt \ref{sec:B_systeme}
beschrieben. Diese Ausführungen sind dabei an \cite{Kie97a}
angelehnt, da für die zentralen Aspekte dieser Arbeit eine
anwendungsorientierte Betrachtungsweise von größerer Bedeutung
ist. Die verwendeten Bezeichnungen richten sich zudem streng nach
den in \cite{MBC99} aufgestellten VDI/VDE--Richtlinien $3550$
\glqq{\em Fuzzy--Logik und Fuzzy--Control --- Begriffe und
Definitionen}\grqq{}.

Schließend wird in Abschnitt \ref{sec:B_rosa} das hier verwendete
Fuzzy--ROSA--Verfahren zur datenbasierten Generierung von
Fuzzy--Systemen kurz vorgestellt sowie die detektierten
Ansatzpunkte zur Effizienzsteigerung  der datenbasierten
Fuzzy--Modellierung durch die im Rahmen dieser Arbeit zu
entwickelnden Methoden herausgearbeitet.

Anschließend werden die Grundlagen für diese neuen methodischen
Ansätze für den Bereich der Merkmalsselektion in Abschnitt
\ref{chap:B_Merkmalselekt} und für das Gebiet der
Evolutionsstrategien in Abschnitt \ref{chap:B_ES} eingeführt.


\section{Fuzzy--Logik}
\label{sec:B_logik} Die in \cite{Zad65,Zad68} eingeführte
Fuzzy--Logik basiert auf der Verwendung von Fuzzy--Mengen, die aus
geordneten Wertepaaren
\begin{equation}
\label{eq:B_menge} \s=\{\x,\msf_\s(\x)\}\;\quad \mbox{mit } \x\in
\mathcal{U} \quad \mbox{und } \msf_\s(\x)\in [0,1]
\end{equation}
bestehen. Dabei repräsentiert $\x$ ein Element des betrachteten
Universums $\mathcal U$, dessen Zugehörigkeit zur (unscharfen)
Fuzzy--Menge $\s$ durch den Zugehörigkeitsgrad $\msf_\s(\x)$
spezifiziert wird. Die in dieser Arbeit betrachteten Ereignisse
$\x$ beinhalten immer die numerischen (scharfen) Werte $\x$ einer
Eingangsvariablen $\X$, so dass das Universum $\mathcal U$ (auch
{\dfc Grundbereich} genannt) mit der Menge $\Ree$ der reellen
Zahlen gleichgesetzt werden kann. Im Gegensatz zur booleschen
Logik, bei der ein Element $\x$ ausschließlich mit den
Wahrheitswerten $\msf_{\it bool}(\x)=1$ (\textit{wahr}) oder
$\msf_{\it bool}(\x)=0$ (\textit{falsch}) zu einer Menge zugehörig
sein kann, verwendet die Fuzzy--Logik somit auch Zwischenwerte aus
dem Intervall $[0,1]$ zur Spezifizierung einer (unscharfen)
Zugehörigkeit. Die wesentlichen Kenngrößen und Eigenschaften von
Fuzzy--Mengen und Zugehörigkeitsfunktionen sind im
Anhang~\ref{chap:A_A} aufgeführt.

Zur Ermöglichung logischer Verknüpfungen von Fuzzy--Mengen wurden
die aus der Booleschen Logik bekannten Operatoren {\em UND}, {\em
ODER} und {\em NICHT} durch verschiedene arithmetische Beziehungen
zu Fuzzy--Operatoren so verallgemeinert, dass für den Fall von
Booleschen Operanden das Ergebnis der Verknüpfung dem der
Verwendung der klassischen Booleschen Operatoren entspricht. Es
gibt unterschiedliche Möglichkeiten für die Definition von
Fuzzy--Operatoren die dieser Forderung entsprechen. Die
gebräuchlichsten Fuzzy--Operatoren sind in Tabelle
\ref{tab:fuzzyOps} zu finden.

\begin{table}[!ht]
\begin{center} {
\caption{\label{tab:fuzzyOps} Arithmetische Realisierungen von
Fuzzy--Operatoren} \vspace{0.3cm}
\begin{tabular}{|c|l|rl|l|}
\hline Symbol         &  Operator        &
\multicolumn{2}{|c|}{Definition} & Bezeichnung \\ \hline\hline
$\neg$         &  Fuzzy--NICHT    & $\neg \msf_\s\;:=$           &
$1-\msf_\s$                                &             \\ \hline
               &                  & $\msf_{\s_1} \wedge \msf_{\s_2}\; :=$ & $\msf_{\s_1} \cdot \msf_{\s_2}$       & Algebraisches Produkt \\
$\wedge$       &  Fuzzy--UND      & $\msf_{\s_1} \wedge \msf_{\s_2}\; :=$ & $\min\{\msf_{\s_1},\msf_{\s_2}\}$     & Minimum      \\
               &                  & $\msf_{\s_1} \wedge \msf_{\s_2}\; :=$ & $\max\{0,\msf_{\s_1}+\msf_{\s_2}-1\}$ & Beschränkte Differenz \\
\hline
               &                  & $\msf_{\s_1} \vee \msf_{\s_2}\; := $  & $\msf_{\s_1}+\msf_{\s_2}-\msf_{\s_1}\cdot\msf_{\s_2}$ & Algebraische Summe\\
  $\vee$       &   Fuzzy--ODER    & $\msf_{\s_1} \vee \msf_{\s_2}\; := $  & $\max\{\msf_{\s_1},\msf_{\s_2}\}$     & Maximum \\
               &                  & $\msf_{\s_1} \vee \msf_{\s_2}\; := $  & $\min\{1,\msf_{\s_1}+\msf_{\s_2}\}$   & Beschränkte Summe\\
\hline
\end{tabular}
}
\end{center}
\end{table}


\section{Fuzzy--Systeme} \label{sec:B_systeme}

Für die Beschreibung der Struktur und der Funktionsweise von
Fuzzy--Systemen bezeichnen im Folgenden $\x_1,\dots,\x_\NV$ die
numerischen (scharfen) Werte der $\NV$ Eingangsvariablen
$\X_1,\dots,\X_\NV$ des Fuzzy--Systems zu einem festen Zeitpunkt,
wodurch genau eine bestimmte Eingangssituation spezifiziert ist.
Entsprechend ist der Ausgangsvariablen $\Y$ der numerische Wert
$\y$ zugeordnet.

Fuzzy--Systeme basieren auf dem in Abschnitt \ref{sec:B_logik}
eingeführten Konzept der Fuzzy--Mengen und beschreiben im
mathematischen Sinne einen funktionalen Zusammenhang
\begin{equation}
f:{\cal\X}\longmapsto\Y\;,\quad \mbox{mit }
{\cal\X}=\X_1\times\dots\times\X_\NV\:.
\end{equation}

\begin{definition}{Fuzzy--System:} Ein Fuzzy--System ist ein System, das linguistische
Regeln verwendet und mit Hilfe der Teilblöcke Fuzzifizierung,
Inferenz und Defuzzifizierung numerische Eingangsgrößen in
numerische Ausgangsgrößen abbildet.
\end{definition}

Im Teilblock der {\dfc Fuzzifizierung} werden dabei zunächst die
Eingangsinformationen $\x_1,\dots,\x_\NV$ auf Fuzzy--Mengen
abgebildet. Diese werden einer Abbildungsvorschrift, die durch
linguistische Regeln der Form $\Regel{\mbox{\em
Prämisse}}{\mbox{\em Konklusion}}$ repräsentiert wird, unterzogen
({\dfc Inferenz}). Als Inferenzergebnis resultiert wiederum eine
Fuzzy--Menge, die letztendlich auf eine reellwertige Größe
abgebildet wird ({\dfc Defuzzifizierung}).

Diese verschiedenen Teilbereiche eines Fuzzy--Systems sowie die
wesentlichsten Definitionen, die zur Berechnung des
Ausgangsgrößenwerts notwendig sind, werden in Abschnitt
\ref{sec:B_mam} exemplarisch an einem Fuzzy--System vom Typ \Mam{}
erläutert, der im Bereich Fuzzy Control und Fuzzy--Modellierung am
weitesten verbreitet ist. Ein daraus weiter entwickelter
funktionaler Typ --- das \TSK--Fuzzy--System
--- mit dem in der Regel unter starker Beeinträchtigung der
Transparenz bei Approximationsproblemen höhere Modellgüten erzielt
werden können, wird im anschließenden Abschnitt \ref{sec:B_tsk}
kurz vorgestellt.

\subsection{Mamdani--Fuzzy--Systeme}
\label{sec:B_mam} Die wesentlichen Module eines Fuzzy--Systems vom
Typ \Mamdani{} \cite{Mam77,MA75} sind zur nachfolgenden
Erläuterung in Abbildung~\ref{fig:B_mam} dargestellt.
\begin{figure}[ht] \centering
\ingraph{11}{0.5}{../Bilder/basics/modell2}
\caption{\label{fig:B_mam}Vereinfachte modulare Struktur eines
\Mam--Fuzzy--Systems.}
\end{figure}

\subsubsection{Fuzzifizierung} Die Eingangsgrößen eines Fuzzy--Systems werden {\dfc
linguistische Variablen} genannt. Deren zu Grunde liegender
Wertebereich wird im Modul der Fuzzifizierung einer unscharfen
Granularisierung, der {\dfc Fuzzy--Partitionierung}, unterzogen.

\begin{definition}{Fuzzy--Partitionierung:}\label{def:B_FuzzPart}
Eine Fuzzy--Partitionierung ist eine Teilung eines
(mehrdimensionalen) Raumes in unscharfe Teilräume, wodurch jeder
Punkt allen Teilräumen zu einem bestimmten Zugehörigkeitsgrad
zugeordnet wird.
\end{definition}

Auf Grundlage von $\Nls_i$ Fuzzy--Partitionen für eine
Eingangsvariable $\X_i$ werden die zugehörigen reellwertigen
scharfen Werte $\x_i$ auf {\dfc linguistische Werte} $\ls_{i,j}$
($j=1,2,\cdots,\Nls_i$) abgebildet.

\begin{definition}{Linguistischer
Wert/Term:} Ein Linguistischer Wert/Term ist eine natursprachliche
Bezeichnung zur Kennzeichnung der Eigenschaften einer Größe. Die
gegenseitige Zuordnung zwischen numerischen und linguistischen
Werten einer Größe erfolgt über Fuzzy--Mengen.
\end{definition}

Die linguistischen Werte ermöglichen die Verarbeitung unscharfer
qualitativer Aussagen der Form {\em \glqq Patient hat hohes
Fieber\grqq} mit Hilfe der Fuzzy--Logik
(Abschnitt~\ref{sec:B_logik}). Die Zuordnung eines numerischen
Wertes $\x_i$ von einer Eingangsvariablen $\X_i$ (z.~B. $\mbox{\em
Temperatur}=41.3\;^oC$) zu einem linguistischen Wert $\ls_{i,5}$
gemäß Abbildung~\ref{fig:B_InfoSys} $\mbox{\em Temperatur}=${\em
\glqq sehr hoch\grqq{}}, erfolgt über {\dfc
Fuzzy--Zugehörigkeitsfunktionen} $\msf_{i,j}(\x_i)$ mit
$j=1,2,\cdots,\Nls_i$.
\begin{figure}[ht] \centering
\ingraph{14}{0}{../Bilder/basics/msf} \caption{\label{fig:B_msf}
Gebräuchliche Formen für Zugehörigkeitsfunktionen $\msf_\s(\x)$}
\end{figure}

\begin{definition}{Fuzzy--Zugehörigkeitsfunktion:} Eine Fuzzy--Zugehörigkeitsfunktion ist
Funktion, die jedem Element $\x$ aus dem im allgemeinen
numerischen Grundbereich --- dem Definitionsbereich --- einen
Zugehörigkeitsgrad $\msf_\s(\x)$ zu einer Fuzzy--Menge $\s$ nach
Gleichung (\ref{eq:B_menge}) zuordnet. Ein Zugehörigkeitsgrad
$\msf_\s(\x)=1$ bedeutet, dass der Wert $\x$ vollständig zur
Fuzzy--Menge $\s$ gehört. Bei $\msf_\s(\x)=0$ gehört $\x$
überhaupt nicht zur Fuzzy--Menge $\s$. Werte zwischen Null und
Eins bedeuten, dass der Wert teilweise zur Fuzzy--Menge $\s$
gehört.
\end{definition}

Die gebräuchlichsten Zugehörigkeitsfunktionen für linguistische
Werte sind dreieckförmig (triangular), trapezförmig,
rechteckförmig oder gaußförmig (Abbildung \ref{fig:B_msf}). Häufig
werden die Zugehörigkeitsfunktionen für jede Eingangsvariable
$\X_i$ derart festgelegt, dass für jeden Wert $\x_i$ des
zugehörigen Definitionsbereichs die Summe aller Zugehörigkeiten
$\msf_{i,j}(\x_i)$ Eins ergibt:
\begin{equation}\label{eq:B_InfoSys}
\sum_{j=1}^{\Nls_i}\msf_{i,j}(\x_i)=1\;.
\end{equation}

\begin{definition}{Standard--Fuzzy--Partitionierung:}
\label{def:standardpart} Gilt für alle Werte $\x$ des
Definitionsbereichs einer linguistischen Variablen $\X$ Gleichung
(\ref{eq:B_InfoSys}) und sind weiterhin alle
Zugehörigkeitsfunktionen der linguistischen Werte normalisiert und
konvex (Anhang~\ref{chap:A_A}), dann wird diese Einteilung
Standard--Fuzzy--Partitionierung oder auch
Fuzzy--Informationssystem genannt.
\end{definition}

Ein Beispiel für eine Standard--Fuzzy--Partitionierung ist in
Abbildung \ref{fig:B_InfoSys} für die Modellierung der
Körpertemperatur eines Menschen dargestellt.
\begin{figure}[h]
\centering \ingraph{10}{0}{../Bilder/basics/InfoSys}
\caption{\label{fig:B_InfoSys} Beispiel für die Festlegung einer
Standard--Fuzzy--Partitionierung.}
\end{figure}

Eine spezielle Form von Zugehörigkeitsfunktionen bilden {\em
Singletons}, die fast ausschließlich als ausgangsseitige
linguistische Werte oder zur eingangsseitigen Modellierung von
Klassen verwendet werden.

\begin{definition}{Singletons:}\label{def:singleton}
Singletons sind Zugehörigkeitsfunktionen, die an genau einer
einzigen Stelle des Definitionsbereichs den Funktionswert Eins und
für alle übrigen Werte des Definitionsbereichs den Wert Null
annehmen.
\end{definition}


Insgesamt werden aber im Modul der Fuzzifizierung alle
Eingangsgrößenwerte $\x_i$ einer gegebenen Eingangssituation
$\Vx^T=(\x_1,\cdots,\x_\NV)$ in Zugehörigkeitsgrade
$\msf_{i,j}(\x_i)$ mit $i=1,2,\cdots,\NV\;$ und
$j=1,2,\cdots,\Nls_i$\; umgewandelt. Für eine konkrete statische
Eingangssituation werden im Folgenden die Werte für
$\msf_{i,j}(\x_i)$ zur Vereinfachung mit $\msf_{i,j}$ abgekürzt.

\subsubsection{Inferenz}
Die Generierung einer ausgangsseitigen Fuzzy--Menge
$\msf_{\Y}(\Vx,\y)$ auf Grundlage der fuzzifizierten
Eingangsgrößenwerte $\Vx$ wird als Inferenz bezeichnet. Sie
basiert auf der Auswertung der {\dfc Regelbasis} $\SR$, die aus
$\NR$ Regeln der Form
\begin{equation} \label{eq:B_MamRegel}
\Regel{\prem_\iR}{\conc_\iR}\;\quad \mbox{mit } \iR=1,2,\cdots,\NR
\end{equation}
besteht. Der so genannte \WENN--Teil enthält die {\em Prämisse}
$\prem_\iR$ der $\iR$--ten Regel, die aus einer oder mehrerer
konjunktiv verknüpfter\footnote{In dieser Arbeit wird die
Betrachtung auf konjunktive Verknüpfungen von Partialprämissen
beschränkt.} Partialprämissen $\LE_{i}$ besteht.

\begin{definition}{Partialprämisse:}\label{def:lingexpr} Eine
Partialprämisse $\LE_i$ ist eine Elementaraussage \glqq$\X_i$ ist
$\ls_{i,j}$\grqq{} $(\X_i=\ls_{i,j})$ in einer Regel, in der nur
eine linguistische Variable $\X_i$ und ein linguistischer Wert
$\ls_{i,j}\;$ vorkommen.
\end{definition}

Eine {\dfc vollständige Regel} $\iR$ verknüpft für jede der $\NV$
Eingangsvariablen des Fuzzy--Systems genau eine Partialprämisse
$\LE_{\iR,i}\;$ gemäß
\begin{equation}
\Regel{\LE_{\iR,{\it 1}}\;\wedge\;\LE_{\iR,{\it 2}} \;\wedge\;
\cdots \;\wedge\; \LE_{\iR,\NV}}{\conc_\iR}\;,
\end{equation}
so dass die Prämisse $\prem_\iR$ durch
\begin{equation}
\prem_\iR=\bigwedge^\NV_{i=1} \LE_{\iR,i}\; = \;
\bigwedge^\NV_{i=1} (\X_i=\ls_{i,l_i}) \quad \mbox{mit }
l_i\in\{1,2,\cdots,\Nls_i\}\;
\end{equation}
definiert wird. Für Fuzzy--Systeme mit vielen Eingangsgrößen
besteht eine Regelbasis häufig aus unvollständigen ({\dfc
generalisierenden}) Regeln. Die {\dfc Kombinationstiefe}
$\;\cd_\iR$ gibt dann die Anzahl der verknüpften Partialprämissen
innerhalb der Premisse $\prem_\iR$ an.

Der \DANN--Teil einer Regel $\iR$ wird {\dfc Konklusion}
$\conc_\iR$ genannt und beinhaltet eine Elementaraussage, bezogen
auf die Ausgangsgröße $\Y$
\begin{equation}\label{eg:Konk}
\conc_\iR=(\Y=\ls_{\Y,l_\Y})\quad \mbox{mit }
l_\Y\in\{1,2,\cdots,\Nls_\Y\}\;.
\end{equation}

Die Inferenz wertet die vollständige Regelbasis $\SR$ aus und
erzeugt für eine gegebene Eingangssituation $\Vx$ eine
ausgangsseitige Fuzzy--Menge, die auch {\em Empfehlungsgebirge}
genannt wird. Dieses Empfehlungsgebirge gibt für jeden
Ausgangsgrößenwert $\y$ des Definitionsbereichs genau den Grad
$\msf_\Y(\Vx,\y)$ der Empfehlung an. Die dafür notwendigen
Teilschritte sind die {\dfc Aggregation} (Prämissenauswertung),
die {\dfc Aktivierung} (Komposition) und die {\dfc Akkumulation}.

\begin{definition}{Aggregation:}
\label{def:aggregation} Unter Aggregation wird die Bestimmung des
Erfülltheitsgrads $\msf_\prem$ der Prämisse $\prem_\iR$ einer
linguistischen Regel in Ab\-hän\-gig\-keit der Eingangsgrößenwerte
$\Vx$ durch Verknüpfung der Erfülltheitsgrade $\msf_{i,l_i}$ aller
Partialprämissen $\LE_{\iR,i}$ mittels Fuzzy--Operatoren
verstanden:
\begin{equation}
\nonumber
\msf_{\prem_\iR}(\Vx):=\bigwedge_{k=1}^{\cd}\msf_{i_kj_k}(x_{i_k})\;.
\end{equation}
\end{definition}

Dabei entspricht $k$ dem $k$--ten linguistischen Ausdruck in der
Prämisse $\prem_\iR$. Eine Übersicht über die Definitionen der
gebräuchlichsten Fuzzy--Operatoren ist in Tabelle
\ref{tab:fuzzyOps} zusammengestellt. Aus der ermittelten
Erfülltheit der Prämisse $\prem_\iR$ wird die Aktivierung der
Zugehörigkeitsfunktion der Konklusion $\conc_\iR$ bestimmt.

\begin{definition}{Aktivierung:}\label{def:aktivierung} Mit
Aktivierung wird die Bestimmung des Erfülltheitsgrads $\msf_C$ der
Konklusion $\conc_\iR=(\Y=\ls_{\Y,l_\Y})$ einer
lin\-gu\-is\-ti\-schen Regel aus dem Erfülltheitsgrad der Prämisse
$\msf_{\prem_\iR}$ und einem eventuell vorhandenen Wichtungsfaktor
(Glaubensmaß) $\JI_\iR\in[0,1]$ bezeichnet:
\begin{equation}
\nonumber
\msf_{\conc_\iR}(\Vx,y):=\msf_{\prem_\iR}(\Vx)\wedge\msf_{Y,l_\Y}(\y)\wedge\JI_\iR\;.
\end{equation}
\end{definition}

Das {\dfc Glaubensmaß} $\JI_\iR$ wird häufig bei Regeln verwendet,
die datenbasiert generiert wurden. Es basiert auf dem bei der
Regelsuche verwendeten statistischen Test und ist ein Maß dafür,
wie gut die Regel $\iR$ durch die Daten gestützt wird.

Abschließend werden im Prozess der Inferenz die aktivierten
Zugehörigkeitsfunktion der Konklusion $\conc_\iR$ akkumuliert.

\begin{definition}{(Akkumulation)}\label{def:akkumulation}
Unter Akkumulation wird die Zusammenfassung der Erfülltheitsgrade
$\msf_{\conc_\iR}(\Vx,y)$ der Konklusionen aller $\NR$
linguistischen Regeln einer Regelbasis $\SR$ zu einer
ausgangsseitigen Zugehörigkeitsfunktion $\tilde\msf_Y$, auch
Empfehlungsgebirge genannt, verstanden:
\begin{equation}
\nonumber
\msf_\Y(\Vx,y):=\bigvee_{\iR=1}^{\NR}\msf_{\conc_\iR}(\Vx,y)\;.
\end{equation}
\end{definition}

Die bisher betrachteten Regeln beziehen sich auf positives
Erfahrungswissen, die Empfehlungen für ausgangsseitige
linguistische Werte aussprechen. Eine Erweiterung der
herkömmlichen Inferenz bildet die von \Kiendl{} eingeführte
Verwendung {\em negativer Regeln}
\cite{Kie93a,Kie93b,Kie94c,KKN96,Kie97a,Kra99}, mit denen auch
negatives Erfahrungswissen im Sinne von Warnungen und Verboten
implementiert werden kann. Dabei handelt es sich um Regeln der
Form
\begin{equation}
\mbox{\WENN}\; \prem_\iR \;\; \mbox{\DANN} \; \conc_\iR \;\;
\mbox{VERBOTEN}\;.
\end{equation}

Für diese Form der Regeln wird die Aggregation und Aktivierung wie
zuvor beschrieben durchgeführt. Die Akkumulation wird jedoch für
die positiven und negativen Regeln getrennt durchgeführt, so dass
zwei ausgangsseitige Zugehörigkeitsfunktionen $\msf^+_\Y(\y)$ für
{\dfc Empfehlungen} und $\msf^-_\Y(\y)$ für {\dfc Warnungen}
berechnet werden. Die Verrechnung der beiden
Zugehörigkeitsfunktionen erfolgt mit Hilfe der {\em Hyperinferenz}
gemäß
\begin{equation}
\msf_Y(\Vx,\y)=\msf^+_\Y(\y)\wedge \neg \msf^-_\Y(\y) \;.
\end{equation}

\subsubsection{Defuzzifizierung}
Die Abbildung der akkumulierten ausgangsseitigen
Zugehörigkeitsfunktion $\msf_\Y(\Vx,\y)$ auf einen numerischen
(scharfen) Ausgangsgrößenwert $\yD$ wird \emph{Defuzzifizierung}
genannt. Die beiden gräuchlichsten Defuzzifizierungsmethoden sind
in Tabelle \ref{tab:defuzzy} angegeben.

\begin{table}[!ht]
\begin{center} {
\caption{\label{tab:defuzzy} Definitionen der gräuchlichsten
Defuzzifizierungsmethoden.} \vspace{0.3cm}
\begin{tabular}{|c|l|rl|}
\hline
Abk.           &  Bezeichnung             &   \multicolumn{2}{|c|}{Definition}\\
\hline\hline
               &                           &                                     & \\
\rb{COG}       &   \rb{Schwerpunktmethode} & \rb{$\yD^{COG}\;:=$}
& \rb{$\int
y\cdot\msf_\Y(\Vx,\y) \cdot dy/\int \msf_Y(\Vx,\y)\cdot dy$} \\
\hline
               &                          &                                      & \\
\rb{MAX}       &   \rb{Maximum--Defuzzifizierung} &
\rb{$\yD^{MAX}\;:=$} &
\rb{$\{\yD|\msf_Y(\Vx,\yD)=\max\{\msf_Y(\Vx,\y)\},\forall\;\y\in\Y\}$}
\\ \hline
\end{tabular}
}
\end{center}
\end{table}

Die MAX--Defuzzifizierung liefert dabei den am meisten empfohlenen
Wert als Ausgangsgrößenwert $\ym = \yD^{MAX}$. Für den Sonderfall,
dass mehrere Maxima vorliegen, wird als häufigste Variante der
mittlere Wert $\y^{MOM}_D$ ({\bf M}ean {\bf O}f {\bf M}aximum) als
Ausgangsgrößenwert verwendet. Sehr selten dagegen wird von der
Möglichkeit der Selektion des minimalen Wertes $\yD^{min}$ oder
des maximalen Wertes $\y^{max}_D$ Gebrauch gemacht. Demgegenüber
bildet die COG--Defuzzifizierung ({\bf C}enter {\bf O}f {\bf
G}ravity) aus allen Empfehlungen anhand ihrer Gewichte einen
Kompromiss zum Ausgangsgrößenwert $\ym = \yD^{COG}$.

In der Praxis werden sehr häufig ausgangsseitig Singletons
(Definition \ref{def:singleton}) als Zugehörigkeitsfunktionen
verwendet, weil diese im Allgemeinen einfacher und rechentechnisch
schneller ausgewertet werden können. Die in Tabelle
\ref{tab:defuzzy} angegebenen Methoden sind einfach auf den Fall
ausgangsseitiger Singletons über\-trag\-bar und werden dann COS
({\bf C}enter {\bf O}f {\bf S}ingletons) bzw. MOS ({\bf M}aximum
{\bf O}f {\bf S}ingletons) genannt.

Weitere Methoden zur Defuzzifizierung sind u.~a. die von \Kiendl{}
eingeführte Drehmomentmethode (TOR/TOS)
\cite{Kie94c,Kie97b,Kie99a} zur verstärkenden Überlagerung
gleichsinniger Empfehlungen sowie das Inferenzfilter
\cite{Kie94b,Kie96,KKN96,Kie97a,Kie99a}, welches herkömmliche
Defuzzifizierungsmethoden in einem parametrisierten Ansatz
verallgemeinert und durch {\em stufenlose Übergänge} zwischen den
Defuzzifizierungsmethoden weiteres Optimierungspotenzial
erschließt.


\subsection{\TSK--Fuzzy--Systeme}
\label{sec:B_tsk} Durch \Takagi, \Sugeno{} und \Kang{} ist aus dem
\Mam--Fuzzy--System das ebenso verbreitete \TSK--Fuzzy--System
entwickelt worden \cite{TS85}.
\begin{figure}[ht]
\centering \ingraph{11}{0.5}{../Bilder/basics/modellTSK2}
\caption{\label{fig:B_modelltsk} \TSK--Fuzzy--System.}
\end{figure}

Mit dem Ziel der Ermöglichung höherer Approximationsgüten wurden
dabei die linguistischen Werte der Konklusion eines \Mam--Systems
durch funktionale Abhängigkeiten von den Eingangsgrößen $\Vx$
ersetzt, so dass sich für \TSK--Regeln die Form
\begin{equation}
\RegelTSK{\prem_\iR}{\tilde{y_\iR}=f_\iR(\Vx)}
\end{equation}
ergibt. Die zugehörige Struktur ist in Abbildung
\ref{fig:B_modelltsk} dargestellt. Das Modul der Fuzzifizierung
sowie die Aggregation werden mit analoger Funktionsweise zum
\Mam--Fuzzy--System verwendet. Für die Auswertung des Regelsatzes
kommt eine erweiterte Auswertung der Funktionen $f_\iR(\Vx)$ der
Regeln hinzu. Aus den Erfülltheitsgraden $\p_\iR$ der Prämissen
$\prem_\iR$ und den Funktionswerten $\tilde{\y}_\iR$ wird durch
eine gewichtete Mittelwertbildung der Ausgangsgrößenwert $\ym$ mit
\begin{equation}
\ym=\frac{\sum\limits^{\NR}_{\iR=1}\msf_{\prem_\iR}\cdot\tilde{\y}_\iR}
{\sum\limits^{\NR}_{\iR=1}\msf_{\prem_\iR}}
\end{equation}

bestimmt. In \cite{Kra00,KS01} wird eine Vorgehensweise zur
datenbasierten Generierung von interpretierbaren
Takagi--Sugeno--Kang--Systemen (TSK--Systeme) vorgeschlagen. Sie
basiert auf einer Transformation von Mamdani--Regeln, die mit dem
Fuzzy--ROSA--Verfahren generiert werden, in TSK--Regeln, wie sie
auch im Rahmen dieser Arbeit verwendet wird.

\section{Datenbasierte Fuzzy--Modellierung}
%\section{Modellierung mit dem Fuzzy--ROSA--Verfahren}
\label{sec:B_rosa}Die im Rahmen dieser Arbeit zu entwickelnden
Methoden zur Selektion relevanter nichtredundanter Merkmalssätze
und Generierung von den Daten angepassten Fuzzy--Partitionen
definieren die linguistischen Werte für alle selektierten Größen.
Daraus ergibt sich direkt die Menge aller möglichen Fuzzy--Regeln
ergibt. Die zwei grundlegenden Ansätze zur Regelgenerierung, die
zur Bestimmung einer möglichst geeigneten Teilmenge als
resultierender Regelsatz verfolgt werden können, sind in Abschnitt
\ref{sec:A_fuzz_modellierung} beschrieben und hinsichtlich
Interpretierbarkeit und Genauigkeit diskutiert worden. Ausgehend
von diesen Kriterien ist für die im Rahmen dieser Arbeit zu
generierenden Fuzzy--Systeme das von \namestyle{Kiendl},
\namestyle{Krabs}, \namestyle{Krone} und \namestyle{Slawinski}
entwickelte \FR--Verfahren
\cite{KK89,Kra94,KK95a,Kro99,Sla01,SKK01} ausgewählt worden.
Dieses datenbasierte Verfahren zeichnet sich durch eine effiziente
Generierung kompakter und transparenter Regelsätze mit im
Allgemeinen auch hoher Modellierungsgüte aus. Neben diesen
Eigenschaften ist der Aspekt der Verfügbarkeit sowie die
akzeptable durchschnittliche Generierungszeit von Regelsätzen bei
der Auswahl des \FR--Verfahrens berücksichtigt worden.

Die Grundidee des \FR--Verfahrens wird in Abschnitt
\ref{subsec:B_rosa_idee} beschrieben. Eine zusammenfassende
Übersicht über die einzelnen Teilschritte des zugehörigen
Regelgenerierungsprozesses erfolgt in Abschnitt
\ref{subsec:B_regelgenerierung}. Daran angelehnt werden in
Abschnitt \ref{subsec:B_Effizienzsteigerung} die wesentlichen
Ansatzpunkte zur Effizienzsteigerung von datenbasierten
Modellierungsverfahren konkretisiert, die im Rahmen dieser Arbeit
konzipiert und am Beispiel des Fuzzy--ROSA--Verfahrens erprobt
werden.


\subsection{Grundidee des Fuzzy--ROSA--Verfahrens}
\label{subsec:B_rosa_idee} Ausgangspunkt des \FR--Verfahrens ist
die $1989$ von \Kiendl{} und \Krabs{} vorgeschlagene {\bf
R}egel--{\bf O}rientierte {\bf S}tatistische {\bf A}nalyse (ROSA)
\cite{KK89} zur automatischen Generierung regelbasierter Systeme.
Die grundlegende Idee des Verfahrens besteht darin, einzelne
potenzielle Regeln anhand von Beobachtungsdaten mit Hilfe eines
statistischen Tests daraufhin zu testen, ob sie einen relevanten
Teilaspekt des betrachteten Systems beschreiben. Der dafür
entwickelte Relevanzindex als Regeltest- und Bewertungsstrategie
vereinigt ein aus der Literatur bekanntes Schema zur Bewertung der
Unsicherheit von Regeln in Expertensystemen mit dem statistischen
Konzept der Konfidenzintervalle \cite{Kra94}.

Im Gegensatz zu anderen Verfahren, die gemäß des
Pittsburgh--Ansatzes den vollständigen Regelsatz evaluieren und
optimieren, wird mit dem ROSA--Verfahren nach dem Michigan--Ansatz
der Regelsatz sukzessive aus individuell getesteten und bewerteten
Regeln aufgebaut. Damit wird das komplexe Problem, einen guten
Regelsatz zu generieren, auf das einfachere Problem, einzelne
relevante Regeln zu finden, zurückgeführt. Hieraus resultiert im
Vergleich eine Verkleinerung des Suchraumes, da ausschließlich
Regeln statt Mengen von Regeln betrachtet werden müssen. Des
Weiteren wird durch die statistische Absicherung implizit
gewährleistet, dass die Regeln in ihrem lokalen Wirkungsbereich
vernünftige Aussagen beinhalten und somit auch wirklich
interpretierbar sind. Infolgedessen ermöglicht dieser Ansatz
einerseits, befriedigende Lösungen auch für komplexere
Aufgabenstellungen in akzeptabler Zeit zu erzielen, andererseits
wird das globale Optimum im Allgemeinen nicht erreicht.

Mit dem Ziel, diese Vorteile auch für die datenbasierte
Fuzzy--Modellierung zu nutzen, ist $1994$ die Vorgehensweise des
ROSA--Verfahrens von \Kiendl{} und \Krone{} auf den Fall von
Fuzzy--Regeln übertragen worden \cite{KK94b,Kro99}. Die dabei
verwendete Regelstruktur basiert auf \Mam--Fuzzy--Regeln gemäß
Gleichung (\ref{eq:B_MamRegel}). Das \FR--Verfahren berücksichtigt
grund\-sätzlich auch generalisierende Regeln, deren
Kombinationstiefe $\cd$ kleiner als die gesamte Anzahl
linguistischer Eingangsvariablen $\NV$ ist. Insbesondere bei
Modellierungsproblemen mit vielen Eingangsgrößen können die
hochdimensionalen Suchräume mit weniger generalisierenden Regeln
abgedeckt werden, so dass der resultierende Regelsatz im Vergleich
zur Verwendung vollständiger Regeln meist kleiner und entsprechend
besser interpretierbar ist. Weitere Strategieelemente zur Analyse
und effizienten Generierung relevanter Fuzzy--Regeln in
hochdimensionalen Suchräumen sind von \Slawinski{} zur Erweiterung
der Anwendungsfelder des \FR--Verfahrens implementiert worden
\cite{Sla01}. Als jüngste Erweiterung des \FR--Verfahrens ist zur
Erhöhung der Modellierungsgüte bei Approximationsproblemen von
\Krause{} ein Verfahren entwickelt und implementiert worden, das
ein datenbasiert generiertes \Mam--Fuzzy--Modell in ein
\TSK--Fuzzy--Modell umwandelt, ohne die Interpretierbarkeit und
Transparenz des \Mam--Fuzzy--Modells zu verlieren \cite{Kra01}.


\subsection{Der Regelgenerierungsprozess} \label{subsec:B_Effizienzsteigerung}
\label{subsec:B_regelgenerierung}Der Regelgenerierungsprozess des
\FR--Ver\-fah\-rens lässt sich grob in die folgenden vier Schritte
einteilen \cite{SKK01}:

\begin{description}
\item{\em Projektdefinition: } Vor der eigentlichen Regelgenerierung
müssen die linguistischen Werte für die
Eingangs-/Ausgangsvariablen des betrachteten Systems festgelegt
werden. Dies kann wissensbasiert, datenbasiert oder heuristisch
erfolgen \cite{KS98}. Außerdem kann die maximale Kombinationstiefe
$\cmax$ für die Prämisse und gegebenenfalls eine maximale
Zeittiefe $\tmax$ festgelegt werden, um den Rechenaufwand zu
beschränken.
\item{\em Regelgenerierung: } Abhängig von der Suchraumgrö\-ße kann
eine komplette Suche, eine evolutionäre Suche oder eine
Kombination von beiden gewählt werden \cite{SKK01}. Der Regelsatz
wird sukzessive aus allen relevanten, nicht redundanten Regeln
aufgebaut. Die Bewertungsgrundlagen, nach denen Regeln getestet
und bewertet werden, werden in Anhang \ref{chap:A_B} beschrieben.
\item{\em Regelreduktion: } Die Anzahl der Regeln kann an\-schlie\-ßend
durch Offline--Re\-gel\-re\-duk\-tio\-ns\-ver\-fah\-ren
verringert werden \cite{Kro96}. Dabei können verschiedene
Anforderungen, wie z.~B. komplette Überdeckung aller
Eingangssituationen, gleich\-mä\-ßi\-ge Ausnutzung der Daten,
Verringerung des Modellierungsfehlers oder der Regelanzahl,
berücksichtigt werden \cite{KKS00a}.
\item{\em Regelsatzanalyse und -optimierung: }
Durch die ab\-schlie\-ßen\-de Analyse des Regelsatzes kann der
Modellierungsprozess und das Modellierungsergebnis bewertet und
gegebenenfalls Feedback für die Problemformulierung erhalten
werden. Zusätzlich kann das Eingangs-/Ausgangsverhalten des
erhaltenen Fuzzy--Systems durch Anpassung der verbleibenden freien
Parameter optimiert werden \cite{KKS00a,KKS00b,KWS00}.
\end{description}


\subsection{Ansatzpunkte für die vorliegende Arbeit} \label{subsec:B_Effizienzsteigerung}
Wie in Kapitel \ref{sec:A_ziele} illustriert, werden mit der
\emph{Projektdefinition} direkt zu Beginn des
Regelgenerierungsprozesses  die erfolgsbestimmenden Einstellungen
bezüglich der erzielbaren Modellgüte gelegt. Typischerweise werden
für die Modellierung mit dem \FR--Verfahren gemäß der von
\Slawinski{} entwickelten \emph{Systematischen Vorgehensweise}
alle potenziellen Einflussgrößen $\X_{\iV}$ unter Verwendung von
äquidistant verteilten Standard--Fuzzy--Partitionen bei der
Regelgenerierung berücksichtigt. Im Rahmen dieser Arbeit sollen
Verfahren zur Effizienzsteigerung des Regelgenerierungsprozesses
erarbeitet werden, die automatisiert und datenadaptiv besonders
günstige Vorgaben dieser entscheidenden Einstellungen zur direkten
Verwendung in der \emph{Projektdefinition} erstellen:

\begin{description}
\item{\bf Selektion relevanter Einflussgrößen}
Für den Regelgenerierungsprozess ist aus einer gegebenen Menge
$\SX$ von potenziellen Einflussgrößen eine Teilmenge $\SM$ von
denjenigen Einflussgrößen $\X_{\iV}$ zu selektieren, die entweder
direkt oder im Zusammenhang mit weiteren Einflussgrößen $\X_{j}$
Informationen über die zu modellierende Ausgangsgröße $\Y$
beinhalten.

\item{\bf Eliminierung redundanter Einflussgrößen}
Für den Regelgenerierungsprozess sind aus der ermittelten
Teilmenge $\SM$ relevanter Einflussgrößen diejenigen
Einflussgrößen $\X_{\iV}$ zu eliminieren, deren Informationsgehalt
bezüglich der zu modellierenden Ausgangsgröße $\Y$ bereits von
anderen relevanteren Einflussgrößen $\X_{j}$ abgedeckt wird.

\item{\bf Optimierung der Fuzzy--Partitionen}
Für die selektierten relevanten und nichtredundanten
Einflussgrößen $\X_{\iM}$ der Menge $\SM$ sind zur Bestimmung der
linguistischen Werte $\ls_{\iV,j}$ zugehörige datenadaptierte
Fuzzy--Partitionen derart zu generieren, dass vom
Regelgenerierungsprozess ein möglichst transparentes und
generalisierungsfähiges Modell mit hoher Modellgenauigkeit
gebildet werden kann.

\end{description}

\section{Selektion relevanter Merkmale}
\label{chap:B_Merkmalselekt}

Ein Hauptproblem bei der datenbasierten Fuzzy--Modellierung
besteht in der Auswahl der zu berücksichtigenden Einflussgrößen.
Erfahrungsgemäß sind nur selten alle gemessenen oder zur Verfügung
stehenden Größen des zu modellierenden Systems notwendig, um die
zugrunde liegenden Prozesszusammenhänge mit ausreichender
Genauigkeit zu modellieren. Der Erfolg einer datenbasierten
Fuzzy--Modellierung hängt somit häufig entscheidend von einer
geeigneten Auswahl der tatsächlich berücksichtigten Einflussgrößen
aus einer Vielzahl von potenziell wichtigen Einflussgrößen ab.
Eine dem Modellierungsprozess vorgelagerte Selektion von
relevanten und nichtredundanten Einflussgrößen wirkt sich aus
mehreren Gründen oftmals vorteilhaft aus:

\begin{itemize}
\item höhere erzielbare Modellgenauigkeit

\item deutliche Reduzierung des Modellierungsaufwandes

\item erhöhte Transparenz des generierten Fuzzy--Modells

\item verringerter Aufwand der Modellauswertung.
\end{itemize}


Eine Einteilung der aus der Literatur bekannten
Selektionsverfahren kann zum einen anhand der verwendeten {\em
Bewertungsfunktion} und zum anderen auf der Basis der verfolgten
{\em Suchstrategie} vorgenommen werden. Dabei ist es die Aufgabe
der Bewertungsfunktion, einzelnen Einflussgrößen oder einem ganzen
Satz betrachteter Größen (einem potenziellen {\em Merkmalssatz})
einen Relevanzwert zuzuordnen. Die verwendete {\em Suchstrategie}
bestimmt die Vorgehensweise, wie im Raum aller möglichen
Merkmalssätze ein im Sinne der verwendeten Bewertungsfunktion
möglichst günstigster Merkmalssatz gesucht wird.


\subsection{Bewertungsfunktion} In der Literatur werden bezüglich
der Wahl der Bewertungsfunktion zwei grundsätzlich verschiedene
Ansätze \cite{JoKoPf94, KoJo97, KoWo00} voneinander unterschieden.

Beim sogenannten {\em Wrapperansatz} (engl. {\em wrapper} =
einwickeln) wird die Relevanz eines Satzes von Einflussgrößen
dadurch ermittelt, dass mit diesem Satz von Einflussgrößen anhand
der verfügbaren Messdaten eine Modellidentifikation mit Hilfe des
vorgesehenen Modellierungsverfahrens vorgenommen und die
resultierende Modellgüte als Maß für die Relevanz angesehen wird.
Ein wesentlicher Vorteil dieses Ansatzes besteht darin, dass der
{\em Bias} der Bewertungsfunktion mit dem des hinterher
verwendeten Modellierungsverfahrens übereinstimmt. Demgegenüber
wird bei dem sogenannten {\em Filteransatz} ein im Allgemeinen
einfach und schnell zu berechnendes Maß zur Bewertung eines
Merkmalssatzes oder einer einzelnen potenziellen Einflussgröße
verwendet. Bei einem Filteransatz kann somit nicht gewährleistet
werden, dass eine im Sinne der Bewertungsfunktion als günstig
bewertete Lösung sich auch als günstig für das nachgeschaltete
Modellierungsverfahren erweist. Der wesentliche Vorteil des
Filteransatzes hingegen liegt in dem meist vergleichsweise
wesentlich geringeren Rechenaufwand. In Anbetracht der Komplexität
und Rechenintensivität des \FR--Verfahrens wird der Filteransatz
im Folgenden verfolgt.

Eine etablierte Bewertungsfunktion für die Relevanzbewertung
einzelner reellwertiger Einflussgrößen $\X$ im Sinne eines
linearen Zusammenhangs mit der Ausgangsgröße $\Y$ ist die aus der
Statistik bekannte \emph{Korrelation} \cite{HEK95}. Sie bewertet
die Relation zwischen genau einer Einflussgröße und einer
Ausgangsgröße. Die ebenfalls aus der Statistik bekannte
\emph{Hauptkomponentenanalyse} \cite{Jac91} verallgemeinert eine
solche Bewertung auf eine beliebige Anzahl $\NV$ von
Einflussgrößen $\X_1, \X_2, \ldots,\X_{\NV}$. Hierzu werden diese
durch eine lineare Transformation in $\NVsel$ möglichst
unkorrelierte, also orthogonal zueinander stehende Komponenten
$\VM$, die sogenannten Hauptkomponenten, transformiert. Das
Verfahren der Hauptkomponentenanalyse hat neben der Beschränkung
auf einen linearen Strukturansatz den weiteren wesentlichen
Nachteil, dass die neu ermittelten Komponenten $\M_1, \M_2,
\ldots,\M_{\NVsel}$ aufgrund ihrer Berechnung als
Linearkombination der ursprünglichen Einflussgrößen $\X_1, \X_2,
\ldots,\X_{\NV}$ im Allgemeinen keine interpretierbaren
Systemgrößen darstellen. Die erzielbare Transparenz eines darauf
aufsetzenden Modells wäre dementsprechend äußerst gering.

Zur Analyse nichtlinearer Abhängigkeiten zweier Einflussgrößen mit
diskret verteilten Werten ist aus der Informationstheorie die
\emph{Transinformation} bekannt \cite{Mat96}. Von \cite{Pra99}
wird für diese Aufgabenstellung ein Eindeutigkeitsmaß definiert,
welches insbesondere auch für fuzzifizierte Größenwerte anwendbar
ist. Es untersucht potenzielle Einflussgrößen auf lineare und
nichtlineare Zusammenhänge mit der Ausgangsgröße (Relevanzanalyse)
und mit den übrigen potenziellen Einflussgrößen
(Redundanzanalyse). Das Verfahren berücksichtigt eine durch
Fuzzy--Zugehörigkeitsfunktionen vorzugebende Granularisierung
(\emph{Fuzzy--Partitionierung}) der Einflussgrößen und der
Ausgangsgröße und ist daher auf eine nachgeschaltete
Fuzzy--Modellierung zugeschnitten. Allerdings bewertet das
Verfahren die potenziellen Einflussgrößen einzeln und nicht ---
was angemessener wäre --- ganze daraus zusammengestellte Sätze von
Einflussgrößen. Zudem verbleibt das Problem einer günstigen
Granularisierung der Einflussgrößen. Insbesondere bei
hochdimensionalen Modellierungsproblemen komplexer Systeme wird,
wie in \ref{sec:A_fuzz_partitionierung} dargelegt, eine
Partitionierung häufig heuristisch durch äquidistante
Raumeinteilung vorgenommen. Aufgrund einer derartigen, nicht
optimal gewählten, Granularisierung kann die Relevanz einer
potenziellen Einflussgröße falsch bewertet sowie die mit dem
Fuzzy--ROSA--Verfahren erzielbare Modellierungsgüte erheblich
beeinträchtigt werden.

\pagebreak
Der beschriebene Mangel des Verfahrens aus
\cite{Pra99}, dass die potenziellen Einflussgrößen einzeln
bewertet werden, wird in \cite{Xio01} abgestellt. Dort wird ein
Verfahren zur Auswahl eines relevanten Satzes von potenziellen
Einflussgrößen vorgestellt. Allerdings erfolgt die
Relevanzbewertung ohne Berücksichtigung einer Granularisierung des
Eingangsraumes. Dies ist nachteilig für eine nachgeschaltete
Fuzzy--Modellierung.



\subsection{Suche von relevanten Sätzen von Einflussgrößen} Für
die Suche eines Merkmalssatzes, der im Sinne der verwendeten
Bewertungsfunk\-tion als möglichst relevant bewertet wird, werden
in der Literatur verschiedene Ansätze vorgeschlagen.

Die {\em vollständige Suche} durchmustert den Raum aller möglichen
Kombinationen der vorhandenen Einflussgrößen und findet daher
garantiert das globale Optimum. Die exponentiell mit der Anzahl
vorhandener Einflussgrößen anwachsende Größe des Suchraums führt
unweigerlich zu einem immens hohen Rechenaufwand, so dass diese
Strategie in der Praxis nur selten anwendbar ist. Meistens werden
daher sogenannte {\em Greedy--Algorithmen}, etwas seltener auch
{\em Genetische Algorithmen}, verwendet \cite{ImVa94, Den98}.

\begin{figure}[ht]
\centering \ingraph{14}{0.3}{../Bilder/task/greedy}
\caption{\label{fig:greedy} Veranschaulichung des Ablaufs von
Greedy--Algorithmen am Beispiel von vier potenziellen
Einflussgrößen. Jeder Knoten des Graphen repräsentiert einen
Merkmalssatz, der durch die Teilmenge der berücksichtigten
Einflussgrößen (markiert durch gefüllte Kreise) definiert wird.
Zwei miteinander verbundene Merkmalssätze unterscheiden sich in
genau einer Einflussgröße.}
\end{figure}

Bekannte {\em Greedy--Algorithmen} sind die sogenannte {\em
Rückwärts-} und {\em Vorwärtsselektion}. Bei der Vorwärtsselektion
wird zunächst die Relevanz einer jeden potenziellen Einflussgröße
separat ermittelt und die Einflussgröße mit der höchsten Relevanz
als erste Größe des Merkmalssatzes übernommen. Darauf aufbauend
wird der Merkmalssatz iterativ um diejenige noch nicht ausgewählte
Einflussgröße erweitert, deren Hinzufügung zum bereits
selektierten Merkmalssatz die größte Relevanzsteigerung erbringt.
Dieser sequentielle Erweiterungsprozess wird beendet, wenn keine
oder keine \glqq signifikante\grqq{} Relevanzsteigerung durch
Hinzufügung einer weiteren potenziellen Einflussgröße erzielt
werden kann. Bei der Festlegung, was als \glqq signifikant\grqq{}
anzusehen ist, ist ein meist anwendungsspezifischer Kompromiss
zwischen den gegenläufigen Zielen \glqq hohe Relevanz\grqq{} und
\glqq möglichst wenig Einflussgrößen\grqq{} zu schließen.
Demgegenüber startet die {\em Rückwärtsselektion} mit der
Relevanzanalyse des vollständigen Satzes aller potenziellen
Einflussgrößen und verkleinert diesen iterativ immer um diejenige
Einflussgröße, die bei Entfernung aus dem bestehenden Merkmalssatz
die größte Relevanzsteigerung (oder auch geringste
Relevanzverminderung) auslöst. Falls sich bei der Relevanzanalyse
eines verkleinerten Merkmalssatzes in jedem Fall eine
Verschlechterung der Relevanz ergibt, wird derjenige Merkmalssatz
ausgewählt, der zur geringsten Relevanzverschlechterung führt,
sofern diese als Preis für die Verkleinerung des Merkmalssatzes
noch akzeptabel ist.

\section{Evolutionsstrategien}
\label{chap:B_ES}

\subsection{Einführung}
Evolutionsstrategien ordnen sich in die Klasse der
\emph{Evolutionären Algorithmen} ein, die durch die biologische
Evolution inspiriert wurden. Dabei geht man von der Sichtweise
aus, dass die natürliche Evolution selbst ein Optimierungsprozess
ist, dessen Ziel es ist, die Fähigkeit des Überlebens eines
Individuums zu verbessern. Im Jahre 1859 veröffentlichte Charles
Darwin diese Erkenntnis in seinem Buch "`\emph{On the Origin of
Species by Means of Natural Selection}"'. Was seitdem als
Evolutionstheorie bekannt und bisher nicht widerlegt ist, beruht
auf drei grundlegenden Beobachtungen und Annahmen:
\begin{itemize}
    \item Nahezu alle Lebewesen erzeugen mehr Nachkommen, als tatsächlich überleben
    können.
    \item Lebewesen einer Art können sich zwar sehr stark ähneln, sind aber nie vollständig
    identisch.
    \item Erbinformationen werden an eine Nachfolgegeneration nur weitergegeben, wenn sich diese im Kampf um Anpassung und Überleben bewährt
    haben.
\end{itemize}

Die meisten Nachkommen einer Art sterben also, bevor diese sich
wieder vermehren können. Lebewesen einer Art unterliegen demnach
einem \emph{Selektionsdruck}, welcher die \emph{Populationsgröße},
also die Anzahl aller Individuen einer Art, auf natürliche Art und
Weise konstant hält. Die genetische Information eines Lebewesens
ist in seinem Genom oder auch Gensatz dargestellt, welches sich
aus einzelnen Genen zusammensetzt (\emph{Genotyp}). Lebewesen
unterscheiden sich in der Art ihres genetischen Materials, so dass
einige aufgrund ihres Erscheinungsbildes, dem sogenannten
\emph{Phänotyp}, besser an ihre Umgebung angepasst sind als
andere. Ein solcher Kampf um die beste Anpassung an
Umweltbedingungen wird als \emph{natürliche Selektion} oder
\emph{survival of the fittest} bezeichnet \cite{Nis97}. So werden
vor allem nur die besten Lebewesen ihrer Art Nachkommen zeugen,
deren Fitness also am höchsten ist.


Das Erbgut eines Nachkommen setzt sich dann aus den Eigenschaften
beider Elternteile zusammen, in der Hoffnung, dass so nur die
besten Eigenschaften weitergegeben werden. Gelegentlich unterliegt
das Erbmaterial auch der Mutation, die zu zufälligen Änderungen
einzelner Erbinformationen führt. Dabei können sowohl eine
Verschlechterung als auch eine Verbesserung der Fitness eintreten,
die das weitere Überleben des Individuums entsprechend
beeinflusst. Auf diese Weise entwickeln sich
Nachfolgegenerationen, die immer besser an ihre Lebensräume (die
sich im Laufe der Zeit auch verändern können) angepasst sind.

Evolutionäre Algorithmen simulieren genau diesen Evolutionsprozess
anhand eines als \emph{Gütefunktion} (häufig auch als
\emph{Zielfunktion} bezeichnet) definierten Lebensraumes, des
mathematisch formulierten Optimierungsproblems. Durch die Wahl
einer Menge zufällig erzeugter Individuen entspricht die Anwendung
der Selektion einem stochastischen Suchprozess im Raum aller
möglichen Chromosome, der zu einer optimalen Lösung eines
Optimierungsproblems führen kann. Im Bereich der Evolutionären
Algorithmen haben sich im Laufe der Zeit folgende Ausprägungen
etabliert:


\begin{description}
\item[Genetische Algorithmen] (\emph{GA}) wurden
als erste jemals entworfene und angewendete  evolutionäre
Paradigma von \Holland{} und \Goldberg{} in den 70er Jahren
publiziert \cite{Hol75,Gol89}. Die Codierung der Informationen
eines Individuums erfolgt in der Regel durch einzelne Bits, ein
ganzes Chromosom wird durch einen Bit-String repräsentiert.
Alternativ gibt es aber auch vektorbasierte Darstellungen,
Codierungen in Form von Matrizen oder Permutationen. Eine
geeignete Wahl der Repräsentation ist nicht allgemeingültig
formulierbar, sonder problemspezifisch zu definieren. Evolutionäre
Operatoren hängen somit auch von der Codierung ab, im Falle von
Bit-String-Darstellung werden binäre Operationen auf die einzelnen
Individuen angewendet. Der maßgebliche Operator zur Reproduktion
für genetische Algorithmen ist die Rekombination. Mutation spielt
nur eine geringe Rolle und tritt nur mit einer sehr kleinen
Wahrscheinlichkeit auf.

\item[Genetische Programmierung] (\emph{GP}) kann als Spezialisierung
genetischer Algorithmen betrachtet werden. Auch hier unterliegen
lediglich die Genotypen der Evolution, wobei sich nur in der
Repräsentation von Individuen Unterschiede ergeben. Hierfür werden
keine Zahlen, Vektoren oder Bits verwendet, sondern ganze
ausführbare Programme herangezogen. Dabei löst jedes Programm für
sich ein Teilproblem. Gesucht wird die Kombination von
Teilprogrammen, welche ein größeres komplexeres Problem am
effizientesten löst. Dabei werden die Individuen in Baumstrukturen
verwaltet. Die Bewertung der Fitness eines Individuums erfolgt
aufgrund der Leistung des so generierten Computerprogramms bei
Anwendung auf das Optimierungsproblem.

\item[Evolutionäre Programmierung] (\emph{EP}) unterscheidet sich grundlegend von den beiden
zuvor genannten  evolutionären Paradigmen. Anders als GA und GP
liegt hierbei der Schwerpunkt auf der Entwicklung von
Verhaltensmodellen, es wird die Anpassung von Verhalten in der
Evolution simuliert. Demzufolge werden hier die Phänotypen
verändert, so dass eine Menge von optimalen Verhalten aus einem
Raum von beobachtbaren Verhalten erzeugt wird. Von den
evolutionären Operatoren wird Rekombination nicht verwendet. Die
Nachfolgegenerationen werden ausschließlich durch Mutation
erzeugt.

\item[Evolutionsstrategien] (\emph{ES}) wurden in den sechziger Jahren von
\Rechenberg{} und \Schwefel{} \cite{Sch77} entwickelt und erlebte
ihren Durchbruch mit der zunehmenden Rechenleistung der heutigen
Computer. Als wesentlicher Grundbestandteil dieser Arbeit werden
diese daher im Folgenden ausführlich beschrieben.
\end{description}


\subsection{Ablauf einer Evolutionsstrategie}\label{chap:B_ES_Schwefel}
Der Aufgabenbereich von Evolutionsstrategien besteht in der
Optimierung einer gegebenen reellwertigen Zielfunktion
\(f(\Vx):\mathbb{R}^{n}\rightarrow \mathbb{R}\) mit \(n\) reellen
zu optimierenden Parametern \(\x_{1}\) bis \(\x_{n}\). In der
Regel beschränken sich technische Optimierungsprobleme aufgrund
der gegebenen Randbedingungen auf Suchräume \(S\) in Form eines
Teilraumes \(S \subset \mathbb{R}^{n}\).

Ein Individuum $\Ind$ beinhaltet eine potenzielle Lösung $\Vx$
(\emph{Zielvariablenvektor}) des Optimierungsproblems sowie einen
\emph{Strategieparametervektor} $\Vgr{\sigma}$, dessen Komponenten
die Schrittweiten für den genetischen Operator \emph{Mutation}
sind:
\begin{equation}
\Ind = (\;\; \underbrace{\\x_1, \x_{2}, \ldots,
\x_{n}}_{Zielvariablen}\;, \underbrace{{\sigma}_{1}, {\sigma}_{2},
..., {\sigma}_{n}}_{Strategieparameter})\;.
\end{equation}



 Der Wert \(f(\Vx)\) entspricht dem \emph{Fitness}- oder
\emph{Gütewert} eines Individuums. Gesucht im Sinne des
Optimierungsproblems ist das Individuum mit der besten Fitness,
das heißt mit dem kleinsten bzw. größten Wert $f(\Vx)$. Dazu
arbeitet die Evolutionsstrategie gemäß
Abbildung~\ref{fig:AblaufES} über mehrere \emph{Generationen} $j$
mit einer Population $\SInd_j$ von \(\mu\) Individuen, von denen
über die genetischen Operatoren der \emph{Rekombination} und
\emph{Mutation} in jeder Generation \(\lambda\) Nachkommen erzeugt
werden. Eine nachfolgende \emph{Selektion} entscheidet, welche der
Individuen die Elternpopulation $\SInd_{j+1}$ der nachfolgenden
Generation $j+1$ werden.

\begin{figure}[ht]
\centering \ingraph{11}{0.3}{../Bilder/basics/StdES}
\caption{\label{fig:AblaufES} Üblicher Ablauf einer
Evolutionsstrategie.}
\end{figure}





\subsubsection{Startpopulation}

Als erster Schritt wird eine Startpopulation $\SInd_0$ erzeugt. Im
Interesse einer guten Breitensuche wird diese in der Regel
zufällig im Suchraum \(S\) generiert. Wenn der Suchraum nicht
begrenzt ist und bereits Vorwissen über eine relativ gute Lösung
des Optimierungsproblems vorliegt, wird häufig eine
normalverteilte Startpopulation um diesen Lösungspunkt im Suchraum
erzeugt. Andererseits besteht hierbei auch die Gefahr, dass der
Optimierungsprozess gegen diese bereits bekannte Lösung
konvergiert oder diese nur noch wenig verbessern kann, obwohl an
anderen Stellen im Suchraum bessere Lösungen zu finden sind. In
diesem Fall wäre der Suchraum nicht breit genug durchsucht worden.
Die Startpopulation kann auch deterministisch, zum Beispiel über
ein Gitternetz, festgelegt werden. Sind bereits mehrere relativ
gute Lösungen des Optimierungsproblems bekannt, so kann die Menge
dieser Vektoren als Startpopulation verwendet werden. Allerdings
besteht hierbei ebenfalls die oben genannte Gefahr der
frühzeitigen Konvergenz gegen eine nur suboptimale Lösung.

Die Strategieparametervektoren $\Vgr{\sigma}$ mit den
komponentenweisen Schrittweiten der Mutation werden zufällig gemäß

\begin{equation}\label{equ:schr_1}
\sigma_i=|\tilde{\sigma_{i}}\cdot
N_i(0,1)|\;\;\;\textnormal{mit}\;\;\;i=1,\dots,n
\end{equation}

erzeugt. Hierbei ist $N(0,1)$ eine normalverteilte skalare
Zufallsvariable mit Erwartungswert Null und Standardabweichung
Eins,
\begin{equation}\label{equ:dichte_normal}
P(s)=\frac{1}{\sqrt{2\cdot\pi}} \cdot e^{-\frac{1}{2} \cdot
{s^2}}\;,
\end{equation}
deren Wert unabhängig für jede Dimension $i$ des
Optimierungsproblems erzeugt wird. $\tilde{\sigma_{i}}$ ist eine
auf die Breite des Suchraums in der Dimension $i$ normierte
Standardabweichung:
\begin{equation}\label{equ:schr_2}
\tilde{\sigma_{i}}=0.05 \cdot (\x_{i,max}-\x_{i,min})\;.
\end{equation}

Die Schrittweitenvektoren werden in dieser Arbeit komponentenweise
durch $\Vgr{\sigma}_{min}=0.001 \cdot (\Vx_{max}-\Vx_{min})$ und
$\Vgr{\sigma}_{max}=0.1 \cdot (\Vx_{max}-\Vx_{min})$ begrenzt.
Kleinere oder größere Suchschritte sind dennoch möglich, da die
Schrittweitenvektoren der einzelnen Individuen ausschließlich die
Standardabweichungen der im Programmschritt Mutation auftretenden
normalverteilten Suchschritte festlegen. Die Individuen der
Startpopulation werden in dieser Arbeit für reale
Optimierungsprobleme immer gleichverteilt im Such\-raum erzeugt.
Lediglich zum Vergleich neuer Strategieelemente für den
evolutionären Optimierungsprozess werden alle Individuen der
Startpopulation auf einem einzigen Punkt im Suchraum platziert, um
so künstlich erschwerte Anfangsbedingungen zu schaffen.

\subsubsection{Rekombination}
Die Rekombination --- auch Fortpflanzung genannt --- erzeugt in
der Generation $j$  aus mehreren bereits bestehenden Vektoren
$\Vx$ der Menge $\SInd_j$ (der sogenannten Elternpopulation) neue
potenzielle Lösungen des Optimierungsproblems. Dabei werden auch
die Strategieparameter $\Vgr{\sigma}$ jedes neu erzeugten
Individuums in Abhängigkeit von den Strategieparametern der
Eltern--Individuen, die zur Erzeugung dieses Individuums verwendet
wurden, ebenfalls zufällig neu generiert.

Die Idee der Rekombination ist, dass gute Individuen ihre Gene
austauschen, um eventuell noch bessere Lösungen zu erzielen. Die
Anzahl der ``Sexualpartner'', die zur Erzeugung eines Nachkommens
herangezogen wird, wird mit der \emph{Gruppenpaarungszahl}
\(\rho\) bezeichnet. Die Rekombination ist ein ungerichteter
Operator, das heißt, die \(\rho\) Individuen werden unabhängig von
ihrer Qualität zufällig mit gleicher Wahrscheinlichkeit aus der
Menge der \(\mu\) Eltern gewählt. Für jeden Nachkommen wird eine
neue Menge von \(\rho\) Eltern ermittelt. Es ergeben sich drei
übliche Formen der Rekombination \cite{Eng03}:
\begin{description}
\item[Lokale diskrete Rekombination] Ein Nachkomme $\Ind_{j}^{rek}$ wird aus zwei Eltern
erzeugt, wobei die Parameter zufällig gleichverteilt aus beiden
Eltern gewählt werden.
\item[Globale  diskrete Rekombination]Jede Komponente des
Nachkommens $\Ind_{j}^{rek}$ wird durch die entsprechende Position
eines zufällig aus der Menge der \(\rho\) Eltern gewählten
Individuums gebildet. Für jede Komponente wird zufällig ein neues
Individuum bestimmt.
\item[Intermediäre Rekombination]In diesem Falle wird das arithmetische Mittel aller
involvierten Eltern als Parameterwert des Nachkommens  verwendet.
Der Nachkomme $\Ind_{j}^{rek}$ entspricht also dem Schwerpunkt der
\(\rho\) Individuen  $\Ind_{j}^{k}$ der Elternpopulation
$\SInd_j$:

\begin{equation}
\Ind^{rek}_j=\frac{1}{\rho}\sum_{k=1}^{\rho}\Ind_{j}^k\;.
\end{equation}
\end{description}
In den meisten Anwendungsfällen erweist sich die Strategie,
Optimierungsparameter $\Vx$ mit einer lokal diskreten
Rekombination und Strategieparameter $\Vgr{\sigma}$ über eine
intermediäre Rekombination zu verändern, als besonders effizient
\cite{BHS97}.

\subsubsection{Mutation}

Im Anschluss an die Rekombination wird üblicherweise die Menge
$\mathcal{P}_j^{rek}$ dem Programmschritt Mutation unterworfen und
dadurch die Menge $\mathcal{M}_j^{mut}$ erzeugt. Hierbei können
alle oder nur einige der Optimierungsparameter $\Vx$ aus
$\mathcal{P}_j^{rek}$ durch die Mutation verändert werden. Dabei
sind kleine Änderungen wahrscheinlicher als große. Bei
Evolutionsstrategien wird die Mutation durch Addition eines
$n$-dimensionalen Zufallsvektors $\Vmut$ zu den bereits
bestehenden Optimierungsparametern $\Vx$ realisiert. Üblicherweise
wird hierbei ein normalverteilter Zufallsvektor $\Vmut$ mit
Erwartungswert Null und vektorieller Standardabweichung $\sigma$
verwendet. Mit
\begin{equation}\label{equ:zufallsvektor_rech}
\Vmut=(N_1(0,\sigma_1),\dots,N_n(0,\sigma_n))
\end{equation}

wird der Mutationsschritt für ein Individuum $\Ind_i$
folgendermaßen vorgenommen:
\begin{equation}\label{equ:mut_rech}
\Vx^{mut}_i=\Vx_{i}+\Vmut \;.
\end{equation}


Die Mutation stellt eine wesentliche Komponente der
Evolutionsstrategie dar, denn nur durch die Mutation ist es
möglich, in bestimmte Bereiche des Suchraums $S$ zu gelangen. Dies
können beispielsweise Bereiche sein, die am Rand des Suchraums
liegen. Bei den gängigen Rekombinationsmethoden treten nur
Nachkommen--Individuen auf, deren Parameterwerte zwischen denen
der Eltern--Individuen liegen (intermediäre Rekombination) oder
mit diesen identisch sind (diskrete Rekombination). Die Mutation
dient dazu, auch Individuen außerhalb dieses Gebiets zu erzeugen.

Von entscheidender Bedeutung für die erfolgreiche Wirkungsweise
des Programmschritts Mutation ist eine geeignete Schrittweite für
die zufallsgesteuerten Mutationsschritte. Zu große Schrittweiten
können dazu führen, dass die Suche einer reinen Zufallssuche
gleich wird, zu kleine Schrittweiten bringen kaum Änderung und
ermöglichen daher kaum das Verlassen eines lokalen Minimums. Die
Festlegung der Startschrittweiten erfolgt bereits bei Generierung
der Startpopulation. Für die Veränderung der Schrittweiten sowie
der Individuen $\Ind_i$ der Menge $\mathcal{P}_j^{rek}$ im
Programmschritt Mutation existieren zwei grundlegende Strategien.

Nach \textsc{Rechenberg} ist die 1/5--Erfolgsregel anzuwenden,
nach der während des Optimierungsprozesses 1/5 der Mutationen
erfolgreich sein sollten, also zu einer Verbesserung des
Gütewertes führen. Sind weniger als 1/5 der Mutationen
erfolgreich, so ist die Schrittweite zu verkleinern, sind mehr als
1/5 der Mutationen erfolgreich, so ist die Schrittweite zu
vergrößern.

Von \textsc{Schwefel} wurde die 1/5--Erfolgsregel konkretisiert,
d.~h. es wurde eine algorithmische Umsetzung erarbeitet. Eine
Erweiterung der Vorgehensweise von \textsc{Rechenberg} stellen
Mutationsschritte unter Verwendung eines $n$-dimensionalen
Zufallsvektors mit \emph{vektorieller} Schrittweite $\Vgr{\sigma}$
dar. In diesem Zusammenhang geht auf \textsc{Schwefel} das
Verfahren der \emph{Selbstadaption der Schrittweiten} zurück
\cite{Sch77}. Hierbei wird bei jedem Mutationsschritt zunächst die
Schrittweite des betrachteten Nachkommen--Individuums aus
$\mathcal{P}_j^{rek}$ mutiert, d.~h. einer zufälligen Änderung
unterworfen, und anschließend unter Verwendung dieser mutierten
Schrittweite der eigentliche Mutationsschritt des betrachteten
Individuums durchgeführt. Zunächst wird die neue Schrittweite des
zu mutierenden Nachkommen--Individuums erzeugt:
\begin{equation}\label{equ:schritt_schwefel}
\sigma_{i}^{mut}=\sigma_{i} \cdot
e^{N(0,\tau_1)+N_i(0,\tau_2)}\;\;\;\text{für}\;\;\;i=1, \dots, n
\end{equation}
mit
\begin{equation}\label{equ:tau}
\tau_1=\frac{c}{\sqrt{2 \cdot n}}, \; \; \;
\tau_2=\frac{c}{\sqrt{2 \cdot \sqrt{n}}}\; \; \;\text{und} \; \;
\; c=1 \;.
\end{equation}

Die Standardabweichungen der Normalverteilungen in
Gleichung~(\ref{equ:schritt_schwefel}) sind über $\tau_1$ und
$\tau_2$ nach Gleichung~(\ref{equ:tau}) parametrisiert, wodurch
sich der Optimierungsprozess speziell an die Gütefunktion anpassen
lässt. Dabei wirkt $\tau_1$ global für alle Komponenten eines
Individuums, $\tau_2$ wirkt individuell für jede einzelne
Komponente. Das Nachkommen--Individuum $\Ind^{rek}_i$ wird analog
Gleichung \ref{equ:zufallsvektor_rech} über:
\begin{equation}\label{equ:zufallsvektor_sch}
\Vmut=(N_1(0,\sigma_{1}^{mut}),\dots,N_1(0,\sigma_{n}^{mut}))
\end{equation}
zu
\begin{equation}\label{equ:mut_rech}
\Vx^{mut}_i=\Vx_{i}+\Vmut \;
\end{equation}
durchgeführt. Nähere Ausführungen herzu sind in \cite{Bae94, BS96}
zu finden.

\subsubsection{Selektion}\label{ssec:c2:sec2:ss4}
Der letzte Programmschritt innerhalb einer Iteration der
Optimimierung ist die Selektion. Aus der gesamten Population
werden die $\mu$ Individuen $\Ind_i$ bestimmt, die als Teil der
Elternpopulaton $\SInd_{j+1}$  der nächsten Generation überleben.
Es werden dabei zwei verschiedene Strategien unterschieden:
\paragraph{Plus-Strategie}
Bei der \((\mu+\lambda)\)--ES werden die gemäß ihrer Fitness
\(\mu\) besten Individuen aus der Vereinigungsmenge der Eltern--
und Nachkommen--Individuen gewählt.
\paragraph{Komma-Strategie}
Bei der \((\mu,\lambda)\)--ES werden die gemäß ihrer Fitness
\(\mu\) besten Individuen nur aus der Menge der \(\lambda\)
Nachkommen gewählt. Dabei ist natürlich die Bedingung \(\lambda
\geq \mu\) einzuhalten. Dabei wird sehr häufig nach dem
\emph{Eliteprinzip} selektiert, das heißt, die besten \(\mu\)
Individuen der aktuellen Population $\SInd_{j}$ werden die Eltern
der nächsten Generation $\SInd_{j+1}$. Der Fitnesswert dient somit
dabei als alleiniges Bewertungskriterium. Damit ist die Selektion
das einzige gerichtete Element der Evolutionsstrategie, da sie
vorgibt, wohin sich die Population der \(\mu\) Eltern im Suchraum
\(S\) bewegt.

Bei der Plus-Strategie bleibt somit die beste je gefundene Lösung
auf jeden Fall in der Population erhalten und wird in die
nachfolgende Generation übernommen. Somit wird die beste Lösung
von Generation zu Generation nie schlechter. Allerdings birgt die
Plus-Strategie die Gefahr, dass das Verfahren schnell gegen ein
lokales Optimum konvergiert. Eine gemäß der Fitness sehr gute
Lösung kann die gesamte Population dominieren. Liegt diese sehr
gute Lösung in der Nähe eines lokalen Optimums, dann konvergiert
mit der Zeit die gesamte Population gegen dieses lokale Optimum.
Die Varianz der Gene innerhalb der Population geht verloren und
der Suchraum wird nur noch an einer lokalen Stelle untersucht. Das
globale Optimum kann dann nicht mehr gefunden werden. Diese Gefahr
ist bei der Komma-Strategie geringer. Sie hat aber den Nachteil,
dass die beste je gefundene Lösung verloren gehen kann. Eine
ausführliche Darstellung dieser Problematik ist in \cite{SHF94} zu
finden. Strategien zur Festlegung von $\mu$ und $\lambda$ sind in
\cite{Sch87} zu finden.

Eine typischerweise bei Genetischen Algorithmen übliche
Selektionsmethode ist die sogenannte
\emph{Roulette-Wheel-Selektion} (auch \emph{Proportionale
Selektion} genannt) \cite{Spr95, Spr99}.  Hierbei geschieht die
Auswahl der Individuen der Menge $\SInd_{j+1}$ zufalls\-abhängig,
wobei die Selektionswahrscheinlichkeit für ein Individuum umso
größer ist, je besser der ihm zugeordnete Fitnesswert ist. Diese
Strategie kann in geeignet modifizierter Weise auch bei
Evolutionsstrategien eingesetzt werden.

Bei \emph{multikriteriellen} Optimierungsproblemen, wo mehrere,
meist gegenläufige Zielfunktion synchron optimert werden, besteht
die wesentliche Schwierigkeit der Selektion darin, eine in der
Regel \emph{kontinuierliche} Menge von Vektoren $\mathbf{x}$, die
Pareto-Menge $\mathcal{X}$, durch eine \emph{endliche} Anzahl von
Individuen möglichst gleichmäßig abzudecken. Bei allen bisher
bekannten Varianten der Evolutionsstrategien liegen die Defizite
darin, dass die Individuen auf einen oder mehrere ausgezeichnete
Punkte der Pareto-Menge zustreben, aber keine ausreichend
gleichmäßige Abdeckung der gesamten Pareto-Menge erreicht wird
\cite{SV01}. Verschiedene aus der Literatur bekannte
Vorgehensweisen bei multikriteriellen Optimierungsproblemen sind
in \cite{Hor97} übersichtlich zusammengefasst.



\subsection{Abbruchkriterium}
Der Abbruch des iterativen evolutionären Optimierungsprozesses
liefert die Lösungspopulation $\SInd_{end}$, wovon das
Indidividuum $\Ind_{end}^{best}$ mit dem besten Fitnesswert die
beste gefundene Lösung des Optimierungsproblems darstellt. Der
Optimierungsprozess wird beendet, wenn erstmalig mindestens eine
der folgenden Abbruchbedingungen erfüllt ist:

\begin{itemize}
  \item Eine vom Anwender vorgegebene maximale Generationenzahl $j_{max}$ wurde erreicht.
  \item Eine vom Anwender vorgegebene maximale Anzahl an Fitnessevaluierungen
  wurde durchgeführt. Insbesondere bei der Optimierung an realen Prozessen oder rechenintensiven Simulationen
  kosten diese Gütebewertungen in  vielen praktischen Anwendungsfällen viel Zeit. In vielen Fällen kann von der
  Generationenzahl ausgehend recht einfach auf die Anzahl an Gütebewertungen umgerechnet
  werden. Dies ist jedoch nicht immer möglich. Manchmal fehlen hierfür notwendige Angaben
  oder es wurde nicht mit einer konstanten Anzahl an Gütebewertungen pro Generation
  gearbeitet. Deshalb kann nur anhand der Angabe dieser Anzahl ein fairer Vergleich
  zwischen unterschiedlichen Optimierungsverfahren oder
  verschiedenen Strategievarianten vorgenommen werden.
  \item Bei der Lösung skalarer Optimierungsprobleme kann ein Schwellwert  für
  die Fitnesswerte angegeben werden. Wird dieser innerhalb des
  Optimierungsprozesses erreicht, so kann das Optimierungsproblem als gelöst angesehen
  und der Optimierungsprozess abgebrochen werden. Liegt hingegen ein multikriterielles
  Optimierungsproblem vor, so ist das Auffinden der gesamten
  Pareto-Menge -- bzw. deren möglichst genaue Approximation -- Ziel
  des Optimierungsprozesses. Da diese Pareto-Menge wohl kaum vorab
  bekannt ist, macht ein Abbruchkriterium, das auf einem
  Schwellwert für das Gütemaß basiert, bei multikriteriellen Optimierungsproblemen
  keinen Sinn.
  \item In praktischen Anwendungsfällen ist neben der Lösung des Optimierungsproblems auch der zugehörige Fitnesswert
  völlig unbekannt. In diesen Fällen bietet es sich an, für die letzten $k$ Populationen
  $\SInd_j$ jeweils den mittleren Fitnesswert $\bar{f}$ über  alle Individuen $\Ind_i^j$  zu
  ermitteln. Hat dieser Mittelwert sich nicht um einen
  vorgegebenen Schwellwert $\rho$ verbessert, kann analog zum vorherigen
  Fall abgebrochen werden.
\end{itemize}




%
% Ende von basics.tex
