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

Angewandte Informatik und Mathematik
Fachhochschule Südwestfalen
Meschede

Implementierung des Evolutionären Algorithmus

In dem oben beschriebenen Anwendungsfall der Optimierung von Unwuchten wurde entschieden, ein Programm zu entwickeln, das mit Hilfe eines Evolutionären Algorithmus das Hammerproblem löst. Dabei mussten folgende Randbedingungen beachtet werden.

Das Programm sollte auf beliebigen PCs unter den aktuellen Versionen des Betriebssystems Windows laufen. Ein Einsatz vor Ort auf einem Laptop sollte möglich sein. Ferner sollte die Anwendung des Programms so unkompliziert sein, dass eine einfache Einweisung in das Programm für die Bedienung ausreicht. Kenntnisse über Evolutionäre Algorithmen durften hierbei nicht vorausgesetzt werden. Die Geometriedaten des Hammerbrechers sollten interaktiv eingegeben werden, ebenso die gemessenen, unterschiedlichen Massen der Hämmer. Die gefundenen Lösungen sollten ausgedruckt und als Datei gespeichert und wieder eingelesen werden können. Ferner sollte das Programm mit einem anderen Optimierungsprogramm zur Optimierung von Scheibenunwuchten gekoppelt werden, auf das hier nicht weiter eingegangen wird.

Implementiert wurde das Programm, das wir OPT genannt haben, in C++; als Entwicklungsumgebung wurde Visual C++, Version 6.0 benutzt. Andere Programmiersprachen und Entwicklungsumgebungen (soweit sie das Windows-API unterstützen) wären durchaus denkbar gewesen.

Ein sehr wichtiger, wenn nicht sogar entscheidender Punkt beim Entwurf und der Implementierung eines Evolutionären Algorithmus ist die gewählte Repräsentation einer Lösung. In unserem Anwendungsfall sind die Lösungen direkt durch Permutationen gegeben. Aus diesem Grund haben wir uns entschieden, eine für Permutationen geeignete Repräsentation in Form von ganzzahligen Vektoren zu wählen. Die Repräsentation beeinflusst auch entscheidend die Wirkung einer Mutation. Als Mutation haben wir das zufällige Vertauschen zweier oder mehrerer Positionen eines Lösungsvektors gewählt. Auf eine Kreuzung der Lösungen haben wir ganz verzichtet.

Die ursprüngliche Idee, gewisse Grundgrößen wie Populationszahl oder Anzahl der Nachkommen durch Parameter zu hinterlegen, die vom Benutzer interaktiv verändert werden können, wurde in der Praxis schnell verworfen. Die Benutzer konnten mit diesen Parametern nichts verbinden und das eigentliche Ziel, hierdurch den Algorithmus flexibler zu machen und an den jeweiligen konkreten Anwendungsfall besser anzupassen, wurde nicht erreicht. Stattdessen wurden feste, empirisch durch Testläufe ermittelte Parameterwerte benutzt, die der Benutzer nicht mehr verändern konnte. Die Größe der Elternpopulation in einer Generation wird vom Programm zyklisch verändert, sie bewegt sich zwischen 4 und 200. In jedem Iterationsschritt wächst die gesamte Population vor der Selektion auf eine Größe von 600.

Ein anderes grundsätzliches Problem Evolutionärer Algorithmen betrifft das Abbruchkriterium. Selbst wenn ein Evolutionärer Algorithmus eine optimale Lösung findet, wird er diese nicht als optimal erkennen und versuchen, bessere Lösungen zu finden. Auch kann der Algorithmus zu keinem Zeitpunkt beurteilen, wie gut eine gefundene Lösung ist. Von außen muss daher ein Abbruchkriterium vorgegeben werden. Ursprünglich vorgesehen war, dass der Benutzer die Anzahl der Iterationen vorgibt. Aus Sicht des Benutzers war dies jedoch nicht sehr transparent. In einer zweiten Version konnte der Benutzer eine maximale Berechnungszeit und einen minimalen Bewertungswert (Lagerkraft) eingeben. Sobald eine Lösung gefunden wurde, die diesen minimalen Bewertungswert unterschritt oder die eingegebene maximale Berechnungszeit vorüber war, brach der Algorithmus ab. In der endgültigen Version schließlich wird dem Benutzer während der Optimierung mitgeteilt, wie gut die bis dahin beste gefundene Lösung ist. Der Benutzer kann jederzeit die Berechnung abbrechen, die bis dahin beste gefundene Lösung im Detail betrachten und die Daten ausdrucken oder abspeichern. Auch kann der Benutzer jederzeit auf der gefundenen Lösung neu aufsetzen und versuchen die Lösung weiter zu verbessern.


weiter

nach oben

Impressum     Datenschutz
nach oben

29.7.2003