Information Technology Reference
In-Depth Information
Das praktische Ergebnis der beispielhaften ES ist damit, dass die optimale Zusammensetzung
des Klebers mit den gewünschten Kennwerten keine viskositätserhöhenden Füllstoffe und
37 % der maximal zulässigen Menge Beschleuniger enthält und das bei einer Arbeitstempera-
tur, die um 41 % der Temperaturdifferenz zwischen der minimalen und maximalen Arbeits-
temperatur über der minimalen Arbeitstemperatur liegt.
Zum Verhalten einer Optimierung mit einer ES seien hier noch einige Bemerkungen angefügt:
Beachten Sie, dass unterschiedliche Anfangsvektoren (erste Elterngeneration) durchaus zu
verschiedenen Endergebnissen führen können. Daher ist es zweckmäßig, die Berechnungen
immer mehrfach, mit verschiedenen Anfangsvektoren durchzuführen.
Wird eine nicht-elitistische Variante gewählt, kann es auch bei großer Schrittzahl immer wie-
der zu Verschlechterungen der Werte kommen; der Vorteil ist jedoch, wie schon mehrfach
erwähnt, dass das Verfahren sich nicht so leicht in einem Nebenminimum „festläuft“. Die
elitistische Variante konvergiert zwar zuverlässig, vor allem wenn die Standardabweichung der
Mutation schrittweise verringert wird, die Konvergenz kann aber unter Umständen ein Artefakt
sein, d. h. weit entfernt vom Optimum liegen. Auch um dies Risiko zu verringern, empfehlen
sich verschiedene Anfangsvektoren.
Da die ES stochastisch ist, können verschiedene Durchläufe trotz gleicher Anfangswerte und
Parameter durchaus in verschiedenen Attraktoren enden. Will man reproduzierbare Ergebnisse
erzeugen, muss man daher dafür sorgen, dass alle im Programm aufgerufenen Zufallsgenerato-
ren mit immer denselben Startwerten (seeds) beginnen und so immer dieselben Folgen von
Zufallszahlen generieren.
3.6.2 Minimierung der Länge von Kabelnetzen
durch einen Genetischen Algorithmus
Angenommen ein Telekommunikationskonzern will eine Anzahl von Kommunikationsgeräten
bei Kunden, die über ein gewisses Gebiet verteilt sind, durch ein neuartiges, teures Breitband-
kabel mit einer Verteilerstelle verbinden. Der Konzern will natürlich die Installationskosten für
die Verkabelung möglichst niedrig halten und sucht dafür die optimale Lösung. Bei diesem
Problem kann ein genetischer Algorithmus zur Optimierung vorteilhaft sein, da es für die Ver-
bindungen zwischen verschiedenen Punkten bereits bei einer mäßigen Anzahl eine sehr hohe
Zahl kombinatorischer Möglichkeiten gibt.
Ein einfaches Modell für dieses Problem geht von n Punkten aus, die beliebig in einem Gebiet
der Ebene verteilt sind. Mit Punkt 1 wird der Ausgangspunkt des herzustellenden Netzes be-
zeichnet. Mathematisch formuliert hat man es also mit einem zusammenhängenden Digraphen
mit n Ecken zu tun, für den bestimmte Bedingungen gegeben sind.
Erstens wird angenommen, dass die Installationskosten der Länge der zu legenden Kabel, d. h.
der Summe der Länge der Kanten, die die Kabel repräsentieren, proportional sind. Das optima-
le Netz ist also der Graph, dessen Kantenlängensumme - ausgehend von Ecke 1 - minimal ist.
Die Kantenlängen werden als Euklidische Distanzen aus den jeweiligen Koordinaten von
Ecken-Paaren berechnet.
Zweitens kann unterstellt werden, dass das optimale Netz mit n Ecken genau n-1 Kanten be-
sitzt, denn jede weitere Kante wäre für einen zusammenhängenden Graphen überflüssig und
würde die Längensumme vergrößern.
Drittens sind die Kanten gerichtet, und zwar in der Weise, dass der Digraph einen Baum dar-
stellt mit einer Quelle in Punkt 1. Von dort gibt es also nur ausgehende Kanten.
Search WWH ::
Custom Search