Dissertation Universität Bielefeld 1998 Der Autor zeigt Perspektiven für ein Zusammenwachsen konkurrierender naturanaloger Verfahren auf und belegt die Leistungsfähigkeit hybrider Ansätze an Hand des Open-Shop-Scheduling-Problems.
Dissertation Universität Bielefeld 1998Der Autor zeigt Perspektiven für ein Zusammenwachsen konkurrierender naturanaloger Verfahren auf und belegt die Leistungsfähigkeit hybrider Ansätze an Hand des Open-Shop-Scheduling-Problems.
Dr. Martin Feldmann ist wissenschaftlicher Assistent am Lehrstuhl von Prof. Dr. Klaus-Peter Kistner für Betriebswirtschaftslehre und Unternehmensforschung an der Universität Bielefeld.
Inhaltsangabe
A Einführung.- 1 Einleitung.- 1.1 Motivation.- 1.2 Ziele der Arbeit.- 1.3 Aufbau der Arbeit.- 2 Reihenfolgen und Lösungsverfahren.- 2.1 Reihenfolgen als Spezialfall kombinatorischer Probleme.- 2.2 Komplexität von Reihenfolgeproblemen.- 2.3 Lösungsverfahren für Reihenfolgeprobleme.- 2.3.1 Verfahren mit Pfad-Struktur.- 2.3.2 Verfahren mit Baum-Struktur.- 2.3.3 Verfahren mit heuristischer Struktur.- 2.4 Ansätze des Local Search.- 2.4.1 Startlösung.- 2.4.2 Nachbarschaft.- 2.4.3 Selektionskriterium.- 2.4.4 Abbruchkriterium.- 2.5 Erweiterungen des Local Search.- 2.5.1 Variable Depth Search.- 2.5.2 Tabu Search.- 2.5.3 Naturanaloge Erweiterungen.- 3 Biogenetische Grundlagen.- 3.1 Evolution.- 3.2 Chromosomale Repräsentation.- 3.3 Vererbung.- B Grundlagen.- 4 Naturanaloge Verfahren im Überblick.- 5 Beschreibung der Verfahrensabläufe.- 5.1 Genetische Algorithmen.- 5.1.1 Kanonischer Genetischer Algorithmus.- 5.1.2 Permutationskodierter Genetischer Algorithmus.- 5.1.3 Anwendungsbeispiel.- 5.2 Evolutionsstrategien.- 5.2.1 (?/?,?)-Evolutionsstrategie.- 5.2.2 Combinatorial Evolution Strategy.- 5.2.3 Anwendungsbeispiel.- 5.3 Evolutionary Programming.- 5.3.1 Fogels Evolutionary Programming.- 5.3.2 Combinatorial Evolutionary Programming.- 5.3.3 Anwendungsbeispiel.- 5.4 Simulated Annealing und Varianten.- 5.4.1 Simulated Annealing.- 5.4.2 Threshold Accepting.- 5.4.3 Anwendungsbeispiel.- 5.4.4 Sintflut-Algorithmus.- 5.4.5 Record-to-Record-Travel.- 6 Komponenten naturanaloger Verfahren.- 6.1 Repräsentation.- 6.1.1 Eigenschaften einer guten Repräsentation.- 6.1.2 Goldbergs Gestaltungshinweise.- 6.1.3 Davis Gestaltungshinweise.- 6.1.4 Repräsentation im Spannungsfeld.- 6.2 Auswahl.- 6.2.1 Initialisierung und Größe der Population.- 6.2.2 Populationskonzepte und Selektion zum Überleben.- 6.2.3 Behandlung von Doubletten.- 6.2.4 Selektion zur Fortpflanzung.- 6.3 Operation.- 6.3.1 Crossover.- 6.3.2 Mutation.- 6.3.3 Schemata Theorem.- 6.4 Gemeinsamkeiten der Verfahren.- 6.4.1 Konvergenzeigenschaften.- 6.4.2 Die Verfahren im A-R-0 Modell.- C Anwendung.- 7 Naturanaloge Verfahren zur Lösung des Open Shop Problems.- 7.1 Problemstellung der Maschinenbelegung.- 7.2 Beurteilung und Darstellung von Maschinenbelegungsplänen.- 7.3 Das Open-Shop-Scheduling Problem.- 7.4 Relevanz des Open-Shop-Scheduling Problems.- 7.5 Einsatz des A-R-0 Modells.- 7.5.1 Wahl der geeigneten Repräsentation.- 7.5.2 Wahl der Operatoren.- 7.5.3 Wahl der Steuerung.- 7.6 Wahl der Parameter.- 7.7 Ergebnisse.- 8 Zusammenfassung und Ausblick.
