Algorytmy genetyczne - ewolucjonizm

Nasza ocena:

3
Pobrań: 245
Wyświetleń: 3108
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Algorytmy genetyczne - ewolucjonizm - strona 1 Algorytmy genetyczne - ewolucjonizm - strona 2 Algorytmy genetyczne - ewolucjonizm - strona 3

Fragment notatki:


 (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)

Zaloguj się, aby dodać komentarz