Evolutionäre Algorithmen:
Chancen für die praxisorientierte Optimierung
Prof. Dr. J. Willms

Angewandte Informatik und Mathematik
Fachhochschule Südwestfalen
Meschede

Evolutionäre Algorithmen

Mit Evolutionären Algorithmen bezeichnet man eine Gruppe von unterschiedlichen Algorithmen wie z.B. genetische Algorithmen oder Evolutionsstrategien, deren Entwicklung bereits in den sechziger Jahren begann. Gemeinsam ist hierbei allen die Idee, bei der Lösungssuche die Simulation des biologischen Evolutionsprozesses zu nutzen.

Wir wollen das oben geschilderte Hammerproblem zur Bestimmung einer möglichst geringen Unwucht nutzen, um die grundsätzliche Idee Evolutionärer Algorithmen zu erläutern. Gefragt war, wie man bei fest vorgegebenen Hammerpositionen n unterschiedlich schwere Hämmer am Rotor anordnen soll, um möglichst geringe Unwuchtkräfte zu erhalten. Mit einer (zulässigen) Lösung wird dabei jede beliebige Montageanordnung der n Hämmer bezeichnen. Wie bereits dargestellt wurde, gibt es selbst bei einer relativ kleinen Anzahl von Hämmern eine immense Zahl von zulässigen Lösungen. Gesucht sind Lösungen mit möglichst geringen Unwuchtkräften.

Bewertungsfunktionen und optimale Lösungen

Um entscheiden zu können, ob eine Lösung besser als eine andere Lösung ist, braucht man ein Bewertungskriterium, das anhand einer reellen Zahl (der sogenannten Bewertung) angibt, wie gut jede möglich Lösung ist.

Wie findet man nun aber eine geeignete Bewertung? Bei vielen Problemstellungen gibt es natürliche Bewertungsfunktionen wie zum Beispiel Kosten, Aufwand oder Gewinn.

In unserem Hammerbeispiel ist es naheliegend, die Gesamtunwucht als Bewertungsfunktion heranzuziehen. Da jedoch die Gesamtunwucht keine skalare Größe (reelle Zahl) ist, stößt man auf eine weitere Schwierigkeit, die sich jedoch leicht lösen lässt.

Durch nichtausgeglichenen Fliehkräfte wirken Kräfte F und G auf die beiden Lager: in dem Rotor ist dann eine Unwucht vorhanden. Die Beträge der beiden Unwuchtkräfte sind hierbei proportional dem Quadrat der Winkelgeschwindigkeit der Drehung. Als Bewertungsfunktion kann man nun den jeweils größeren der beiden Beträge der Unwuchtkräfte F und G wählen. Gesucht sind dann zulässige Lösungen (d.h. Montagereihenfolgen der Hämmer) mit einer möglichst kleinen Bewertung (Minimierungsproblem).

Allgemein wird zwischen Maximierungs- und Minimierungsproblem unterschieden. Bei Maximierungsproblemen sind die Lösungen um so besser, je größer die Bewertung ist. Eine Lösung mit maximaler Bewertung wird dann eine optimale Lösung genannt, da es keine weitere Lösung gibt mit einer noch besseren Bewertung. Abhängig von der Problemstellung kann es mehrere optimale Lösungen geben. Ganz analog kann das Minimierungsproblem behandelt werden, dessen Ziel es ist, eine Lösung mit einer minimalen Bewertung zu finden. Dies ist zum Beispiel der Fall, wenn die Bewertungsfunktion einer Kostenfunktion oder Aufwandsfunktion oder, wie in unserem Fall, die Minimierung auftretender Kräfte entspricht.


weiter

nach oben

Impressum     Datenschutz
nach oben

29.7.2003