Algorytmy genetyczne

Algorytmy genetyczne Paweł Cieśla

8 stycznia 2009

Genetyka - nauka o dziedziczeniu cech pomiędzy pokoleniami. Geny są czynnikami, które decydują o wyglądzie, zachowaniu, rozmnażaniu każdego żywego organizmu. Podstawy dziedziczenia cech z jednego pokolenia na drugie zostały odkryte 150 lat temu. DNA - (ang. Deoxyribonucleic acid) - kwas deoksyrybonukleinowy, wielocząsteczkowy organiczny związek chemiczny należący do kwasów nukleinowych. Występuje w chromosomach, pełni rolę nośnika informacji genetycznej.

Rodzaje genetyki

1. klasyczna - dziedziczenie cech 2. molekularna - nauka o chemicznej i fizycznej strukturze DNA 3. populacji 4. ilościowa - statystyczne relacje pomiędzy genami a cechami, które są kodowane przez geny

Podział organizmów ze względu na rodzaj komórek 1. eukarionty - organizmy, które posiadają jądro, które ochroni DNA. 2. prokarionty - organizmy nie posiadające jądra komórkowego. DNA znajduje się w płynnym wnętrzu komórki.

Podział organizmów ze względu na rodzaj chromosomów

1. organizmy diploidalne - chromosomy połączone w pary 2. organizmy haploidalne - chromosomy pojedyncze

Rozmnażanie organizmów diploidalnych

Pary chromosomów krzyżują się u każdego rodzica, tworząc pojedynczy chromosom zwany gametą. Obie gamety rodziców tworzą parę chromosomów potomka

Rozmnażanie organizmów haploidalnych

Pojedyncze chromosomy rodziców krzyżują się, tworząc pojedynczy chromosom potomka.

Programy ewolucyjne

Program ewolucyjny jest algorytmem probabilistycznym, w którym generuje się populację osobników P(t) = {x1t , x2t , . . . , xnt } w każdej iteracji t. Każdy osobnik przedstawia możliwe rozwiązanie rozpatrywanego zadania i jest reprezentowany przez strukturę danych S. Każde rozwiązanie xit ocenia się na podstawie miary dopasowania. Nową populację tworzy się (w iteracji t + 1) przez selekcję osobników najlepiej dopasowanych. Nowe osobniki podlegają dodatkowo transformacji za pomocą operatorów genetycznych.

Schemat algorytmu genetycznego I

t := 0;

I

ustal początkowowe P(t);

I

oceń P(t);

I

while(not warunek zakończenia) do

I

begin

I

– t := t + 1;

I

– wybierz P(t) z P(t − 1)

I

– zmień P(t)

I

– oceń P(t)

I

end

Operatory genetyczne

1. Krzyżowanie - połączenie cech dwóch rodzicielskich chromosomów w chromosomach dwóch potomków przez wymianę odcinków chromosomów rodziców. Na przykład jeżeli osobniki (rozwiązania) są reprezentowane przez pięcio elementowe wektory (a1 , b1 , c1 , d1 , e1 ) i (a2 , b2 , c2 , d2 , e2 ), to po operacji krzyżowania po drugim genie będą one miały postać: (a1 , b1 , c2 , d2 , e2 ) oraz (a2 , b2 , c1 , d1 , e1 ). 2. Mutacja - polega na losowej zmianie jednego lub więcej genów wybranego chromosomu.

Algorytm ewolucjny musi zawierać 5 następujących elementów:

1. podstawową reprezentację potencjalnych rozwiązań 2. sposób tworzenia początkowej populacji 3. funkcję oceniającą, która gra rolę środowiska 4. operatory genetyczne, które wpływają na populację potomków 5. wartości różnych parametrów (np. rozmiar populacji, prawdopodobieństwa użycia operatorów krzyżowania i mutacji)

Optymalizacja funkcji Niech funkcja ma postać: f (x) = x sin(10πx) + 1, 0.

Zadanie polega na znalezieniu x ∈ [1, 2] maksymalizującego funkcję f . To znaczy szukamy takiego x0 , że f (x0 ) ­ f (x) dla każdego x ∈ [−1, 2]. Maksimum, które musimy znależć to f (1, 85) = 2, 85.

Reprezentacja zmiennej x

Do reprezentacji zmiennej rzeczywistej x użyjemy chromosomu w postaci wektora binarnego. Długość tego wektora zależy od żądanej dokładności. W moim przykładzie ustalę dokładność do 6 cyfr po przecinku. Dziedzina zmienności x ma długość 3. Ustalona przeze mnie dokładność wymaga aby przedział [−1, 2] był podzielony na 3 ∗ 1000000 podprzedziałów. Oznacza to, że chromosom musi mnieć długość 22 bity, ponieważ: 2097152 = 221 < 3000000 ¬ 222 = 4194304

Odwzorowanie łańcucha binarnego na zmienną rzeczywistą x ∈ [−1, 2]

21 X

< b21 , b20 , . . . , b0 >2 = (

bi 2i )10 = x 0 ,

i=0

x = −1 +

3x 0 . 222 − 1

Ogólnie: x = poczatek +

dlugosc ∗ 3 2iloscbitow − 1

Populacja początkowa

Tworzymy populację chromosomów, w której każdy chromosom ma długość 22 bity. Każdy bit w populacji wyznaczamy losowo.

Jedna iteracja algorytmu genetycznego Pawel Ciesla, Maksymalizacja funkcji: x * sin(10 * Pi * x) + 1 Wypisuje losowa populacje: (1) 1110111011100001000001 (2) 1001110010111010000111 (3) 0110101010010111101010 (4) 1000111001010010110011 (5) 0111110110011001110111 (6) 1011011101010010110111 (7) 1001001111101111000010 (8) 1000101100010110111000 (9) 0000001110011001100011 (10) 1100010010011000100111 (11) 0010011110110111101001 (12) 1011000111010100110011 (13) 1100110101101000000011 (14) 1100101010101100000010 (15) 1011111101100100100010

(16) 1001101100010100010101 (17) 0001010111011010010010 (18) 0100001011100010011100 (19) 0100011111001001001101 (20) 1000011110101101001111 Wypisuje wartosci oceny: (1) 0.912492 (2) 1.759471 (3) 1.249008 (4) 1.569280 (5) 1.366899 (6) -0.145438 (7) 0.365917 (8) 1.505357 (9) 0.067464 (10) 0.869124 (11) 0.529223 (12) 1.539694

(13) 1.280748 (14) 0.008509 (15) 2.206261 (16) 1.414353 (17) 0.271368 (18) 1.104672 (19) 0.847105 (20) 0.811755 Calkowite dopasowanie: 19.533261 Wypisuje prawdopodobienstwa wyboru chromosomow: (1) 0.046715 (2) 0.090076 (3) 0.063943 (4) 0.080339 (5) 0.069978 (6) -0.007446 (7) 0.018733 (8) 0.077066 (9) 0.003454 (10) 0.044495

(11) 0.027093 (12) 0.078824 (13) 0.065568 (14) 0.000436 (15) 0.112949 (16) 0.072407 (17) 0.013893 (18) 0.056553 (19) 0.043367 (20) 0.041558 Wypisuje dystrybuanty: (1) 0.046715 (2) 0.136790 (3) 0.200733 (4) 0.281072 (5) 0.351050 (6) 0.343604 (7) 0.362337 (8) 0.439404 (9) 0.442857 (10) 0.487352

(11) 0.514445 (12) 0.593270 (13) 0.658837 (14) 0.659273 (15) 0.772222 (16) 0.844629 (17) 0.858522 (18) 0.915075 (19) 0.958442 (20) 1.000000 Wypisuje liczby losowe z przedzialu [0, 1]: (1) 0.530000 (2) 0.370000 (3) 0.080000 (4) 0.940000 (5) 0.690000 (6) 0.240000 (7) 0.600000 (8) 0.850000 (9) 0.800000 (10) 0.910000

(11) 0.400000 (12) 0.410000 (13) 0.390000 (14) 0.740000 (15) 0.880000 (16) 0.930000 (17) 0.860000 (18) 0.110000 (19) 0.840000 (20) 0.790000 Wypisuje chromosomy po selekcji: (1) 1011000111010100110011 (2) 1000101100010110111000 (3) 1001110010111010000111 (4) 0100011111001001001101 (5) 1011111101100100100010 (6) 1000111001010010110011 (7) 1100110101101000000011 (8) 0001010111011010010010 (9) 1001101100010100010101

(10) 0100001011100010011100 (11) 1000101100010110111000 (12) 1000101100010110111000 (13) 1000101100010110111000 (14) 1011111101100100100010 (15) 0100001011100010011100 (16) 0100011111001001001101 (17) 0100001011100010011100 (18) 1001110010111010000111 (19) 1001101100010100010101 (20) 1001101100010100010101 Wypisuje wartosci oceny po selekcji: (1) 1.539694 (2) 1.505357 (3) 1.759471 (4) 0.847105 (5) 2.206261 (6) 1.569280 (7) 1.280748 (8) 0.271368

(9) 1.414353 (10) 1.104672 (11) 1.505357 (12) 1.505357 (13) 1.505357 (14) 2.206261 (15) 1.104672 (16) 0.847105 (17) 1.104672 (18) 1.759471 (19) 1.414353 (20) 1.414353 Calkowite dopasowanie po selekcji: 27.865266 Wybrane chromosomy do krzyzowania: 1 3 5 11 13 14 15 17 18 20 Wypisuje chromosomy wybrane do krzyzowania: 1011000111010100110011 1001110010111010000111 1011111101100100100010 1000101100010110111000

1000101100010110111000 1011111101100100100010 0100001011100010011100 0100001011100010011100 1001110010111010000111 1001101100010100010101 Wypisuje chromosomy po krzyzowaniu: 1011000110111010000111 1001110010010100010101 1011111101100100100010 1000101100010110111000 1000101100010110111000 1011111101100100100010 0100001011100010011100 0100001011100010011100 1001110010010100010101 1001101101010100110011 Wypisuje chromosomy przed mutacja: (1) 1011000110111010000111 (2) 1000101100010110111000

(3) 1001110010010100010101 (4) 0100011111001001001101 (5) 1011111101100100100010 (6) 1000111001010010110011 (7) 1100110101101000000011 (8) 0001010111011010010010 (9) 1001101101010100110011 (10) 0100001011100010011100 (11) 1000101100010110111000 (12) 1000101100010110111000 (13) 1000101100010110111000 (14) 1011111101100100100010 (15) 0100001011100010011100 (16) 0100011111001001001101 (17) 0100001011100010011100 (18) 1001110010010100010101 (19) 1001101101010100110011 (20) 1001101101010100110011 Wypisuje chromosomy po mutacji: (1) 1011000110111010000111

(2) 1000100100010110111000 (3) 1001110010010100010101 (4) 0100011111001001001101 (5) 1011111101100100100010 (6) 1000111001010010110011 (7) 1100110111111000000011 (8) 0001010111011110010010 (9) 1001101101010100100011 (10) 0100001011100010011000 (11) 1000100100010110111000 (12) 1000100100010110111000 (13) 1000100100010110111000 (14) 1011111101100100100010 (15) 0100001011100010011000 (16) 0100011111001001001101 (17) 0100001011100010011000 (18) 1001110010010100010101 (19) 1001101101010100100011 (20) 1001101101010100100011 Wypisuje wartosci oceny po mutacji i krzyzowaniu:

(1) 1.574700 (2) 1.117555 (3) 1.737772 (4) 0.847105 (5) 2.206261 (6) 1.569280 (7) 1.560727 (8) 0.272421 (9) 1.479246 (10) 1.104691 (11) 1.117555 (12) 1.117555 (13) 1.117555 (14) 2.206261 (15) 1.104691 (16) 0.847105 (17) 1.104691 (18) 1.737772 (19) 1.479246 (20) 1.479246

Calkowite dopasowanie: 26.781437

Metody selekcji I

Metoda proporcjonalna 1. Wyznacz prawdopodobieństwa wyboru osobników z populacji w postaci względnego przystosowania f (xi ) ; i = 1, . . . , N. ps (xi ) = PN i=1 f (xi ) 2. Wyznacz dystrybuantę dla ustalonej sekwencji osobników q(xi ) =

i X

ps (xi ).

j=1

3. N - krotnie zakręć kołem ruletki: I

I

Wygeneruj dla każdego osobnika z populacji liczbę losową r ∈ [0, 1]. Ustal pierwszego napotkanego osobnika w populacji, dla którego spełniony jest warunek: r ¬ q(xi ).

I

Skopiowanie wylosowanego osobnika do nowej populacji.

Metody selekcji II I

Metoda ze stochastycznym doborem resztowym: 1. Wyznacz oczekiwaną liczbę kopii osobników w populacji: e(xi ) = PN

f (xi )

i=1

f (xi ) ∗ N

; i = 1, . . . , N.

PN 2. Skopiuj Nint = i=1 be(xi )c osobników do nowego pokolenia. ˜ = N − Nint Oblicz N 3. Wyznacz dystrybuantę osobników: q(xi ) =

i X {e(xi ) − be(xi )c}. j=1

˜ - krotnie 4. Kręcimy kołem ruletki N I I

Losujemy dla każdego osobnika liczbę r ∈ [0, 1]. Ustalenie pierwszego napotkanego osobnika w populacji, dla którego spełniony jest warunek: r¬

I

q(xi ) . q(xn )

Skopiowanie wylosowanego osobnika do nowego pokolenia.

Metody selekcji III

I

Metoda turniejowa - metoda polegająca na rywalizacji dwóch osobników.

Ocena stopnia przystosowania W algorytmach genetycznych wymagane jest, aby przeciwdziedzina funkcji celu miała wartości dodatnie. Sposoby przekształcenia funkcji celu w przypadku wartości ujemnych: 1. Dla funkcji kosztu u(x), gdy jej przeciwdziedzina przyjmuje wartości dodatnie i ujemne f (x) = Cmax − u(x). 2. 3. Dla funkcji zysku g (x), gdy jej przeciwdziedzina przyjmuje wartości dodatnie i ujemne f (x) = g (x) + Cmin .