Sztuczna inteligencja wykład cz4


Algorytmy ewolucyjne

Wprowadzenie

Inspiracją do podjęcia badań dotyczących algorytmów ewolucyjnych było naśladowanie natury w zakresie zjawisk na gruncie genetyki (przekazywanie korzystnych cech potomstwu poprzez krzyżowanie i mutacje).

Idea ta została wykorzystana do rozwiązywania zagadnień optymalizacyjnych. Mówiąc najprościej - poszukiwanie takich rozwiązań oparte jest o zasadę, że spośród rozwiązań, które dziedziczą pewne cechy po swoich rodzicach, „przeżywają” tylko te rozwiązania, które są najlepiej przystosowane.

Klasyczne metody optymalizacji

Klasyczne metody poszukiwania optymalnych rozwiązań dzielą się na: metody analityczne, przeglądowe, oraz losowe.

W metodach analitycznych poszukujemy lokalnych ekstremów funkcji rozwiązując układy równań (zwykle nieliniowych). Metody te maja liczne wady - są złożone, nie zawsze dadzą się zastosować, często „utykają” w lokalnych ekstermach funkcji.

Metody przeglądowe polegają, mówiąc w uproszczeniu, na obliczaniu wartości funkcji celu w całej przestrzeni poszukiwań po kolei. Oczywiście dla dużych przestrzeni jest to bardzo nieefektywne i często po prostu niemożliwe.

Metody losowe polegają na losowym przeszukiwaniu przestrzeni rozwiązań i zapamiętywaniu otrzymanych wyników, z których potem wybiera się najlepsze. Są one również mało efektywne.

Idea algorytmów ewolucyjnych

Są to algorytmy oparte na mechanizmach doboru naturalnego i dziedziczenia. Korzystają z ewolucyjnej zasady przeżycia osobników najlepiej dostosowanych.

Główne cechy algorytmów ewolucyjnych, to:

Podstawowe pojęcia:

Bardzo ważnym pojęciem jest funkcja przystosowania, zwana również funkcją dopasowania, lub funkcją oceny. Pozwala ona ocenić stopień dopasowania danego osobnika w populacji i w ten sposób wybrać osobniki najlepiej przystosowane ( o największej wartości funkcji dopasowania) zgodnie z ewolucyjną zasadą przetrwania „najsilniejszych”. W teorii sterowania funkcją przystosowania może być funkcja błędu, którą się minimalizuje. W teorii gier - funkcja kosztu, podlegająca również minimalizacji.

W algorytmie ewolucyjnym w każdej jego iteracji, ocenia się przystosowanie każdego osobnika danej populacji za pomocą funkcji przystosowania i na tej podstawie tworzy nową populację osobników, stanowiących zbiór potencjalnych rozwiązań problemu.

Klasyczny algorytm genetyczny

0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic
Nie Tak

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
warunek

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
Wyprowadzenie „najlepszego

0x08 graphic
0x08 graphic
chromosomu

0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic

0x08 graphic

Rys. 16. Schemat blokowy klasycznego algorytmu
genetycznego

Inicjacja (utworzenie populacji początkowej) polega na losowym wyborze żądanej liczby chromosomów (osobników) reprezentowanych przez ciągi binarne o określonej długości.

Ocena przystosowania osobników z populacji polega na obliczeniu wartości funkcji przystosowania dla każdego chromosomu z populacji.

Sprawdzenie warunków zatrzymania. Zależą one od konkretnego zadania. Najczęściej jest to:

Selekcja chromosomów polega na wybraniu na podstawie wartości funkcji przystosowania, tych chromosomów, które będą brały udział w tworzeniu następnego pokolenia. Najbardziej popularną metodą selekcji jest metoda ruletki.

W wyniku procesu selekcji zostaje utworzona populacja (pula) rodzicielska o liczebności zazwyczaj takiej, jak liczebność bieżącej populacji.

Operatory genetyczne

Zastosowanie operatorów genetycznych do chromosomów wybranych metodą selekcji prowadzi do utworzenia nowej populacji, która jest populacją potomków, otrzymanej z populacji rodziców.

W klasycznym algorytmie genetycznym stosuje się dwa podstawowe operatory genetyczne: operator krzyżowania i operator mutacji. W klasycznym algorytmie genetycznym krzyżowanie występuje prawie zawsze (z prawdopodo-bieństwem pk ,które zwykle zawiera się w przedziale [0.5,1]), podczas, gdy mutacja zachodzi dość rzadko (z prawdo-podobieństwem pm zwykle nie większym niż 0.1 ). Wynika to także z analogii do świata organizmów żywych, gdzie mutacje zachodzą niezwykle rzadko.

W algorytmach genetycznych mutacje stosuje się zarówno na populacji rodziców przed operacją krzyżowania, jak i na populacji potomków, utworzonych w wyniku krzyżowania.

Przykład operacji krzyżowania i mutacji

Weźmy dwa chromosomy ch1 i ch2 majce po 10 genów. Stanowić one będą parę rodzicielską. W celu przeprowadzenia krzyżowania wylosujmy liczbę z przedziału [1,9]. Wylosowano 5.

para rodziców krzyżowanie para potomków

ch1=[10010|01100] Ch1=[10010|11110]

0x08 graphic
ch2=[10011|11110] Ch2=[10011|01100]

Omówmy teraz przykład rozwiązania problemu mutacji.

W tym celu losujmy liczbę rzeczywistą z przedziału [0,1] dla każdego z dziesięciu genów. Wylosowano:

0.23 0.76 0.54 0.10 0.28 0.68 0.01 0.30 0.95 0.12

Przyjmijmy, że pm=0.02. Do mutacji zostaną wybrane tylko te geny, dla których wylosowana liczba jest <= pm - u nas gen siódmy.

mutacja

0x08 graphic
ch1=[1001001100] Ch1=[1001000100]

Przykład wykorzystania algorytmu genetycznego

Zadanie 1:

Znaleźć maksimum funkcji y=2*x+1 w przedziale liczb całkowitych [0,31]. Zbiorem potencjalnych rozwiązań (czyli przestrzenią poszukiwań) jest więc zbiór {0,1,2,…,32}. Każdy z elementów tego zbioru jest fenotypem. Fenotypy zakodujemy przy pomocy chromosomów 5-bitowych (bo wartości 32) odpowiada chromosom [11111].

  1. Losowanie populacji początkowej

Ustalono liczność populacji początkowej na N=8.

Chromosom fenotyp funkcja dostosowania
F(ch
i)=2* chi+1

ch1=[00110] ch1*= 6 13

ch2=[00101] ch2*= 5 11

ch3=[01101] ch3*=13 27

ch4=[10101] ch4*=21 43

ch5=[11010] ch5*=26 53

ch6=[10010] ch6*=18 37

ch7=[01000] ch7*= 8 17

ch8=[00101] ch8*= 5 11

  1. Ocena funkcji dostosowania

Wartości funkcji dostosowania obliczono wg. wzoru
F(chi)=2* chi+1

3. Selekcja chromosomów

Selekcji dokonano metoda koła ruletki.

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic

Pola wycinków koła ruletki obliczono wg wzoru

0x01 graphic

Selekcja chromosomów za pomocą koła ruletki sprowadza się do losowego wyboru poprzez zakręcenie kołem ruletki ( w tym przypadku ośmiu) liczb z przedziału [0,100]. Suma wszystkich wartości ν( chi) jest równa 100%.

Wylosowano następujące liczby:

79 44 9 74 45 86 48 23

co odpowiada następującym wylosowanym chromosomom

ch6 ch4 ch2 ch6 ch5 ch6 ch5 ch3

Dla przykładu piąty z wylosowanych chromosomów jest chromosomem ch5 ponieważ jako piątą wylosowano liczbę 45 a jest to liczba większa od sumy granicznej 44,34.

Selekcja metodą koła ruletki pozwoliła wzmocnić „garnitur chromosomowy”. Dla przykładu: najlepiej dostosowany chromosom ch6 wylosowano dwukrotnie, słabo dostosowane ch1 , ch7 i ch8 ani razu. Wylosowano też chromosom ch2 o najniższym dostosowaniu.

Zadanie 2:

Zadaniem będzie rozwiązanie tzw. problemu plecakowego.

Dane jest n przedmiotów, każdy o wadze wi i ważności pi. Zadanie polega na takim załadowaniu plecaka, aby znalazły się w nim przedmioty, z których mielibyśmy jak największą korzyść. Założymy, że największej korzyści odpowiada maksymalna możliwa wartość sumy ważności przedmiotów, które da się zabrać przy ograniczeniu wagowym W.

0x01 graphic

Tutaj n jest ilością zabranych przedmiotów, xi przyjmuje dla danego przedmiotu wartość 0, lub 1, ( zależności od tego, czy i-ty przedmiot występuje, czy nie występuje w plecaku), W jest dopuszczalną wagą plecaka.

Funkcja dostosowania może mieć postać

0x01 graphic

gdzie chj jest zakodowanym binarnie chromosomem o długości n genów.

Problem plecakowy jest problemem o wykładniczej złożoności obliczeniowej. Zastosowanie algorytmu genetycznego pozwala rozwiązać go w czasie wielomianowym.

Przeprowadzono eksperyment, w którym:

Zastosowano klasyczny algorytm genetyczny z selekcją proporcjonalną (koło ruletki) z prawdopodobieństwem krzyżowania pk=0,7 i prawdopodobieństwem mutacji pm=0,01

Liczba osobników w populacji wynosiła 10.

0x08 graphic
F(chj)

0x08 graphic
0x08 graphic
6

0x08 graphic
0x08 graphic
0x08 graphic
5

0x08 graphic
4

3

2

1

0

1 11 21 31 41 51 61 71 81 91

generacje

Rys. Wykres maksymalnej w populacji funkcji dostosowania (najlepszego chromosomu) w 100 kolejnych generacjach

Dopiero w 43 populacji algorytm znalazł najlepsze rozwiązanie z wartością funkcji dostosowania równą 6.

Algorytm został uruchomiony 100 razy. Znaleziono:

0x08 graphic
100 rozwiązań

Przykładowe rozwiązanie z 6 przedmiotami: 1,2,4,5,7,8.

W kolejnym eksperymencie założono: n=50, W=318. Ze względu na skomplikowanie zadania ustalono wielkość populacji na 100 osobników. Pozostałe parametry - bez zmian

Eksperyment przeprowadzono dla 200 generacji.

0x08 graphic
0x08 graphic
F(chj)

30

25

20

15

10

5

0

1 21 41 61 81 101 121 141 161 181

generacje

Rys. Wykres maksymalnej w populacji funkcji dostosowania (najlepszego chromosomu) w 200 kolejnych generacjach

Jak wynika z wykresu, już po dwudziestu kilku generacjach, w populacji występowały chromosomy (rozwiązania) o wysokiej, zbliżonej do maksymalnej, wartości funkcji dostosowania. W dalszych generacjach zdarzały się jeszcze lepsze rozwiązania, ale bywało, że w kolejnych generacjach znikały. Na przykład, znaleziono tylko 2 rozwiązania z 33 przedmiotami, ale aż 38 rozwiązań z 31 przedmiotami.

Strategie ewolucyjne

Strategie ewolucyjne są algorytmami ewolucyjnymi, w których w odróżnieniu od algorytmów genetycznych:

Istnieje wiele różnych strategii ewolucyjnych. Pozwalają one przybliżyć sztucznie symulowany proces ewolucji do procesu naturalnego.

Eksploracja i eksploatacja

Każdy algorytm ewolucyjny ma tendencję podążania w kierunku lepszych rozwiązań. Proces ten nazywamy naciskiem selektywnym. Z dużym naciskiem selektywnym mamy do czynienia, gdy większa jest średnia wartość liczby kopii lepszych osobników, niż średnia liczba kopii gorszych osobników. Nacisk ten jest ściśle powiązany z zależnością między eksploracją i eksploatacją.

Eksploracja pozwala przeszukiwać całą przestrzeń rozwiązań w celu znalezienia rozwiązania globalnego. Eksplorację osiągamy poprzez zmniejszenie nacisku selektywnego. Wybierane są osobniki nie najlepiej przystosowane, ale mogące w przyszłości zbliżyć nas do rozwiązania globalnego.

Eksploatacja natomiast jest poruszaniem się po fragmencie przestrzeni rozwiązań, dobrze jeśli w pobliżu rozwiązania globalnego. Eksploatacje uzyskujemy poprzez zwiększenie nacisku selektywnego, co powoduje że osobniki przechodzące do następnej populacji szybko uzyskują wartości coraz bliższe oczekiwanym, i tu należy zadbać aby odbywało się to w pobliżu rozwiązania globalnego.

Algorytm ewolucyjny może balansować między tymi dwoma mechanizmami, co można osiągnąć poprzez zmianę jego parametrów. Na przykład zwiększenie prawdopodobieństwa krzyżowania i mutacji powoduje większą różnorodność osobników, co w konsekwencji prowadzi do poszerzenia obszaru poszukiwań i zapobiega przedwczesnej zbieżności (na przykład do minimum lokalnego, które nie jest globalnym). Natomiast zmniejszenie tych prawdopodobieństw prowadzi do tworzenia osobników podobnych do siebie i zawęża obszar poszukiwań.

Porównanie metod selekcji

Jak to już zostało powiedziane, metody selekcji polegają na wyborze najlepiej dostosowanych osobników (populacji rodzicielskiej) w celu dalszego przetwarzania za pomocą operatorów genetycznych. W klasycznym algorytmie genetycznym używa się proporcjonalnej metody selekcji, zwanej kołem ruletki. Jej niewątpliwe słabości to:

W celu eliminacji wyżej wymienionych wad metody koła ruletki, stosuje się różne metody skalowania funkcji dostosowania (będą omówione w dalszej części wykładu).

Omówione teraz zostaną inne metody selekcji.

Selekcja rankingowa

0x08 graphic

liczba

0x08 graphic
kopii

0x08 graphic

ranga

0x08 graphic
0x08 graphic
W selekcji rankingowej liczba kopii osobników wybrana do puli rodzicielskiej jest tym większa, im wyższa jest ich ranga (wartość funkcji dostosowania). Metoda może być używana zarówno w zadaniach maksymalizacji, jak i minimalizacji funkcji dostosowania. Nie ma też potrzeby odrębnego skalowania tej funkcji, gdyż skalowanie można osiągnąć poprzez odpowiednie nachylenie funkcji określającej zależność liczby kopii od rangi osobnika (jak na rysunku wyżej).

Selekcja turniejowa

0x08 graphic

l

0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic

0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic

W selekcji turniejowej dzieli się całą pulę osobników na 2-3 elementowe podgrupy, a następnie biorąc po dwie podgrupy, wydziela się w każdej z podgrup po jednym „najlepszym” osobniku. Wchodzą one jako para do puli rodzicielskiej (patrz rysunek wyżej).

Metoda turniejowa nadaje się zarówno do maksymalizacji, jak i minimalizacji funkcji, ponadto - można łatwo zmieniać rozmiar podgrup, na jakie dzielona jest populacja. Badania wykazują, że działa ona lepiej od metody ruletki.

Selekcja progowa

Selekcja progowa jest szczególnym przypadkiem selekcji rankingowej. Tutaj zależność liczy kopii osobników od rangi ma postać progu, którego przekroczenie daje pewność wejścia do puli rodzicielskiej. Umożliwia to sterowanie naciskiem selektywnym poprzez odpowiedni dobór wartości progu.

Selekcja stłoczenia

Jest to ciekawa metoda selekcji. Przeprowadza się ją w ten sposób, że tworzy się pewną pulę nowych osobników, a następnie zastępuje się nimi, najbardziej podobne do nich osobniki populacji poprzedniej niezależnie od wartości ich funkcji dostosowania.

Postępuje się w ten sposób, aby zachować jak największą różnorodność populacji. Jest to metoda o słabym nacisku selektywnym. Wprowadzony parametr CF (ang. crowding factor) określa liczbę rodziców podobnych do nowo powstałego osobnika, spośród których wyznaczony zostanie osobnik do usunięcia. Podobieństwo między nowymi i starymi osobnikami wyznacza tzw. miara Hamminga.

Skalowanie funkcji dostosowania

Proporcjonalna metoda koła ruletki umożliwia wybór osobników rodzicielskich proporcjonalnie do wartości ich funkcji dostosowania. Z metody koła ruletki można korzystać, gdy wartości funkcji dostosowania są dodatnie.

Drugą słabą stroną tej metody jest to, że osobniki o bardzo małej wartości funkcji dostosowania są dość wcześnie eliminowane z populacji, co doprowadza do ogólnie przedwczesnej zbieżności algorytmu genetycznego.

Kolejną słabą stroną jest fakt, że nawet po wielu generacjach, populacja będzie zawierała kopie najlepszych chromosomów, ale zbudowanych w oparciu o określoną populację początkową. Jest mało prawdopodobne, aby najlepszy chromosom reprezentował optymalne rozwiązanie globalne, skoro populacja początkowa była małą próbką losową z całej przestrzeni poszukiwań. Skuteczną ochroną przed dominacją nie całkiem optymalnych chromosomów okazały się metody skalowania funkcji przystosowania. Jest ich kilka.

Skalowanie liniowe

0x08 graphic

wartości F'

0x08 graphic
funkcji F

0x08 graphic
dostosow.

0x08 graphic

0x08 graphic

_ _ przestrzeń poszukiwań

F= F'

Rys. Skalowanie liniowe dla przykładowej liniowej funkcji
dostosowania F

Skalowanie liniowe odbywa się wg. wzoru F' = a * F + b.

gdzie:

F jest wartością funkcji przystosowania,

F' jest jej przeskalowaną wartością,

a i b są stałymi dobranymi tak, aby średnia wartość funkcji przystosowania była równa średniej wartości przed skalowaniem, natomiast wartość maksymalna po skalowaniu była kilkakrotnie większa od wartości średniej i aby funkcja F' nie przyjmowała wartości ujemnych. Zwykle przyjmuje się wartość a między 1,2 a 2,0.

Skalowanie liniowe pozwala proporcjonalnie zwiększać, lub zmniejszać nacisk selektywny.

Obcinanie typu sigma

Skalowanie odbywa się tu wg. wzoru F' = (FS - c*σ)

gdzie:

FS jest wartością średnią funkcji przystosowania w populacji,

F' jest jej przeskalowaną wartością,

c jest mała liczbą naturalną (zwykle od 1 do 5),

σ jest odchyleniem standardowym średniej w populacji.

Wartości ujemne funkcji F' są obcinane do zera.

W tej metodzie stopień zwiększenia nacisku zależy od kształtu funkcji obrazującej rozkład normalny wartości funkcji dostosowania. Im odchylenie wartości średniej funkcji dostosowania σ większe, tym stopień zmniejszenia siły nacisku mniejszy.

Skalowanie potęgą

Skalowanie odbywa się wg. wzoru F' = F k.

Wybór wartości stałej k zależy zwykle od rodzaju rozwiązywanego problemu. Można przyjąć na przykład k=1.005.

0x08 graphic

0x08 graphic
wartości F'

0x08 graphic
funkcji F

dostosow.

0x08 graphic

przestrzeń poszukiwań

Rys. Skalowanie potęgą dla przykładowej liniowej funkcji
dostosowania F

Z innych, spotykanych w literaturze metod skalowania, można wymienić: skalowanie logarytmiczne, skalowanie „metodą okna”, metodę Boltzmana, oraz rankingowanie liniowe i rankingowanie wykładnicze.

Specjalne procedury reprodukcji

Oprócz wyżej wymienionych metod selekcji stosuje się jeszcze specjalne procedury reprodukcji, z których dwie zostaną omówione.

Strategia elitarna

Strategia elitarna polega na ochronie najlepszych chromosomów w kolejnych generacjach. W klasycznym algorytmie genetycznym nie zawsze najlepszy chromosom przechodzi do następnej generacji. Strategia elitarna zabezpiecza przed utratą takiego osobnika, bowiem zawsze przechodzi on do następnej generacji.

Algorytm genetyczny z częściową wymianą populacji

Strategia ta charakteryzuje się tym, że część populacji przechodzi do następnej generacji bez jakichkolwiek zmian (nie podlegając mutacji i krzyżowaniom).

Przykład:

Metodę koła ruletki oraz strategię elitarną zastosowano do rozwiązania omawianego wcześniej problemu plecakowego. Strategia elitarna polegała na automatycznym przechodzeniu do następnej populacji 2 osobników najlepiej przystosowa-nych. Pozostałe parametry pozostawiono bez zmian.

0x08 graphic
F(chj)

0x08 graphic
30

25

20

15

10

5

0

1 21 41 61 81 101 121 141 161 181

generacje

Rys. Wykres maksymalnej w populacji funkcji dostosowania (najlepszego chromosomu) w 200 kolejnych generacjach z zastosowaniem strategii elitarnej

Łatwo zauważyć, że zmiany wartości funkcji przystosowania najlepszego osobnika nie zachodzą już tak nieregularnie, bowiem w kolejnych generacjach najlepsze rozwiązania nie są już tracone.

Najciekawszym jednak jest fakt, że znaleziono nowe rozwiązania, które w poprzednich (bez strategii elitarnej) 100 kolejnych uruchomieniach algorytmu genetycznego nie zostały znalezione.

Teraz znaleziono:

0x08 graphic
100 rozwiązań

Poprzednio w ogóle nie znaleziono rozwiązań z 34 i 35 przedmiotami. Dominowały gorsze rozwiązania z 30 i 31 przedmiotami.

Metody hybrydowe

Metody hybrydowe są to metody, które łączą w sobie (najczęściej dwie) różne metody sztucznej inteligencji.

Algorytmy ewolucyjne w projektowaniu sieci neuronowych

Algorytmy ewolucyjne znalazły zastosowanie w celu wspomagania niżej wymienionych problemów z zakresu sieci neuronowych:

Architektura sieci (liczba warstw, liczba neuronów w warstwie, sposób połączenia neuronów) jest zwykle tworzona metodą prób i błędów.

Optymalne projektowanie architektury sieci neuronowych z wykorzystaniem algorytmów ewolucyjnych traktować można jako poszukiwanie takiej struktury sieci, która działa najlepiej dla określonego zadania, rozwiązywanego przez sieć. Oznacza to przeszukiwanie przestrzeni architektur i wybór najlepszej przestrzeni.

Etapy przykładowego projektowania architektury sieci neuronowej z wykorzystaniem algorytmów genetycznych:

  1. 0x08 graphic
    0x08 graphic
    0x08 graphic
    0x08 graphic
    0x08 graphic
    0x08 graphic
    0x08 graphic
    0x08 graphic
    0x08 graphic
    0x08 graphic
    0x08 graphic
    Wybór sposobu reprezentowania architektury sieci w chromosomie. Jedną z wielu, najprostszą, metodą jest tu kodowanie bazujące na połączeniach.


    [0110110011]



    Rys. Przykład reprezentacji chromosomowej dla sieci z
    połączeniami „do przodu”

  2. Dekodowanie każdego osobnika bieżącej generacji (chromosomu) do architektury wynikającej z przyjętego schematu kodowania.

  3. Uczenie każdej sieci neuronowej.

  4. Ocena dostosowania każdego osobnika (zakodowanej architektury) na podstawie rezultatów uczenia, np. najmniejszego średniego kwadratowego błędu uczenia.

  5. Reprodukcja osobników z prawdopodobieństwem odpowiednim do ich dostosowania.

  6. Zastosowanie operatorów genetycznych i otrzymanie nowej generacji.

Algorytmy ewolucyjne w uczeniu wag sieci neuronowych

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

w1 w5

x1 w2 w6 w9

w3 w7 w10

0x08 graphic
x2

0x08 graphic
w4 w8

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic

Rys. Odwzorowanie wag sieci neuronowej w chromosomie
dla przykładowej sieci

0x08 graphic
Uczenie sieci neuronowej polega na wyznaczeniu wartości wag sieci, której architektura została wcześniej ustalona. Wagi mogą być kodowane w chromosomie za pomocą wektora liczb rzeczywistych. Każdy osobnik populacji jest określony przez całkowity wektor wag. Kolejność umieszczenia wag w chromosomie jest dowolna, ale nie może być zmieniana w trakcie uczenia.

Ocena przystosowania osobników dokonywana jest na podstawie funkcji przystosowania zdefiniowanej jako suma kwadratów błędów, będących różnicami między sygnałem wzorcowym a sygnałem wyjściowym sieci dla różnych danych wejściowych.

Po wybraniu schematu chromosomowej reprezentacji, np. tak jak pokazano na rys. powyżej, algorytm działa na populacji osobników (chromosomów reprezentujących sieci neuronowe o tej samej architekturze i metodzie uczenia, ale różnych wartościach początkowych wag) wg. typowego cyklu ewolucji, przedstawionego powyżej.

Algorytmy ewolucyjne do uczenia wag i określania architektury sieci neuronowych jednocześnie

Opisany proces ewolucji architektur ma wiele wad. Uczenie dla dużej populacji chromosomów wymaga bardzo dużo czasu, a jego wynik zależy od początkowego zainicjowania wag połączeń. Podobnie dobieranie wag za pomocą algorytmów genetycznych może odbywać się tylko dla jednej, określonej architektury. Wady te można wyeliminować łącząc metody kodowania wag i struktur (opartych na kodowaniu połączeń) jednocześnie.

Bity wystąpienia połączenia

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

1 111 0 110 1 010 1 000 0 100

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

Bity zakodowanych wag połączeń

Rys. Przykład jednoczesnego kodowania struktury i wag sieci
neuronowej

Rysunek przedstawia najprostszy sposób. Połączenie neuronów w sieci jest określone za pomocą jednego bitu. Dodatkowo wprowadzono zakodowane binarnie wartości wag połączeń. Jeżeli jednak gen odpowiadający za połączenie jest nieaktywny (przyjmuje wartość zero), zakodowane wartości wag tego połączenia nie są brane pod uwagę przy dekodowaniu struktury.

Inny sposób kodowania informacji o wagach i połączeniach sieci jednocześnie wykorzystuje fakt, że informacja o połączeniu zawarta jest w samej wartości wagi - jeśli waga wynosi zero, to połączenie nie jest brane pod uwagę przy dekodowaniu struktury chromosomu. Metoda ta wymaga dodatkowego operatora genetycznego, który z pewnym prawdopodobieństwem usuwa, bądź tworzy nowe połączenia, zerując, bądź losując wartości wag połączeń.

Adaptacyjne rozmyte algorytmy ewolucyjne

Jednym z najpoważniejszych problemów w trakcie pracy algorytmu jest dobór właściwych proporcji między eksploatacją, a eksploracją. Jak to już zostało powiedziane, równowagę osiągać można poprzez zwiększanie, lub zmniejszanie nacisku selektywnego.

Spośród metod zmiany nacisku selektywnego wymienić należy:

Wszystkie te metody zostały już omówione w rozdziałach poprzednich. Potraktujmy je jako parametry sterujące pracą algorytmu genetycznego.

Adaptacyjne algorytmy ewolucyjne same mogą nastawiać te parametry w celu osiągnięcia jak najlepszych rezultatów. Do modyfikacji parametrów używa się rozmytych systemów wnioskujących.

Podczas pracy algorytmu ewolucyjnego (patrz rys. poniżej) generowane są różne statystyki. Na podstawie ich wartości rozmyty system wnioskujący analizuje pracę algorytmu i dynamicznie dobiera wartości wybranych parametrów. Rozmyty system wnioskujący ma, odpowiednio przygotowaną przez eksperta, bazę wiedzy w formie reguł lingwistycznych. Na ich podstawie dobiera parametry algorytmu. Proces ten odbywa się w sposób ciągły sterując pracą algorytmu ewolucyjnego.

0x08 graphic

0x08 graphic

0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic

0x08 graphic
0x08 graphic

Rys. Schemat ogólny adaptacyjnego algorytmu ewolucyjnego

0x08 graphic
0x08 graphic
Statystyki, na podstawie których sterownik rozmyty podejmuje decyzje o zmianie parametrów, można podzielić na kilka grup:

Można stosować inne jeszcze statystyki.

Przykład:

Niech danymi wejściowymi do sterownika rozmytego będą cztery parametry:

- statystyka
α = średnie przystosowanie / najlepsze przystosowanie

- statystyka
β = najgorsze przystosowanie / średnie przystosowanie

Załóżmy, że wyżej wymienione cztery parametry opisane zostały za pomocą zbiorów rozmytych: duże, średnie, małe.

0x08 graphic
Przykładowy fragment bazy reguł, sterujących doborem parametrów algorytmu, może wyglądać jak poniżej.

W tym przykładzie parametrem sterującym jest wielkość populacji, za pomocą której możemy bezpośrednio wpływać na stopień różnorodności osobników, czyli zwiększać, lub zmniejszać nacisk selektywny.

Algorytmy ewolucyjne w projektowaniu systemów rozmytych

Projektowanie systemów rozmytych, podobnie jak w innych metodach sztucznej inteligencji, wymaga czasu, doświadczenia i wiedzy eksperta. Proces ten można znacznie wspomóc dzięki algorytmom ewolucyjnym, których elastyczność i niezależność, można wykorzystać w rozwiązywaniu takich problemów, jak:

Interesujące jest zwłaszcza drugie rozwiązanie. Stosuje się tu trzy podejścia:

Dopasowanie funkcji przynależności za pomocą algorytmu genetycznego

Mając wybraną bazę reguł decyzyjnych systemu rozmytego można jeszcze zwiększyć ich skuteczność poprzez odpowiednie dopasowanie funkcji przynależności użytych zbiorów rozmytych. Algorytm ewolucyjny może modyfikować funkcje przynależności poprzez zmianę położenia punktów charakterystycznych tych funkcji. Są to najczęściej współrzędne wierzchołków figur, które te funkcje opisują. Informacje o wierzchołkach kodowane są w chromosomach.

Podejście to pozwala modyfikować często używane kształty funkcji przynależności: trójkątne, trapezowe, funkcje gaussowską, sigmoidalną.

W zależności od zastosowanego algorytmu ewolucyjnego, punkty charakterystyczne koduje się w chromosomie w postaci binarnej, lub za pomocą liczb rzeczywistych.

1

START

INICJACJA - wybór początkowej

populacji chromosomów

OCENA przystosowania

chromosomów w populacji

SELEKCJA chromosomów

Zastosowanie operatorów

genetycznych

Utworzenie nowej populacji

STOP

6,13%

5,19%

25%

12,74%

20,28%

17,45%

8,02%

5,19%

suma=44,34%

K osobników

populacji

2-3 osobniki

2-3 osobniki

1 „najlepszy”

osobnik

1 „najlepszy”

osobnik

pula

rodzicielska

1

2

3

4

5

5

4

1

2

3

w1

w2

w3

w4

w10

w9

w8

w7

w6

w5

Optymalizowany problem

Algorytm ewolucyjny

Statystyki działania

Parametry algorytmu

Rozmyty system wnioskujący

JEŻELI α jest duże TO zwiększ populację

JEŻELI β jest małe TO zmniejsz populację

JEŻELI pk jest małe I populacja jest mała TO zwiększ
populację



Wyszukiwarka

Podobne podstrony:
Sztuczna inteligencja wykład.cz6.2
Sztuczna inteligencja wyklad 2, WI, Semestr III N2, Metody sztucznej inteligencji
Sztuczna Inteligencja - wyklady streszczenie, Sztuczna Inteligencja cz.2
Sztuczna Inteligencja - wyklady streszczenie, AL - najwazniejsze informacje
Sztuczna inteligencja wyklad 1, WI, Semestr III N2, Metody sztucznej inteligencji
streszczenie, Robotyka, Metody sztucznej inteligencji, Wykład
wyklad 7-8, UWM, 7 Semestr, Sztuczna inteligencja
Elementy Sztucznej Inteligencji, UŁ WMiI, Wykłady EL SZT INT, nr2 (1-03-2011)
wyklad 1-2, UWM, 7 Semestr, Sztuczna inteligencja
Elementy Sztucznej Inteligencji
MSI-program-stacjonarne-15h-2011, logistyka, semestr IV, sieci neuronowe w log (metody sztucznej int
Ściąga ze sztucznej inteligencji(1), uczenie maszynowe, AI
wprowadzenie do sztucznej inteligencji-wyk łady (10 str), Administracja, Administracja, Administracj
system ekspercki i sztuczna inteligencja word 07
NARZĘDZIA SZTUCZNEJ INTELIGENCJI
Indukcja drzew decyzyjnych, Robotyka, Metody sztucznej inteligencji
MSI oprac, Mechatronika, Metody Sztucznej Inteligencji, msi materiały
Roboty będą posiadały własną sieć internetową RoboEarth, SZTUCZNA INTELIGENCJA, ROBOTYKA, ROBOTYKA
msi2, Automatyka i Robotyka, Semestr 4, Metody sztucznej inteligencji

więcej podobnych podstron