To tylko jedna z 15 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
(ur. 02 lutego 1929), amerykański naukowiec, profesor psychologii i profesor Elektrotechniki i Informatyki na Uniwersytecie Michigan. Jest on znany jako ojciec algorytmów genetycznych . Twierdzenie o schematach (twierdzenie Hollanda) : Schematy małego rzędu (liczba ustalonych pozycji w schemacie) o małej rozpiętości (odległość miedzy skrajnymi ustalonymi pozycjami) i o przystosowaniu powyżej średniej otrzymują rosnącą wykładniczo liczbę swoich reprezentantów w kolejnych generacjach algorytmu genetycznego. Populacja zespół osobników zamieszkujących wspólne środowisko i konkurujących o jego zasoby. Fenotyp w przypadku algorytmów ewolucyjnych są to te parametry rozwiązania, które podlegają ocenie. Genotyp “plan konstrukcyjny”, kompletny i jednoznaczny opis osobnika zawarty w jego genach. W przypadku algorytmów ewolucyjnych cechy rozwiązania kodowane są w określony sposób, np. za pomocą ciągów binarnych ustalonej długości (odpowiednikiem genotypu osobnika jest w tym przypadku ciąg bitów). Osobnik podstawowa jednostka podlegająca ewolucji. Zakładamy zwykle, że ów osobnik przebywa w pewnym środowisku, do którego może być lepiej lub gorzej przystosowany. “Celem” ewolucji jest stworzenie osobnika możliwie dobrze przystosowanego do danego środowiska. Chromosom miejsce przechowywania genotypu osobnika. Algorytm genetyczny - rodzaj algorytmu przeszukującego przestrzeń alternatywnych rozwiązań problemu w celu wyszukania rozwiązań najlepszych. Algorytm ewolucyjny - algorytm wzorowany na biologicznej ewolucji, stosowany do zadań optymalizacyjnych i modelowania. W tych pierwszych istotniejszą rolę odgrywa krzyżowanie osobników, natomiast w drugich zmienność jest realizowana zwykle poprzez mutacje. Algorytmy ewolucyjne używają bardziej bezpośrednich reprezentacji modelu i operatory mutacji często działają na fenotypach. W algorytmach genetycznych istotna jest binaryzacja genotypu (operatory krzyżowania i mutacji działają na genotypach). Losowana jest pewna populacja początkowa. Populacja poddawana jest ocenie ( selekcja ). Najlepiej przystosowane osobniki biorą udział w procesie reprodukcji. Genotypy wybranych osobników poddawane są operatorom ewolucyjnym: są ze sobą kojarzone poprzez złączanie genotypów rodziców ( krzyżowanie ), przeprowadzana jest mutacja, czyli wprowadzenie drobnych losowych zmian. Rodzi się drugie (kolejne) pokolenie. Aby utrzymać stałą
(…)
… zastosowaniu otworów o dziwnych,
kwiecistych kształtach (zamiast wcześniej
stosowanych sześciokątnych); turbiny, śmigła,
skrzydła, obiektywy, implanty ślimakowe,
wzmacniacze, filtry, anteny...
…
….
Na rysunku oś pionowa odpowiada kosztowi rozwiązań (im niższa wartość,
tym lepiej).
W kolejnych krokach słabsze rozwiązania (o wyższym koszcie) giną, a lepsze
są rozmnażane,
mutowane i krzyżowane. Już po pierwszym i drugim pokoleniu widać,
jak populacja skupia się w obszarach dobrych rozwiązań
Funkcja przystosowania (fitness)
funkcja
pozwalająca dla danego osobnika określić jego
jakość. Zakładamy…
… funkcja jest zaszumiona,
zmienia się w czasie, ma wiele ekstremów lokalnych.
Metoda jest stosunkowo szybka: znalezienie rozwiązania
często jest możliwe po przejrzeniu zaskakująco
niewielkiej części przestrzeni stanów.
Ponieważ algorytm genetyczny jest algorytmem
losowym, możemy powtarzać obliczenia wielokrotnie w
nadziei otrzymania lepszych wyników.
Metoda jest uniwersalna, więc nie tak skuteczna…
... zobacz całą notatkę
Komentarze użytkowników (0)