close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

1. Was sind GA? - Ein GA ist ein Algorithmus, der Strategien aus der

EinbettenHerunterladen
Hochschule Regensburg
Genetische Algorithmen 1
Übung 12_3
Spezielle Algorithmen (SAL)
Name: ________________________
Lehrbeauftragter: Prof. Sauer
Vorname: _____________________
1. Was sind GA?
- Ein GA ist ein Algorithmus, der Strategien aus der Evolutionstheorie nachahmt, um
zu einem Problem eine möglichst gut Lösung zu finden.
- Diese Suchalgorithmen basieren auf dem Mechanismus der natürlichen Selektion:
-- Verbinden das Überleben der Stärksten
-- mit strukturiertem aber zufälligem Informationsaustausch
- Ziel: Anpassungsfähigkeit und Widerstandsfähigkeit der Natur nachzuahmen
- Einfach zu realisieren
-. Grund der Entwicklung:
-- Abstraktion des Prozesses der natürlich Selektion
-- Software für KI-Systeme
1
Vgl. Skriptum, 5.
1
2. Prinzip der genetischen Algorithmen
Population zum Zeitpunkt t
Kreuzung (crossover)
Selektion
Mutation
Verdrängung
Population zum Zeitpunkt t + 1
3. Rezept für die Konstruktion genetischer Algorithmen
Man nehme ein oder mehrere Eltern, die durch Rekombination der Erbinformationen
eine Anzahl von Nachkommen erzeugen. Nun streut man eine Prise Chaos hinein
und mutiert damit die Information der Nachkommen.
Man erhält nach diesem Rezept eine Population von einander ähnlichen Individuen
(Reproduktionen), die mathematisch betrachtet , eine zufällige Auswahl der
Umgebungsbeschreibung der Eltern im n-dimensionalen Parameterraum und deren
Repräsentation im Lösungsraum darstellen.
Zur Selektion dient ein Vergleich: Zielvorgabe mit den Randparametern (vorrangige
Auswahl der Stärksten unter Berücksichtigung schwächerer Gruppen, Roulette-Rad).
Glücksradauswahl (roulette wheel selection) ist der einfachste Selektionsalgorithmus,
bei dem die Individuen von bester Fitness für die Reproduktion mit größerer
Wahrscheinlichkeit selektiert werden. Aus einer Population mit n Individuen wird nmal gezogen (mit Zurücklegen) und die selektierten Individuen im „matching pool“
akkumuliert.
2
f rel ( s ) =
f abs ( s )
ist die Auswahlwahrscheinlichkeit eines Individuums (sog.
∑s '∈p (t ) f abs (s' )
fitnessproportionale Selektion 2)
Veranschaulichung: Glücksrad mit einem Sektor je Individuum s. Die Sektorgröße entsprechen den
relativen Fitnesswerten f rel (s )
Markierung
s4
s3
s2
s5
s6
s1
Auswahl eines Individuums:
-
Drehe Glücksrad
Wähle Chromosom dessen Sektor an der Markierung liegt
Auswahl der Zwischenpopulation:
-
Wiederhole die Auswahl so oft, wie es Individuen in der Population gibt.
Die daraus resultierenden Eltern werden nach Fitness im folgenden Generationsschritt benutzt, alle übrigen werden vergessen. Häufig verwendet man auch die
folgende Form der Selektion (mit dem Parameter r, 0 < r < populations _ groesse und
p c , 0 < p c < 1 ):
-
-
Wähle aus der Population p(t) zufällig (aber unter Berücksichtigung der Fitneß) r
Chromosomen (mit Zurücklegen)
Bestimme für jedes für jedes dieser r Chromosomen, ob es am Crossover teilnimmt
(Wahrscheinlichkeit p c ) oder mutiert wird (Wahrscheinlichkeit 1 − p c ) und wende die
genetischen Operatoren an.
Wähle aus p (t ) zufällig (aber unter Berücksichtigung der Fitneß populations _ groesse − r
Chromosomen (ohne Zurücklegen)
Diese populations _ groesse − r Chromosomen werden unverändert übernommen
Mutationsschritte sind begrenzt und so in die zu optimierenden Größen
einzubeziehen. Eine Schrittweiten-Festlegung legt fest, dass Mutationen nicht allzu
zahlreich vorliegen.
2
Die absolute Fitness f abs (s ) darf in diesem Fall nicht negativ sein, ggf. ist ein positiver Wert zu addieren und
negative Werte sind Null zu setzen.
Die Fitneß muß zu maximieren sein. (Sonst würden schlechte Individuen mit hoher Wahrscheinlichkeit gewählt).
3
4. Modellierung einer Problemstellung, die mit einem genetischen Algorithmus gelöst
werden soll
Definition einer Abbildung, so dass Lösungen des relevanten Suchraums durch
Zeichenketten (Strings 3, Zeichen sind in der Regel 0 und 1) repräsentiert werden
können (Genotypen). Die zugehörigen Lösungen bezeichnet man als Phänotyp
(äußere Erscheinungsbild eines Individuums)
Durch Anwendung genetischer Operationen auf die n Individuen einer
Ausgangspopulation werden neue Individuen (Strings) erzeugt (auf der Ebene
Genotypen).
Die Bewertung der Individuen (Fitness) erfolgt auf der Ebene der Phänotypen
4.1 Welche Aktivitäten zählen zum Entwurf eines genetischen Algorithmus?
Modellierung
Finden einer geeigneten Codierung durch Strings
Konfigurierung
Auswahl einer geeigneten Verfahrensvariante, insbesondere durch effiziente
Operatoren
4.2 Welche Arbeiten umfasst die Realisierungsphase?
Arbeiten zum Umsetzen des Entwurfs in ein lauffähiges Optimierungsverfahren.
Hierunter fallen Implementierung und Parametrisierung, d.h. Bestimmen der Werte
für externe Parameter
3
Ein String ist eine Zeichenkette der Länge m, deren Glieder einem vorgegebenen Alphabet entnommen sind.
4
5. Aufbau und Funktionsweise von GAs
Ein genetischer Algorithmus durchläuft die folgenden Schritte:
- Kodierung
- Fitness auswerten
- Selektion
- Crossover / Mutation
5.1 Kodierung
Man unterscheidet: binäre Codierung, Permutation-Kodierung, Wert-Kodierung,
Baum-Kodierung.
Binäre Codierung
r
- Binärer Vektor x aus Menge M := {0,1} heißt Chromosom: x = x1 , x 2 ,..., x n ∈ M
r
- n = l (x ) ist die Länge des Vektors
n
- M ist eine Population
n
für n > 1
- i-te Position eines Chromosoms heißt i-tes Gen.
- Wert des Gens heißt Allel (hier nur 0 und 1) möglich).
- Gene sind Variable, die als Platzhalter dienen und Allele sind Werte dieser Variablen.
- Programmtechnisch hat binäre Codierung erhebliche Vorteile:
-- Individuen lassen sich wesentlich kompakter im Speicher verarbeiten (wichtig bei großen
Populationen)
-- schnelle Verarbeitung mit binären Zahlen (z.B. Shift-Operationen)
- Es gibt aber auch Nachteile:
-- Positionsabhängigkeit der Codierung: Positionen innerhalb des Codes sind nicht
gleichwertig.
-- führende Stellen codieren definitionsgemäss größere Zweierpositionen als hintere
Die Wahl der Codierung erfolgt problemspezifisch. Es gibt kein allgemeines
Kochrezept für eine gute Codierung. Man kann nur einige wünschenswerte
Eigenschaften fordern:
-
Ähnliche Phänotypen sollen durch ähnliche Genotypen dargestellt werden.
Ähnliche Lösungskandidaten sollen eine ähnliche Fitness besitzen.
Der Suchraum (die Menge der möglichen Lösungskandidaten) sollte, wenn möglich, unter den
verwendeten genetischen Operatoren abgeschlossen sein.
Hamming-Klippen. Ähnliche Phänotypen sollen durch ähnliche Genotypen dargestellt
werden. Benachbarte Elemente, z.B. Zahlen, können bspw. bei einer Darstellung
durch Binärcodes sehr verschieden codiert sein, d.h. die Codierungen haben einen
großen Hamming-Abstand (Anzahl verschiedener Bits). Große Hamming-Abstände
können durch Mutationen und Crossover nur sehr schwer überwunden werden (sog.
Hamming-Klippen).
Bsp.: Der Bereich der Zahlen von 0 bis 1 werde durch 4-Bit-Zahlen dargestellt. Dann
haben die Kodierungen von 7/15 (0111) und 8/15 (1000) den Hamming-Abstand 4.
Die Lösung können Gray-Codes sein. Hier unterscheiden sich benachbarte Zahlen
nur in einem Bit.
5
5.2 Fitnessfunktion
Fitness ist der Erfolgsindikator, wird bei der Selektion verwendet. Mit der Fitness
definiert man, was optimiert werden sollte. Allerdings gibt es auch hier ein Problem:
(Epitasie): Die Änderung der Fitness durch die Änderung eines Gens hängt stark
von den Ausprägungen der anderen Gene ab.
5.3 Neue Populationen erzeugen
Eine neue Population erzeugt man durch folgende Schritte
- Selektion (Auswahl der Individuen für Crossover)
Individuen mit besserer Fitness sollen größere Chancen haben, Nachkommen zu erzeugen. Die
Stärke der Bevorzugung guter Individuen heißt Selektionsdruck. Bei der Wahl des
Selektionsdrucks gibt es aber einen Gegensatz von
„
Durchforstung des Suchraums (exploration).
Die Individuen sollen möglichst breit gestreut sein, damit die Chancen, dass das globale
Optimum gefunden wird, möglichst groß sind. Ein geringer Selektionsdruck ist
wünschenswert.
„ Ausbeutung guter Individuen (exploitation)
Es sollte das (u.U. lokale) Optimum in der Nähe guter Individuen angestrebt werden
(Konvergenz zum Optimum). Ein hoher Selektionsdruck ist wünschenswert.
Wahl des Selektionsdrucks: Die beste Strategie wäre: ein zeitabhängiger Selektionsdruck mit
„
„
geringem Selektionsdruck in früheren Generationen
höherer Selektionsdruck in späteren Generationen
Allgemein wird der Selektionsdruck über eine Skalierung der Fitnessfunktion oder Parameter des
Selektionsverfahrens gesteuert (z. B. Glücksradauswahl).
- Crossover (verwirklicht den Informationsaustausch zwischen 2 Individuen)
Man unterscheidet:
Single-Point Crossover (zufällig wird ein Trennpunkt bestimmt.
Parent A
Parent B
Resultat
11001011
11011111
11001111
Two-Point-Crossover
Parent A
Parent B
11001011
11011111
Resultat
11011111
Uniform-Crossover
Parent A
Parent B
11001011
11011101
Resultat
11011111
Arithmetisches Crossover (UND)
Parent A
Parent B
11001011
11011111
Resultat
11001011
- Mutation (verändert rein zufällig ein oder mehrere Gene eines Individuums)
Ziel: gänzlich andere Lösungen zu finden, die mit der Kreuzung nicht allein generiert werden können.
Die Mutation soll gewährleisten, daß die Vielfalt (viele unterschiedliche Lösungen) in der Population
erhalten bleibt.
6
6. Programmablaufplan eines genetischen Algorithmus
Auswahl einer Ausgangspopulation
Wahl der Codierung
Ermittlung der Fitness der Individuen
Selektion
der
Eltern
Auswahl eines Individuums
NEIN
Matching-pool voll?
Auswahl eines oder mehrerer Eltern
Zeugung
der
Auswahl
und
Rekombination (Reproduktion)
Anwendung
Mutation
Crossover
Nachkommen
NEIN
Neue Generation voll?
NEIN
JA
Abbruchbedingung
erfüllt
Ende der Optimierung
7
7. Reproduktionsmodell
Der Selektionsoperator wählt jedes Mal nur so viele Individuen aus, wie zur
einmaligen Ausführung des Crossover- bzw. Mutationsoperators benötigt werden.
Die entstandenen Nachkommen werden unmittelbar nach Anwendung des Operators
in die Population eingefügt. Eltern bleiben in der Population. Anschließend werden so
viele der schlechtesten Individuen aus der Population entfernt, wie Nachkommen
eingesetzt werden. Falls derselbe Genotyp vor dem Einsetzen bereits in der
Population existiert, wird er verworfen. Auf diese Weise wird sichergestellt, daß die
Population ausschließlich Unikate enthält.
Die Strings werden in Abhängigkeit zur Fitness kopiert, z.B.:
1
2
3
String
01101
11000
01000
Fitness
169
576
64
1
3
2
Roulette-Rad
Bei der Glücksradauswahl kann ein Individuum mit hoher Fitness die Auswahl dominieren. Das zeigt
den starken Einfluss der Fitnessfunktion bei einer fitnessproportionalen Selektion.
Dominanzproblem bei der Glücksradauswahl
- hat ein Individuum eine sehr hohe Fitness, kann es die Auswahl dominieren
- In den Folgegenerationen wird diese Dominanz noch verstärkt, da dann Kopien und dehr ähnliche
Individuen vorliegen
- Als Ergebnis kommt es zum Crowding. Diese Population besteht aus gleichen oder sehr ähnlichen
Individuen
- Crowding führt dazu, dass das (lokale) Optimum sehr schnell gefunden wird.
- Nachteil: Die Diversität der Population geht verloren
8
8. Bsp.:
1. Gegeben ist f ( x) = x ⋅ sin(10 ⋅ π ⋅ x) + 1 . Gesucht ist Maximum im Intervall -1 bis 2,
also xo mit f ( xo ) ≥ f ( x) für alle x ∈ [− 1,2]
- Mathematische Lösung
- Notw. Bedingung: 1. Ableitung = 0
- f ' ( x) = sin(10 * pi * x) + 10 * pi * x * cos(10 *
pi * x) = 0
tan(10 * pi * x) = −10 * pi * x
- Unendlich viele Lösungen
2 ⋅ i −1
+ εi
20
xo = 0
2 ⋅i +1
xi =
+ εi
20
xi =
i = 1,2,...
i = −1,−2,...
{ε i } repräsentiert reelle Nullfolge (ε i
> 0)
- Mit Hilfe der 2. Ableitung (Hinreichende Bedingung)
Für ungerade i: Maximum
Für gerade i: Minimum
Graph der Funktion: f ( x ) = x ⋅ sin(10 ⋅ π ⋅ x ) + 1
9
- Für die Funktion
f ( x) = x ⋅ sin(10 ⋅ π ⋅ x) + 1 auf dem Intervall I=[-1,2] ist das Maximum
bei x19
- f ( x19 ) ist etwas größer als f (1.85) = 1.85 * sin(10π ⋅
bei x = 1.8504
f ( x) = 2.8502539
f ( x) = 2.850271708
f ( x) = 2.850271265
x = 1.8505
bei x = 1.8506
bei
37
) + 1 = 2.85
20
Repräsentation
- binärer Vektor mit 22 Bits:
(b
b ...b0
21 20
)
2
⎞
⎛
= ⎜⎜ ∑ bi ⋅ 2 i ⎟⎟ = x'
⎠10
⎝
- auf Intervall normieren:
Bsp.:
- Chromosom (1000101110110101000111) = 0.637197
x' = (1000101110110101000111)2 = 228896710
3
x = −1 + 2288967 ⋅
= 0.637197
4194303
- natürlich sind (0000000000000000000000 ) = −1 und (1111111111111111111111) = 2
Bewertung (Evaluation)
- Funktion eval (v) = f ( x)
- Bsp.:
v1 = (1000101110110101000111)
v 2 = (0000001110000000010000 )
v3 = (1110000000111111000101)
ergibt
x1 = 0.637197
x 2 = −0.958973
x3 = 1.627888
eval (v1 ) = f ( x1 ) = 1.586345
eval (v 2 ) = f ( x 2 ) = 0.078878
eval (v3 ) = f ( x3 ) = 2.250650
Mutation
- das 5. Gen des Chromosoms v 3 ist (zufällig) ausgesucht für Mutation
v3 = (1110000000111111000101)
v3' = (1110100000111111000101)
x3 = 1.627888,
f ( x3 ) = 2.250650
x3' = 1.721638
f ( x3' ) = −0.082257
- gewaltige Veränderung der Bewertung bei nur einer Mutation
- wenn allerdings das 10. Gen mutiert:
v3 = (1110000000111111000101)
v3'' = (1110000001111111000101)
10
v3'' = (1110000001111111000101)
x3 = 1.627888,
f ( x3 ) = 2.250650
x3'' = 1.630818
f ( x3'' ) = 2.343555
- geringe Veränderung der Bewertung (aber Verbesserung)
Crossover
- Crossover der beiden letzten Chromosomen nach dem 5. Gen
v 2 = (0000001110000000010000 )
v3 = (1110000000111111000101)
- Ergebnisse (Nachwuchs)
v 2 ' = (0000000000111111000101)
v3' = (1110001110000000010000 )
x 2 ' = −0.998113
f ( x 2' ) = 0.940865
x3' = 1.666028
f ( x3' ) = 2.459245
v3' hat bessere Bewertung als beide Eltern
11
2. Gefangenendilemma
- 2 Gangster begehen gemeinsam einen Raub und werden gefaßt
- der Raub kann nicht nachgewiesen werden
- Gefängnisdirektor steckt beide in getrennte Zellen und macht Angebot:
- Raub kann gestanden oder geleugnet werden
- Leugnen beide, kann ihnen Raub nicht nachgewiesen werden, aber Strafe wegen
unerlaubten Waffenbesitzes (1 Jahr Gefängnis)
- gesteht einer, während der andere leugnet: Kronzeugenregelung für den Gestehenden, 5
Jahre für den Leugnenden
Gestehen beide, erhalten sie jeweils 5 Jahre
Gefangener 2
Gefangener 1
Leugnen
(Cooperate)
Gestehen
(Defect)
Leugnen
(Cooperate)
(-1,-1)
Gestehen
(Defect)
(-5,0)
(0,-5)
(-4,-4)
- spieltheoretische Lösung des Spiels „(gestehen, gestehen)“ 4
- intuitiv ist die Lösung merkwürdig, weil die Spieler hier in der Summe schlechtesten Zustand
erreichen:
leugnen beide, bekommen sie -1 + (-1) = -2
gestehen beide, bekommen sie -4 + (-4) = -8
Repräsentation
- Strategien sollen Ergebnisse der 3 vorliegenden Spielzüge benutzen und dann aktuellen Spielzug
wählen
- Da 4 verschiedene Möglichkeiten für jeden Spielzug vorhanden, gibt es 4 ⋅ 4 ⋅ 4 = 64 verschiedene
Möglichkeiten für die 3 vorherigen Spielzüge
- Somit kann Strategie repräsentiert werden als String von 64 Bits (oder Ds und Cs), die angeben, was
getan wird bei jeder der 64 Möglichkeiten
- beim Start noch die 3 hypothetischen vorherigen (nicht gespielten) Spielzüge angeben, dazu noch 6
Bits -> 70 Bits.
C
C
C
C
C
C
D
C
C
C
C
C
C
D
C
C
C
C
C
D
C
……
64 Bits
C
D
D
D
D
D
D
D
D
D
D
D
C
D
letzte 3 Züge
D
……..
C
6 Bits
virtuelle 3 letzten Züge vor dem
Start
GA von Axelrod
1. Wähle Startpopulation: Jeder Spieler bekommt einen zufällig erzeugten 70-Bit-String
2. Bestimmen der Wirksamkeit von jedem Spieler, die Punktezahl des Spiels ist die
Durchschnittspunktzahl von allen seinen Spielern
3. Spieler aussuchen zur Fortpflanzung. Spieler mit durchschnittlicher Punktzahl bekommen eine
Paarung, mit überdurchschnittlicher Punktzahl keine Paarung
4
C
Streng dominante Strategie
12
4. zwischen erfolgreichen Spielern werden Paare gebildet, 2 Kinder je Paar werden produziert,
Strategie des Nachwuchses entsteht durch Strategien der Eltern über Crossover und Mutation
Experimentelle Ergebnisse
Einige Verhaltensmuster entwickeln sich in der Mehrheit der Individuen
1. weiter leugnen nach 3 gegenseitigen Kooperationen: C nach (CC)(CC)(CC)
2. gestehen, wenn anderer gesteht: D nach (CC)(CC)(CD)
3. leugnen, wenn Kooperation wiederhergestellt ist: C nach (CD)(DC)(CC)
4. leugnen, wenn gegenseitige Kooperation wiederhergestellt ist: C nach (DC)(CC)(CC)
5. D nach (DD)(DD)(DD)
13
3. TSP
Repräsentation: Problem mit binärer Kodierung für n = 20 Städte.
Stadt
1
2
3
4
5
6
7
Codierung
00001
00010
00011
00100
00101
00110
00111
Stadt
8
9
10
11
12
13
14
Codierung
01000
01001
01010
01011
01100
01101
01110
Stadt
15
16
17
18
19
20
Codierung
01111
10000
10001
10010
10011
10100
Probleme bei der Mutation:
- Mutation kann Tour erzeugen, in der eine Stadt zweimal vorkommt, z.B.
0
0
0
0
1 … 0
5
1
1
1
0
… 0
1
1
0
0
40
1
1
1
0
… 0
1
1
1
0
40
Die Mutation am Gen 39 führt zu:
0
0
0
0
1 … 0
5
Die Stadt 14 gibt es jetzt zweimal
- Mutation kann Städte erzeugen, die keine Städte sind, z.B.
0
0
0
0
1
… 0
1
1
1
0
… 1
0
1
0
0
100
… 0
1
1
1
0
… 1
0
1
0
1
100
Mutation an Gen 100
0
0
0
0
1
Es wird die nicht existierende Stadt 21 erzeugt
Ähnliche Problem gibt es beim Crossover
- Entweder wird ein „Reparier-Algorithmus“ verwendet oder besser gleich auf eine ganzzahlige
Repräsentation verzweigt. Bei der Initialisierung kann die Population dann ausgehen von einer
zufällig zusammengestellten Permutation von <1 2 … n>
- OX Operator (order crossover): Aus 2 Eltern wird ein Nachwuchs aufgebaut, in dem eine
Subsequenz einer Tour eines Elternteils gewählt wird und die verhältnismäßige Ordnung der Städte
beim anderen Elternteil beibehalten wird.
14
9. Schlussfolgerungen aus den Beispielen
- Die 3 Beispiele von GA zeigen eine große Anwendbarkeit von Gas aber auch
Probleme
- Der neue Operator OX Crossover war nicht trivial
- Im ersten und dritten Bsp (Funktionsoptimierung, TSP) ist die Bewertungsfunktion
klar definiert.
- Im 2. Bsp. (Gefangenendilemma) hat ein einfacher Simulationsprozess die
Bewertung der Spieler gegeben (Effektivität jedes Spielers wird getestet: Jeder
Spieler spielt seine Strategie (Chromosom) gegen andere, seine Punktzahl ist die
Durchschnittspunktzahl von allen Spielen)
- Im ersten Bsp. (Funktionsoptimierung) konnte man eine zweckmäßige
Repräsentation benutzen, bei der jedem binären String ein Wert einer Variable des
Intervalls -1 … 2 zugeordnet wurde.
- d.h.: jede Mutation und Crossover produziert einen zulässigen Nachwuchs
- auch beim zweiten Beispiel funktioniert es
- Beim 3. Problem ist es anders: Jede Stadt durfte nur einmal in der Tour
vorkommen.
- Dadurch entstanden Probleme: Benutzt wurden Vektoren aus ganzen Zahlen
(anstelle von binären Zahlen) und der Crossover-Operator verändert.
15
10. Das Schematheorem
Es gibt weder empirische Gesetze noch eine allgemeine Theorie, die die
Eigenschaften von genetischen Algorithmen hinreichend beschreibt. 1973 stellte
John Holland eine Hypothese auf, die den Erfolg der genetischen Algorithmen zu
erklären versucht. Die Hypothese ist als Schematheorem bekannt.
Ein Schema ist ein Muster, das aus den Zeichen 0, 1 und dem Platzhalter # besteht
und beschreibt eine Menge von Chromosomen, die in dieses Schema passen, z.B.:
Die Chomosomen 0101, 0001, 1101 passen in das Schema ##01.
Die Ordnung O(H ) eines Schemas H ist die Anzahl der festen Bits.
Die definierte Länge δ ( H ) des Schemas H ist definiert durch die Differenz der
letzten und der ersten Stelle eines festen Bits.
Zur Erklärung der Funktionsweise eines genetischen Algorithmus betrachtet man ein
Schema mit hoher Fitness und untersucht welchen Einfluss die Operationen
Selektion, Crossover und Mutation auf das Überleben solcher guten Schemata
haben.
16
11. Implementierungen
1. Lösung des 8-Damen-Problems mit einem GA 5
Aufgabe: Entwerfe einen Algorithmus, der eine gültige Damenaufstellung als
Ergebnis liefert.
Folgendes Entwurfsschema dürfte hilfreich sein:
- Festlegen einer geeigneten Repräsentation (Wie wird die Schachbrettaufstellung codiert?)
- Definition der Fitness (Formulierung des Problems in Form einer Zielfunktion)
- Definition von Rekombinations- bzw. Mutationsoperator
- Festlegung der Selektionsoperation (Wer rekombiniert mit wem? bzw. Wer von Kindern und Eltern
bleibt für die neue Generation erhalten?)
- Festlegen der Populationsgrösse
1. Codierung für die Schachbrettaufstellung
Günstig spaltenweise Codierung: Insgesamt gibt es 8 Spalten, die jeweils nur von einer Dame
belegt werden können, da ansonsten ein unmittelbarer Konflikt entsteht. Es reicht die
Zeilennummer zu notieren, in der die Dame steht. Insgesamt ergibt sich ein Codestring der länge
8, der die Zahlen 1 bis 8 enthält.
Die Größe des Suchraums beträgt 8! = 40320 Komnbinationen
2. Fitness
3. Rekombination
4. Mutation
5. Selektion
6. Populationsgrösse
7. Gefundene Lösung und Optimierungsverlauf
2. TSP 6
5
6
vgl. ueb12_3, pr44020
vgl. ueb12_3, pr44010
17
Document
Kategorie
Gesundheitswesen
Seitenansichten
6
Dateigröße
91 KB
Tags
1/--Seiten
melden