Naturanaloge Verfahren: Metaheuristiken Zur Reihenfolgeplanung

ISBN-13: 9783824468904 / Niemiecki / Miękka / 1999 / 361 str.

Martin Feldmann

Opis

Der Autor zeigt Perspektiven fur ein Zusammenwachsen konkurrierender naturanaloger Verfahren auf und belegt die Leistungsfahigkeit hybrider Ansatze an Hand des Open-Shop-Scheduling-Problems."

Spis treści

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.

O autorze

Dr. Martin Feldmann ist wissenschaftlicher Assistent am Lehrstuhl von Prof. Dr. Klaus-Peter Kistner für Betriebswirtschaftslehre und Unternehmensforschung an der Universität Bielefeld.

Blurb

Im Rahmen der betrieblichen Planung, wie z. B. beim Scheduling oder bei der Tourenplanung, müssen häufig kombinatorische Probleme gelöst werden. Dabei haben sich Metaheuristiken, insbesondere die naturanalogen Verfahren wie genetische Algorithmen, Evolutionsstrategien, Simulated Annealing u. a. bewährt. Martin Feldmann systematisiert die wesentlichen Varianten naturanaloger Verfahren und stellt ein Meta-Modell vor, mit dessen Hilfe hybride Ansätze entwickelt werden können. Durch eine Kombination von Verfahrenskomponenten werden die Vorteile der Ansätze, wie hohe Robustheit, leichte Modifizierbarkeit und Selbstadaptivität, synergetisch verbunden. Der Autor zeigt damit Perspektiven für ein Zusammenwachsen bislang konkurrierender Verfahren auf und belegt die Leistungsfähigkeit hybrider Ansätze an Hand des Open-Shop-Scheduling-Problems.