strengthga.m

Matlab, The Mathworks, Inc.

August 31, 2009

0001 function [] = strengthga( overallfitness )
0002 %STRENGTHGA Genetischer Algorithmus zur Anpassung der Fitnesswerte
0003 %   Dieser GA soll nach mehreren erfolgten Simulationslufen mit dem
0004 %   gleichen Regelsatz aber unterschiedlichen Fitnesswerten der einzelnen
0005 %   Regeln die Ergebnisse der Lufe miteinander vergleichen und aufgrund
0006 %   der globalen Fitness der entstandenen Strukturen die einzelnen
0007 %   Strkewerte der Regeln genetisch rekombinieren. Dadurch sollen neue
0008 %   Regelstze erzeugt werden, die sich nur durch die Fitness der einzelnen
0009 %   Regeln von den alten Regelstzen unterscheiden.
0010
0011 global wespe;
0012 global Wabengitter;
0013 global MittelWabe;
0014
0015 probcrossover = 0.7; % feste Crossoverwahrscheinlichkeit
0016 probmutation = 0.2; % feste Mutationswahrscheinlichkeit
0017
0018 elternzahl = 20; % Zahl der auszuwhlenden Individuen pro GA-Durchlauf
0019                 % - muss ein Vielfaches von 2 sein
0020
0021 overallrezip = 1 ./ overallfitness; % Die reziproken Werte der Gesamtfitness
0022                                   % zur Berechnung der zu lschenden
0023                                   % Elemente
0024 overallrezip = overallrezip / sum(overallrezip); % Normierung auf Gesamtsumme 1
0025
0026 overallfitness = overallfitness / sum(overallfitness); % Normierung auf Gesamtfitness 1
0027                      % wichtig fr Roulette wheel-Selection
0028
0029 cumulfitness = 0;
0030 cumulrezip = 0;
0031 % es werden zwei Vektoren (maxfitness und maxrezip) erzeugt, in denen fr
0032 % jeden Regelsatz in wespe ein Wert abgespeichert ist, der der Position des
0033 % jeweiligen Abschnitts auf dem Roulette-Wheel entspricht. Der Vektor ist
0034 % normiert auf 1, d.h. der letzte Wert im Vektor sollte 1.0 betragen.
0035 for regelsatz=1:length(overallfitness)
0036     cumulfitness = cumulfitness + overallfitness(regelsatz);
0037     maxfitness(regelsatz) = cumulfitness;
0038     cumulrezip = cumulrezip + overallrezip(regelsatz);
0039     maxrezip(regelsatz) = cumulrezip;
0040 end
0041
0042 % Selektion
0043 eltern = roulette(overallfitness, maxfitness);
0044
0045 % Rekombination

0046 newstrings = onepointxover(eltern);
0047
0048 % Mutation
0049 newstrings = mutation(newstrings);
0050
0051 % Selektion der zu lschenden bauagent-Objekte
0052 % - Es wird das gleiche Prinzip zur Roulette-Wheel-Selektion angewendet wie
0053 % bei der Eltern-Selektion, nur dass auf den Kehrwerten der Fitnesswerte
0054 % gearbeitet wird und deshalb die Selektionswahrscheinlichkeit mit
0055 % steigender Fitness abnimmt, d.h. dass weniger fitte bauagent-Objekte mit
0056 % hherer Wahrscheinlichkeit gelscht werden.
0057 todelete = roulette(overallrezip, maxrezip);
0058
0059 % Erzeugen von zwei zustzlichen bauagent-Objekten in wespe
0060 % - nicht mehr ntig, da die Populationsgre konstant gehalten werden soll
0061 % und fr die neuen Objekte alte berschrieben werden
0062 % Stattdessen direktes Ersetzen der zu lschenden Objekte und Einfgen der
0063 % neuen Fitnessstrings
0064
0065 % rulesetanzahl = size(wespe,1);
0066 for elternindex=1:elternzahl
0067     wespe(todelete(elternindex),1) = bauagent(Wabengitter(1:2, MittelWabe)', 1);
0068     wespe(todelete(elternindex),1).classifierfitnessstring = newstrings(1,:);
0069     wespe(todelete(elternindex),1).updatefitness;
0070 end
0071
0072
0073 function index = roulette(fitnessvektor, maxvektor)
0074
0075     for candid=1:elternzahl
0076         a = rand;
0077         % b = rand;
0078
0079         for ruleset=length(fitnessvektor):-1:2
0080             if ( (a >= maxvektor(ruleset-1)) && (fitnessvektor(ruleset) > 0.0) )
0081                 index(candid) = ruleset
0082                 % maxfitness(ruleset-1) = 1.0; % verhindert, dass fr index2 der gleiche Wert gewhlt wird
0083
0084                 break;
0085             end
0086         end
0087         if ( a < maxvektor(1) )
0088             index(candid) = 1
0089         end
0090
0091         fitnessvektor(index(candid)) = 0.0; % Fitness des gewhlten Individuums auf 0 setzen
0092         fitnessvektor = fitnessvektor / sum(fitnessvektor); % neue Normierung
0093
0094         cumul = 0;
0095         for regel=1:length(fitnessvektor)
0096             cumul = cumul + fitnessvektor(regel);
0097             maxvektor(regel) = cumul;
0098         end % neuen Vektor mit Maximalwerten fr Roulette-Selection erzeugen
0099     end
0100 end
0101

0102     function kinder = onepointxover(eltern)
0103       for xoverindex=1:uint8(elternzahl/2)
0104         string1 = wespe(eltern(xoverindex),1).classifierfitnessstring;
0105         string2 = wespe(eltern(xoverindex+1),1).classifierfitnessstring;
0106            % kopiert die Fitness-Strings der ausgewhlten Eltern in Graycode
0107            % in zwei lokale String-Variablen
0108            % Es wird der Gesamtstring (Strke aller Regeln
0109            % hintereinander) verwendet
0110         xoverpoint = uint16(rand * length(string1));
0111            % whlt einen zuflligen Crossoverpunkt
0112
0113         if (rand <= probcrossover) % nur dann Crossover, wenn Zufallszahl
0114                                    % kleiner als
0115                                    % Crossover-Wahrscheinlichkeit ist
0116             neustring1 = [string1(1:xoverpoint) string2(xoverpoint+1:length(string2))];
0117             neustring2 = [string2(1:xoverpoint) string1(xoverpoint+1:length(string1))];
0118         else % sonst werden die Elternstrings einfach kopiert
0119             neustring1 = string1;
0120             neustring2 = string2;
0121         end
0122
0123         kinder(xoverindex,:) = neustring1;
0124         kinder(xoverindex+1,:) = neustring2;
0125       end
0126     end
0127
0128     function newbitstring = mutation(bitstring)
0129       for mutindex=1:uint8(elternzahl/2)
0130         bitstring1 = bitstring(mutindex,:);
0131         bitstring2 = bitstring(mutindex+1,:);
0132
0133         if (rand < probmutation) % wenn Zufallszahl unter Mutationswahrscheinlichkeit
0134             mutbit = uint16(rand * length(bitstring1));
0135             if strcmp(bitstring1(mutbit),'0')
0136                 bitstring1(mutbit) = '1';
0137             end
0138             if strcmp(bitstring1(mutbit),'1')
0139                 bitstring1(mutbit) = '0';
0140             end
0141         end % fr bitstring1
0142
0143         if (rand <= probmutation) % wenn Zufallszahl unter Mutationswahrscheinlichkeit
0144             mutbit = uint16(rand * length(bitstring2));
0145             if strcmp(bitstring2(mutbit),'0')
0146                 bitstring2(mutbit) = '1';
0147             end
0148             if strcmp(bitstring2(mutbit),'1')
0149                 bitstring2(mutbit) = '0';
0150             end
0151         end % fr bitstring2
0152
0153         newbitstring(mutindex,:) = bitstring1;
0154         newbitstring(mutindex+1,:) = bitstring2;
0155       end
0156     end
0157

0158 end

4