Flowhop Scheduling mit parallelen Genetischen Algorithmen

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.