Gegenstand der Diplomarbeit sind Evolutionäre Algorithmen, die Grundmechanismen der biologischen Evolution auf abstrakter Ebene algorithmisch imitieren, und deren Anwendungen auf Optimierungsprobleme.
Evolutionäre Algorithmen (EA) sind
Evolutionäre Algorithmen enthalten bewußt stochastische Elemente und erzeugen so durch Selektion und genetische Operatoren im Rahmen einer Lösungsrepräsentation und eines Populationskonzeptes immer bessere Lösungspunkte.
EA arbeiten nach einem relativ kurzen und einfachen, iterativen Basisalgorithmus, der jedoch bzgl. Lösungsrepräsentationen, Populationskonzepten, Selektionsverfahren, genetischen Operatoren sowie Terminierungskriterien viel Freiraum für unterschiedliche Implementierungen bietet. In dieser Diplomarbeit sind die wichtigsten dazu in der Fachwelt bekannten und diskutierten Ansätze und Realisierungen ausführlich vorgestellt und bewertet worden.
Da eine große Vielzahl unterschiedlicher Implementierungen von EA-Varianten, sei es als Genetischer Algorithmus oder als Evolutionsstrategie, existiert, ist ein Überblick über deren wirkliche Leistungsfähigkeit beim Optimieren praxisrelevanter Problemstellungen schwierig. Zum Testen der Algorithmen wird meist eine Serie von Testfunktionen herangezogen, die jeweils bestimmte Eigenschaften aufweisen (z. B. große Anzahl lokaler Minima und deren unregelmäßige Verteilung im Definitionsbereich; unstetiges und multimodales Verhalten der Funktionen) und dadurch klassischen Optimierungsverfahren große Schwierigkeiten bereiten. Mit Hilfe der bei der Minimierung dieser Testfunktionen erzielten Ergebnisse kann anschließend auf einfache und objektive Art und Weise eine Bewertung des EA erfolgen.
LEO besteht aus Repräsentationsmodul, Populationsmodul, Selektionsmodul,
Operatormodul und Fitneßmodul sowie Hauptprogramm. Dieses Konzept
ermöglicht eine hohe Flexibilität und problemlose Erweiterbarkeit
der Implementierung und ist auch aus Sicht der Softwareentwicklung und
-wartung (arbeitsteiliger Entwicklungsprozeß, Transparenz der
Implementierung, Wiederverwendbarkeit und Erweiterbarkeit des
Softwaresystems) besonders sinnvoll und zweckmäßig.
Den prinzipiellen Ablauf des evolutionären Optimierungsprozesses im
Hauptmodul von LEO zeigt die folgende Übersicht:
LEO produzierte im EA-Standardtest ausgezeichnete Ergebnisse, da es aus Gründen der Effizienz und Qualität der evolutionären Optimierung simultan mit mehreren Selektionsverfahren und etlichen, an die gewählte Lösungsrepräsentation angepaßten, genetischen Operatoren arbeitet. Dies bewirkt, daß LEO hervorragend in der Lage ist, bei einer fixen Einstellung seiner EA-Parameter alle zehn Testfunktionen sehr gut bis ausgezeichnet zu optimieren. Fast immer wurde das globale Minimum in allen Testläufen exakt und zügig ermittelt.
Ein wirkungsvoll arbeitender Evolutionärer Algorithmus nutzt einerseits die in bereits ermittelten, guten Lösungspunkten enthaltenen Informationen aus (Exploitation), hält andererseits jedoch auch nach neuen, erfolgversprechenden Regionen im Lösungsraum Ausschau (Exploration). Die Balance dazwischen kann über die Populationsgröße gesteuert werden. Mit LEO können die dabei auftretenden Auswirkungen auf die Güte eines Optimierungslaufes und dessen Länge bis zur Terminierung analysiert und aufgezeigt werden.
Die Anwendungsmöglichkeiten von LEO zur optimalen Konfigurierung diskreter Systeme entsprechend der Aufgabenstellung wurden exemplarisch anhand von Fertigungssystemen mit dynamischen KANBAN-Systemen dargelegt. Letztere stellen eine Möglichkeit dar, eine Just-In-Time-Fertigung zu steuern. Hierbei geht eine Minimierung des Lagerbestandes insbesondere der Halbfertigerzeugnisse einher mit einer signifikanten Kostenreduzierung. Die dennoch notwendige Entkoppelung und Pufferung der Produktion geschieht in KANBAN-Systemen durch den Materialtransport. Betriebswirtschaftlich sinnvoll ist es, die Anzahl und Größe der Transportbehälter zwischen den Fertigungszellen als variabel anzusehen. Dadurch ergibt sich eine Vielzahl von Variationsmöglichkeiten, so daß auch wegen der Diskretheit bzgl. Anzahl und Größe der Transportbehälter und der stochastischen Einflußgrößen in Form von Bediendauern je produziertem Teil das daraus resultierende Optimierungsproblem zur Kostenminimierung überaus komplex ist. Eine global-optimale Lösung kann dadurch im Rahmen eines klassischen Optimierungsverfahrens oder eines analytischen Modells nicht erreicht werden.
Deshalb wurde in dieser Diplomarbeit der Weg über die Koppelung von LEO mit einem Simulationsmodell eingeschlagen. Es sind mehrere Fertigungssysteme untersucht und evolutionär optimiert worden. Dabei konnten mit geringerem Simulationsaufwand pro Lösungspunkt (wesentlich) bessere Konfigurationen der KANBAN-Systeme ermittelt werden als durch ein klassisches Hillclimbing-Optimierungsverfahren mit wissensbasierten Elementen. Bezüglich der Gesamtkosten für die Fertigungssysteme ergaben sich Einsparungen zwischen knapp zehn und knapp zwanzig Prozent je nach Fertigungssystem. Solche Verbesserungen müssen unter betriebswirtschaftlichen Aspekten als äußerst beachtlich eingeschätzt werden.
Wird ein Evolutionärer Algorithmus weiterentwickelt, so soll dabei einerseits die Effizienz des EA gesteigert werden (Schnelligkeit des Auffindens guter Lösungen durch den EA) und andererseits auch die Robustheit des EA erhöht werden (Unempfindlichkeit des Optimierungsprozesses gegenüber kleinen Änderungen der EA-Parameter oder geringen Modifikationen in der zu bearbeitenden Aufgabenstellung).
Kombinationen zwischen Evolutionären Algorithmen und anderen Problemlösungsverfahren sind vorteilhaft, weil sie oft zu drastischen Leistungssteigerungen der entstehenden Hybridimplementierung gegenüber den beteiligten Einzelverfahren führen. Dies konnte in der Diplomarbeit exemplarisch am Beispiel eines Weltrundreiseproblems mit 80 Städten nachgewiesen werden. Dabei wurde in LEO ein Standard-EA mit einem hybriden EA verglichen, bei dem für jeden Lösungspunkt nochmals eine lokale Optimierung auf der Basis einer Heuristik für das Travelling-Salesman-Problem vorgenommen wurde. Es zeigte sich, daß die schlechteste gefundene Lösung des hybriden EA immer noch kürzer war als die beste gefundene Lösung des Standard-EA, obwohl letzterer zehnmal mehr Lösungspunkte erzeugen und bewerten durfte als ersterer. Die Abweichung beim Tourdurchschnitt betrug mehr als fünf Prozent zugunsten des hybriden EA, der auch in der Wahrscheinlichkeit des Auffindens der besten Lösung wesentlich überlegener war. Dies spricht für seine Robustheit. Zusätzlich war der hybride EA noch schneller beim Auffinden der jeweils besten Lösung.
Durch eine Selbstadaptivität von Strategieparametern werden Evolutionäre Algorithmen einfacher handhabbar. Dies ist besonders für deren Akzeptanz bei der praktischen Anwendung durch Nutzer sehr wichtig. Im Rahmen der Diplomarbeit wurde eine Methode entwickelt, die einem Bucket-Brigade-Algorithmus ähnelt und bei der die Anwendungswahrscheinlichkeiten für die einzelnen genetische Operatoren und die einzelnen Selektionsverfahren in LEO selbstadaptiv entsprechend der Güte der damit erzeugten Nachkommen über mehrere Generationen rückwirkend angepaßt werden. Dazu ist auch eine dynamische Datenstruktur in Form eines Stammbaums mit einem zugehörigen Garbage-Collection-Algorithmus entworfen worden. Diese Methode der selbstadaptiven EA-Parameter wurde mit LEO schließlich an einem Graphfärbeproblem mit 100 Knoten und 400 Kanten in dieser Diplomarbeit praktisch realisiert und erfolgreich angewendet. Die dabei erhaltenen Ergebnisse sind anschließend einer weitergehenden theoretischen Untersuchung und Analyse unterzogen worden.