Benutzer-Werkzeuge

Webseiten-Werkzeuge


sbas:ss2013:genalg

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
sbas:ss2013:genalg [15.09.2013 10:06] – [Crossover] Tobias Kaminskysbas: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 ====== 
-<code matlab>+<code>
 Gegeben: Optimierungsproblem mit Suchraum S und Fitnessfunktion f Gegeben: Optimierungsproblem mit Suchraum S und Fitnessfunktion f
  
Zeile 37: Zeile 37:
 pop_size = 50; % Populationsgröße pop_size = 50; % Populationsgröße
 generations = 100; % Anzahl an Generationen generations = 100; % Anzahl an Generationen
-Leere Population: [Anzahl Populationen, Chromosom & FitnessfunktionAnzahl Generationen+Protokoll [Chromosom #Generation #, (Chromosomausprägung, Fitnesswert)
-% Pouplations entspricht "Protokoll" +protocol=zeros(pop_size,generations, 2);
-populations=zeros(pop_size,2,generations);+
 </code> </code>
  
 +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: p(c_i) = f(c_i) / sum j=1 n f(c_i)+Die Fitness beschreibt die Überlebenswahrscheinlichkeit eines Chromosoms mit der Formel:  
 +<html><br> 
 +`p(c_i) = f(c_i) / (\sum_{j=1}^nf(c_j))` 
 +</html>
  
  
 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 Chromsomen+% Index von bestem Chromosom
 % bestind == [fitness generation element] % bestind == [fitness generation element]
 bestind = [0 0 0]; bestind = [0 0 0];
  
-% Prüfe, ob neues bestes Ergenis+% Prüfe, ob neues bestes Ergebnis
         if (fitness > bestind(1))         if (fitness > bestind(1))
             bestind(1) = fitness;             bestind(1) = fitness;
Zeile 70: Zeile 77:
 Die Auswahl der Chromosomen, die die nächste Generation bilden, erfolgt aufgrund der Überlebenswahrscheinlichkeit. Alle Überlebenswahrscheinlichkeiten werden in ein Intervall gespeichert. Eine Pseudozufallszahl wählt nun ein Chromosom aus. Es ist sofort ersichtlich, dass Chromosomen mit einer größeren Überlebenswahrscheinlichkeit öfter ausgewählt werden.  Die Auswahl der Chromosomen, die die nächste Generation bilden, erfolgt aufgrund der Überlebenswahrscheinlichkeit. Alle Überlebenswahrscheinlichkeiten werden in ein Intervall gespeichert. Eine Pseudozufallszahl wählt nun ein Chromosom aus. Es ist sofort ersichtlich, dass Chromosomen mit einer größeren Überlebenswahrscheinlichkeit öfter ausgewählt werden. 
 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.
-[{{ :sbas:ss2013:selektion.jpg?nolink&500 |Abb. x: Selektion der Chromosomen anhand ihrer Überlebenswahrscheinlichkeit (Harbich, 2007, S. 7}}]+[{{ :sbas:ss2013:selektion.jpg?nolink&500 |Abb. x: Selektion der Chromosomen anhand ihrer Überlebenswahrscheinlichkeit (Harbich, 2007, S. 7)}}]
 **Umsetzung in Matlab** **Umsetzung in Matlab**
 <code matlab> <code matlab>
 % Sortiere aktuelle Population nach Fitness % Sortiere aktuelle Population nach Fitness
-    populations(:,:,f) = sortrows(populations(:,:,f),2);+    protocol(:,:,f) = sortrows(protocol(:,:,f),2);
    
     % 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 84: 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:1:length(P(:,1))     for i=1:1:length(P(:,1))
-        Pnew(i,:) = P(wheel_select(populations(:,:,f),R),:);+        Pnew(i,:) = P(wheel_select(protocol(:,:,f),R),:);
     end     end
          
Zeile 118: 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, aber existierendes Allel ersetzt. Somit ist gewährleistet, dass mit dem veränderten Chromosom gerechnet werden kann (vgl. Harbich, 2007, S. 7f). 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, aber existierendes Allel ersetzt. Somit ist gewährleistet, dass mit dem veränderten Chromosom gerechnet werden kann (vgl. Harbich, 2007, S. 7f).
-[{{ :sbas:ss2013:mutation.jpg?nolink&500 | Abb. x: Mutation eines Chromosoms}}]+[{{ :sbas:ss2013:mutation.jpg?nolink&500 | Abb. x: Mutation eines Chromosoms (Harbich, 2007, S.8)}}]
 **Umsetzung in Matlab** **Umsetzung in Matlab**
 <code matlab> <code matlab>
Zeile 188: 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  ====== 
 +
 +{{:sbas:ss2013:genalg.m| Genetischer Algorithmus}}
 +
 +{{:sbas:ss2013:rwheel.m| Ordnet Chromosome in Intervall [0,1]}}
 +
 +{{:sbas:ss2013:wheel_select.m| Wählt Chromosom auf Intervall aus}}
  
  
 ====== Literatur  ======  ====== Literatur  ====== 
  
-Harbich, S. 2007. Einführung genetischer Algorithmen mit Anwendungsbeispiel. Zugriff am 15. Juli 2013 unter http://www-e.uni-magdeburg.de/harbich/download.php?f=genetische_algorithmen/genetische_algorithmen.pdf+Harbich, S. 2007. //Einführung genetischer Algorithmen mit Anwendungsbeispiel//. Zugriff am 15. Juli 2013 unter http://www-e.uni-magdeburg.de/harbich/download.php?f=genetische_algorithmen/genetische_algorithmen.pdf 
 + 
 +{{indexmenu_n>2}}
sbas/ss2013/genalg.1379232411.txt.gz · Zuletzt geändert: 28.11.2022 00:11 (Externe Bearbeitung)


Warning: Undefined variable $orig_id in /is/htdocs/wp1019470_OPI92FFHXV/www/wikiLehre/lib/plugins/openas/action.php on line 232