WYKŁAD 08: ALGORYTMY EWOLUCYJNE

Do tej pory było o algorytmach kreślących trajektorie. Te metody są takie, któ¶e dosyć dobrze
znajdują minimum lokalne. Ale to mało. Należy szukać metod, które dobrze atakują temat z wielu
stron.

zACZĘTO SIĘ PRZYGLĄDAĆ JAK ZNALEŹĆ OPTYMALNE cehy osobnika, które sprawą, ze
będzie on lepszy od innych - natura, geny itd.

Zagadnienie jest szersze. Algorytmy te opieracją sie na pojęciu ewolucje. Początek w ok '65.
Generowanie automatów skończonych wówczas były... Wtedy pojawiła się ewolucja w
informatyce.

z jednej strony problemy natury kombinatorycznej, z drugiej będziemy te robić takie algorytmy,
które będą optymalizacyjne.

Populajca - osobnik, pewien wzór. Osobnik może być "rozwiązaniem", ale trochę będzie to inaczej.

Pierwsza rzecz:
Algorytm musi stworzyć populację początkową. Jeżeli przyjmiemy, że nasz osobnik to rozwiązanie
probvlemu komiwojażera (permutacja), to potrzebujemy wylosować zadaną liczbę permutacji.

Należy dobrać reprezentację. Musimy mnieć na uwadze to, że w zależności od problemu osobniki
mogą co innego reprezentować. Jeżeli natury reprezentacji ciągłej, to osobnik moze być wektorem
liczb 64bitowej. Ale może to też być permutacja, wektor binarny itd. Mamy populację początkową.
Należey dokonać oceny tej populacji.

P = utwórz_populację()
OceńPopulację(P);

Ocena: liczbowe dopasowanie cech osobnika do środowiska.
Nie jest to warotść funkcji kryterialnej. To też dodatkowe cechy, które powodują, ze osobnik jest
lepszy niż inne.

Jeżeli mamy to:

while (G.O.) //game over

Dopóki nie spełnione warunki zatrzymania algorytmu, to wykonujemy to. Może to być liczba
iteracji, po której nie otrzymaliśmy poprawy warttości funkcji celu itd.

Próbujemy popatrzeć jak problem rozwiązano i stworzyć OPERATOR REKOMBINACJI i
tworzymy:

P = Rekombinacje(P)

czyli jeżeli weźmiemy dwójkę rodziców i skrzyżujemy ich geny, to otrzymamy potomka. Np.
mozemy decydować kto ojcem, a kto matką, albo że np potomek powstaje z wszystkich
osobników...
Jeżeli popatrzymy na to:
p = p'

jeżeli tutaj się zatrzyma naszz algorytm, to mamy coś w tylu znalezienia minimum. Mamy
ograniczoną pulę genów. Ona ma wsyztskie możliwe kombinacje, ale poza nie nie wychodzimy.
Aby proces nie był tożsamy z tym, że te wszystkie elementy do jednego pkt się schodzą, to trzeba
dodać jakiś element losowy, zwany MUTACJĄ. Czyli osobniki, które dostajemy po rekombinacji
rodziców podlegają mutacji.

Teraz musimy zdecydować co z tego zostawił. Zał: ilość osobników stała. Patrząc na to, mamy
populację rodzicielską i zmutowaną populację dzieci. Teraz populacja startowa iteracjik to selekcja
p z rodziców i permutacji z dzieci. IU to schemat algorytmu. Każdy se podstawi swoje funkcje i
mamy algorytm.

P = utwórz_populację()
Oceń_populację(P)
while(GO){
P' - Rekombinacje (P)
P'' - Mutacja(P')
OceńPopucjację(P'')
P = Selekcja (P, P'')
}

Zacznijmy od wektora:

A: 101001101
B: 101111111

I musimy na podstawie tych rodziców wygenerować potomka. Musmy nie losowo to zrobić, ale tak,
że jeżeli rodzić ma dobrą cechę, drugi też, to dziecko ma te dobre cechy.

Losujemy pkt krzyżowania i mówimy, że potomek skłąda się z jednej części potomka a i jednej
potomka B.

A: 101
B: 1111111
C: 1011111111

Tak mamy w przypadku wektorów. W permutacjach:

A = 1 5 3 2 6 4
B = 4 1 2 3 6 5

Musimy stworzyć metodę krzyżowania tak, aby otrzymać osobnika trzeciego.

Pomysły są: losujemy albo ustawiamy jakiś pkt i osobnik wynikowy wygląda tak, że ma prefix z
rodzica A natomiast elementy pozostałe są w takiej kolejności jak w rodzicu B
C: 1 5 3 | 4 2 6

Czasami będą dobre wyniki, czasami nie... Ale nie przejmujemy się tym.

Tych operatorów jest wiele.

A jak w naturze ciągłej?
A: a

B: b
C: ?

Można wybrać kombinację liniową, np:

C: c= alfa * a + (1 - alfa)*b

To są operatory krzyżowania. Ale zakładamy, że gdy mamy n osobników, to chcemy otrzymać też n
osobników. Metoda musi jakoś wybrać osobniki, które muszą sie rozmnażać. Najprostsze podejście:

Chcemy mieć n potomków, to pętle od 1 do n i każda iteracja musi wygenerować potomka.
Losujemy z puli dwójkę rodziców, albo więcej - ile trzeba.

Są też inne: najpopularniejsze, to metoda ruletkowa. Z każdym z osobników związujemy
prawdopodobieństwo bycia wylosowanym do rozmnażania.

<rys 1>

Rozwinięcie: np piątka najlepszych można wziąć, a resztę losujemy.

Mutacja. Mutacja ma za zadanie rozszerzenie obszaru poszukiwań na inne fragmenty przestrzeni
poszukiwać. Te metody lubią się skupiać na jednym obszarze, przez co jest on wąski. Aby przenieść
poszukiwania, potrzeba mutacji. Ten operator musi to umieć, ale nie może być równoważny z tym,
że przez 10000000 iteracji losujemy byle co. Jeżeli operator będzie za mocny to może wszytsko
popsuć.

Dla każdego potomka mutacja zachodzi z jakimś mały prawdopodobieństwem. Jak zachodzi, to
dokonujemy małą zmianę w nim. Np przy wektorze binarnym można jeden bit zanegować. W
permutacji operacja insert, w ciagłych obszarze losujemy i dodajemy jakiegoś małego epsilona itd.

Selekcja: mając dane populacje decydujemy kto dożyje do następnej iteracji. Potem selekcja - np
zostają najleszy, najgorszy, a reszta losowo. Mamy z resztą dowolność. Mus zostać jedna populacja.

Jeżeli o genetyczny algorytm chodzi, to mamy wsyztsko.

Z ostatnich nowinek:

Są techniki, które co pewną liczbę iteracji zmiejszają populacje. Istnieje taki moment, że populacja
bedzie jednoosobnikowa i koniec. Albo: nic się nie dzieje, mielimy, a nie znaleźliśmy lepszego
rozwiązania, to czas na drastyczne zmiany. I wówczas z naszej populacji 80% osobników
wybijamy, a resztę losujemy.

A może warto parametry co jakiś czas je zmieniać? Bo albo mamy stałe, albo losowe... A my
zróbmy stałe, ale losowe co jakiś czas.

Znaczenie ma też: na liście tabu nie zapisywaliśmy rozwiązń, tylko ruchy, które nas do niej
doprowadziły. Podobnie tyutaj: jeżeli poatrzymy na organizm, to to jak wygląda nie ma związku z
jego kodem DNa. Ale jest efektywny. Więc mówiliśmy, że każdy osobnik może, ale nie musi
kodować rozwiązania. Można nie być tym osobnikiem, ale być do niego przekształconym. Więc
taki mamy dna i rozwijamy je. Potem gdy jest dorosłe, to je oceniamy.

Można też tak jak w nehu do tworzenia populacji wprowadzać wartości wstępne.

Albo mieć cechy, które ukierunkowują algorytm do znalezienia lepszych osobników.

MAmy pkt początkowy, np wektor w przestrzeni R^k. Mamy funkcję, który parametr ma wektor i
musimy znaleźć fiunckje. Najprościej. Mamy jakiś punkt i idziemy w przeciwnym kierunku niż
gradient. Czyli największego spadku wartości funckji celu. Zawsze ona dojdzie natomiast do
minimum lokalnego. Ale patrzymy nie na konkretne rozwiazania, lecz cechy ich, które doprowadzą
do rozwiązań.

Inny pomysł: My często definiujemy rpzestrzeń rozwiąań tak, aby dla nich istniały proste operatory
i operacje krzyżowania. Ale nie są one równoważne z przestrzenią rozwiązań. Bo ona nie zawiera
optymalnego. Musmy założyć dopiero, że ona go zawiera. Musimy zdef, że nasza przestrzeń jest
mniejsza, ale zawiera optimum. Albo czasami musimy dodać rozwiązania, któr nie zawierają sie i
nie mają związku z przestrzenią.

Np mamy komiwojarzera, ale jest ograniczenie, że nie morze przejść przez 3 miasta nieparzyste pod
rząd. Nie da się takich permutacji zrobić skrócie mówiąc. Łatwiej zrobić rpzestrreń permutacji. Ale
nie wszytskie rozwiązania są dopuszczalne. Bo nie odzwierceidlają rozwiązania naszego problemu.
Ale wszędzie jest taki problem.

Nie ma problemu w sytuacjach, w któ¶ych łatwo trafić losowo na rozwiązanie dopuszczalne.
Czsami jest 1 na milion. I jak trafić na nie? Jak jest dużo takich rozwiązań równomiernie, to do
skutku robimy sobie potomków. Ale są taki przestrzenie, że nie zawsze można sobie t\na to
pozwolić. Bo takie losowanie może się nie wylosować. Można więc dopuścić np na chwilową utratę
rozwiązań z populacji - uznać, że są niedopuszczalne, ale będą.

Mając potomka niedopuszczalne piszemy taką metodę, którago poprawi, zmieniając cechy mówiące
o tym, że jest on niedopuszczalny.

JEżeli mamy dokobncać selekcji na podst 2 populacji, która zawiera dopuszczalne i niedpousczalne,
to selekcje musimy zmodyfikować, aby premiowała rozwiązanie, które jest dopuszczalne. Np
niedopuszczalne dostają jakąś karę, która odejmuje jakąś wartość od niedopuszczalnej wartości.

Ale niezależnie od tego co zrobimy w tych algorytmach, to one jakoś tam działają. Munusem jest
to, że nie ma ogólnej metody jak ma to wyglądać. Mamy roziwązać problem, piszemy waerianty z
nadzieję, że może one zadziałają....