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.