sbas:ss2013:genalg
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen RevisionVorhergehende ÜberarbeitungNächste Überarbeitung | Vorhergehende Überarbeitung | ||
sbas:ss2013:genalg [15.09.2013 09:54] – Tobias Kaminsky | sbas:ss2013:genalg [28.11.2022 00:11] (aktuell) – Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 13: | Zeile 13: | ||
====== Grundform eines genetischen Algorithmus ====== | ====== Grundform eines genetischen Algorithmus ====== | ||
+ | < | ||
+ | Gegeben: Optimierungsproblem mit Suchraum S und Fitnessfunktion f | ||
+ | |||
+ | Lösung: | ||
+ | | ||
+ | | ||
+ | { | ||
+ | Berechne Fitness der Individuen aus P | ||
+ | Selektiere nach Fitness | ||
+ | Wende genetische Operatoren an | ||
+ | } | ||
+ | |||
+ | Ergebnis: bestes Individuum aus der Population | ||
+ | </ | ||
(vgl. Harbich, 2007, S. 5) | (vgl. Harbich, 2007, S. 5) | ||
Zeile 23: | Zeile 37: | ||
pop_size = 50; % Populationsgröße | pop_size = 50; % Populationsgröße | ||
generations = 100; % Anzahl an Generationen | generations = 100; % Anzahl an Generationen | ||
- | % Leere Population: | + | % Protokoll |
- | % Pouplations entspricht " | + | protocol=zeros(pop_size, |
- | populations=zeros(pop_size,2, | + | |
</ | </ | ||
+ | In dem Protokoll wird die Chromosomen- und Generationsnummer in einem Array gespeichert. Zu dieser eindeutigen Kombination (z.B. 5. Generation und 10. Chrosomom) wird die aktuelle Chromosomausprägung und der dazugehörige Fitnesswert gespeichert. | ||
====== Fitness ====== | ====== Fitness ====== | ||
- | Die Fitness beschreibt die Überlebenswahrscheinlichkeit eines Chromosoms mit der Formel: | + | Die Fitness beschreibt die Überlebenswahrscheinlichkeit eines Chromosoms mit der Formel: |
+ | < | ||
+ | `p(c_i) = f(c_i) / (\sum_{j=1}^nf(c_j))` | ||
+ | </ | ||
Die Summe aller Überlebenswahrscheinlichkeiten ist 1 (vgl. Harbich, 2007, S. 6). | Die Summe aller Überlebenswahrscheinlichkeiten ist 1 (vgl. Harbich, 2007, S. 6). | ||
+ | |||
+ | Der Fitnesswert ist abhängig von der jeweiligen Modellierung und wird in dort beschrieben. | ||
+ | |||
+ | Der nachfolgende Matlab-Code zeigt speichert das beste Chromosom in einer Variable, sodass der genetische Algorithmus zu jedem Zeitpunkt beendet werden kann und dennoch eine gültige und (zu diesem Zeitpunkt) beste Lösung vorhanden ist. | ||
**Umsetzung in Matlab** | **Umsetzung in Matlab** | ||
<code matlab> | <code matlab> | ||
- | % Index von bestem | + | % Index von bestem |
% bestind == [fitness generation element] | % bestind == [fitness generation element] | ||
bestind = [0 0 0]; | bestind = [0 0 0]; | ||
- | % Prüfe, ob neues bestes | + | % Prüfe, ob neues bestes |
if (fitness > bestind(1)) | if (fitness > bestind(1)) | ||
bestind(1) = fitness; | bestind(1) = fitness; | ||
Zeile 56: | Zeile 77: | ||
Die Auswahl der Chromosomen, | Die Auswahl der Chromosomen, | ||
Dieser Vorgang wird so oft wiederholt, bis die nachfolgende Generation die gleiche Populationsgröße wie die vorherige hat. | Dieser Vorgang wird so oft wiederholt, bis die nachfolgende Generation die gleiche Populationsgröße wie die vorherige hat. | ||
+ | [{{ : | ||
**Umsetzung in Matlab** | **Umsetzung in Matlab** | ||
<code matlab> | <code matlab> | ||
% Sortiere aktuelle Population nach Fitness | % Sortiere aktuelle Population nach Fitness | ||
- | | + | |
% Erstelle neues Intervall [0,1] | % Erstelle neues Intervall [0,1] | ||
- | R = rwheel(populations(:,:,f),2); | + | R = rwheel(protocol(:,:,f),2); |
% Erstelle temporäre Generation | % Erstelle temporäre Generation | ||
Zeile 70: | Zeile 91: | ||
% Fülle temporäre Generation mit alten Chromosomen anhand deren Wahrscheinlichkeit | % Fülle temporäre Generation mit alten Chromosomen anhand deren Wahrscheinlichkeit | ||
for i=1: | for i=1: | ||
- | Pnew(i,:) = P(wheel_select(populations(:,:, | + | Pnew(i,:) = P(wheel_select(protocol(:,:, |
end | end | ||
| | ||
Zeile 104: | Zeile 125: | ||
====== Mutation ====== | ====== Mutation ====== | ||
Bei der Mutation werden zufällig die Gene eines Chromosoms verändert. Hierbei wird die Wahrscheinlichkeit meist auf 1/Anzahl der Gene gesetzt. Ist ein Gen ausgewählt worden, so wird dieses durch ein zufälliges, | Bei der Mutation werden zufällig die Gene eines Chromosoms verändert. Hierbei wird die Wahrscheinlichkeit meist auf 1/Anzahl der Gene gesetzt. Ist ein Gen ausgewählt worden, so wird dieses durch ein zufälliges, | ||
+ | [{{ : | ||
**Umsetzung in Matlab** | **Umsetzung in Matlab** | ||
<code matlab> | <code matlab> | ||
Zeile 127: | Zeile 148: | ||
Bei der Kreuzung werden immer zwei Chromosome paarweise ausgewählt. Über eine Zufallszahl wird entschieden, | Bei der Kreuzung werden immer zwei Chromosome paarweise ausgewählt. Über eine Zufallszahl wird entschieden, | ||
+ | [{{ : | ||
In der Abbildung ist das Vorgehen schematisch für zwei Chromosome gezeigt. Die Kreuzung erfolgt bei z=3 (vgl. Harbich, 2007, S. 7f). | In der Abbildung ist das Vorgehen schematisch für zwei Chromosome gezeigt. Die Kreuzung erfolgt bei z=3 (vgl. Harbich, 2007, S. 7f). | ||
Zeile 173: | Zeile 195: | ||
* Keine signifikante Verbesserung zur vorherigen Generation | * Keine signifikante Verbesserung zur vorherigen Generation | ||
(vgl. Harbich, 2007, S. 8) | (vgl. Harbich, 2007, S. 8) | ||
+ | |||
+ | |||
+ | ====== Download | ||
+ | |||
+ | {{: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | {{: | ||
====== Literatur | ====== Literatur | ||
- | Harbich, S. 2007. Einführung genetischer Algorithmen mit Anwendungsbeispiel. Zugriff am 15. Juli 2013 unter http:// | + | Harbich, S. 2007. //Einführung genetischer Algorithmen mit Anwendungsbeispiel//. Zugriff am 15. Juli 2013 unter http:// |
+ | |||
+ | {{indexmenu_n> |
sbas/ss2013/genalg.1379231687.txt.gz · Zuletzt geändert: 28.11.2022 00:11 (Externe Bearbeitung)