Flowhop Scheduling mit parallelen Genetischen Algorithmen: by Christian Bierwirth

By Christian Bierwirth

Rungs challenge en in unterschiedlichen wissenschaftlichen Disziplinen anwen deten [Gold89. 1, S. 126-130]. Das Optimierungsproblem in seiner allgemeinsten shape 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 challenge 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 three. 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 ok als Zweierpotenz, additionally z. B. ok = 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 okay darstellen. x) = ( 25 ) eleven 1 zero zero 1 I (12) ( y 14 -+ zero 1 1 1 zero Die geordnete Menge binarer Strings definiert den Genotypus einer Lasung.

Show description

Read or Download Flowhop Scheduling mit parallelen Genetischen Algorithmen: Eine problemorientierte Analyse genetischer Suchstrategien PDF

Best german_10 books

Exportmarketing

Der Absatzstil im AuBenhandel weist von jeher einen starker konservativen Charakter als derjenige des Inlandsgeschaftes auf. Das ist eine alte Tatsache. 1m Export wurde erst relativ spat zu einer kontinuierlichen, konsequent geplanten Marktbearbeitung und Marktpflege iibergegangen. Mit der nahezu permanenten Ausweitung des Ausfuhrvolumens und der Exportquote vieler Unternehmen fan den die Auslandsmarkte immer groBere Beachtung, und dies urn so mehr, als sich die Exportunternehmen, verglichen mit friiheren Zeiten, veranderten Bediirfnissen, Wiinschen und Problemen der ausHindischen Abnehmer gegeniibergestellt und einem intensiveren Wett bewerb auf fremden Absatzmarkten ausgesetzt sahen.

Internationale Handelsfinanzierung: Strategien für Auslandsinvestitionen und Handel

Herbert Keßler ist Prokurist und Abteilungsdirektor für Außenhandelsfinanzierung einer großen Landesbank und als Fachautor und Referent bekannt.

Wie beurteilt man eine Bilanz?

1 Das Recht des Jahresabschlusses. . . . . . eleven 1. 1 Die Bestandteile des Jahresabschlusses. . . . . . . . . . . 12 1. 1. 1 Die Bilanz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1. 1. 2 Die Gewinn- und Verlustrechnung . . . . . . . . . . sixteen 1. 2 Die Grundsätze ordnungsmäßiger Buchführung .

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

Example text

N. 1 Einfiihrung 35 (15) mittels der ein Pool von N Losungen erstellt wird. AnschlieBend werden die Mitglieder des Pools durch eine zufa1lige Wahl zu Paaren zusammengestellt. Mit der Verteilung pt wird die Eigenschaft der natiirlichen Selektion modelliert, derzufolge besser an die Umgebung angepaBte Individuen mehr Nachkommen haben. Mit zunehmender Fitness, relativ zum durchschnittlichen Adaptionsgrad einer Population, steigt die Wahrscheinlichkeit einer Losung, als Partner gewahlt zu werden. Folglich beschreibt pt(xD in der dynamischen Selektionsgleichung (15) das Attraktionsniveau, welches eine Losung zur Zeit t auf die anderen Mitglieder der Population ausiibt.

Urn das SFSP in ein iiquivalentes, nicht-symmetrisches TSP zu iiberfiihren, muB schlieBlich die allgemeine Losungssequenz rp( i) mit i = 1 ... n als abgeschlossene Rundreise dargestellt werden. Dies ermoglicht die EinfUhrung eines fiktiven Auftrags Jo in das Problem. Hierzu erweitern wir die Darstellung der allgemeinen Losung als Sequenz von Auftriigen urn eine Position: Es solI fUr aIle Losungen rp(i) mit i = 0 ... n gelten, daB rp(O) = 0 ist, d. h. die Operationen von Auftrag 0 sollen als erste auf allen Maschinen ausgefUhrt werden.

Aus diesem Ansatz lassen sich zwei Evolutionsspiele zur Optimierung numerischer Modelle ableiten, die auf dem Wettbewerb unterschiedlicher Losungen ums Uberleben basieren. Ein drittes Spiel - das GA-Paradigma - resultiert, wenn genetische Operatoren eingeschaltet werden, die den Prinzipien der Mendelschen Genetik folgen. Sie bewirken, daB neben Konkurrenz eine Kooperation der Losungen durch sexuelle Reproduktion stattfindet. Es wird ein Grobmodell skizziert, in dem die phanotypische Losungsreprasentation auf einer makroskopischen Ebene und die genotyschische Reprasentation auf einer mikroskopischen Ebene der Evolution agieren.

Download PDF sample

Rated 4.64 of 5 – based on 30 votes