Implementierung und Evaluation von Heuristiken aus dem Gebiet "Evolutionary Computation" zur Lösung komplexer Schedulingprobleme


Studienarbeit, 2010

161 Seiten, Note: 2,0


Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Grundlagen
2.1 Einordnung des Themengebietes
2.2 Vorbild Natur
2.3 Problemstellung
2.4 Basis der Optimierung
2.5 Aufbau und Funktionsweise eines Cluster Tools
2.6 Matrix Prediciton Method
2.7 Struktur des Suchraumes und Lösungsansätze

3 Algorithmen
3.1 Random Down Swing
3.1.1 Implementierung
3.1.2 Optimierung
3.1.3 Modifikationen
3.2 Ameisenalgorithmus
3.2.1 Das Vorbild in der Natur .
3.2.2 Anwendung auf Scheduling .
3.2.3 Implementierung
3.2.4 Monte Carlo Auswahl
3.3 Partikel Schwarm Algorithmus
3.3.1 Das Vorbild der Natur
3.3.2 Anwendung auf Scheduling
3.3.3 Implementierung
3.3.4 Richtungsableitung
3.4 Vergleichsalgorithmen
3.4.1 Monte Carlo Methode
3.4.2 Random Walk
3.4.3 Simulated Annealing
3.4.4 Genetischer Algorithmus
3.4.5 Brute Force
3.4.6 Strong Derivative

4 Simulation
4.1 Framework
4.2 Simulationsumgebung
4.3 Random Down Swing
4.3.1 Shift oder Swap
4.3.2 Modifikation
4.4 Ameisenalgorithmus
4.4.1 Pheromonablagerung
4.4.2 Gruppenmarkierung
4.4.3 Verwitterung
4.4.4 Auswertung der Ameisenalgorithmus Ergebnisse
4.5 Partikel Schwarm Algorithmus
4.5.1 Modifikation
4.5.2 Richtungsableitung
4.6 Vergleich der Algorithmen
4.6.1 Berechnungsaufwand
4.6.2 Leistung in Abhängigkeit der Wiederholungsanzahl und Loadportanzahl
4.6.3 Unterschiedliche Maschinen
4.6.4 Vergleich mit dem Optimum in ausgewählten Aufgaben

5 Zusammenfassung und Ausblick

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

A Werkzeuge und Hilfsmittel

B Simulation
B.1 Simulationsumgebung
B.1.1 Betriebsumgebungen
B.1.2 Testfälle
B.2 Random Down Swing
B.2.1 Shift oder Swap
B.2.2 Swap Modifikationen
B.2.3 Swap Modifikationen vier Loadports
B.3 Ameisenalgorithmus
B.4 Partikel Schwarm Algorithmus
B.5 Vergleich der Algorithmen bei unterschiedlichen Loadportanzahlen . .
B.6 Vergleich mit Optimum

1 Einleitung

Die Natur ist immer wieder ein Vorbild für technologische Entwicklungen. Beispielsweise fungieren Vögel und Fische als Modell für strömungsgünstige Fahrzeugformen. Das Blatt der Lotospflanze dient als Anschauungsobjekt in der Nanotechnologie für geringe Benetzbarkeit einer Oberfläche. Weitere bekannte Beispiele sind die stabilen Waben der Bienen oder die beim Richtungswechsel sich verbreiternden Pfoten der Katzen, sowie die Ultraschallwellen der Delphine und Fledermäuse. In einer Meisterleistung der Evolution entstanden über Generationen hinweg ausgereifte Methoden und Eigenschaften. Der Fundus der Schöpfung bietet ein bedeutendes Potential für zukünftige technische Konzeptionen. Diese Wissenschaft der Umsetzung von Entwicklungen aus der Natur in die Technik wird Bionik genannt.

Parallel zur Entwicklung der physikalischen Eigenschaften, wie den oben genannten Beispielen, bildeten die Lebewesen in der Natur auch Verhaltensweisen heraus, die zur Optimierung von komplexen Sachverhalten dienen. Mehrere Tiere leben in Schwärmen, Rudeln oder Kolonien und operieren mit einem gemeinschaftlichen Verhalten, um Herausforderungen zu meistern. Durch das Zusammenwirken der einzelnen Individuen als Kollektiv entsteht Schwarmintelligenz, welche auf andere Sachverhalte übertragbar ist. Die Organisation der Tiere wurde durch natürliche Auslese von Generation zu Generation optimiert und verfeinert. Inspiriert durch das Verhalten bestimmter Tierarten kann der Mensch von solchen natürlichen Strategien lernen und sie zur eigenen Problemlösung einsetzen. Die vorliegende Arbeit beschäftigt sich mit dem Adaptieren der Intelligenz von Tierschwärmen auf kombinatorische Optimierungsprobleme.

Verbesserungsstrategien werden für viele unterschiedliche Problemsituationen benötigt. Die in dieser Arbeit untersuchte Anforderung ist vorwiegend bei der Produktion von Wafern in der Halbleiterindustrie bei Cluster Tools wieder zu finden. Für effiziente Herstellung von Chips ist ein optimierter Ablaufplan erforderlich, um die Produktionszeit zu verkürzen und die damit verbundenen Kosten zu senken.

1 Einleitung

Dieser Schedule ist mit Hilfe der evolutionären Algorithmen aus der Natur zu erzeugen und die erreichte Leistung mit herkömmlichen Verfahren zu verglichen. Dazu werden die Optimierungsstrategien des Ameisenalgorithmus und des Partikel Schwarm Algorithmus eingesetzt.

In Kapitel 2 erfolgt zunächst eine detailliert Beschreibung der Problemstellung. Darüber hinaus enthält es die Grundlagen für eine mögliche Optimierung, die genau Berechnung eines Schedules, so wie eine Erläuterung des komplexen Lösungsraumes. Danach erfolgt in Kapitel 3 die Vorstellung der verschiedenen Algorithmen. Neben einer präzisen Erklärung der Optimierungsideen und deren Eigenschaften bezüglich des komplexen Lösungsraumes, ist die Adaption auf die Problemstellung beschrieben. Daran schließt sich die daraus entwickelte Implementierung an. Mögliche Modifikationen werden ebenfalls abgehandelt. Anschließend findet in Kapitel 4 eine ausgiebige Analyse der Algorithmen bei verschiedenen Problemstellungen statt. Mit Hilfe eines Frameworks und einer Vielzahl von Simulationen erfolgt eine Beschreibung des Verhaltens der Algorithmen in den bestimmten Situationen. Ein abschließender Vergleich mehrerer unterschiedlicher Algorithmen und mit dem globalen Optimum beendet die Untersuchung. Zum Schluss wird in Kapitel 5 die vorliegende Arbeit zusammengefasst und ein Ausblick gegeben.

2 Grundlagen

2.1 Einordnung des Themengebietes

Evolutionary Computation ist ein Teilgebiet der Künstliche Intelligenz, welches kombinatorische Optimierungsprobleme untersucht. Der Spezialbereich Evolutionsstrategien1 gehören zu den heuristischen Optimierungsverfahren und den Evolutionären Algorithmen. Sie werden vor allem für Probleme eingesetzt, für die keine konventionellen Lösungmethoden vorliegen und stehen in Konkurrenz zu klassischen Suchstrategien. Das Themengebiet Evolutionäre Algorithmen setzt sich aus den drei Bereichen Biologie, Mathematik und Informatik zusammen. Als Grundlage muss zuerst das biologische Vorbild aus der Natur untersucht werden, um im Anschluss die Verhaltensweisen in ein künstliches System übertragen zu können. Dabei ist es essentiell, die Schwarmintelligenz zu verstehen. Die Methoden der Natur werden abstrahiert und ein mathematisches Modell erstellt. Durch Variation der Parameter kann das Verhalten des Algorithmus auf das jeweilige Problem angepasst werden. Zum Schluss lässt sich durch die Informatik der entwickelte Algorithmus in ein Programm übertragen. Die Computersimulation bietet die Möglichkeit, zahlreiche Analysen durchzuführen.

Die Anwendungsgebiete der Schwarmintelligenz sind sehr vielseitig. Beispielsweise werden die Lösungsideen in den Bereichen von künstlicher Intelligenz, Multiagentensystemen und Robotik, sowie Logistik angewendet. Des Weiteren dienen die Erkenntnisse dem Operations Research. Optimierungsprobleme, auch mit mehreren Kriterien, lassen sich auf diese Art lösen. Eine bekannte Problemstellung auf diesem Gebiet ist das des Travelling Salesmans.

2.2 Vorbild Natur

Im Tierreich lassen sich Möglichkeiten zur Lösung von Optimierungsproblemen finden. Tiere leben in Kolonien, bilden Schwärme und interagieren mit ihrer Umwelt und miteinander. Durch das Zusammenwirken der einzelnen Lebewesen über das soziale Verhalten gelingt es ihnen komplexe Aufgaben zu bewältigen. Die Koordination erfolgt dabei meist ohne zentrale Steuerung. Diese Dezentralisierung ist oft auch ein Designkriterium beim Entwurf moderner verteilter Informationssysteme. Dies setzt ein hohes Maß an Selbstorganisation voraus. Solche Systeme sind sehr flexibel, robust und fehlertolerant gegenüber dem Versagen einzelner Teile. Die aus dem sozialen Verhalten resultierende Gruppendynamik ist kaum vorhersagbar. In den hier betrachteten Algorithmen besitzen die einzelnen Lebewesen nur sehr eingeschränkte kognitive Fähigkeiten. Anspruchsvolle Aufgaben werden durch das gemeinschaftliche Verhalten erfüllt und nicht durch die Leistung eines Individuums. Diese Organisationsform wird Superorganismus2 genannt. Das emergente3 Verhalten auf der Mikroebene spiegelt seine Auswirkung erst auf der Makroebene wieder. Das ist der Grundgedanke der kollektiven Intelligenz, welche auch als Schwarmintelligenz bezeichnet wird. Das Zusammenwirken der spezialisierten Handlungsweisen übertrifft die Möglichkeit der einzelnen Mitglieder. Der klassische Superorganismus dieser Kategorie ist der Ameisenstaat. Eine einfache Form von Superorganismen stellen Schwärme dar. Zum Beispiel bewegen sich Fische im Schwarm, um Feinde zu irritieren.

2.3 Problemstellung

In dieser Arbeit geht es um das Lösen komplexer Schedulingprobleme mit evolutionären Schätzungsverfahren. Scheduling befasst sich mit der Erstellung von Ablaufplänen. Dabei werden einer begrenzten Anzahl von Ressourcen in einer bestimmten Reihenfolge Jobs zugewiesen. Die Ressourcen sind bei dieser Problemstellung Maschinen mit mehreren Load Ports und mehreren Bearbeitungseinheiten, so genannten Bedienern zur parallelen Verarbeitung. Die Jobs werden in der Warteschlange vor den Bedienern angeordnet und der Reihe nach abgearbeitet. Dieses analytische Warteschlangenmodelle dient zur Modellierung von Warteschlangensystemen. In dem hier gegebenen speziellen Problem werden kombinatorische sequenzabhängige Schedulingprobleme für eine Maschine behandelt. Kombinatorisch bezieht sich auf die möglichen Anordnungen der diskreten Objekte in der Warteschlange. Sequenzabhängig bedeutet, dass die zeitliche Reihenfolge der nicht unterbrechbaren Jobs ausschlaggebend für die Qualität der Lösung ist. Dabei kann nach verschiedenen einzelnen Kriterien oder Kombinationen von Kriterien optimiert werden. Einige häufige Zielkriterien sind:

- Durchsatz:

Möglichst viele Jobs werden innerhalb eines festgelegten Zeitraums fertig gestellt.

- Effektivität:

Die zur Verfügung stehenden Maschinen werden möglichst vollständig ausgelastet.

- Termintreue:

Jobs mit einem gegebenen Fertigstellungszeitpunkt erfordern eine termingerechte Einplanung.

- Verspätung:

Die Summe der Verspätungszeit aller Jobs soll so gering wie möglich gehalten werden.

Die in dieser Arbeit entscheidende Zielstellung ist die Maximierung des Durchsatzes und damit die Minimierung der Gesamtbearbeitungszeit. Der späteste Fertigstellungszeitpunkt Cmax (engl. Completion Time) aller Jobs ist dabei ausschlaggebend.

Cmax = max(CJob1,... ,CJobn) (2.1)

Als einfaches Beispiel für diese Problemstellung sei eine Maschine gegeben, welche nur eine Verarbeitungseinheit enthält. Die einzelnen Jobs werden in die Warteschlange vor dem Bediensystem einsortiert und ihrer Reihenfolge nach ohne weitere Nebenbedingungen abgearbeitet. Jede Anordnung der Jobs führt dann zur gleichen Gesamtbearbeitungszeit, sodass Cmax die Summe aller Rohprozesszeiten (RPT; engl. Raw-Prozess-Time) ist. Wenn für die

Bearbeitung mehrere Einheiten zur Verfügung stehen, dann ergibt sich ein NPvollständiges Problem4. Dafür existieren bisher keine praktikablen, konventionellen Lösungsverfahren. Schwerpunkt dieser Arbeit ist es, verschiedene Algorithmen zur Problemlösung für eine Maschine mit mehreren Bearbeitungseinheiten zu evaluieren. Die Erweiterung der Problemstellung für mehrere Maschinen und die Aufteilung der Jobs auf diese ist nicht Teil dieser Untersuchung. Dazu sei auf [Uhl09] verwiesen. Diese kombinatorische sequenzabhängige Schedulingaufgabe tritt in der Halbleiterindustrie während der Waferfertigung bei so genannten Cluster Tools auf. Aber auch in Krankenhäusern existiert dieses Problem, wenn Patienten den Räumen und Ärzten zugewiesen werden.

2.4 Basis der Optimierung

Cluster Tools sind spezielle integrierte Maschinen in der Halbleiterfertigung für die Waferbearbeitung. Diese Systeme dienen unter anderem der Reduzierung von Produktionszeiten. Einzelne Maschinen werden als Prozesskammern des Cluster Tools aufgefasst. Die Verbundmaschine kann mehrere Herstellungsprozesse parallel ausführen. Wafer mit vielschichtigen Prozessschritten lassen sich somit gleichzeitig bearbeiten. Der Vorteil gegenüber mehreren Einprozess-Maschinen besteht darin, dass die Wafer während der Herstellung das Gerät nicht verlassen müssen und im Hochvakuum im Inneren der Maschine verbleiben können, welches bei der Herstellung notwendig ist. Gleichzeitig werden Transportwege reduziert. Die Prozesssierungszeit von den einzelnen Jobs im Cluster Tool hängt von der Kombination parallel verarbeiteter Aufgaben ab. Der Produktionsprozess der Jobs wird durch die Parallelverarbeitung verlangsamt, da Konkurenz um die Ressourcen besteht. Im Allgemeinen sinkt die Gesamtbearbeitungsdauer jedoch und der Durchsatz wird erhöht. Ansonsten sollten die Jobs sequenziell abgearbeitet werden, um die parallelisierte Produktion nicht gegenüber einer sequentiellen zu verlangsamen. Die Abbildung 2.1 zeigt die Veränderung Δ der Fertigstellungszeitpunkte C bei sequentieller und paralleler Verarbeitung von zwei Jobs (A und B) auf einem Cluster Tool.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Vergleich von sequentieller und paralleler Verarbeitung ([UR07], S. 1)

Die Reihenfolge der Eingangsjobs ist ausschlaggebend für die Verarbeitungszeit. Dabei weisen unterschiedliche Kombinationen auch unterschiedliche Prozesszeiten auf. Es besteht die Abhängigkeit der Produktionszeit von der Eingangssequenz. Die detaillierte Auswertung eines Schedules auf einem Cluster Tool benötigt mittels Simulation sehr viel Rechenaufwand. Um dennoch die günstige Möglichkeit einer Computersimulation zu nutzen, wird der Aufwand reduziert und die Verlangsamung bei Parallelverarbeitung der Jobs in einem so genannten ”SlowDownFaktor“ (SDF; dt. Verlangsamungsfaktor) für jede Jobkombination zusammengefasst. Dieses Modell der Matrix Prediciton Method zur annähernden Bestimmung von sequenzabhängigen Prozesszeiten ist beschrieben in [UR[07]]. Alle Kombinationen deren Parallelverarbeitung länger dauert als bei einer sequentiellen Verarbeitung sind einzeln und nicht parallel zu verarbeiten. Ebenfalls werden identische Rezepte sequentiell bearbeitet. Die Optimierung der Jobabarbeitung bei Cluster Tools stellt ein komplexes Schedulingproblem dar.

2.5 Aufbau und Funktionsweise eines Cluster Tools

Ein Cluster Tool besteht aus mehreren Prozesskammern, in denen die Wafer bearbeitet werden. Mögliche Herstellungsschritte sind beispielsweise Ätzen, Dotieren oder Beschichten. Die Wafer eines Loses durchlaufen diese Kammern nach einer bestimmten vorgegebenen Reihenfolge, welche in einem Rezept beschrieben ist. Des Weiteren besitzt die Maschine Load Ports, die als Schleuse zum betreten und verlassen der Lose in und aus der Bedieneinheit dienen. In Abhängigkeit der Anzahl dieser Schnittstellen kann eine Parallelverarbeitung stattfinden, so dass Wafer von mehreren unterschiedlichen Losen bearbeitet werden. Ein Transportroboter befördert die Siliziumscheiben zwischen allen Prozesskammern und Load Ports. Durch die gleichzeitige Bearbeitung der Wafer entsteht eine Konkurrenz der Jobs um die Ressourcen der Maschine und die Bearbeitungszeit steigt. Die Kombination der parallel verarbeiteten Lose bestimmt die jeweilige Prozesszeit. Aus diesem Grund wird nur die Rohprozesszeit bei einer alleinigen Verarbeitung angegeben und alle weiteren Einflüsse, inklusive der Losekombination, im SDF zusammengefasst. Die tatsächliche Verarbeitungsdauer errechnet sich aus der Rohprozesszeit multipliziert mit dem SDF. Welche Jobs zeitgleich prozessiert werden, hängt von der Reihenfolge in der Eingangssequenz ab. Ziel ist es, eine Sequenz zu finden, welche das Optimierungskriterium am besten erfüllt.

Diese Systeme besitzen eine starke Ähnlichkeit mit Jobshops, jedoch mit dem Unterschied, dass die Parallelverarbeitung der Jobs durch die Load Port-Anzahl begrenzt ist. Die Wafer müssen in Abhängigkeit vom Rezept die Prozesskammern mehrfach durchlaufen oder gewisse Kammern nicht durchwandern. Typische Load Port-Anzahlen liegen bei zwei bzw. vier. Ein Beispiel für ein CVD5 Cluster Tool zeigt die Abbildung 2.2.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Beispiel eines CVD Cluster Tools in der Halbleiterfertigung ([UR07], S. 1)

Weitere Komponenten des Cluster Tools sind:

- Vakuumhauptgerät, welches das Hochvakuum erzeugt und alle Elemente der Maschine verbindet
- Load Lock dient als Ablage der Lose zwischen den Load Ports und dem Vakuumhauptgerät
- Gerätevorschaltmodul bildet den Übergang zwischen den Load Ports und den Load Locks

2.6 Matrix Prediciton Method

Das Modell der Matrix Prediciton Method betrachtet das Cluster Tools als eine Black Box. Die Slow Down Faktoren dienen zum beschreiben des Verhaltens der Maschine von Außen. Die inneren Vorgänge werden abstrahiert. Die Anzahl der Prozesskammern ist unerheblich. Abbildung 2.3 stellt die Einflüsse auf das Black Box System dar.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Cluster Tools als Black Box ([Uhl09], S. 17)

Um das Verhalten von außen bewerten zu können, müssen Näherungswerte für die Prozesszeiten experimentell, simulativ oder auf Grundlage historischer Daten bestimmt werden. Zunächst ist die Rohprozesszeit für jedes Rezept im günstigsten Fall zu ermitteln. Dies geschieht indem die Jobs einzeln auf dem Cluster Tool prozessiert werden und keine Ressourcenkonkurrenz besteht. Tabelle 2.1 zeigt exemplarisch die Rezeptarten und deren RPT. Damit die Konkurrenz der Rezepte um die Ressourcen beschrieben werden kann, ist anschließend für jede mögliche Rezeptkombination die Gesamtbearbeitungszeit zu bestimmen. Dies geschieht ebenfalls über Experimente, Simulationen oder reale Daten, in der die Komposition verarbeitet wird. Aus dem Verhältnis von RPT und Durchlaufzeit (DLZ) bei der jeweiligen Komposition ergibt sich der SDF nach Formel 2.2. Für zwei Jobs A und B und zwei Loadports berechnet sich der SDF von A dementsprechend nach Formel

2.3 ([UR07], S. 2). Dabei bezeichnet CT die Fertigstellungszeit (engl. Cycle Time).

Abbildung in dieser Leseprobe nicht enthalten

Somit enthält die SDF Tabelle 2.2 für jede Rezeptkombination einen Wert für jedes Rezept. Die Anzahl der parallel unterschiedlichen Rezepte in einer Zusammenstellung ist durch die Load Ports begrenzt. Die Schätzung der Prozesszeit erfolgt somit ohne Kenntnis der inneren Abläufe im Tool. Dadurch kann auch die genaue Zusammensetzung der Rezepte, also die Reihenfolge der Prozesskammern, vernachlässigt werden. Es ist lediglich die Art der Rezepte zu unterscheiden, welche eingegeben werden.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1: Beispiel für RPT Tabelle 2.2: Beispiel für SDF

Tabelle Tabelle

Die Berechnung des Schedules von der gegebenen Warteschlange auf Basis der SDF geschieht auf folgende Weise [Uhl08]:

1. Solange Jobs in der Warteschlange vorhanden sind und freie Load Ports existieren, belege alle freien Load Ports mit den Jobs der Warteschlange der Reihenfolge entsprechend. Bei identischen Rezepten in den Load Ports ist immer nur eins aktiv. Die anderen werden blockiert.

2. Aktualisiere den SDF und die CT für jeden aktiven Job i im Cluster Tool wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

3. Ermittle den nächsten Simulationszeitpunkt (tnext). Setzte den

Fertigstellungszeitpunkt aller Jobs im Cluster Tool und gibt den Job mit dem minimalen Fertigstellungszeitpunkt zurück.

Abbildung in dieser Leseprobe nicht enthalten

4. Berechne die verbleibende RPT für die restlichen Jobs in dem Cluster Tool.

Abbildung in dieser Leseprobe nicht enthalten

5. Solange noch Jobs vorhanden sind, kehre zum ersten Schritt zurück.

Aus dem entstehenden Schedule kann jede Zielfunktion errechnet werden, welche ausschließlich die Jobzeitpunkte benutzt. Beispiele dafür wurden bereits im Abschnitt 2.3 genannt. Die Zielfunktion ist vom Zielkriterium abhängig und wird auch Fitnessfunktion genannt. Der erreichte Wert nennt sich dementsprechend Fitnesswert. Die Ergebnisse des Modells stimmen in einem hohen Maß mit den tatsächlichen Werten überein [UR07]. Allerdings sind diese Werte erheblich schneller zu bestimmen, als bei der aufwendigen Analyse. Für alle in diesem Beleg erstellten Simulationen wird dieses Modell angewendet.

2.7 Struktur des Suchraumes und Lösungsansätze

Der Suchraum besteht aus allen möglichen Anordnungen der Jobs in einer Reihenfolge. Die Anzahl aller Permutationen (Sall) einer Menge von Jobs (L - Anzahl der Jobs) berechnet sich wie folgt.

Abbildung in dieser Leseprobe nicht enthalten

Da hauptsächlich das Bewertungskriterium Cmax betrachtet wird, ist nur die Rezeptart an der entsprechenden Position entscheidend. Gleiche Rezepte (R Anzahl der Jobs einer Art) sind demzufolge nicht zu unterscheiden. Da eine Rezeptart mehrfach in der Sequenz auftreten kann, ergibt sich das stochastische Problem der Permutationen mit Wiederholungen. Dadurch verringert sich die Größe des Suchraumes. Die Anzahl aller möglichen Zusammensetzungen von Permutationen mit Wiederholungen (Spermu) wird wie folgt berechnet.

Abbildung in dieser Leseprobe nicht enthalten

Um das globale Optimum für eine Problemstellung zu finden, müssen sämtliche Kombinationen als Warteschlange simuliert werden. Bisher existiert kein effizientes universelles Optimierungsverfahren, das stets das beste Resultat findet, welches nicht alle Möglichkeiten testet. Das exponentielle Wachstum des Lösungsraumes erschwert die vollständige Suche.

An dem folgenden Beispiel wird das Problem ersichtlich.

Jobsequenz: AAABBBCCCDDDEEEFFF

Abbildung in dieser Leseprobe nicht enthalten

Wenn in jeder Sekunde 1.000 Möglichkeiten ausprobiert werden können, benötigt die Simulation rund 4 Jahre.

Da der Problemraum schon bei dieser geringen Sequenzlänge eine schwer beherrschbare Größe annimmt, ist es zeitlich nicht akzeptabel die Aufgabe mit einem Brute Force Ansatz zu lösen, um das globale Optimum zu finden. Aus diesem Grund wurden verschiedene alternative Strategien entwickelt, um das Problem zumindest bestmöglich zu lösen. Das Ziel dabei ist es, in einem zeitlich angemessenen Rahmen, möglichst nah an das globale Optimum zu gelangen. Da nicht alle Alternativalgorithmen geeignet sind, hat die Auswahl der, für das Problem angewendeten Methode eine wesentliche Auswirkung auf die Qualität der Lösung.

Um dieses komplexe Problem bestmöglich zu lösen, werden so genannte Metaheuristiken eingesetzt. Spezielle Alternativalgorithmen haben die hierfür problematische Eigenschaft nach nur einem optimalen Wert zu suchen. Diese sind eindeutig zielführend, wenn der Suchraum eine streng monotone Konvergenz besitzt. Abbildung 2.4 zeigt ein Beispiel im dreidimensionalen Raum. Dies ist unter anderem bei unimodalen Funktionen der Fall. Das bedeutet, das einzige lokale Extremum stellt gleichzeitig das globale Extremum dar. Die hier gegebene Problemstellung spannt aber einen multimodalen Suchraum auf. Abbildung 2.5 zeigt ein Beispiel im dreidimensionalen Raum. Es existieren mehrere lokale und zumeist auch mehrere globale Extremstellen. Dies ist ein Problem, das bei bestimmten Verfahren auftritt, da nach einer gewissen Anzahl von Verbesserungsschritten meist ein lokales Optimum erreicht wird. Metaheuristiken zeichnen sich dadurch aus, dass sie nur wenige oder keine Annahmen über das Problem benötigen und große Lösungsräume durchsuchen können. Einige Algorithmen zeichnen sich zusätzlich durch die Möglichkeit aus, lokale Optima wieder zu verlassen und nach besseren Ergebnissen zu suchen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.4: Unimodaler

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.5: Multimodaler

Lösungsraum Lösungsraum

Um die Lösungssuche zu vereinfachen, müssen im Modell alle relevanten Parameter von den zu vernachlässigenden Einflüssen abgetrennt werden, da jeder Freiheitsgrad die Dimension des Optimierungsproblems erhöht. Die Aufgabenstellung spannt in Abhängigkeit der vorgegebenen Jobs einen mehrdimensionalen Suchraum auf. Eine Darstellung des kompletten Ergebnisraumes gestaltet sich daher für hohe Dimensionsordnungen problematisch. Die Erkenntnisgewinnung, sowie das Entwickeln von speziell angepassten Algorithmen und die Justierung der Heuristiken auf das Problem, wird dadurch erschwert.

Optimierungen wurden in der Vergangenheit überwiegend experimentell durchgeführt. Dies verlangte ausgezeichnete Problemkenntnis und langjährige Erfahrung. Zumeist sind Versuche an realen Systemen kostenaufwendig und zeitintensiv. Die Evaluierung des Optimierungsfortschrittes erfordert oft die Herstellung und das Austesten von Prototypen. In Bereichen wie der Flugzeugkonstruktion sind solche Experimente häufig mit Risiken verbunden. In heutiger Zeit werden oft Computersimulationen eingesetzt, welche meist enorme Rechenleistung erfordern. Das Ziel besteht deshalb darin, möglichst wenige Versuche durchzuführen.

3 Algorithmen

Zur bestmöglichen Lösung der komplexen Problemstellung des kombinatorischen sequenzabhängigen Schedulings werden die naturinspirierten Verfahren Ant Colony Optimization (ACO; dt. Ameisenalgorithmus) und Particle Swarm Optimization (PSO; dt. Partikel Schwarm Algorithmus), sowie das einfache heuristische Optimierungsverfahren Random Down Swing (RDS) eingesetzt. Die ACO und PSO Verfahren gehören zu den Evolutionären Algorithmen [EA10], welche auf Grundlage der Schwarmintelligenz operieren. Alle Verfahren gehören in die Kategorie der Metaheuristiken. Solche Strategien dienen zur näherungsweisen Lösung eines kombinatorischen Optimierungsproblems, bei denen der Zufall einen entscheidenden Einfluss besitzt. Metaheuristiken definieren eine abstrakte Folge von Handlungsschritten, die auf verschiedene Problemstellungen angewandt werden können. Sie eignen sich für Probleme, bei denen kein effizienter Lösungsalgorithmus bekannt ist. Allerdings ist nicht garantiert, dass die Heuristik eine optimale Lösung findet. Ein Vorteil der Metaheuristiken ist, dass bei einer Veränderung der Problemparameter während der iterativen Lösungssuche sich der Algorithmus dynamisch auf die neue Gegebenheit anpasst. Mehrfache Ausführung bei ein und dem selben Problem kann zu unterschiedlichen Ergebnissen führen. Dies resultiert aus der Einbeziehung von Zufallsentscheidungen.

Die drei Verfahren RDS, ACO und PSO werden mit weiteren Algorithmen in unterschiedlichen Simulationen verglichen. Die Vergleichsalgorithmen sind Random Walk, Simulated Annealing und ein genetischer Algorithmus. Die rein zufallsbasierte Monte Carlo Methode bildet den Referenzwert für alle Verfahren, falls kein Optimum bekannt ist. Sofern rechentechnisch realisierbar, wird der optimale Wert mittels Brute Force ermittelt. Anhand dessen lässt sich die Leistung der Algorithmen präziser bewerten. Alle Verfahren werden zu Beginn mit einem Evaluator initialisiert. Dieser beinhaltet das zu optimierende Zielkriterium. Anschließend erfolgt der Aufruf des entsprechenden Algorithmuses mit den Jobs und den Maschinen.

3.1 Random Down Swing

Das in dieser Arbeit entwickelte Random Down Swing (RDS) Verfahren basiert auf dem Random Walk (RW) Algorithmus. Die beiden Verfahren gehören zu den Hill Climbing (HC) Strategien. Das Grundprinzip des HC besteht darin eine Anfangslösung iterativ zu verbessern. Dabei bleibt ein Iterationsschritt erhalten, wenn eine Verbesserung hinsichtlich der Zielfunktion eingetreten ist. Eine Veränderung, die keine Verbesserung im Vergleich zum vorherigen Ergebnis darstellt, wird rückgängig gemacht. Der Basisalgorithmus RW beginnt mit einer zufällig erzeugten Lösung und sucht anschließend nach nur einem optimalen Wert. Bei einem streng monoton konvergenten Suchraum liefert der Algorithmus das globale Extremum. Die hier gegebene Aufgabenstellung beinhaltet jedoch einen multimodalen Suchraum. Dies stellt ein Problem für das RW Verfahren dar, da es häufig in einem lokalen Optimum stagniert. Dieser Nachteil wird durch die RDS Strategie in den meisten Fällen behoben, indem mehrfach nach den besten Lösungen gesucht wird. Der Algorithmus wählt, nach der Stagnation in einem Extremum, eine neue zufällige Anfangslösung und beginnt erneut mit der Suche. Die Abbildung 3.1 zeigt den Unterschied und gleichzeitig den Einfluss des Zufalls bei der Lösungsfindung. Abhängig vom zufälligen Startpunkt und dem zufallsbasierten Veränderungsschritt, welcher die Suchrichtung bestimmt, erreichen die Algorithmen das lokale oder das globale Optimum. In der Abbildung 3.1 a erreicht der Random Walk nur das lokale Extremum. Die Abbildung 3.1 b zeigt beim RDS die mehrfache Suche und den Einfluss der Suchrichtung, welche mit entscheidend ist, ob das lokale oder das globale Optimum gefunden wird.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Beispiel für Einfache-Lösungssuche (a - Random Walk) und

Mehrfach-Lösungssuche (b - Random Down Swing)

3.1 Random Down Swing

3.1.1 Implementierung

Der Pseudocode lautet für den RDS wie folgt:

1. Erzeuge eine zufällige Jobsequenz.
2. Vertausche zwei zufällige Jobs und inkrementiere den Zähler für Verbesserungsversuche.
3. Wenn der Fitnesswert sich verbessert hat, bleibt der Tausch erhalten, anderenfalls werden die beiden Jobs zurück gewechselt.
4. Prüfe ob das aktuelle Ergebnis, das global beste ist und speichere es gegebenenfalls ab.
5. Wenn die gegebene maximale Anzahl an Verbesserungsversuchen erreicht ist, dann generiere eine neue zufällige Jobsequenz. Setze gleichzeitig den Zähler für Verbesserungsversuche auf Null.
6. Solange die maximale Anzahl der Iterationen nicht erreicht ist, kehre zu Punkt 2 zurück.

Der Random Down Swing Algorithmus erzeugt zu Beginn aus allen gegebenen Jobs eine zufällig gemischte Jobserie, um eine von der Eingabe unabhängige Startsequenz zu erhalten. In der folgenden Hauptschleife generiert ein Zufallsgenerator zwei unterschiedliche Zahlen. Diese stehen für Positionen in der Jobreihe. Eine Anweisung vertauscht die beiden Jobs an den entsprechenden Stellen in der Anordnung. Begleitend erhöht sich der Zähler für Verbesserungsversuche um eins. Anschließend findet eine Bewertung des Schedules statt.

Der Algorithmus kontrolliert, ob sich die Qualität des Ergebnisses durch den Tausch verbessert hat. Dabei wird das zu einer gemischten Jobserie zugehörige, beste Resultat gegebenenfalls aktualisiert. Dies sei als lokale Lösung für eine Jobsequenz definiert, welche versucht wird zu verbessern. Weiterhin prüft das Verfahren bei einer lokalen Verbesserung, ob der erzielte Wert ebenfalls der Beste bisher überhaupt erreichte ist. In diesem Fall muss die Abfolge und der erzielte Fitnesswert als globales Ergebnis gespeichert werden. Wenn keine lokale Verbesserung durch die Umformung eingetreten ist, wechselt das Programm die beiden Stellen zurück. Anderenfalls behält der Algorithmus die neue verbesserte Reihenfolge der Rezepte. Diese Prozedur wird bis zum Erreichen einer vorgegebene Anzahl an Verbesserungsversuchen durchgeführt.

Danach kann mit hoher Wahrscheinlichkeit angenommen werden, dass der Algorithmus ein lokales Optimum erlangt hat, von dem aus kein besseres Resultat erreichbar ist. Die Anzahl der Verbesserungsversuche ist entsprechend vorzugeben. Um ein besseres Ergebnis zu finden, ist es in dieser Situation zweckmäßiger den Algorithmus mit einem anderen Ausgangspunkt neu zu beginnen. Dafür wird eine neue, zufällig gemischte Jobsequenz erstellt und der Zähler für Verbesserungen auf Null gesetzt. Nun sucht der Algorithmus erneut nach einem Optimum.

Es besteht dabei die Möglichkeit, nicht wieder in der gleichen Lösung zu enden und ein anderes, besseres Resultat als Lösung zu finden. Die Hauptschleife beginnt von vorn bis die vorgegebene Anzahl an Iterationen abgearbeitet ist. Zum Schluss liefert der Algorithmus das globale Ergebnis zurück. Die Abbildung 3.2 verdeutlicht die Implementierung. Aus Verständlichkeitsgründen fällt die strukturelle Reihenfolge der Beschreibung anders aus als die Anordnung der Elemente der performanzorientierten Programmierung. Im Programm erfolgt zuerst die Bewertung des Schedules und danach wird die Jobsequenz novelliert.

Diese Arbeit hat unter anderem das Ziel, die vermutlich nötig Anzahl von Swaps heraus zu finden, bis der Algorithmus in einem lokalen Optimum stagniert. Die Iterationsanzahl beeinflusst ebenfalls die Anzahl von Verbesserungsversuchen, ab welchem Wert es zweckmäßiger ist mit einer neuen gemischten Jobsequenz fortzusetzen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Flussdiagramm des Random Down Swing Algorithmus

3.1.2 Optimierung

Die Betrachtung des Zielkriteriums des spätesten Fertigstellungszeitpunktes Cmax ermöglicht eine Verbesserung des Verfahrens. Die Effizienz der Tauschungen lässt sich dadurch steigern, indem geprüft wird, dass die zwei erzeugten Zufallszahlen Positionen von Rezepten unterschiedlicher Art sind. Somit geschieht wirklich eine Veränderung im Sinne des Kriteriums. Bei einem Swap von gleichartigen Jobs ändern sich die Rohprozesszeit und die Slow Down Faktoren an den entsprechenden Stellen nicht, der Schedule und der letzte Fertigstellungszeitpunkt bleiben gleich. Somit verändert sich auch das Zielkriterium Cmax nicht, welches vom spätesten Zeitpunkt abhängig ist. Durch die eine Iteration entsteht kein Wissenszuwachs.

3.1.3 Modifikationen

Anstatt einen Tausch von zwei Jobs vorzunehmen, kann ein Job verschoben werden. Die erste Zufallszahl steht für die Position des Jobs, der an der Stelle der zweiten generierten Zahl positioniert wird. Dabei kommt es zum Verschieben meist mehrerer aufeinanderfolgender Jobs um eine Position.

Eine weitere Möglichkeit besteht darin, den Zähler für Verbesserungsversuche, bevor eine komplett neu gemischte Jobsequenz entsteht, nur bei jedem Fehlversuch zu erhöhen. Dadurch wird eine tatsächliche Verbesserung nicht als Versuch gezählt.

Die letzte hier vorgestellte Maßnahme zu Optimierung des Verfahrens ist, den Zähler für Verbesserungsversuche bei jeder tatsächlichen Verbesserung auf Null zurückzusetzen. Somit steht in jeder Stufe die volle Anzahl von Versuchen zur Verfügung. Nach jeder Veränderung verschiebt sich der Schedule, sodass bereits versuchte Vertauschungen, die vorher zu keiner Leistungssteigerung geführt haben, nun zu einer Verbesserung führen können. Somit ergibt sich in jeder Stufe eine neue Aufgabenstellung, wobei wieder alle Möglichkeiten, bis auf den gerade ausgeführten Swap, offen sind. Dies rechtfertigt eine Zurücksetzung des Zählers.

3.2 Ameisenalgorithmus

Der italienische Wissenschaftler Marco Dorigo ließ sich von der Nahrungssuche der Ameisen inspirieren und übertrug 1991 als Erster das heuristische Verfahren auf ein kombinatorisches Optimierungsproblem. Die Idee der Lösungssuche wandte der Mathematiker erfolgreich auf das so genannte Traveling Salesman Problem an ([Boy04a], S. 1). Prinzipiell ist die Handlungsvorschrift jedoch auf jedes kombinatorische Optimierungsproblem anwendbar. Es kann aber nicht garantiert werden, dass das Problem optimal gelöst wird.

3.2.1 Das Vorbild in der Natur

Den Ausgangspunkt stellen die Ameisen in der Natur dar. Die bestmögliche Futterversorgung dieser ist gewährleistet, wenn viel Futter in kürzester Zeit zum Nest gelangt, welches am günstigsten über den kürzesten Weg verwirklicht werden kann. Ameisen errichten Straßen zwischen ihrem Nest und dem Futter fast immer auf einem optimalen Weg. Dies ist sehr erstaunlich, da die Tiere zwar Augen besitzen, aber durch ihre geringe Größe keinen Überblick über ihre Umgebung bekommen.

Durch folgende zwei Methoden gelingt es den Ameisen dennoch, einen kurzen, oft sogar den kürzesten Weg zu finden.

- Die Tiere können mit ihrer Drüse am Hinterleib Pheromone1 auf den Weg absondern. Artgenossen können dies als Wegweiser nutzen.
- Die Ameisen treffen ihre Wegwahl mit einer Wahrscheinlichkeitsentscheidung, wobei die Wahrscheinlichkeit proportional zur Stärke der Kennzeichnung mit Pheromon ausfällt. Das bedeutet, je stärker ein Weg markiert ist, desto höher ist die Chance bei der Auswahl.

Mit diesen beiden Methoden kann die Ameisenkolonie das kombinatorische Optimierungsproblem lösen, wohingegen eine einzelne Ameise dazu nicht in der Lage wäre. Über das Pheromon werden die vergangenen Wegentscheidungen für die Nachfolger gespeichert und bilden damit eine Art kollektives Gedächnis. Dieses Verhalten entspricht Schwarmintelligenz.

Methoden der Ameisen - ein Beispiel aus der Natur

Das folgende Beispiel verdeutlicht das Zusammenwirken der Ameisen und deren Methoden, um eine optimierte Lösung zu finden.

Auf dem Weg zwischen Ameisenhaufen und Futter liegt eine Barriere. Die Tiere können zwischen der zeitlich langen Route oder der kurzen Route wählen um die Blockade zu umgehen. In der Abbildung 3.3 ist der Versuchsaufbau dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Versuchsaufbau der Futtersuche von Ameisen

Die Lebewesen wandern paarweise mit einer konstanten Rate aus dem Bau. Die Bewegungsgeschwindigkeit aller Ameisen ist gleich. Auf dem Weg zum Futter stoßen beispielsweise zwei Tiere auf das Hindernis, wobei keine Orientierungsmöglichkeit besteht. Da keine der beiden Strecken mit Pheromon bestäubt ist, sei unterstellt, dass eine Ameise den langen Pfad und die andere Ameise den kurze Pfad einschlägt. Nach einer gewissen Zeit, kriechen die nächsten Tiere aus dem Bau und gelangen an die Schranke. Folgende Situationen entstehen:

1. Die Wahrscheinlichkeit für beide Wege ist gleich, so wie beim ersten Ameisenpaar. Die beiden Routen wurden entweder einmal mit Pheromon gekennzeichnet, falls die ersten beiden Tiere noch unterwegs sind, oder zweimal markiert, falls die Tiere bereits zurück gekehrt sind.
2. Der entscheidende Fall ist der, dass die eine Ameise auf der kürzeren Strecke wieder zum Nest zurückgekehrt ist, da die Tour weniger Zeit im Vergleich zur langen Strecke beansprucht. Die andere Ameise auf dem längeren Pfad ist jedoch noch unterwegs. Dadurch wurde der schnelle Weg mit zwei Pheromon Einheiten und der langsame nur mit einer Pheromon-Einheit markiert. Somit wählen die nächsten Ameisen mit höherer Wahrscheinlichkeit die kurze Route anstatt die lange.
3 Algorithmen

Die Wegfindung auf dem Rückweg geschieht auf die gleiche Weise, wie beim Hinweg. Der Pfad mit der höheren Pheromonintensität erhält die größere Wahrscheinlichkeit. Als Sonderfall sei auf die erste Ameise an der Futterquelle hingewiesen. Da die Tiere ein sehr gutes Gedächnis besitzen und keine andere Route bekannt ist, nehmen sie den gleichen Weg zurück. Wenn die Futterquelle aufgezehrt ist, verflüchtigen sich die Duftspuren mit der Zeit durch Umwelteinflüsse.

Verallgemeinert werden kann Folgendes. Ameisen nutzen aus, dass kürzere Wege schneller zu passieren sind und dadurch eher mit erhöhter Pheromonkonzentration gekennzeichnet werden. Die Anziehungskraft steigt langsam iterativ durch die zunehmenden Pheromonspuren weiter an und damit auch die Wahrscheinlichkeit für die kurze Wegauswahl. Somit befindet sich mit der Zeit auf dem kürzeren Pfad eine höhere Pheromonkonzentration als auf den anderen. Es entsteht die bekannte Ameisenstraße. Der lange Weg wird kaum noch benutzt.

Nun gibt es sowohl in der Natur als auch bei Optimierungsproblemen eine größere Anzahl an Stufen der Entscheidung und mehr Möglichkeiten als bei der Lösungsfindung im Beispiel. Dementsprechend benötigt die Konvergenz gegen ein optimiertes Ergebnis viele Versuche und ausreichend Zeit. Das Prinzip bleibt jedoch das Gleiche. Die Biologen Pastel, Goss und Deneubourg haben in mehreren Experimenten, z.B. im so genannten Double-Bridge-Experiment, die Resultate bestätigt [DAG+89].

Notwendige Irregularität

Die Wahrscheinlichkeitsentscheidung spielt bei der Wegauswahl noch eine weitere wichtige Rolle. Wenn alle Ameisen lediglich dem stärker gekennzeichneten Pfad folgen, dann kann eine anfänglich schlechte Wegwahl nicht behoben werden. Die ungünstige Route wird dann nicht auf Grund der schnelleren Verbindung zur meist benutzten Straße, sondern nur wegen der stärker markierten Richtung. Wenn in dem Beispiel aus Abschnitt 3.2.1 die Tiere zu Beginn den längeren Weg nehmen, dann sollte trotzdem die Ameisenstraße nicht auf dem langen Pfad entstehen. Manche Tiere weichen von den mit Pheromon gekennzeichneten Wegen ab und untersuchen neue Möglichkeiten. Wenn eine Ameise eine Abkürzung findet, dann kennzeichnet sie den Erfolg mit Pheromonabgabe auf der neuen Strecke. Weitere Ameisen folgen darauf hin und es gibt eine Optimierung. Die anfängliche

Fehlentscheidung verliert an Bedeutung. Auf diese Art können lokale Optima überwunden und zu besseren Varianten bis hin zum globalen Optimum verändert werden. Durch den Ameisenalgorithmus ist es somit möglich, den kürzesten Weg zu finden. Dies kann allerdings nicht garantiert werden.

3.2.2 Anwendung auf Scheduling

Der Ameisenalgorithmus wird auf das Schedulingproblem angewendet. Gesucht ist eine Sequenz mit einer geringst möglichen Durchlaufzeit. Dazu werden die einzelnen Methoden des Ameisenalgorithmus wie folgt übertragen. Die Wegentscheidung der Ameisen ist in diesem Optimierungsproblem die Entscheidung, welches Rezept an welcher Stelle der Sequenz steht. Für jede Position wird ein Array geführt, welches für jede Rezeptart die Wahrscheinlichkeit enthält, sich an dieser Position zu befinden. Das Ganze lässt sich als eine Matrix auffassen. Zu Beginn erhält das Gitter eine Vorbelegung, in der alle Wahrscheinlichkeiten gleichverteilt sind. Dies vereinfacht die Implementierung.

Die Bewertung der einzelnen Entscheidungen, welches Rezept an welcher Stelle bevorzugt wird, erfolgt erst am Ende eines Suchdurchlaufes und nicht wie bei dem Anschauungsobjekt in der Natur mit der Pheromonablage während der Wegsuche. Dies hat folgende Bewandtnis. Die Optimierung bei den Ameisen passiert auf dem Rückweg der einzelnen Tiere. Je schneller sie zurückkehren, desto besser ist der Weg. Da jedoch im vorliegenden Optimierungsproblem kein Rückweg in dem Sinne der Ameisen besteht, sondern nur die Gesamtverarbeitungsdauer des Ergebnisses existiert, genügt es, erst im Nachhinein die entsprechenden Entscheidungen mit einer qualitativen Wertung des Ergebnisses zu markieren.

Die Wahrscheinlichkeitsauswahl, welches Rezept als nächstes an der entsprechenden Position steht, erfolgt über eine Monte Carlo Auswahl. Bei dieser werden alle Wahrscheinlichkeiten für eine Position aufsummiert und ergeben den Gesamtwert S. Zur Verdeutlichung sind die einzelnen Werte als Beispiel in einem Kreisdiagramm abgetragen, wie in der Abbildung 3.4. Anschließend erfolgt eine Generierung einer Zufallszahl im Bereich von 0 bis S. Daraufhin wird das Segment errechnet in dem die Zufallszahl liegt. Das Segment gibt das gewählte Rezept an. Je größer das Segment dabei ist, desto höher ist die Wahrscheinlichkeit, dass das Rezept ausgewählt wird. Dies ist analog zur Pheromonkonzentration auf den Wegen und der Richtungsentscheidung bei den Ameisen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.4: Beispiel für eine Monte Carlo Auswahl. Die Farben symbolisieren die verschiedenen Rezeptarten und die zugehörigen Prozente geben die Wahrscheinlichkeit der Auswahl an.

Es gibt mehrere Modifikationsmöglichkeiten für den Algorithmus. Diese werden in den folgenden Absätzen vorgestellt.

Modifikation 1 - Harmonisierung:

Entgegen dem Beispiel in der Natur lässt sich in den Mechanismus eine Berechnung einbauen, mit der eine Perspektive für den Zielwert geschätzt werden kann. Mit Hilfe des Wissens der gegenwärtig prozessierenden Rezepte im Cluster Tool und der möglichen neuen Hinzunahme des nächsten Jobs kann ein potentieller Verlangsamungsfaktor kalkuliert werden. Dadurch wird eine Harmonisierung dieser Möglichkeit symbolisiert. Aus diesem Faktor und der Wahrscheinlichkeit für das neue Rezept entsteht die tatsächliche Auswahlwahrscheinlichkeit. Je größer die Verlangsamung ist, desto mehr sinkt die Wahrscheinlichkeit. Somit erfolgt eine Wichtung nach den gegebenen Slow Down Faktoren und die Lösungssuche wird positiv beeinflusst. Für die Monte Carlo Auswahl muss daraufhin der maximale Zufallswert bei der Implementierung angepasst werden, da sich durch die Berechnung die Gesamtwahrscheinlichkeit ändert.

Modifikation 2 - Gruppierung:

Eine weitere Möglichkeit die Ergebnisse von einzelnen Durchläufen zu selektieren und zu werten besteht darin, mehrere Sequenzen in einer Gruppe zusammenzufassen. Von einer Gruppe dürfen dann nur die Sequenzen mit den besten Fitnesswerten eine Markierung auf dem Weg hinterlegen. Dadurch wird verhindert, dass schlechte Ergebnisse aus der Gruppe Spuren zurücklassen. Die Lösungssuche wird zielstrebiger und es erfolgt eine Einengung der Variationsmöglichkeit.

Modifikation 3 - Verwitterung:

Bei dieser Variation werden zurückliegende Lösungen abgeschwächt. In der Natur können die Pheromonspuren der Ameisen verwittern, z.B bei Regen. Es wird verhindert, dass folgende Lösungssuchen stets den gleichen Weg beschreiten. Dadurch entsteht eine gewünschte Abweichung der Ergebnisse von einer Lösung. Außerdem greifen zuletzt erzeugte Sequenzen auf die Erfahrung der Vorgänger zurück, sodass diese Ergebnisse aus der Suche gegenüber früheren, eher zufällig gefundenen Lösungen weiter verstärkt werden.

3.2.3 Implementierung

Der Pseudocode lautet für den ACO wie folgt:

1. Erzeuge die Wahrscheinlichkeitsmatrix.
2. Erstelle eine Jobsequenz mittels Monte Carlo Auswahl
3. Vergleich des Ergebnisses mit dem global besten und aktualisiere es gegebenenfalls.
4. Veränderung der Werte in der Wahrscheinlichkeitsmatrix für die Monte Carlo Methode entsprechend der Modifikation.
5. Solange die maximale Anzahl der Iterationen nicht erreicht ist, kehre zu Punkt 2 zurück.

Die bei der Eingabe übermittelten Jobs legen die Länge der zu erzeugenden Jobsequenz fest und liefern Informationen über die Anzahl der verschiedenen Rezeptarten. Mit dieser Erkenntnis wird zu Beginn des Ameisenalgorithmus eine Matrix mit Wahrscheinlichkeiten für die Monte Carlo Auswahl erstellt. Jede Spalte steht für eine Position in der Jobabfolge. Die einzelnen Einträge in dem Spaltenvektor enthalten die Wahrscheinlichkeiten für die unterschiedlichen Jobarten, sich an dieser Stelle zu befinden. Alle Zellen in der Matrix werden mit einem fest vordefinierten Startwert vorbelegt. Der Algorithmus benutzt ganzzahlige Werte für die Wahrscheinlichkeiten. Vorab ist eine minimale und maximale Wahrscheinlichkeit festzulegen. Damit erhält jeder Job eine Mindestwahrscheinlichkeit, wie auch jeder Weg bei den Ameisen diese besitzt. Zum Anderen werden mögliche Bereichsüberschreitungen und negative Werte verhindert.

Der Algorithmus erstellt im Hauptteil als erstes eine Sortier-Liste deren Elemente wiederum Listen sind. Die Sortier-Liste enthält für jede Rezeptart als Element eine Liste mit den einzelnen Jobs der zugehörigen, einen Art. Diese Sortierung der Rezepte in ihre eigene Tabelle, beschleunigt die folgenden Berechnungen. Als nächstes erstellt der Algorithmus eine Jobserie. Dazu wird für jede Position in der Jobreihe, von vorn beginnend, eine Monte Carlo Auswahl angestoßen. Dafür nutzt die Auswahl die entsprechenden Wahrscheinlichkeiten aus der Matrix und eine zuvor erstellte Liste der noch nicht in der Jobanordnung vorhandenen Jobs. Die entstandene Folge erhält anschließend durch den Evaluator eine Bewertung in Form des Fitnesswertes. Unterschiedliche Bewertungskriterien sind im Kapitel 2.3 aufgelistet. Eine Anweisung vergleicht das Ergebnis mit dem bisher besten Resultat. Die Jobserie mit dem günstigeren Wert wird als globale Lösung gespeichert. Nun erfolgt auf der Grundlage der erzeugten Jobsequenz eine gewichtete Veränderung der Wahrscheinlichkeiten in der Matrix, welche für die Monte Carlo Simulation dienen. Dies erfolgt je nach Modifikation, bzw. Kombinationen dieser, auf unterschiedliche Weise. Im folgenden Abschnitt werden mehrere mögliche Modifikationen erläutert. Nach Beendigung aller Wiederholungen liefert der Algorithmus das beste gefundene Ergebnis zurück.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.5: Flussdiagramm des Ameisenalgorithmus

3.2.4 Monte Carlo Auswahl

Bei diesem Auswahlverfahren muss zuerst festgestellt werden, welche Rezeptarten aus allen verbleibenden Jobs noch zur Verfügung stehen und nicht bereits in der Jobsequenz enthalten sind. Dazu iteriert eine Schleife über die Sortier-Liste und kontrolliert, ob die Unterliste mindestens ein Element enthält. In diesem Fall muss der dazugehörige Wert aus der Wahrscheinlichkeitsmartix auf einen Summationswert S addiert werden. Dieser Wert S bildet nachher die Obergrenze für den Zufallsgenerator. Nachdem alle Wahrscheinlichkeiten von allen noch zur Verfügung stehenden Rezeptarten aufsummiert sind, generiert der Zufallsgenerator mit der Obergrenze S eine Zahl. Diese liegt in einem Wahrscheinlichkeitsbereich eines Jobs, welcher zu ermitteln ist. Dazu summiert eine Schleife, wie schon zuvor, die einzelnen Bereiche der Jobchancen auf, bis der entsprechende Bereich gefunden ist, in dem die Zufallszahl liegt. Auf diese Weise wählt der Generator zufällig einen Job aus, aber mit der entsprechenden Wahrscheinlichkeit. Der zum Wahrscheinlichkeitsbereich zugehörige Job wird zurückgeliefert und aus der Unterliste entfernt, damit er bei der nächsten Auswahl nicht mehr gewählt werden kann. Der Vorteil an diesem Verfahren besteht darin, dass die Sortier-Liste stets nur noch die verbleibenden, unpositionierten Jobs enthält und erneut mit diesem Speicher aufgerufen werden kann. Weil der Algorithmus nur mit ganzzahligen Wahrscheinlichkeitswerten arbeitet, entfällt die Normierung der Auswahlbereiche auf 100%.

Die folgenden Abschnitte erläutern die Implementierung der Modifikationen aus Kapitel 3.2.2.

Wahrscheinlichkeitsveränderung nach dem Vorbild der Natur

Das Optimierungskriterium der zeitlichen Differenz beim Beschreiten von langen und kurzen Weg bei den Ameisen, kann nicht direkt übertragen werden. Als Alternative wurde ein Kriterium entwickelt, dass sich dynamisch an die erreichten Ergebnisse des Algorithmus anpasst und dennoch stets zu einer Verbesserung der bisherigen Lösungen beiträgt.

Dazu wird ein erhaltenes Scheduleergebnis als erstes auf einen Ergebnisdurchschnittswert M addiert. M besitzt als Startwert die Summe der RPTs der einzelnen Jobs SRPT. Dies verhindert eine zu schnelle Konvergenz des Gütekriteriums gegen einen niedrigen Wert. Dadurch werden eventuelle anfängliche Startprobleme umgangen. Anschließend vergleicht die Modifikation den aktuellen Fitnesswert mit M, dem Durchschnitt von allen bisher erreichten Ergebnissen. Die folgende Formel 3.1 verdeutlicht das Gütekriterium.

Abbildung in dieser Leseprobe nicht enthalten

Wenn die derzeitige Lösung besser ist, werden alle entsprechenden Wahrscheinlichkeiten (P) in der Matrix, die von der Rezeptart und der Position in der gegenwärtigen Sequenz abhängen, positiv verändert. Der neue Wert ergibt sich aus dem bisherigen, plus eines vorher festgelegten Bonuswertes. Dieser Bonuswert symbolisiert die Pheromonkonzentration, die eine Ameise auf dem Weg hinterlässt. Dabei ist das Überschreiten der Grenzwerte von den Wahrscheinlichkeiten zu prüfen. Die Höhe des Bonuswertes, welche zu einer günstigen Konvergenz führt, ist in dieser Arbeit zu ermitteln. Weitere davon abweichende Varianten sind das Wichten und Bestrafen. Beide gehören ebenfalls in diese Modifikationskategorie. Beim Wichten wird der auf die Wahrscheinlichkeit zu addierende Bonuswert um einen Faktor erhöht. Um so mehr der Fitnesswert von der Summe der Rohprozesszeiten SRPT der einzelnen Jobs abweicht, desto größer wird der Additionswert. Dadurch erhalten bessere Ergebnisse auch mehr Einfluss auf die nachfolgenden Simulationen. Die folgende Formel 3.2 zeigt die genau Berechnung.

Abbildung in dieser Leseprobe nicht enthalten

Die Variation des Bestrafens verringert die entsprechenden Wahrscheinlichkeiten um den Bonuswert, falls der Fitnesswert höher als M liegt. Nicht favorisierte Resultate werden dadurch auch negativ Beeinflusst. Diese Varianten werden ebenfalls betrachtet.

Wahrscheinlichkeitsveränderung nach Harmonisierung

Aufbauend auf der Idee der Harmonisierung entstand der Strong Derivative Algorithmus. Dieser wird im folgenden Kapitel 3.4.6 beschrieben. Die Auswertung der Ergebnisse dieses Algorithmus zeigt, dass keine zufriedenstellenden Lösungen erzeugt werden können. Zudem würden sich die ohnehin schon lang andauernden Berechnungen weiter verzögern. Aus diesen Gründen wird die Modifikation der Harmonisierung, die dem Algorithmus zu Grunde liegt, in der Arbeit nicht weiter untersucht.

Wahrscheinlichkeitsveränderung nach Gruppierung

In dieser Abwandlung erfolgt eine Veränderung der Wahrscheinlichkeitsmatrix nur nach bestimmten Iterationen. Die Resultate dieser Wiederholungen werden als Gruppe zusammengefasst. Die Gruppengröße ist vorher zu definieren. Der Algorithmus durchläuft die Hauptschleife mehrfach und speichert aus der jeweiligen Gruppierung nur eine fest vorgegebene Anzahl von besten Jobsequenzen mit ihrem Fitnesswert ab. Beispielsweise werden die fünf besten Ergebnisse aus zehn Wiederholungen gesichert. Dazu sammelt das Verfahren alle Resultate des Ameisenalgorithmus in einer Bestenliste. Sobald diese Liste die vorgegebene Größe überschreitet, wird das schlechteste Ergebnis aus der Bestenliste gelöscht. Wenn die Gruppenstärke erreicht ist, erhöht der Algorithmus die Wahrscheinlichkeiten der Rezeptarten entsprechend ihrer Position in den Sequenzen. Dafür iteriert eine Schleife über die Liste der besten Jobserien. Eine weitere innere Schleife ermittelt die Rezeptart an den jeweiligen Stellen und die zugehörigen Auswahlchancen in der Matrix. Diese Werte werden daraufhin um den Bonuswert erhöht. Abschließend ist die Bestenliste zu löschen, da die nächste Gruppe betrachtet wird. Als weitere Variation könnte eine Liste mit den schlechten Jobreihen geführt werden, wobei die entsprechenden Wahrscheinlichkeiten negativ zu bewerten sind.

Wahrscheinlichkeitsveränderung nach Verwitterung

Nach dem Vorbild der Natur kann zusätzlich zu den anderen Modifikationen noch eine Verwitterung eintreten. Dazu werden nach jeder Iteration alle Wahrscheinlichkeiten um einen geringen Betrag verringert. Die zuletzt erzeugten Ergebnisse erhalten dadurch eine höhere Bedeutung gegenüber weiter zurückliegenden. Eine weitere Variante wäre den Bonuswert bei fortgeschrittener Iterationszahl zu erhöhen, da auf mehr Erfahrung zurückgegriffen wird.

3.3 Partikel Schwarm Algorithmus

Der Partikel Schwarm Algorithmus (PSO; engl. Particle Swarm Optimization) wurde von Dr. Eberhart und Dr. Kennedy im Jahre 1995 zur Lösung kontinuierlicher Probleme entwickelt ([BS07], S. 13). Inspiriert vom sozialen Verhalten von Vogelscharen und Fischschwärmen entstand eine populationsbasierte stochastische Optimierungstechnik.

Grundlage dafür bildet folgendes Szenario. Eine Gruppe von Vögeln sucht in einem Gebiet Futter. Die Suche erfolgt dabei zufällig. In diesem Gebiet gibt es genau ein Stück Futter. Die Vögel wissen nicht, wo die Nahrung liegt. Aber vorausgesetzt wird, dass die Tiere zu jeder Zeit Kenntnis über die eigene Entfernung zum Futter haben. Nun ist die beste Strategie um das Futter zu finden, dem Vogel zu folgen, der den geringsten Abstand zum Ziel besitzt. [Hu10]

3.3.1 Das Vorbild der Natur

Die Basis für die PSO entstand im Jahre 1987. Angetrieben von der ästhetischen Choreographie, erfand Reynolds das so genannte Boids Modell. Jeder Boid stellt ein einzelnes Individuum dar und verhält sich den drei folgenden Regeln entsprechend. ([BS07], S. 13)

-Ausrichtung:

Ein Boid bewegt sich in die gleiche Richtung, wie seine Nachbarn.

-Kohäsion:

Ein einzelner Boid bewegt sich zum Mittelpunkt einer definierten Gruppe.

-Separation:

Die Bewegung der Boids strebt auseinander, wenn der Abstand zueinander zu gering ist.

Die Wirkung der einzelnen Regeln ist in Abbildung 3.6 veranschaulicht. Der grün gefärbte Boid richtet sich je nach Regel an seinen Nachbarn aus. Die Spitze der Dreiecke gibt die aktuelle Bewegungsrichtung an. Der Pfeil zeigt die Veränderung durch die jeweilige Regel. Alle Boids innerhalb des grau hinterlegten Kreises gehören zu einer Gruppe und beeinflussen den selektierten Nachbarn.

[...]


1 Evolution ist die Veränderung der vererbbaren Merkmale einer Population von Lebewesen von Generation zu Generationen.

2 Der Begriff wurde 1910 von dem US-amerikanischen Biologen William Morton Wheeler auf der Grundlage seiner Arbeiten an Ameisen geprägt. [WWM10]

3 Emergenz bezeichnet das Entstehen neuer Strukturen oder Eigenschaften aus dem Zusammenwirken der Elemente in einem komplexen System . Als emergent werden Eigenschaften eines ”Ganzen“bezeichnetdiesichausdeneinzelnen ”Teilen“nichtdirektherleitenlassenund nur aus dem Zusammenwirken der Teile d. h. aus ihrem Prozess heraus erklärbar sind. [UP[10]]

4 nichtdeterministisch polynomielle Vollständigkeit; Das heißt, das Problem ist vermutlich nicht effizient lösbar. Alle bekannten deterministischen Algorithmen für diese Probleme erfordern exponentiellen Rechenaufwand.

5 CVD - Chemical Vapour Deposition (dt. chemische Gasphasenabscheidung)

1 Pheromon: chemischer Lockstoff, Kunstwort aus den griechischen Begriffen phereon = übertragen und horamn = erregen von Karlson und Butenandt (1959) ([ZT06], S. 10)

Ende der Leseprobe aus 161 Seiten

Details

Titel
Implementierung und Evaluation von Heuristiken aus dem Gebiet "Evolutionary Computation" zur Lösung komplexer Schedulingprobleme
Hochschule
Technische Universität Dresden
Note
2,0
Autor
Jahr
2010
Seiten
161
Katalognummer
V353388
ISBN (eBook)
9783668399006
ISBN (Buch)
9783668399013
Dateigröße
4191 KB
Sprache
Deutsch
Schlagworte
implementierung, evaluation, heuristiken, gebiet, evolutionary, computation, lösung, schedulingprobleme
Arbeit zitieren
Peter Hillmann (Autor), 2010, Implementierung und Evaluation von Heuristiken aus dem Gebiet "Evolutionary Computation" zur Lösung komplexer Schedulingprobleme, München, GRIN Verlag, https://www.grin.com/document/353388

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Implementierung und Evaluation von Heuristiken aus dem Gebiet "Evolutionary Computation" zur Lösung komplexer Schedulingprobleme



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden