%% This LaTeX-file was created by <root> Sun Apr 11 03:44:49 1999
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass[a4paper,austrian]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{babel}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}
%% Special footnote code from the package 'stblftnt.sty'
%% Author: Robin Fairbairns -- Last revised Dec 13 1996
\let\SF@@footnote\footnote
\def\footnote{\ifx\protect\@typeset@protect
    \expandafter\SF@@footnote
  \else
    \expandafter\SF@gobble@opt
  \fi
}
\expandafter\def\csname SF@gobble@opt \endcsname{\@ifnextchar[%]
  \SF@gobble@twobracket
  \@gobble
}
\edef\SF@gobble@opt{\noexpand\protect
  \expandafter\noexpand\csname SF@gobble@opt \endcsname}
\def\SF@gobble@twobracket[#1]#2{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newenvironment{lyxcode}
  {\begin{list}{}{
    \setlength{\rightmargin}{\leftmargin}
    \raggedright
    \setlength{\itemsep}{0pt}
    \setlength{\parsep}{0pt}
    \ttfamily}%
   \item[]}
  {\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newenvironment{algorithm}
\makeatother

\begin{document}


\title{Projekt Tarifmodell}


\author{Werner Weiser, Franz Wilhelmstötter}

\maketitle
\hspace{2.0cm}

\begin{description}
\item [Thema:]Optimierung der Gesprächskosten bei der Sprachtelefonie
\end{description}
\hspace{1.0cm}

\begin{description}
\item [Lehrveranstaltung:]PS Einführung in die Bioinformatik
\end{description}
\hspace{1.0cm}

\begin{description}
\item [Gruppe\#:]2
\end{description}
\hspace{1.0cm}

\begin{description}
\item [Treffpunkt:]Jeden Dienstag, um 15:30 im Büro von Roland Schwaiger
\end{description}
\hspace{1.0cm}

\begin{description}
\item [Lehrveranstaltungsleiter:]Roland Schwaiger
\end{description}
\hspace{1.0cm}

\begin{description}
\item [E-Mail:]~
\end{description}
\begin{itemize}
\item Werner Weiser: wweiser@cosy.sbg.ac.at
\item Franz Wilhelmstötter: fwilhelm@cosy.sbg.ac.at
\item Roland Schweiger: rschwaig@cosy.sbg.ac.at
\end{itemize}
\pagebreak

\tableofcontents

\begin{abstract}
Dieses Projekt beschäftigt sich mit dem Problem, aus der Vielfalt der Telekom-Anbieter,
einen, für das Gesprächsverhalten des Kunden, adäquaten Mix von Anbietern zu
finden.

Ausgehend vom Telefonieverhalten des Kunden und der Kenntnis der Tarifmodelle
der unterschiedlichen Telekom-Anbietern (Providern) wird ein Mix von Providern
errechnet, welcher die Gesamtkosten der Telefongespräche (über einen begrenzten
Zeitraum) minimiert. Die Optimierung kann jedoch nur für bereits geführte Gespräche
durchgeführt werden. Unter der Annahme, daß sich das Gesprächsverhalten zeitlich
nicht sprunghaft ändert, ist eine Extrapolation des vergangenen Telefonieverhaltens
auf das Zukünftige durchaus zulässig.
\end{abstract}

\section{Einleitung}

Seit der Liberalisierung des Telekom-Marktes in Österreich per 1.1.1998 hat
sich eine erstaunliche Vielfalt von sogenannten >>New Entrants<< etabliert
- oder ist gerade dabei, die Aufbauphase erfolgreich zu bewältigen.

Derzeit sind von der Telekom Control G.m.b.H. (TKC) mehr als 30 Lizenzen für
festnetzgebundene Sprachtelefonie erteilt. Da erfahrungsgemäß nicht jeder Anbieter
in jedem Produktbereich das beste Preis-Leistungsverhältnis hat, sind die Zeiten
des >>One-Stop-Shoppings<< endgültig vorbei und die für einen Kunden heute
optimale Lösung besteht meist aus einer Kombination von Telekom Diensleistungen
unterschiedlicher Provider, die durch moderne Least-Cost-Routertechnologie keine
Komforteinbusen für den Anwender, bei einem Einsparungspotential von 20\% bis
40\% seiner Telefonkosten, bringt.

Welche Einsparungen ein Kunde tatsächlich erzielen kann, hängt primär von seinem
spezifischen >>Call-Verhalten<< ab. Ist dies einmal im Detail analysiert,
so kann, aus der Vielfalt der am Markt befindlichen Tarife und Produkte, die
optimale Kombination für den Kunden ermittelt werden.

Das vorliegende Projekt befaßt sich mit der Erstellung von Modellen, die für
ein vorliegendes Call-Verhalten jene Kombinationen von Providern ermitteln helfen,
mit denen eine Kostenoptimierung erreicht werden kann.\cite{1}


\section{Optimierungsproblem}

Die Eingabedaten liegen in Form von sogenannten Call-Detail-Records (CDR) vor
- ein CDR setzt sich aus 1 bis m Gesprächen zusammen (vgl. Tabelle \ref{tab: CDR}).
Diese werden automatisch aufgezeichnet. Aus ihnen kann für jedes Telefonat die
Vorwahl des Anrufers und des Angerufenen, sowie Zeitpunkt und Dauer des Gespräches
entnommen werden. Auf der Seite des Telekom-Anbieters ist das genaue Tarifmodell
bekannt. Somit kann jedes Gespräch auf seine Kosten abgebildet werden.

\vspace{0.3cm}
{\begin{table}
{\centering \begin{tabular}{|c|c|c|c|c|}
\hline 
&
Startvorwahl&
Zielvorwahl&
Startzeit&
Dauer (sec)\\
\hline 
\hline 
1&
0662&
0664&
13:24&
345\\
\hline 
2&
0664&
03423&
07:45&
45\\
\hline 
3&
07746&
05674&
15:34&
32\\
\hline 
4&
07756&
08857&
18:23&
123\\
\hline 
. . .&
&
&
&
\\
\hline 
m&
02134&
09856&
09:39&
97\\
\hline 
\end{tabular}\par}


\caption{Aufbau eines typischen CDR\label{tab: CDR}}
\end{table} \par}
\vspace{0.3cm}


\subsection{Formale Problembeschreibung}

\begin{description}
\item [\( X \)]... Menge aller gültigen Telefongespräche
\item [\( x_{i} \)]... das i-te Telefongespräch
\item [\( SV \)]... Startvorwahl eines Gesprächs
\item [\( ZV \)]... Zielvorwahl eines Gesprächs
\end{description}
Aus der Startvorwahl \emph{SV} und der Zielvorwahl \emph{ZV} läßt sich die \emph{Ortszone}
des Gesprächs ableiten (z.B. Inlandszone 1 usw.)

\begin{description}
\item [\( SZ \)]... Startzeit eines Gesprächs 
\item [\( D \)]... Dauer eines Gesprächs\footnotemark{}
 (in Sekunden)
\item [\( l \)]... Länge einer Vorwahl
\item [\( CDR \)]... Gesprächsaufzeichnung eines abgeschlossenen Zeitraumes (z.B.
Monat) eines Kunden (z.B. Fa. Export G.m.b.H.)
\end{description}\footnotetext{
Die Einheit der Gesprächsdauer ist Sekunden (sec). Wird die Dauer bei einem
Provider in Takten gemessen (oder in anderer Form), so werden diese auf Sekunden
umgerechnet.
}%


\[
X=\{x_{i}\! :\! i\in \{1,...,n\}\}\]



\[
x_{i}\in \left\{ SV\times ZV\times SZ\times D\right\} \]



\[
SV,ZV\in \left\{ 0,1,2,...,9\right\} ^{l}\]



\[
SZ\in \left\{ 00:00,00:01,...,23:59\right\} \]
 
\[
D\in N\]



\[
CDR\subseteq X\]


Es ist leicht einzusehen, daß die Identifizierung des Start- und Zielortes eines
Gesprächs in eindeutiger Weise über die entsprechenden Vorwahlkennungen erfolgen
kann. Diese beiden Angaben sind somit ausreichend, um die, für die Kosten wesentliche,
Ortszone des Gesprächs zu ermitteln.

\begin{description}
\item [\( P \)]... Menge der Provider
\item [\( p \)]... Anzahl aller gültigen Tarifmodelle
\item [\( T_{p_{i}} \)]... Menge der Tarifmodelle von Provider \( i\in \left\{ 1,...,\left| P\right| \right\}  \)
\item [\( Y \)]... Menge der gültigen Tarifmodelle
\item [\( K \)]... normierte Gesprächskosten
\item [\( u_{i} \)]... Fixkosten des \emph{i}-ten Tarifmodells \footnotemark{}
 
\item [\( y_{i} \)]... normierte Gesprächskosten des \emph{i}-ten Tarifmodells
\end{description}\footnotetext{
Bei der Anmeldung muß dem Provider bekanntgegeben werden, mit welchem Modell
die Gespräche abgerechnet werden sollen; z.B. Fun, Business, Start usw.
}%


\[
Y=\left\{ \left( y_{i}\! ,\! u_{i}\right) \! :\! i\in \left\{ 1,...,p\right\} \right\} \]



\[
y_{i}\! :\! \left\{ SV\times ZV\times SZ\right\} \! \rightarrow \! K\]


Ein Tarifmodell setzt sich aus der Funktion \( y_{i} \) ,die jedem Telefonat
\( x_{i} \) \emph{(die Dauer des Gesprächs spielt bei den relativen Kosten
keine Rolle)} einen normierten Wert\footnote{
Kosten (ATS/sec)
} zuordnet, und den gesprächsunabhängigen Kosten \( u_{i} \) zusammen.

\( \left| Y\right| =\sum ^{\left| P\right| }_{i=1}\left| T_{p_{i}}\right|  \)

Die Anzahl der insgesamt verfügbaren Tarifmodell ist natürlich die Summe der
Anzahl der von jedem Provider angebotenen Modelle.

Die normierten Gesprächskosten (z.B. 3,43ATS/sec) mit den Fixkosten\footnote{
Kosten die fällig werden, selbst wenn kein einziges Gespräch geführt worden
ist
} bilden in Kombination ein Tarifmodell. Die relativen Kosten werden hier als
Funktion aufgefaßt, wobei jeder Startvorwahl, Zielvorwahl und Startzeit in eindeutiger
Weise Gesprächskosten (ATS/sec) zugeordnet werden. Das Problem, daß ein Gespräch
über mehrere >>Zeitzonen<<\footnote{
Bei der Berechnung der Kosten spielt nicht nur die zu überbrückende Entfernung
eine Rolle, sondern auch die Tageszeit zu der ein Gespräch geführt wird. Es
wird angenommen, daß vom Anbieter, neben den Ortszonen (Inlandszone 1 usw.),
auch eine entsprechende Einteilung in \emph{Zeitzonen} erfolgt.
} geführt werden kann, wird erst bei der Bestimmung der gesamten Gesprächskosten
berücksichtigt. Tabelle \ref{tab: Tarifmodell} zeigt, wie die Funktion \( y_{i} \)
dargestellt werden kann - bei einer vollständigen Darstellung wäre die \emph{Tabelle}
dreidimensional.

\begin{table}
{\centering \begin{tabular}{|c||c|c|c|c|}
\hline 
&
\multicolumn{4}{|c|}{Zeitzone (Startzeit)}\\
\hline 
Ortszone (Vorwahl)&
00:00 &
01:00 &
. . .&
23:00 \\
\hline 
\hline 
\( ZV_{1} \)&
\( K_{1,1} \)&
\( K2 \)&
&
\( K_{1,24} \)\\
\hline 
\( ZV_{2} \)&
\( K_{2,1} \)&
\( K_{2,2} \)&
&
\( K_{2,24} \)\\
\hline 
. . .&
&
&
. . .&
\\
\hline 
\( ZV_{k} \)&
\( K_{k,1} \)&
\( K_{k,2} \)&
&
\( K_{k,24} \)\\
\hline 
\end{tabular}\par}


\caption{Eine Darstellungsform für \protect\( y_{i}\protect \), unter der Annahme einer
festen Startvorwahl\label{tab: Tarifmodell}.}
\end{table} 


\subsubsection{Optimierungsfunktion}

\begin{description}
\item [\( f \)]... Diese Funktion bestimmt den optimalen Providermix
\item [\( N \)]... Menge der Tarifmodelle, die für die Optimierung berücksichtigt
wird\footnotemark{}

\item [\( M \)]... Menge der Tarifmodelle, mit denen eine Minimierung der Gesprächskosten
erreicht werden kann.
\item [\( a \)]... eine naürliche Zahl, die festlegt, aus wievielen Tarifmodellen
der >>optimale Providermix<< maximal bestehen soll \footnotemark{}
.
\end{description}\addtocounter{footnote}{-1}\footnotetext{
Welche Tarifmodelle für die Optimierung letztendlich verwendet werden, kann/muß
bei der Optimierungsfunktion explizit angegeben werden.
}%
\stepcounter{footnote}\footnotetext{
Diese Einschränkung soll, wenn es notwendig ist, die Rechenzeit für die Optimierung
begrenzen.
}%


\[
f\! :\! \left\{ N,CDR,a\right\} \! \rightarrow \! M\]


\( N\subseteq Y \)

\( M\subseteq N \)

\( 1\leq a\leq \left| N\right|  \)



Mit der obigen Definition der Funktion \( f \), ist festgelegt mit welchen
Eingabedaten der optimale Providermix bestimmt werden soll. Die interne Arbeitsweise
(Algorithmus) der Funktion muß jedoch noch festgelegt werden. 

Die Aufgabe der Funktion besteht darin, für vorhandene CDRs, einen Providermix
mit minimalen Gesprächskosten zu bestimmen. Soll das Optimum (Minimum) der Gesprächskosten
mittels \emph{Brute Force} ermittelt werden, so müssen zu diesem Zweck \emph{sehr
viele} Möglichkeiten berücksichtigt werden. Tabelle \ref{tab: Providermix}
zeigt eine Auflistung \emph{aller} möglichen Zuordnungen eines Gesprächs zu
einem Tarifmodell:

\vspace{0.3cm}
{\begin{table}
{\centering \begin{tabular}{|c|c|c|c|c|c|}
\hline 
\( K_{1} \)&
\( x_{1},y_{1} \)&
\( x_{2},y_{1} \)&
\( x_{3},y_{1} \)&
...&
\( x_{m},y_{1} \)\\
\hline 
\( K_{2} \)&
\( x_{1},y_{2} \)&
\( x_{2},y_{1} \)&
\( x_{3},y_{1} \)&
&
\( x_{m},y_{1} \)\\
\hline 
\( K_{3} \)&
\( x_{1},y_{1} \)&
\( x_{2},y_{2} \)&
\( x_{3},y_{1} \)&
&
\( x_{m},y_{1} \)\\
\hline 
\( K_{4} \)&
\( x_{1},y_{1} \)&
\( x_{2},y_{1} \)&
\( x_{3},y_{2} \)&
&
\( x_{m},y_{1} \)\\
\hline 
...&
&
&
&
...&
\\
\hline 
\( K_{p} \)&
\( x_{1},y_{1} \)&
\( x_{2},y_{1} \)&
\( x_{3},y_{1} \)&
&
\( x_{m},y_{2} \)\\
\hline 
\( K_{p+1} \)&
\( x_{1},y_{2} \)&
\( x_{2},y_{2} \)&
\( x_{3},y_{1} \)&
&
\( x_{m},y_{1} \)\\
\hline 
...&
&
&
&
...&
\\
\hline 
\( K_{p^{m}} \)&
\( x_{1},y_{p} \)&
\( x_{2},y_{p} \)&
\( x_{3},y_{p} \)&
&
\( x_{m},y_{p} \)\\
\hline 
\end{tabular}\par}


\caption{Auflistung der Möglichkeiten, die jedem der \emph{m} Gespräche, eine Providermix
zuzuordnen.\label{tab: Providermix} }

In den Kosten \( K_{i} \) sind noch nicht die Fixkosten (Grundgebühr) der Provider
enthalten. Um die \emph{gesamten} Kosten zu bestimmen, müssen zu jedem \( K_{i} \)
die Grundgebühren, aller für den \emph{i}-ten Mix verwendeten Tarifmodelle,
addiert werden.
\end{table} \par}
\vspace{0.3cm}

Aus dem Minimum der \( p^{m} \)\label{sec: Gr=F6=DFe des Suchraumes} verschiedenen
Kosten, kann man direkt den optimalen Providermix ablesen. \emph{Da die Kostenfunktion
beliebig ist, ist es nicht möglich davon auszugehen, daß sich der optimale Providermix
aus allen verfügbaren Providern zusammensetzt! }

Werden die Kosten einer Providerkombination berechnet, so wird auf jeden Fall
die Grundgebür des Anbieters hinzugerechnet, unabhängig davon ob ein Gespräch
über diesen Provider geführt wird oder nicht.

Selbst wenn bei einem sehr großen CDRs (\( m>10^{5} \)) - die Anzahl der Provider
ist nur vorerst auf 30 \footnote{
Da einem Provider mehrere Tarifmodelle zugeordnet sein könne, multipliziert
sich diese Zahl noch einmal.
} beschränkt - eine vorherige Aggregation der Daten vorgenommen wird, steigt
die Anzahl der erforderlichen Rechenschritte sehr schnell über eine erträgliche
(berechenbare) Grenze.


\subsection{Algorithmus der Kostenfunktion}

Nachdem die Form der Optimierungsfunktion festgelegt wurde, soll nun ein Algorithmus
entwickelt werden, der dieser Form entspricht. Es wird zunächst von einer erschöpfenden
Suche (Brute Force) ausgegangen. Das Ergebnis soll als Grundlage für die Fittnesfunktion
des GA's dienen. Aus diesem Grund wird der Formulierung der Algorithmen entsprechend
ausführlich gestaltet:

Zunächst werden die Kosten eines einzelnen Gespräches mit einem bestimmten Tarifmodell
ermittelt. 

\begin{lyxcode}
\emph{/{*}{*}}

\emph{/{*}Berechnet~die~Kosten~eines~Gesprächs~}

\emph{/{*}mit~einem~bestimmten~Tarifmodell~}

\emph{{*}/}

\textbf{FUNCTION}~call\_cost(\textbf{INT}:~GesprächNummer,~

~~~~~~~~~~~~~~~~~~~\textbf{INT}:~TarifmodellNummer,

~~~~~~~~~~~~~~~~~~~\textbf{GESPRÄCH\_ARRAY}(n,m):~cdr,

~~~~~~~~~~~~~~~~~~~\textbf{TARIFMODELL\_ARRAY}(k,l,i):~modell)~

~~~~~~~~\textbf{~RETURN~FLOAT~IS}

\textbf{BEGIN}

~\textbf{~VORWAHL}:~StartVorwahl,~ZielVorwahl;

~~\textbf{INT}~OrtsZone;

~~\textbf{INT}~ZeitZone;

~~\textbf{INT}~Dauer;

~~\textbf{FLOAT}~Kosten~=~0;

~~~~~~

~~StartVorwahl~=~cdr(GesprächNummer,~1);

~~ZielVorwahl~~=~cdr(GesprächNummer,~2);

~~Dauer~=~cdr(GesprächNummer,~3);

~~~~~~~~~

~~\emph{/{*}Ermittlung~der~kleinsten~gemeinsamen~Ortszone~aus}

\emph{~~~~Startvorwahl~und~Zielvorwahl~{*}/}

~~OrtsZone~=~to\_ortszone(StartVorwahl,~ZielVorwahl);

~~~~~~~~~

~~\emph{/{*}Im~ARRAY~modell~sind~die~normierten~Kosten~aller}

\emph{~~~~verfügbaren~Tarifmodelle~gespeichert.~{*}/}

~~~~~~~~~Kosten~=~modell(TarifmodellNummer,~OrtsZone,~ZeitZone)~

~~~~~~~~~~~~~~~~{*}~Dauer;

~~~~~~

~~~~~~~~~\textbf{RETURN}~kosten;~

\textbf{END}~call\_cost;
\end{lyxcode}
Der Datentyp \textbf{TARIFMODELL\_ARRAY} enthält alle verfügbaren Tarifmodelle.
Mit dem ersten Index \emph{k} werden die verschiedenen Tarifmodelle durchlaufen,
der zweite Index \emph{l} bestimmt die Ortszonen und \emph{i} die Zeitzonen.
Bei all diesen Operationen wird davon ausgeangen, daß die Tarifmodelle auf einheitliche
Orts- und Zeitzonen umgerechnet wurden. Der Datentyp \textbf{GESPRÄCH\_ARRAY}
enthält eine gesamten CDR (Menge von Gesprächen). 

\begin{lyxcode}
\emph{/{*}{*}}

\emph{/{*}Berechnet~die~niedrigsten~Kosten~eines~CDR~}

\emph{/{*}für~die~vorgegeben~Menge~von~Tarifmodellen}

\emph{{*}/}~

\textbf{FUNCTION}~cdr\_cost(\textbf{FIXKOSTEN\_VECTOR}(i):~VectorGrundKosten,

~~~~~~~~~~~~~~~~~~\textbf{TARIFMODELL\_ARRAY}(k,l,i):~modell,

~~~~~~~~~~~~~~~~~\textbf{~GESPRÄCH\_ARRAY}(n,m):~cdr,

~~~~~~~~~~~~~~~~~~\textbf{TARIFMODELL\_VECTOR}(i):~tarifmodelle)~

\textbf{~~~~~~~~~RETURN~FLOAT~IS}

\textbf{BEGIN}

~~\textbf{FLOAT}~GrundKosten~=~0;~~~~~~~~~~~~~\emph{//Grundgebühr}

~~\textbf{FLOAT}~GesamtKosten~=~0;~~~~~~~~~~~~

~~\textbf{FLOAT}~GesamtKostenTemp1~=~10E50;~~~

~~\textbf{FLOAT}~GesamtKostenTemp2~=~10E50;

~~~~~~~~~

\emph{/{*}Die~Grundkosten~müssen~für~alle~für~die~Optimierung}

\emph{~~verwendeten~Tarifmodelle~berücksichtigt~werden.}

\emph{~~Die~Indizes~von~FIXKOSTEN\_VECTOR(i)~und~TARIFMODELL\_ARRAY}

\emph{~~sind~aufeinander~abgestimmt,~d.h.~gleicher~Index,~}

\emph{~~gleiches~Tarifmodell{*}/}

\textbf{FOR}~i~\textbf{IN}~1..VectorGrundKosten'\textbf{length}~\textbf{LOOP}

~~GrundKosten~=~GrundKosten~+~VectorGrundKosten(i);

\textbf{END~LOOP};~~

GesamtKosten~=~GrundKosten;

~~~~~~~~~

\emph{/{*}Durchlaufen~der~einzelnen~Gespräche{*}/}

\textbf{FOR}~i~\textbf{IN}~1..cdr(1)'\textbf{length}~\textbf{LOOP}

~\emph{~/{*}Durchlaufen~der~(berücksichtigten)~Tarifmodelle}

~~~\textbf{FOR}~j~\textbf{IN}~1..tarifmodelle'\textbf{length}~\textbf{LOOP}

~~~~~GesamtKostenTemp1~=~call\_cost(i,~tarifmodelle(j),~cdr,~modell);

~~~~~\textbf{IF}~GesamtKostenTemp1~<~GesamtKostenTemp2~\textbf{THEN}

~~~~~~~GesamtKostenTemp2~=~GesamtKostenTemp1;

~~~~\textbf{~END~IF};~~~~

~~~\textbf{END~LOOP};~

~~~GesamtKosten~=~GesamtKosten~+~GesamtKostenTemp2;~~

\textbf{END~LOOP};

~~~~~~~~~~~

\textbf{RETURN}~GesamtKosten;

\textbf{END}~cdr\_cost;
\end{lyxcode}
Bei dieser Funktion wird davon ausgegangen, daß die gesamten Gesprächskosten
genau dann minimiert werden, wenn jedes einzelne Gespräch mit dem billigsten
Tarifmodell geführt wird. Der Parameter \emph{tarifmodelle} enthält die Indizes
der zu berücksichtigenden Tarifmodelle. 

\begin{lyxcode}
\emph{/{*}{*}}

\emph{/{*}Ermittelt~den~besten~Providermix~aus~allen~Tarifmodellen}

\emph{{*}/}

\textbf{FUNCTION}~best\_modell(\textbf{INT}:~a)~\textbf{RETURN~BESTMODELL\_VECTOR~IS}

\textbf{BEGIN}

\textbf{INT}:~n;~//Anzahl~aller~Tarifmodelle

FLOAT:~kosten~=~10E50;

FLOAT:~kostenTemp~=~10E50;

\textbf{FIXKOSTEN\_VECTOR}(i):~VektorGrundKosten;

\textbf{TARIFMODELL\_ARRAY}(k,l,i):~modell;

\textbf{GESPRÄCH\_ARRAY}(n,m):~cdr;

\emph{/{*}dieser~Vektor~legt~fest,~welche~Tarifmodelle~für~die~}

\emph{~~Optimierung~verwendet~werden~sollen{*}}/

\textbf{TARIFMODELL\_VECTOR}(i,k):~tarifmodelle;~

\emph{/{*}Enthält~die~Indizes~des~besten~Tarifmodellmixes{*}/}

\textbf{BESTMODELL\_VECTOR}(i):~best\_mix;~

~

n~=~modell(1)'\textbf{length};

~

\emph{/{*}Ist~a~die~maximale~Anzahl~der~zu~berücksichtigenden~}

\emph{~~Tarifmodelle,~so~müssen~alle~i-elementigen~(1<=~i~<=a)}

\emph{~~Teilmengen~aller~Tarifmodelle~berücksichtigt~werden{*}/}~

\textbf{FOR}~i~\textbf{IN}~1..a~\textbf{LOOP}

~~tarifmodelle~=~getSubSets(n,i);~

~~\textbf{FOR}~j~\textbf{IN}~1..tarifmodelle(1)'\textbf{length~LOOP}

~~~~kosten~=~cdr\_cost(VektorGrundKosten,

~~~~~~~~~~~~~~~~~~~~~~modell,~cdr,~tarifmodelle(j));

~~~~\textbf{IF}~kosten~<~kostenTemp~\textbf{THEN}

~~~~~~best\_mix~=~tarifmodelle(j);

~~~~~~kostenTemp~=~kosten;

~~~~\textbf{END~IF};

~~\textbf{END~LOOP};

\textbf{END~LOOP};

~

\textbf{RETURN}~best\_mix;

\textbf{END}~best\_modell;~~
\end{lyxcode}
Die Funktion \emph{best\_modell} verwendet die beiden vorher definierten Funktion
um den besten Tarifmodellmix zu erstellen. Dieser Algorithmus berücksichtigt
dabei alle Teilmengen aus der Menge der Tarifmodelle. Die hier verwendete Funktion
getSubSets bestimmt alle i-elementigen Teilmengen einer n-elementigen Menge
(dabei werden die Elemente der Menge von 1 bis n durchnummeriert), das Ergebnis
wird in einem Array der Dimension \( \left[ \left( \begin{array}{c}
n\\
i
\end{array}\right) ,i\right]  \) gespeichert. Da die Umsetzung dieser Funktion nicht sofort einsichtig ist,
wird die JAVA-Klasse angegeben, die diese Funktion enthält. 

\begin{lyxcode}
\textbf{public~class}~subset

\{

\emph{/{*}{*}}

\emph{/{*}Auf~die~Menge~aller~k-elementigen~Teilmengen}

\emph{/{*}einer~n-elementigen~Menge~wird~eine~natürliche}

\emph{/{*}Ordnung~definiert.~Anhand~dieser~Ordnung,~kann}

\emph{/{*}ein~Nachfolger~ermittelt~werden.}

\emph{{*}/}

\textbf{private~static}~\textbf{int}{[}{]}~nachfolger(\textbf{int}{[}{]}~vorgaenger,~\textbf{int}~n,~\textbf{int}~k)

\{

\textbf{int}{[}{]}~vektor\_temp~=~\textbf{new~int}{[}k{]};

vektor\_temp~=~vorgaenger;

\textbf{if}(vorgaenger{[}0{]}~<~n)

\{

~~vektor\_temp{[}0{]}~=~vorgaenger{[}0{]}~+~1;

~~\textbf{return}~vektor\_temp;

\}

\textbf{for}(\textbf{int}~i~=~1;~i~<~k;~i++)

\{

\textbf{~~if}(vorgaenger{[}i{]}~+~2~<=~vorgaenger{[}i-1{]})

~~\{

~~~~vektor\_temp{[}i{]}~=~vorgaenger{[}i{]}~+~1;

~~~~for(\textbf{int}~j~=~i;~j~>~0;~j-{}-)

~~~~\{

~~~~~~vektor\_temp{[}j-1{]}~=~vektor\_temp{[}j{]}~+~1;

~~~~\}

~~~~\textbf{return}~vektor\_temp;

~~\}

\}

\textbf{return~null};

\}

~

\textbf{private~static~int}~binom(\textbf{int}~n,~\textbf{int}~k)~

\{

\textbf{if}(k~==~1)

\{

~~\textbf{return}~n;

\}

\textbf{if}((k~==~0)~||~(k~==~n))

\{

~~\textbf{return}~1;

\}

\textbf{return}~(binom(n-1,k-1)~+~binom(n-1,k));

\}

~

\textbf{public~static~int}{[}{]}{[}{]}~getSubSets(\textbf{int}~n,~\textbf{int}~k)

\{

\textbf{int}{[}{]}{[}{]}~result~=~\textbf{new~int}{[}binom(n,~k){]}{[}k{]};

\textbf{for}(\textbf{int}~i~=~0;~i~<~k;~i++)

\{

~~\textbf{result}{[}0{]}{[}i{]}~=~i~+~1;

\}

\textbf{for}(\textbf{int}~i~=~1;~i~<~binom(n,~k);~i++)

\{

~~result{[}i{]}~=~nachfolger(result{[}i-1{]},~n,~k);

\}

\textbf{return}~result;

\}

~

\textbf{public~static~void}~main(\textbf{String}{[}{]}~args)

\{

\}

\}
\end{lyxcode}

\section{Genetische Algorithmen}


\subsection{Ein kleiner biologische Überblick: Ursachen der Evolution\label{sec: biologische =DCberblick}}

Die Frage nach den Faktoren, die die Evolution hervorrufen, ist im Prinzip von
Darwin im Jahr 1859 beantwortet worden. Darwin läßt durch seine Selektionstheorie
die Anpassung sekundär aus einer ungerichteten Variabilität entstehen, die -
wie man heute weiß - auf Mutation zurückzuführen ist. Durch die selektive Bevorzugung
werden bestimmte Varianten durch die Umweltfaktoren ausgelesen. Die Selektion
des jeweils Geeigneten wirkt, wie Experimente zeigen, sehr schnell. Es ist keineswegs
nötig, daß nur bestimmte Varianten leben bleiben und alle anderen sofort durch
den Kampf ums Dasein vernichtet werden. Es genügt, wenn die Überlebensrate bzw.
die durchschnittliche Nachkommenzahl bestimmter Varianten nur um ein geringeres
höher ist als die anderer, um sich schließlich in der Population durchzusetzen.Durch
Konkurenzzuchten im gleichen Milieu ist vielfach nachgewiesen, daß Erbstämme
einer Art meistens verschiedene Vitalität besitzen, deren Ausmaß durch Umweltfaktoren
beeinflußt wird. In der Natur sind fast alle Populationen aus zahlreichen erbverschiedenen
Varianten zusammengesetzt, so daß die Selektion wirken kann. Je reichhaltiger
an Erbanlagen eine Population ist, desto intensiver kann Selektion umbildend
wirken.

Die moderne Evolotionstheorie unterscheidet sieben Evolutionsfaktoren:\footnote{
Die erstem vier Faktoren werden bei genetischen Algorithmen verwendet.
}

\begin{enumerate}
\item Mutation
\item Gen-Transfer
\item Rekombination
\item Selektion
\item Populationswellen
\item Isolation
\item Anmidation
\end{enumerate}
Mutation und Gen-Transfer schaffen neues Erbmaterial. Mutationen sind durch
verschiedene Umwelteinflüsse hervorgerufene Erbveränderungen, die meist negative
Konsequenzen für den Organismus haben. Unter Gentransfer versteht man die Einfügung
von neuem genetischen Material in einen Genotyp.\footnote{
Gesamtheit der Erbfaktoren eines Lebewesens
}

Rekombination ist das Entstehen neuer Genotypen durch Neuordnung von Erbfaktorne.
Im Sinne der Mendelschen Gesetze kommt es zur Neuverteilung der Chromosomen
im Zuge des crossing over\footnote{
In der Bioinformatik ist der Begriff \emph{Crossover} gebräuchlicher
} besteht außerdem die Möglichkeit des interchromosomalen Austausches. Während
die Bedeutung des Gen-Transfers für die Evolution noch nicht abgeschätzt werden
kann, besteht über Mutation und Rekombination prinzipiell Klarheit: Sie sind
die Quelle ständig neu entstehender Varianten, die sich in der Selektion bewähren
können.

Bei der Selektion handelt es sich um einen statistischen Vorgang, der auf der
unterschiedlichen Eignung der Individuen basiert: Wer stärker als das Durchschnittsindividuum
zur Fortpflanzung\footnote{
Bei genetischen Algorithmen wird die >>stärke<< eines Individuums durch die
Fitnessfunktion bestimmt. Wie sich dieser dann >>fortpflanzt<< wird später
näher erklärt
} kommt, sichert seinen Genen eine größere Verbreitung als diese.

Unter Populationswellen versteht man starke Bestandsschwankungen in einer Population.
Die Geschwindigkeit, mit der sich genetische Veränderungen durchsetzen, ist
in kleinen Populationen besonders hoch. Dieses als genetische Drift bezeichnete
Phänomen ist ebenfalls aus der Resistenzentstehung bekannt: Eingriffe in den
Massenwechsel von Schadorganismen mit Insektiziden führt zur starken Verringerung
der Population und zu einem anschließenden Neuaufbau einer selektiven Restgruppe
mit Resistenzfaktoren.

Kommt es zur Isolation besonderer Genotypen, so können sie zum Ausgangspunkt
für abweichende Populationen werden.

Ähnlich ist die Situation bei der Annidation, bei der einzelne Varianten in
einem bestimmten Lebensbereich besonders günstige Lebensverhältnisse finden.\cite{2}


\subsection{Einleitung }

Bei Genetischen Algorithmen (GA) handelt es sich um eine Klasse von Algorithmen,
die sich Optimierungsstrategien\footnote{
Optimierung kann man als den Versuch auffassen, Eigenschaften eines Systemes
in geschickter Weise so zu verändern, daß eine gestellte Aufgabe besser oder
optimal bewältigt oder sogar gelöst werden kann.
} von biologischen Systemen abschauen (siehe Kapitel \ref{sec: biologische =DCberblick};
Ursachen der Evolution), diese abstrahieren und auf die jeweilige Problemstellung
anpassen.

So ergeben sich neue Ansätze für viele konventionell schwierig oder gar nicht
handhabbare Optimierungsprobleme, die so in akzeptabler Zeit lösbar werden.
Die Leistungsfähigkeit der GA's läßt sich durch folgende Überlegung verstehen:
Jede parametrisierbare Optimierungsaufgabe, bei der jedem Parametersatz ein
Wert zugewiesen werden kann, der für die Qualität der Optimierung steht ist
mittels GA lösbar. Die Rechenzeiten können jedoch bei vielen Ausgangsdaten,
vielen Parametern bzw. komplizierten Modellen Tage dauern; für viele Anwendungen
zu lange. Optimierungsprobleme treten in nahezu allen Bereichen der Naturwissenschaften,
Technik und Logistik auf. Allerdings ist die Bandbreite der Probleme sehr groß,
und die Anzahl der mittlerweile existierenden Verfahren bzw. Algorithmen sehr
groß und nahezu unüberschaubar. 

Optimierungsprobleme können in drei Klassen eingeteilt werden:

\begin{enumerate}
\item Parameteroptimierung: Probleme bei denen bspw. Parameter eines mathematischen
Modells zu optimieren sind.
\item Subset-Selection: Probleme, bei denen aus einer Menge eine Untermenge ausgewählt
werden muß. 
\item Kombinatorische Probleme: Probleme, bei denen die Anordnung von Elementen eine
Rolle spielt. Ein gängiges Beispiel ist das sogenannte traveling salesman Problem\footnotemark{}
. 
\end{enumerate}\footnotetext{
Bei dieser Aufgabe soll die optimale Anordnung von Städten auf einer Reiseroute
bestimmt werden. Als optimal könnte bspw. die kürzeste Strecke definiert werden,
oder auch die Strecke, die die geringsten Kosten verursacht, etc. Probleme dieser
Kategorie werden auch mit dem Begriff Sequencing (SEQ) bezeichnet.
}%

\begin{description}
\item [Parameter:]Unter einem Parameter (=Variable) wird eine veränderliche Größe
des betrachteten Systems verstanden, dessen Veränderung in irgendeiner Weise
mit dem Ergebnis einer Qualitätsfunktion in Zusammenhang steht.
\item [Qualitätsfunktion:]Eine Qualitätsfunktion\footnotemark{}
 ist ein Kriterium, das die qualitative Beurteilung des betrachteten Systemes
in Abhängigkeit von den Parametern erlaubt.
\item [Suchraum:]Unter einem Suchraum wird der Raum verstanden, den die Parameter
aufspannen.
\end{description}\footnotetext{
In weiterer Folge wird die Qualitätsfunktion auch als Fitnessfunktion bezeichnet.
}%

Ein grundlegendes Problem, das mit der Auswahl geeigneter Optimierungsstrategien
in engem Zusammenhang steht, ist die Größe des Suchraumes. Zur Veranschaulichung
der Problematik wird die Größe anhand eines einfachen Beispiels gezeigt:

Es soll ein System mit zwei Parametern optimiert werden, wobei~ beide Parameter
(a1; a2) im Bereich:


\[
100\geq a_{n}\geq 0,1\, ;Schrittweit=0,1\]


liegen. D.h. für jeden Parameter gibt es in diesem Genauigkeitsbereich 1000
mögliche Werte die er annehmen kann. Der Suchraum, der durch die beiden Parameter
aufgespannt wird, umfaßt somit \( 1000\times 1000=10^{6} \) Möglichkeiten.
Sollte noch ein dritter Parameter mit denselben Eigenschaften dazukommen, so
würde die Anzahl der Möglichkeiten um drei Zehnerpotenzen steigen. 

Ausgehend von diesen Überlegungen erscheint es einsichtig, daß ein Durchprobieren
aller möglichen Werte nur in sehr niedrig-dimensionalen Räumen möglich ist.
Sobald die Anzahl der Dimensionen, oder die erforderliche Präzision größer wird,
scheitern die Methoden aufgrund der wachsenden Rechenzeiten\footnote{
vgl. dazu die Problemstellung des Findens eines optimalen Tarifmodellmixes/Profidermixes;
Seite \pageref{sec: Gr=F6=DFe des Suchraumes}
}. 

Bei einfachen Problemstellungen kann also die Brute-Force Methode durchaus eine
angemessene Strategie sein, zumal die Garantie besteht, die optimale Lösung
zu finden, bei größeren Systemen jedoch stößt dieser Ansatz sehr schnell an
die Grenzen des berechenbaren, und andere Verfahren müssen angewandt werden.


\subsection{Konventionelle Suchmethoden}


\subsubsection{Monte-Carlo -Methode : Zufalls-Suche}

Eine Strategie, die zur Suche in von Parametern aufgespannten Suchräumen denkbar
ist, ist eine Suche, die auf reinem Zufall basiert. Die Vorgangsweise ist eine
sehr einfache:

Es werden ein gewisse Anzahl von Punkten zufällig im Suchraum ausgewählt und
die >>Höhe<< (Funktionswert) an diesen Punkten gemessen. Der \emph{beste}
Wert wird ausgewählt und als Optimum verwendet. Es ist klar, daß die Wahrscheinlichkeit
mit diesem Algorithmus ein globales Optimum zu finden äußerst gering ist, bzw.
der Aufwand extrem hoch wird. Allerdings können solche Strategien verwendet
werden, um die Rauhigkeit oder auch Steilheit in bestimmten Bereichen der Suchlandschaft
abzuschätzen. Der Vorteil dieser Methode ist, daß die Suche nicht gefahr läuft
nur ein lokales Optimum zu ermitteln.


\subsubsection{Hill Climbing}

Eine sofort einsichtige Strategie ein zumindest lokales Optimum in einem Suchraum
zu finden, ist, sich von einem beliebig gewählten Punkt immer in Richtung der
größten Steigung (zum lokalen Optimum) zu orientieren. So ist garantiert, zumindest
das nächstliegende lokale Optimum zu finden. Hierzu wird der SIMPLEX-Algorithmus
verwendet.

Der SIMPLEX Algorithmus verwendet die kleinste geschlossene geometrische Figur,
die ausreicht um die Steigung in einem Gebiet zu ermitteln, eben den sogenannten
SIMPLEX: Im Falle einer zwei-dimensionalen Suchlandschaft (= zwei Parameter)
ist dies ein Dreieck, im drei-dimensionalen Fall eine Pyramide. Wird nun z.B.
ein Dreieck in eine zwei-dimensionale Landschaft gelegt so kann man anhand der
Höhe der drei Eckpunkte des Dreiecks leicht die annähernde Richtung des nächsten
Gipfels abschätzen. Die Suche nach dem Maximum oder Minimum erfolgt prinzipiell
nach dem folgenden Schema :

\begin{enumerate}
\item Ein initiales SIMPLEX (also im zwei-dimensionalen Fall ein Dreieck) wird an
zufälliger Position in den Suchraum gelegt. 
\item Die Höhe der Eckpunkte wird ermittelt. 
\item Aus den Höhen der Eckpunkte kann nun die ungefähre Richtung des Optimums ermittelt
werden. Ein neues SIMPLEX, das sich näher dem Optimum befindet wird ermittelt. 
\item Der Eckpunkt mit der schlechtesten Bewertung wird entlang der Verbindungslinie
der besten Punkte gespiegelt. Der schlechteste Punkt im SIMPLEX wird durch den
neuen (gespiegelten) Punkt ersetzt, wodurch ein neues SIMPLEX entsteht. 
\item Wiederholung ab Punkt 2. Sobald das Optimum erreicht ist, wird diese Prozedur
abgebrochen.
\end{enumerate}
Die Einschränkungen der Hill-Climbing Algorithmen stellen sich folgendermaßen
dar:

\begin{itemize}
\item Es besteht keine Garantie ein globales Optimum zu finden, da immer nur das nächst
gelegene Optimum gefunden wird.
\end{itemize}
Eine bessere Strategie ist,mehrere Suchläufe mit unterschiedlichen Ausgangspunkten
durchzuführen. Wird immer dasselbe Optimum gefunden, so ist es wahrscheinlich
, das globale Optimum gefunden zu haben. Sicherheit kann auch so nicht erzielt
werden.

Trotzdem sind Hill-Climbing Strategien in vielen Fällen eine günstige Wahl:

\begin{itemize}
\item Wenn die Bestimmung einzelner Werte sehr aufwendig oder teuer ist,
\item die Beschaffenheit der Suchlandschaft und ein günstiger Ausgangspunkt bekannt
sind, bzw. die Suchlandschaft so einfach ist (nur ein Optimum), daß dieses Verfahren
als ausreichend betrachtet wird, 
\item man sich sicher ist, bereits nahe am gesuchten (globalen) Optimum zu sein, und
nur die letzten Schritte zum Optimum fehlen, 
\item das Suchen des globalen Optimums nicht möglich oder nicht notwendig ist (z.B.
im Falle der Optimierung von Ausbeuten chemischer Prozesse, wo schon eine deutliche
Verbesserung zum nächsten lokalen Optimum als Erfolg gewertet werden kann).
\end{itemize}

\subsection{Biologische Mechanismen }

Diese wurden bereits im einleitenden Kapitel \ref{sec: biologische =DCberblick}
dargelegt, soll an dieser Stelle, jedoch noch kurz wiederholt werden.

\begin{itemize}
\item Selektion: Unter Selektion versteht man die Bewertung der Fähigkeiten eines
Individuums in Wechselwirkung mit seiner Umwelt und der daraus resultierenden
Fortpflanzung der am besten angepaßten Individuen. Mit anderen Worten, diejenigen
Individuen, die durch ihre Eigenschaften über eine bessere Überlebensfähigkeit
in der jeweiligen Umwelt verfügen, werden sich stärker vermehren und somit auch
ihre genetische Information.
\item Paarung, Crossover: Paarung und Fortpflanzung laufen immer unter Informationsaustausch
zwischen den Chromosomen/Genen der Eltern-Individuen ab. Dieser Informationsaustausch
findet in dem genetischen Mechanismus der Crossover genannt wird statt, wobei
der Informationsträger in der Natur Makromoleküle, nämlich die \emph{Desoxyribonucleinsäure}
(DNS, DNA) sind. Unter dem Selektionsdruck sollten die fähigsten Individuen
überleben.
\item Mutation: Durch Mutation können neue Strukturen entstehen. Eigenschaften also,
die noch nicht in der Erbsubstanz der Art zu finden sind! Aufgrund der Eigenschaften
der Codierung der Erbinformation in einem Makromolekül, der DNS , kann es zu
Fehlern beim Kopieren, durch Einwirkung von Strahlung, chemischen Substanzen,
etc. kommen. Diese Fehler werden Mutationen genannt. Die meisten Mutationen
werden von der Selektion wieder ausgemerzt, weil sie entweder keine entscheidende
Verbesserung gebracht haben, oder sogar lebensunfähig sind. Einige mutierte
Individuem können jedoch überleben und für neue (bisher unter Umständen noch
nicht dagewesene) Eigenschaften der Art sorgen. 
\end{itemize}
Nun stellt sich die Frage, wie man die evolutionäre Strategie verwenden kann
um Optimierungsprobleme zu lösen. Evolution im biologischen Sinne bedeutet ,
daß die Eigenschaften einer Art sich so verändern (verbessern), daß diese Art
über bessere Chancen in der Umwelt verfügt. Durch die Evolution wird letztlich
die Erbinformation der Individuen verändert. 


\subsection{Codierung}

Die Art der Repräsentation des Gens für die Umsetzung im Computer ist willkürlich.
Dennoch sollte eine Codierung gewählt werden, auf deren Basis sich die aus der
Genetik kopierten Strategien möglichst gut verwirklichen lassen. An Stelle des
genetischen Codes im biologischen Sinne, tritt eine Binärzahl, d.h. man definiert
das Computergen als eine Folge einer bestimmten Anzahl von 0 und 1. Mit diesem
Gen werden dann, die Operationen Crossover, Mutation und Selektion durchgeführt.
Da das binäre Gen einen realen Sachverhalt, also z.B. Variablen repräsentiert,
ist die Länge dieses binären Gens abhängig von der Problemstellung. Selbstverständlich
ist auch die Art der Codierung stark von der Art des Problemes abhängig.

\begin{description}
\item [NUM]steht für numerical parameter estimation also Parameter Optimierung,
\item [SUB]steht für Subset-Selection (Probleme, bei denen aus einer Gruppe von Elementen
ausgewählt werden soll) 
\item [SEQ]steht für Sequencing Probleme (also Anordnungsprobleme, bzw. auch allgemeiner
kombinatorische Probleme fallen in diese Gruppe).
\end{description}

\subsubsection{NUM: Parameter Estimation Probleme}

Im Modell liegen üblicherweise mehrere Parameter, im Definitionsbereich der
reellen Zahlen vor, deren Optimum gefunden werden soll. Innerhalb des Algorithmus
wird aber nur mit dem binären Gen gearbeitet. Das bedeutet, daß diese Parameter
in irgendeiner eindeutigen Form in ein binäres Gen umgewandelt werden müssen.
Bei ungünstiger Wahl der Codierung kann die Leistungsfähigkeit des Algorithmus
vermindert werden.


\paragraph{Einfache Binäre Codierung:}

Die einfachste Möglichkeit der Codierung ist es, die Parameter zu natürlichen
Zahlen und diese in Binärzahlen umzuwandeln und aneinanderzuhängen:

\begin{enumerate}
\item Zunächst muß die reelle Zahl, die durch den Parameter ausgedrückt wird, in eine
natürliche Zahl umgeformt werden, das geschieht üblicherweise durch folgende
Transformation: \( P_{t}=int(10^{n}\bullet P) \). Die Kommastelle des reelen
Parameters wird je nach gewünschter Genauigkeit nach rechts verschoben und dann
auf eine Ganzzahl gerundet. Dieser transformierte Parameter ist aus den natürlichen
Zahlen, kann also ohne weiteres in eine binäre Zahl umgerechnet werden. 

\( P_{t} \) ... transformierter Parameter

\( P \) ... ursprünglicher Parameter

\( n \) ... die zu berücksichtigenden Dezimalstellen

\item Die binären Parameter werden nun in einer Folge aneinandergereiht. Diese Reihe
wird jetzt als Gen definiert, der Repräsentant des ganzen Parametersatzes. 
\end{enumerate}

\paragraph{Binäre Codierung mit Gray-Code:}

Die binäre Codierung ist jedoch nicht optimal, da jedem Bit ein anderes Gewicht
zukommt. Ein Invertieren, also Umdrehen des niederwertigsten Bits verursacht
eine Veränderung des Parameters um den Wert 1, des zweiten Bits um 2, der dritten
um 4, des n-ten um \( 2^{n-1} \). Das ist normalerweise nicht wünschenswert.
So findet oft anstelle des einfachen binären Codes der Graycode Verwendung .
Das Prinzip der Transformation bleibt allerdings das gleiche. Auch in den folgenden
Operationen ändert sich nichts, das Gen liegt auch hier in Form von 0 und 1
vor. Selbstverständlich müssen die Parameter, bevor sie wieder in das Modell
eingesetzt werden, rücktransformiert werden, d.h. innerhalb des GA wird nur
mit den binären oder gray codierten Genen gearbeitet, extern - also in den Modellen
natürlich mit den reellen Parametern!


\subsubsection{SUB: Subset Selection}

Unter Subset Selection versteht man das Problem, aus einer Menge von Elementen
nach bestimmten Kriterien eine Untermenge auszuwählen. Auch hier sind verschiedene
Codierungen möglich:


\paragraph{Variante 1:}

Die Anzahl der Bits im Bitstring ist so groß wie die Anzahl der Elemente der
Menge aus der gewählt wird. Jede Stelle im Gen entspricht dem Vorhandensein
(1) oder der Abwesenheit (0) des entsprechenden Elementes in der ausgewählten
Menge. (01001001) beispielsweise bedeutet, daß das 2., das 5. und das 8. Element
ausgewählt sind.


\paragraph{Variante 2:}

Die Anzahl der Elemente die ausgewählt werden sollen ist bekannt: Bezeichnen
wir die Anzahl der Elemente die gewählt werden sollen mit n:

Das Gen besteht aus n Variablen. Jede dieser n Variablen codiert das Vorhandensein
eines Elementes. Hätte das binäre Gen z.B. den Wert 001011101111, so bedeutet
daß Element 1 (001), 3 (011), 5 (101) und 7 (111) ausgewählt sind, wenn binär
codiert wird.

Das Problem bei Variante 1 ist, daß die Anzahl der gewählten Elemente mit einer
sinnvollen Bewertungsfunktion begrenzt werden muß, der Nachteil der Variante
2 liegt klarerweise darin, daß die Anzahl der selektierten Elemente im vorhinein
bestimmt werden muß und daß im Algorithmus verhindert werden sollte, daß zwei
oder mehrere gleiche Elemente ausgewählt werden.


\subsubsection{SEQ: Sequencing}

Eine Implementierung von Sequencing-Problemen (also z.B. das traveling salesman
Problem) könnte ähnlich angesetzt werden, wie die Variante 2 von SUB. Allerdings
müßte natürlich im Algorithmus garantiert werden, daß es zu keinen Wiederholungen
der Elemente kommt.


\subsection{Algorithmus}


\subsubsection{Initialpopulation}

Der erste Schritt einer GA-Optimierung besteht darin, eine Population zu generieren.
Die Populationsgröße liegt im allgemeinen zwischen 50 und 1000 Individuen, wobei
man unter einem Indiviuum ein einzelnes Gen (also einen Parametersatz) versteht.
Die Werte der Ausgangspopulation werden in den meisten Fällen mit einem Zufallsgenerator
bestimmt. Werden hierbei spezielle Werte gewählt,besteht die Gefahr, den Algorithmus
zu beeinflussen.


\subsubsection{Bewertung der Population (Selektion)}

Der nächste Schritt ist die Bewertung der Population. Es werden also die Gene
zu den Parametern rücktransformiert und in das jeweilige Modell eingesetzt.
Je nach der Güte der Anpassung erhält jedes Gen eine Bewertung. Der numerische
Wert dieser Bewertung wird auch als Fitness des Gens bezeichnet. An dieser Stelle
folgt die Selektion, für die mehrere Implementationen zur Verfügung stehen:

\begin{itemize}
\item Die neue Population ersetzt die alte (Eltern-) Population vollständig 
\item Die n besten Individuen werden in die neue Generation übernommen 
\item Die Vererbung erfolgt proportional zur Fitness der Individuen, d.h. die Besten
werden mehrfach vererbt, die schlechteren weniger oft, diejenigen, deren Fitness
niedriger als der Durchschnitt ist, werden verworfen.
\end{itemize}
Weiters ist es möglich, die Alterung in die Selektion eingehen zu lassen. Problematisch
bei vielen Implementationen ist die Tatsache, daß das besten Gen verloren gehen
kann. So wird oft ein Seitenweg für das beste Individuum gewählt, indem es gespeichert,
und unverändert in die neue Population wieder eingesetzt wird. Durch diese Vorgangsweise
ist garantiert, daß die Fitness des jeweils besten Gens der Population im Laufe
der Optimierung nur Ansteigen oder wenigstens gleich bleiben, jedenfalls aber
nicht schlechter werden kann.


\subsubsection{Paarung (Mating)}

Bei der Paarung werden aus Individuen aus der Population Paare gebildet, die
dann dem Prozeß des Crossover unterworfen werden. Die Paare werden üblicherweise
zufällig ausgewählt. Die Anzahl der Paare die gebildet werden, können über den
Parameter \emph{probability of mating} (also Wahrscheinlichkeit, daß eine Paarung
zweier Gene erfolgt) gesteuert werden.


\subsubsection{Crossover}

Unter Crossover versteht man einen Informationsaustausch zwischen den beiden
gepaarten Individuen. Das entspricht dem Austausch von Bits zwischen den beiden
Bitstrings. Die einfachste Implementation ist das sogenannte one-point Crossover.
Hierbei wird eine Stelle im Bitstring gewählt (der Crossover Punkt), und ab
hier werden die restlichen Bits der zu paarenden Gene ausgetauscht. Im allgemeinen
werden two-point oder uniform Crossover verwendet. Two-point Crossover ist vergleichbar
mit one-point crossover, nur mit dem Unterschied, daß das Gen eben nicht nur
an einer Stelle, sondern an zwei Stellen geschnitten und Information getauscht
wird. Die meist günstigste Variante ist das uniform-Crossover. Dabei besteht
eine definierte Austauschwahrscheinlichkeit zwischen allen Bits der beiden Bitstrings.
Das bedeutet, daß von links nach rechts mit einer bestimmten Wahrscheinlichkeit
die Bits an gleicher Position ausgetauscht werden. Die Bedeutung des Crossover
liegt darin, daß Individuen Information austauschen und somit mit einer gewissen
Wahrscheinlichkeit das Tochterindividuum über bessere Eigenschaften verfügt
als die Eltern. 


\subsubsection{Mutation}

Der letzte Schritt des Algorithmus ist die Mutation: 

An dieser Stelle werden mit einer bestimmten Wahrscheinlichkeit einzelne Bits
in den Genen invertiert. Diese Wahrscheinlichkeit sollte eher niedrig angesetzt
werden ,ansonsten besteht die Gefahr, daß zuviele gute Gene zerstört werden.


\subsubsection{Abbruchkriterium}

Die neu entstandene Population muß bewertet werden und der oben beschriebene
Ablauf wird wiederholt: Paarung, Crossover, Mutation, Bewertung, ..., solange
bis entweder ein Konvergenzkriterium erfüllt wird, oder eine bestimmte Anzahl
von Generationen erreicht wird. Ein solcher Lauf sollte aber auch mehrmals wiederholt
werden um Auskunft über die Qualität der Ergebnisse zu erhalten.


\subsubsection{Bewertung}

Als Bewertung versteht man das Einsetzen der Parameter in das jeweilige Modell
und die Ermittlung eines Qualitätskriteriums. Die Anzahl der Bewertungen im
Laufe einer Optimierung kann sehr rasch steigen. Die Zeit, die die Einzelbewertung
dauert, sollte also ein Minimum sein.


\subsection{Evolutionäre Algorithmen}

Eine den genetischen Algorithmen sehr ähnliche Strategie ist die Klasse der
evolutionären Algorithmen (EA). Der essentielle Unterschied zwischen EAs und
GAs liegt in der Codierung. Während Parameter aus den reellen Zahlen im Falle
von genetischen Algorithmen zu Bitstrings transformiert werden, werden bei evolutionären
Algorithmen die Parameter direkt verwendet und bilden einen Vektor. Dieser Vektor
ist nun die Ausgangsbasis aller weiteren Schritte, die ähnlich definiert sind
wie bei GAs. 


\section{Sitzungsprotokolle}


\subsection{09.03.1999}

Besprechungspunkte:

\begin{itemize}
\item Allgemeine Definition des Problems
\item Literatursuche; nach möglicherweise bereits bestehender Lösungsansätze des Problems
(Internet).
\item Vergleich mit herkömmlichen Methoden
\item Organisatorisches: erstellen von: Zusammenfassung, Literaturverzeichnis, Einleitung
\end{itemize}

\subsection{16.03.1999}

Besprechungspunkte:

\begin{itemize}
\item Zur Dokumentation: 

\begin{itemize}
\item Titelblatt: Thema, Gruppenmitglieder, E-Mail, Gruppennummer, Lehrveranstaltungsleiter
\item Protokoll jeder Sitzung
\end{itemize}
\item Offene Fragen:

\begin{itemize}
\item Was geschieht wenn Gespräch Zeitzone überschreitet
\item Wie können Start- und Zielort bestimmt werden
\item kleinste Zeiteinheit (Takte) eines Gesprächs
\item wie wird Tarifmodell repräsentiert
\item Definition eines CDRs
\item wie erfolgt die Aufnahme der Gründgebühr in das Tarifmodell
\end{itemize}
\end{itemize}

\subsection{23.03.1999}

Besprechungspunkte:

\begin{itemize}
\item Zur Dokumentation:

\begin{itemize}
\item Noch bestehende Fehler korrigieren; Beschreibung der verwendeten Bezeichnungen
der Gleichungen
\end{itemize}
\item Zusammenfassung über GAs, EC, EP
\item Konventionelle Optimierungsmethoden
\item Fitnessfunktion
\end{itemize}
\begin{thebibliography}{}
\bibitem{1}Entwicklungsprojekt Tarifmodell; Smart.com; DI Peter Werzl
\bibitem{2}Kurzes Lehrbuch der Zoologie; Adolf Rmane, Volker Storch, Ulrich Welsch; Gustav
Fischer Verlag, 6. Auflage (S 323)
\end{thebibliography}
\end{document}
