1 formalnie: Algorytmy genetyczne i wstęp do algorytmów ewolucyjnychDorota Cendrowska nieformalnie: Techniczna wersja teorii Darwina lub parafraza książki Dawkingsona: Samolubny gen...

2 Plan wykładu przykład gdy „duże” staje się „zbyt duże”metody poradzenia sobie ze „zbyt dużym”: poprzez dołączanie/eliminację algorytm wzrostu algorytm symulowanego wyżarzania algorytm genetyczny algorytm genetyczny: podstawowe elementy składowe operatory kłopoty

3 Wybór atrybutów i... skalowalność

4 Wybór atrybutów a skalowalność

5 Wybór atrybutów poprzez dołączaniew każdym wywołaniu dołączany jest jeden z dostępnych atrybutów dla najlepszego „dołączenia” funkcja jest wywoływana rekurencyjnie parametry: T: zbiór uczący A: lista dostępnych atrybutów, na starcie wszystkie: A1, ..., An W: lista wybranych atrybutów, na starcie lista pusta.

6 Wybór atrybutów poprzez dołączanieLista wybierzDołączanie(T,A,W){ double najlepszaOcenaNaTymPoziomie=0; Lista wybor; for(Atrybut a: A){ ocena=uruchomBlackBox_i_OceńPrzydatnosc(T,W+a); if (ocena>najlepszaOcenaNaTymPoziomie){ wybor=W+a pozostałeA=A-a; najlepszaOcenaNaTymPoziomie=ocena; } if (pozostałeA!=null){ Lista tmp=wybierzDołączanie(T,pozostałeA,wybor); ocena=uruchomBlackBox_i_OceńPrzydatność(T,tmp); if (ocena>najlepszaOcenaNaTymPoziomie) wybor=tmp; return wybor;

7 Wybór atrybutów poprzez dołączanieLista wybierzDołączanie(T,A,W){ . } A={1, 2, 3, 4}, W=null

8 Wybór atrybutów poprzez dołączanieLista wybierzDołączanie(T,A,W){ . } A={1, 2, 3, 4}, W=null A={1, 3, 4}, W={2}

9 Wybór atrybutów poprzez dołączanieLista wybierzDołączanie(T,A,W){ . } A={1, 2, 3, 4}, W=null A={1, 3, 4}, W={2} A={3, 4}, W={2, 1}

10 Wybór atrybutów poprzez dołączanieLista wybierzDołączanie(T,A,W){ . } A={1, 2, 3, 4}, W=null A={1, 3, 4}, W={2} A={3, 4}, W={2, 1} A={4}, W={2, 1, 3}

11 Wybór atrybutów poprzez eliminacjęw każdym wywołaniu usuwany jest jeden z branych pod uwagę atrybutów dla najlepszej „eliminacji” funkcja jest wywoływana rekurencyjnie parametry: T: zbiór uczący W: lista atrybutów branych pod uwagę, na starcie wszystkie: A1, ..., An

12 Wybór atrybutów poprzez eliminacjęLista wybierzElimincja(T, W){ double najlepszaOcenaNaTymPoziomie, ocenaWszystkich; Lista wybor; ocenaWszystkich=uruchomBlackBox_i_OceńPrzydatnosc(T,W); if (rozmiar listy W!=1){ for(Atrybut a: W){ ocena=uruchomBlackBox_i_OceńPrzydatnosc(T,W–a); if (ocena>najlepszaOcenaNaTymPoziomie){ wybor=W–a najlepszaOcenaNaTymPoziomie=ocena; } Lista tmp=wybierzEliminacja(T,wybor); ocena=uruchomBlackBox_i_OceńPrzydatność(T,tmp); if (ocena>najlepszaOcenaNaTymPoziomie) { wybor=tmp; najlepszaOcenaNaTymPoziomie=ocena; } if (ocenaWszystkich>najlepszaOcenaNaTymPoziomie) wybor=W; else wybor=ocenaWszystkich; return wybor;

13 Wybór atrybutów poprzez eliminacjęLista wybierzElimincja(T, W){ . }

14 Algorytm największego wzrostuLista wybierzMetodaMaxWzrostu(T, ilePrób, k){ if (ilePrób<=0) return null Lista start=wylosujAktualnyWybór(); double ocenaStartowego=uruchomBlackBox_i_OceńPrzydatnosc(T,start); do{ wyborSasiedzi[]=wylosuj k wyborów różniących się na jednej pozycji od start; oceń każdy z wyborów z tablicy wyborSasiedzi i wybierz z nich najlepsze rozwiązanie  (najlepszySasiad, ocena) if (ocena>ocenaStartowego){ start=najlepszySasiad; ocenaStartowego=ocenaMax; } }while(start==najlepszySasiad); if (ilePrób>1){ Lista innyDobry=wybierzMetodaMaxWzrostu(T, ilePrób-1,k); return (lepsze z rozwiązań: start i innyDobry);

15 Algorytm największego wzrostuLista wybierzMetodaMaxWzrostu(T, ilePrób, k){ if (ilePrób<=0) return null Lista start=wylosujAktualnyWybór(); double ocenaStartowego=uruchomBlackBox_i_OceńPrzydatnosc(T,start); do{ wyborSasiedzi[]=wylosuj k wyborów różniących się na jednej pozycji od start; oceń każdy z wyborów z tablicy wyborSasiedzi i wybierz z nich najlepsze rozwiązanie  (najlepszySasiad, ocena) if (ocena>ocenaStartowego){ start=najlepszySasiad; ocenaStartowego=ocenaMax; } }while(start==najlepszySasiad); if (ilePrób>1){ Lista innyDobry=wybierzMetodaMaxWzrostu(T, ilePrób-1,k); return (lepsze z rozwiązań: start i innyDobry);

16 Algorytm największego wzrostu (przykład)Lista wybierzMetodaMaxWzrostu(T, ilePrób, k){ if (ilePrób<=0) return null Lista start=wylosujAktualnyWybór(); double ocenaStartowego=uruchomBlackBox_i_OceńPrzydatnosc(T,start); do{ sasiedzi[]=wylosuj k wyborów różniących się na jednej pozycji od start; oceń każdy z wyborów z tablicy sasiedzi i wybierz z nich najlepsze rozwiązanie  (najlepszySasiad, ocena) if (ocena>ocenaStartowego){ start=najlepszySasiad; ocenaStartowego=ocenaMax; } }while(start==najlepszySasiad); if (ilePrób>1){ Lista innyDobry=wybierzMetodaMaxWzrostu(T, ilePrób-1,k); return (lepsze z rozwiązań: start i innyDobry); start={2, 3} sasiedzi={{1, 2, 3}, {3}, {2, 3, 4}}

17 Algorytm największego wzrostu (przykład)Lista wybierzMetodaMaxWzrostu(T, ilePrób, k){ if (ilePrób<=0) return null Lista start=wylosujAktualnyWybór(); double ocenaStartowego=uruchomBlackBox_i_OceńPrzydatnosc(T,start); do{ sasiedzi[]=wylosuj k wyborów różniących się na jednej pozycji od start; oceń każdy z wyborów z tablicy sasiedzi i wybierz z nich najlepsze rozwiązanie  (najlepszySasiad, ocena) if (ocena>ocenaStartowego){ start=najlepszySasiad; ocenaStartowego=ocenaMax; } }while(start==najlepszySasiad); if (ilePrób>1){ Lista innyDobry=wybierzMetodaMaxWzrostu(T, ilePrób-1,k); return (lepsze z rozwiązań: start i innyDobry); start={1, 2, 3} sasiedzi={{1, 2}, {1, 3}, {1, 2, 3, 4}}

18 Algorytm symulowanego wyżarzaniaLista wybierzMetodaSymWyżarzania(T){ Lista start=wylosujAktualnyWybór(); double ocenaStartowego=uruchomBlackBox_i_OceńPrzydatnosc(T,start); do{ Lista sasiad=wylosuj „coś” co różni się na jednej pozycji od start; double ocena=uruchomBlackBoz_i_OceńPrzydatność(T,sasiad); if (ocena>ocenaStartowego){ start=sasiad; ocenaStartowego=ocena; } else if (Math.random() start=sasiad; ocenaStartowego=ocena; zmniejsz(T); }while(nie_nastąpi_ochłodzenie);

19 Wyżarzanie vs. metoda maksylnego wzrostumetoda maksymalnego wzrostu: wyżarzanie: „musi/[może] być gorzej aby było lepiej”

20 schemat algorytmu genetycznego

21 schemat algorytmu genetycznego

22 Fenotyp, genotyp, populacja (alg. genetyczny)Fenotyp: konkretne rozwiązanie, w problemie wyboru atrybutów: atrybuty 3, 5 i 9 Genotyp: zakodowane binarnie konkretne rozwiązanie, w problemie wyboru atrybutów: Populacja: ustalony (co do rozmiaru) zbiór genotypów

23 schemat algorytmu genetycznego

24 Ocena członków populacjifunkcja przystosowania (celu): funkcja, która ocenia przydatność rozwiązania reprezentowanego przez genotyp:

25 Własności funkcji przystosowaniamonotoniczna rosnąca (przykład: wybór atrybutów)

26 Własności funkcji przystosowaniamonotoniczna rosnąca (przykład: wybór atrybutów) dodatnia (?)

27 metody selekcji: P(t)R(t)metoda rankingowa: wybór k najlepszych z populacji P(t)

28 metody selekcji: P(t)R(t)metoda rankingowa: wybór k najlepszych z populacji P(t) metoda ruletki:

29 metody selekcji: P(t)R(t)metoda rankingowa: wybór k najlepszych z populacji P(t) metoda ruletki metoda turniejowa: losowy wybór s osobników z P(t); rodzicem staje się zwycięzca z wybranych osobników (mający maksymalną wartość funkcji przystosowania)

30 schemat algorytmu genetycznego

31 reprodukcja: R(t)D(t)reprodukcja oznacza: krzyżowanie — wymiana fragmentu chromosomu — z pewnym prawdopodobieństwem (zwykle dużo większym niż mutowanie, np. 0.2–0.4) mutowanie — zamiana pojedynczego genu — z pewnym prawdopodobieństwem (np. 0.05)

32 reprodukcja: R(t)D(t)reprodukcja oznacza: krzyżowanie — wymiana fragmentu chromosomu — z pewnym prawdopodobieństwem (zwykle dużo większym niż mutowanie, np. 0.2–0.4) mutowanie — zamiana pojedynczego genu — z pewnym prawdopodobieństwem (np. 0.05) klasyczne operatory: operator krzyżowania operator mutacji

33 reprodukcja: R(t)D(t)operator krzyżowania: jednopunktowy

34 reprodukcja: R(t)D(t)operator krzyżowania: jednopunktowy wielopunktowy (np. dwupunktowy)

35 reprodukcja: R(t)D(t)operator krzyżowania: „wygodna implementacja”

36 reprodukcja: R(t)D(t)klasyczne operatory: operator krzyżowania operator mutacji — czy mutować? Jeśli tak, to który gen (dla każdego osobnika osobno)

37 schemat algorytmu genetycznego

38 metody selekcji: D(t)P(t+1)metoda rankingowa: wybór n najlepszych z populacji D(t) wybór (n–m) najlepszych z populacji D(t) i zachowanie m najlepszych ze starej populacji P(t)

39 Kłopoty: funkcja przystosowaniamonotoniczna rosnąca, ale (!), przykład: wybór atrybutów, ale nie więcej niż 5.

40 Kłopoty: funkcja przystosowaniamonotoniczna rosnąca, ale (!), przykład: wybór atrybutów, ale nie więcej niż 5. problem plecakowy: ograniczenie łącznej wagi z jednoczesną maksymalizacją wartości przedmiotów wśród „złych” są „mniej złe” :)

41 Kłopoty: funkcja przystosowaniaznajdowanie optimum: maksimum: f(x)  fc=f(x) minimum: h(x)  fc=1/h(x)

42 Kłopoty: funkcja przystosowaniaznajdowanie optimum: maksimum: f(x)  fc=f(x) (?) minimum: h(x)  fc=1/h(x) (?)

43 Kłopoty: funkcja przystosowaniaznajdowanie optimum: maksimum: f(x)  fc=f(x) (?) minimum: h(x)  fc=1/h(x) (?) przykłady: f(x)=h(x)=x2 dla x z przedziału <0,100> f(x)=h(x)=x2 dla x z przedziału <-50, 50>

44 Kłopoty: reprezentacja binarnaprzykład: f(x)=x2 dla x całkowitego z przedziału <0, 100> fc=f(x)+1 kodowanie — fenotyp  genotyp    

45 Kłopoty: reprezentacja binarnaprzykład: f(x)=x2 dla x całkowitego z przedziału <-50, 50> fc=f(x)+1 kodowanie — fenotyp  genotyp    

46 Kłopoty: reprezentacja binarnaargument rzeczywisty z określoną precyzją: <0, 3.5> z precyzją dwóch miejsc po przecinku fenotyp  genotyp    

47 Kłopoty: reprezentacja binarnaargument rzeczywisty z określoną precyzją: <0, 3.5> z precyzją dwóch miejsc po przecinku a jeśli (co gorsza) jest kilka argumentów rzeczywistych, np. f(x, y, z, t)? fenotyp  genotyp    

48 Kłopoty: reprezentacja binarnakomiwojażer (n miast):

49 Kłopoty: reprezentacja binarnakomiwojażer (n miast): komiwojażer (6 miast):

50 Kłopoty: reprezentacja binarnakomiwojażer (n miast): komiwojażer (6 miast): zdecydowana większość chromosomów nie odpowiada żadnemu sensownemu fenotypowi:

51 Genetyczny czy ewolucyjny algorytm?algorytmy genetyczne algorytmy ewolucyjne

52 po kłopotach: reprezentacja całkowitakomiwojażer (n miast): komiwojażer (12 miast): problemy: klasyczny operator krzyżowania klasyczny operator mutacji (jak?)

53 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle):

54 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”:

55 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”: uzupełnij liczby, które nie powodują konfliktów:

56 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”: uzupełnij liczby, które nie powodują konfliktów: uzupełnij wykorzystując reguły utworzone przez „podtrasy” 12      11

57 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”: uzupełnij liczby, które nie powodują konfliktów: uzupełnij wykorzystując reguły utworzone przez „podtrasy” 12      11

58 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”: uzupełnij liczby, które nie powodują konfliktów: uzupełnij wykorzystując reguły utworzone przez „podtrasy” 12      11

59 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”: uzupełnij liczby, które nie powodują konfliktów: uzupełnij wykorzystując reguły utworzone przez „podtrasy” 12      11

60 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”: uzupełnij liczby, które nie powodują konfliktów: uzupełnij wykorzystując reguły utworzone przez „podtrasy” 12      11

61 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”: uzupełnij liczby, które nie powodują konfliktów: uzupełnij wykorzystując reguły utworzone przez „podtrasy” 12      11

62 po kłopotach: reprezentacja całkowitakrzyżowanie PMX (Goldberg i Lingle): wymień „podtrasy”: uzupełnij liczby, które nie powodują konfliktów: uzupełnij wykorzystując reguły utworzone przez „podtrasy” 12      11

63 Krzyżowanie OX (Davis)zapisz ciągi liczb zaczynając od elementu za „podtrasą”

64 Krzyżowanie OX (Davis)zapisz ciągi liczb zaczynając od elementu za „podtrasą”

65 Krzyżowanie OX (Davis)zapisz ciągi liczb zaczynając od elementu za „podtrasą” skreśl te elementy, które występują w podtrasie drugiego rodzica

66 Krzyżowanie OX (Davis)zapisz ciągi liczb zaczynając od elementu za „podtrasą” skreśl te elementy, które występują w „podtrasie” drugiego rodzica przepisz, zaczynając od elementu za „podtrasą”:

67 Krzyżowanie cykliczne CX (Oliver)Określ cykl rozpoczynając od pierwszego elementu pierwszego rodzica:

68 Krzyżowanie cykliczne CX (Oliver)Określ cykl rozpoczynając od pierwszego elementu pierwszego rodzica: 9  2  10  4  9

69 Krzyżowanie cykliczne CX (Oliver)Określ cykl rozpoczynając od pierwszego elementu pierwszego rodzica: 9  2  10  4  9

70 Krzyżowanie cykliczne CX (Oliver)Określ cykl rozpoczynając od pierwszego elementu pierwszego rodzica: Dokonaj wymiany pozostałych bloków: 9  2  10  4  9

71 mutacja dla problemu komiwojażerawymiana losowo wybranych elementów genotypu:

72 Krzyżowanie i mutacja dla liczb rzeczywistychLiczby w genotypie zapisywane są z określoną precyzją (przed i po przecinku) Krzyżowanie jest „identyczne” z klasycznym krzyżowaniem, np.:

73 Krzyżowanie i mutacja dla liczb rzeczywistychLiczby w genotypie zapisywane są z określoną precyzją (przed i po przecinku) Krzyżowanie jest „identyczne” z klasycznym krzyżowaniem, np.:

74 Krzyżowanie i mutacja dla liczb rzeczywistychLiczby w genotypie zapisywane są z określoną precyzją (przed i po przecinku) Krzyżowanie jest „identyczne” z klasycznym krzyżowaniem, np.:

75 Krzyżowanie i mutacja dla liczb rzeczywistychLiczby w genotypie zapisywane są z określoną precyzją (przed i po przecinku) Krzyżowanie jest „identyczne” z klasycznym krzyżowaniem, np.: Mutacja oznacza zamianę cyfry na dowolną inną z określonego dla danej pozycji możliwych cyfr

76 Podsumowanie algorytm genetyczny/ewolucyjny: reprezentacja operatoryprawdopodobieństwa użycia operatorów rozmiar populacji, populacji rodzicielskiej, populacji potomków

77 jak zwykle, zamiast zakończenia...filozoficznie: — Wie pani — powiedział do pani Bird, gdy przyszła do jadalni, by sprawdzić, czy już zjadł grzankę z marmoladą — nigdy dotąd nie zrobiłem wszystkiego, bo gdybym zrobił, to nie czekałyby mnie już żadne niespodzianki. fragment okładki i książki pt. „Paddington daje sobie radę” (autor: Michael Bond)