Sztuczna inteligencja wykład.cz4.pdf

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:

 Wyjście do przeszukiwania nie z pojedynczego punktu

przestrzeni poszukiwań, lecz z pewnej ich populacji,

 Przetwarzanie nie bezpośrednio parametrów zadania,

lecz pewnej zakodowanej postaci tych parametrów,

 Losowy wybór jest tu tylko pewnym narzędziem, a nie

zasadniczą ideą przeszukiwania, jak w klasycznych

metodach losowych.

Podstawowe pojęcia:

 Populacja jest określonym zbiorem osobników,

 Osobnikiem jest zakodowany w postaci chromosomu

zbiór parametrów zadania,

 Chromosom to uporządkowany ciąg genów,

 Gen jest cechą, pojedynczym elementem genotypu,

 Genotyp to zespół chromosomów danego osobnika

(chociaż często jest to po prostu pojedynczy

chromosom),

 Fenotyp to zdekodowana struktura, czyli po prostu

zbiór parametrów zadania.

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

START

INICJACJA – wybór początkowej

populacji chromosomów

OCENA przystosowania

chromosomów w populacji

Nie Tak

warunek

Wyprowadzenie „najlepszego

chromosomu

Zastosowanie operatorów

genetycznych

STOP

Utworzenie nowej populacji

SELEKCJA chromosomów

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:

- osiągnięcie żądanej wartości optymalnej,

- osiągnięcie wartości optymalnej z określoną

dokładnością,

- przekroczenie ustalonego czasu działania

algorytmu,

- wykonanie obliczeń dla żądanej liczby generacji.

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 p k , które zwykle zawiera się w przedziale [ 0.5,1 ]),

podczas, gdy mutacja zachodzi dość rzadko (z prawdo-

podobieństwem p m 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 ch 1 i ch 2 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

ch 1 =[ 10010 | 01100 ] Ch 1 =[ 10010 | 11110]

ch 2 =[10011 | 11110] Ch 2 =[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 p m =0.02 . Do mutacji zostaną wybrane tylko

te geny, dla których wylosowana liczba jest <= p m – u nas gen

siódmy.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: