Flowhop Scheduling mit parallelen Genetischen Algorithmen: Eine problemorientierte Analyse genetischer Suchstrategien
rungs problem en in unterschiedlichen wissenschaftlichen Disziplinen anwen- deten [Gold89. 1, S. 126-130]. Das Optimierungsproblem in seiner allgemeinsten Form ist die Aufgabe Optimiere -+ f (x), XEM, (10) n n mit f als reellwertiger Funktion des lR und M C lR als Raum aller zulassigen Lasungen. Die Optimierung beliebiger reeller Funktionen unter Verwendung Genetischer Algorithmen wurde zuerst in der Dissertation von de Jong [Jong75] behandelt. Die von ihm experimentell untersuchten unste- tigen, nichtkonvexen, multimodalen und stochastischen Funktionen dienen in der Literatur seither als Standardprobleme zur Validierung genetischer Optimierungsstrategien, siehe etwa [MSB91]. Wird in der Formulierung der Aufgabe (10) zusatzlich die Ganzzahligkeitsbedingung an die Kompo- nenten der Lasungsvektoren x gekntipft, so fallt das Problem bekanntlich in den Bereich der kombinatorischen Optimierung. An einem einfachen Beispiel soll das konstruktive Paradigma der genetischen Optimierung ein- gefiihrt werden. Hierzu werden wir eine der Biologie entlehnte begrifHiche Analogie verwenden, die in Abschnitt 3. 2 zusammenhangend dargestellt wird. Es sei die Aufgabe 2 Max -+ f(x, y)=x -2xy+y2, O::: x, y::: k-lmitx, yElN (11) 2 mit k als Zweierpotenz, also z. B. k = 32, gegeben. Jedes der 32 unter- schiedlichen 2-Tupel, welche als potentielle Optimallasungen der Aufgabe zur Diskussion stehen, bezeichnet den Phanotyp einer zulassigen Lasung. Dieser laBt sich tiber eine Binartransformation in zwei Strings der Lange log2 k darstellen. x) = ( 25 ) 11 1 0 0 1 I (12) ( y 14 -+ 0 1 1 1 0 Die geordnete Menge binarer Strings definiert den Genotypus einer Lasung.
1112043658
Flowhop Scheduling mit parallelen Genetischen Algorithmen: Eine problemorientierte Analyse genetischer Suchstrategien
rungs problem en in unterschiedlichen wissenschaftlichen Disziplinen anwen- deten [Gold89. 1, S. 126-130]. Das Optimierungsproblem in seiner allgemeinsten Form ist die Aufgabe Optimiere -+ f (x), XEM, (10) n n mit f als reellwertiger Funktion des lR und M C lR als Raum aller zulassigen Lasungen. Die Optimierung beliebiger reeller Funktionen unter Verwendung Genetischer Algorithmen wurde zuerst in der Dissertation von de Jong [Jong75] behandelt. Die von ihm experimentell untersuchten unste- tigen, nichtkonvexen, multimodalen und stochastischen Funktionen dienen in der Literatur seither als Standardprobleme zur Validierung genetischer Optimierungsstrategien, siehe etwa [MSB91]. Wird in der Formulierung der Aufgabe (10) zusatzlich die Ganzzahligkeitsbedingung an die Kompo- nenten der Lasungsvektoren x gekntipft, so fallt das Problem bekanntlich in den Bereich der kombinatorischen Optimierung. An einem einfachen Beispiel soll das konstruktive Paradigma der genetischen Optimierung ein- gefiihrt werden. Hierzu werden wir eine der Biologie entlehnte begrifHiche Analogie verwenden, die in Abschnitt 3. 2 zusammenhangend dargestellt wird. Es sei die Aufgabe 2 Max -+ f(x, y)=x -2xy+y2, O::: x, y::: k-lmitx, yElN (11) 2 mit k als Zweierpotenz, also z. B. k = 32, gegeben. Jedes der 32 unter- schiedlichen 2-Tupel, welche als potentielle Optimallasungen der Aufgabe zur Diskussion stehen, bezeichnet den Phanotyp einer zulassigen Lasung. Dieser laBt sich tiber eine Binartransformation in zwei Strings der Lange log2 k darstellen. x) = ( 25 ) 11 1 0 0 1 I (12) ( y 14 -+ 0 1 1 1 0 Die geordnete Menge binarer Strings definiert den Genotypus einer Lasung.
59.99 In Stock
Flowhop Scheduling mit parallelen Genetischen Algorithmen: Eine problemorientierte Analyse genetischer Suchstrategien

Flowhop Scheduling mit parallelen Genetischen Algorithmen: Eine problemorientierte Analyse genetischer Suchstrategien

by Christian Bierwirth
Flowhop Scheduling mit parallelen Genetischen Algorithmen: Eine problemorientierte Analyse genetischer Suchstrategien

Flowhop Scheduling mit parallelen Genetischen Algorithmen: Eine problemorientierte Analyse genetischer Suchstrategien

by Christian Bierwirth

Overview

rungs problem en in unterschiedlichen wissenschaftlichen Disziplinen anwen- deten [Gold89. 1, S. 126-130]. Das Optimierungsproblem in seiner allgemeinsten Form ist die Aufgabe Optimiere -+ f (x), XEM, (10) n n mit f als reellwertiger Funktion des lR und M C lR als Raum aller zulassigen Lasungen. Die Optimierung beliebiger reeller Funktionen unter Verwendung Genetischer Algorithmen wurde zuerst in der Dissertation von de Jong [Jong75] behandelt. Die von ihm experimentell untersuchten unste- tigen, nichtkonvexen, multimodalen und stochastischen Funktionen dienen in der Literatur seither als Standardprobleme zur Validierung genetischer Optimierungsstrategien, siehe etwa [MSB91]. Wird in der Formulierung der Aufgabe (10) zusatzlich die Ganzzahligkeitsbedingung an die Kompo- nenten der Lasungsvektoren x gekntipft, so fallt das Problem bekanntlich in den Bereich der kombinatorischen Optimierung. An einem einfachen Beispiel soll das konstruktive Paradigma der genetischen Optimierung ein- gefiihrt werden. Hierzu werden wir eine der Biologie entlehnte begrifHiche Analogie verwenden, die in Abschnitt 3. 2 zusammenhangend dargestellt wird. Es sei die Aufgabe 2 Max -+ f(x, y)=x -2xy+y2, O::: x, y::: k-lmitx, yElN (11) 2 mit k als Zweierpotenz, also z. B. k = 32, gegeben. Jedes der 32 unter- schiedlichen 2-Tupel, welche als potentielle Optimallasungen der Aufgabe zur Diskussion stehen, bezeichnet den Phanotyp einer zulassigen Lasung. Dieser laBt sich tiber eine Binartransformation in zwei Strings der Lange log2 k darstellen. x) = ( 25 ) 11 1 0 0 1 I (12) ( y 14 -+ 0 1 1 1 0 Die geordnete Menge binarer Strings definiert den Genotypus einer Lasung.

Product Details

ISBN-13: 9783824420513
Publisher: Deutscher Universitätsverlag
Publication date: 01/01/1993
Edition description: 1993
Pages: 233
Product dimensions: 5.83(w) x 8.27(h) x 0.02(d)
Language: German

Table of Contents

1 Motivation.- 2 Flowshop Scheduling.- 2.1 Das deterministische Job Scheduling Modell.- 2.2 Optimierung von Flowshop Problemen.- 3 Genetische Algorithmen.- 3.1 Einführung.- 3.2 Ein Exkurs in Genetik oder das biologische Vorbild.- 3.3 Modellierung evolutionärer Strategien.- 3.4 Parallelisierung Genetischer Algorithmen.- 4 PGA — ein verteilt-asynchrones Optimierungsverfahren.- 4.1 Die PGA Komponenten — eine Funktionsbeschreibung.- 4.2 Terminierungskriterien.- 4.3 PGA Netzwerkimplementation.- 5 Genetische Problemrepräsentation.- 5.1 Binäre Kodierung des TSP.- 5.2 Kanonische Lösungs-Kodierung.- 5.3 Das kanonische Schema.- 6 Problemabhängige PGA Komponenten.- 6.1 Das Crossing-Over.- 6.2 Explizite Mutationen.- 6.3 Lokale Optimierung.- 7 Problemunspezifische PGA Komponenten.- 7.1 Überlappende Populationen.- 7.2 Verteilte Selektion.- 7.3 Balancierung der Selektion in überlappenden Populationen.- 8 Konfigurationsraum-Analysen.- 8.1 Travelling Salesman Problem.- 8.2 Flowshop Probleme.- 8.3 Interpretation konfigurierender Merkmale.- 9 Ergebnisse.- 9.1 Experimentelle Flowshop Plattform.- 9.2 Leistungsverhalten der PGA Heuristik.- 9.3 PGA Leistungsvergleich mit Standardheuristiken.- 10 Zusammenfassung und Ausblick.- A Anhang.- A.1 Dokumentation der Testprobleme und besten Lösungen.- A.2 Konfigurationsdiagramme aller Testprobleme.- A.3 Funktionale Beschreibung der Optimierungsziele.- A.3.3 Übersicht von Optimierungszielen der Ablaufplanung.- Literatur.
From the B&N Reads Blog
Page 1 of

Customer Reviews