Die Entwicklung von Strategien zur Lösung von Optimierungsproblemen ist ein Hauptanwendungsbereich der Mathematik. Die lineare und die quadratische Optimierung sind dabei zwei ebenso bekannte Verfahren wie die Bestimmung von Extrempunkten mit den Mitteln der Analysis.
In der Industrie treten jedoch häufig sehr komplexe Optimierungsprobleme auf, die mit diesen Methoden nicht zu lösen sind. Ein Beispiel ist die optimale Platzierung von Containern auf einem Containerschiff, bei dem die größtmögliche Stabilität des Schiffes, möglichst kurze Entladungszeiten in verschiedenen Häfen und die beste räumliche Anordnung (Kühlcontainer in der  Nähe des Stromaggregats) angestrebt werden.
Derartig komplexe Probleme werden heute häufig mit Evolutionären Algorithmen (Genetischen Algorithmen, Evolutionsstrategien) gelöst. Die Optimierung nach dem Vorbild der Evolution ist erst in den letzten Jahrzehnten entwickelt worden. Diese naturanalogen Methoden orientieren sich an dem Evolutionsprozess der Natur und greifen dabei die drei Grundprinzipien der Selektion von Individuen, der genetischen Veränderung durch Rekombination und Mutation sowie der Reproduktion auf. Die Grundidee der Evolutionären Algorithmen soll an einem stark vereinfachten Beispiel mithilfe von Matrizen verdeutlicht werden.

Problemstellung:                                    
Gesucht ist eine zylindrische 500-cm³-Konservendose, für deren Herstellung möglichst wenig Weißblech verwendet werden soll. Aus dem Marketingbereich kommt die Vorgabe, dass der Radius zwischen 3 cm und 15 cm liegen soll. Da die geplante Konservendose nicht bis zum Rand gefüllt werden soll, darf das Volumen zwischen 500 cm³ und 550 cm³ betragen. Auf die Beachtung von Falzen und Verschnitt soll bei der Modellierung zunächst verzichtet werden.


Lösungsschritte mit einem Evolutionären Algorithmus:

1. Selektion
Aus einer Ausgangspopulation werden die besten Lösungen ausgesucht (nach der Darwinschen These „survival of the fittest“). Dazu werden zunächst die zufällig gewählten Ausgangsdaten in eine 5x2-Matrix eingetragen, wobei die erste Spalte die Werte für den Radius, die zweite Spalte die Werte für die Höhe des Zylinders enthält.

Ausgangsmatrix     

Die Werte für r und h werden nun in die Formel für das Volumen V = pi * r²* h (1.Spalte) und die Oberfläche des Zylinders O = 2*pi*r² + 2*pi*r*h (2. Spalte) eingesetzt.
Wählt man eine Rundungsgenauigkeit von einer Dezimalen, so erhält man die

Bewertungsmatrix  .

Erstes Bewertungskriterium ist das Volumen, das zwischen 500 cm³ und 550 cm³ liegen soll. Zweites (nachgeordnetes) Bewertungskriterium ist die möglichst geringe Oberfläche.

Frage: Welche beiden der fünf Wertepaare (Zeilen der Ausgangsmatrix) liefern die besten Werte?
Antwort: Keines der fünf Wertepaare erfüllt das erste Bewertungskriterium. Die Werte der dritten und vierten Zeile liefern aber die besten Näherungswerte und werden daher ausgewählt.

2.1. Rekombination
Die ausgewählte Untermatrix wird - in Anlehnung an die Vererbung von Genen des Vaters und der Mutter - über Kreuz rekombiniert. Das heißt die Werte der zweiten Spalte werden vertauscht.
Aus der Untermatrix   wird die Rekombinationsmatrix   .
Damit die bisher beste Lösung (4 11) nicht verloren geht, wird diese unverändert (in die 3. Zeile der Matrix) übernommen.

2.2. Mutation
In einem zweiten Schritt wird eine Mutation der Werte der Untermatrix   simuliert. Dazu sind viele Möglichkeiten denkbar. Die Mutation soll gewährleisten, dass die Vielfalt in der Population erhalten bleibt.
In diesem einfachen Verfahren sollen bei den beiden selektierten Lösungen sowohl der Wert des Radius und als auch der Wert der Höhe zufällig verändert werden. Hierzu sind ebenfalls verschiedene Varianten denkbar, z. B. die Erstellung eines Tabellenkalkulationsprogramms unter Verwendung des Zufallszahlengenerators.
Möglich ist natürlich auch die Verwendung des Zufallszahlengenerators des Taschenrechners. Da diese Werte einer gleichmäßigen Wahrscheinlichkeitsverteilung entsprechen, empfiehlt sich folgende Mutationsvorschrift, die Werte zwischen dem 0,5- und dem 1,5-fachen liefert: (0,5 + ran#) * (alter Wert) = neuer Wert.
In unserem Fall erhält man beispielsweise (0,5 + 0.9436) * 4 = ca. 5,7 und (0,5 + 0,9083) * 11  = ca. 15,5.
Dieses Wertepaar ergibt nun die 4. Zeile der neuen Matrix.
Entsprechend erhält man für das andere Wertepaar die 5. Zeile der neuen Matrix.

3. Reproduktion
Nach Selektion, Rekombination und Mutation erhält man die folgende
Reproduktionmatrix .
Diese veränderte Population entspricht einer neuen Generation. Um die nächste Generation zu erzeugen, wird auf diese Matrix nun wieder beginnend mit der Selektion das gesamte Verfahren angewendet.
Wie oft dieser Evolutionäre Algorithmus durchlaufen werden soll, kann vorher festgelegt werden. Bei entsprechend komplexen Problemen durchläuft ein Evolutionärer Algorithmus in der Regel 50 bis mehrere hundert Generationen. Oder man macht die Entscheidung von den gefundenen Werte abhängig. Ändert sich der optimale Wert dreimal hintereinander nicht mehr, beendet man das Optimierungsverfahren.

Aufgabe:
Bestimmen Sie durch Anwendung dieses Evolutionären Algorithmus eine möglichst optimale Lösung für das genannte Problem.