Podstawy algorytmów genetycznych.

W pewnym sencie algorytmy genetyczne próbują naśladować to co w przyrodzie ożywionej trwało przez miliony, dziesiątki czy setki milionów lat.W komputerze podobne procesy mozna przeprowadzić w ciągu godzin czy dni. Natura w toku ewolucji modyfikuje skomplikowane organizmy czy gatunki, w komputerze zaś manipulujemy ich uproszczonymi modelami. Jest oczywistością że w naturze nowy organizm musi dojrzeć do tzw. wieku rozrodczego, aby Natura miała cokolwiek do powiedzenia.W warunkach naturalnych często muszą minąć długie lata , w których dany organizm wystawiony jest na próbe.W komputerze problem czekania na osiągniecie dorosłości nie ma prostego odpowiednika.

-------------------------------------------------------------

Działanie algorytmu genetycznego prześledzimy na następującym przykładzie opisanym w książce Granice złożoności.

Tworzymy genotyp składający się z zer i jedynek.
Każde takie zero lub jedynka odpowiada pewnej zakodowanej właściwości modelowanego przez nas organizmu(obiektu). Np. kolor oczu, wielkość itp. Ja przy pisaniu tego rodzaju programów tworzę je po prostu w tablicy. Cały genotyp obiektu to jest jedna tablica np. Tab1(1 to 100). Następny genotyp jest opisany w tablicy Tab2(1 to 100) i tak dalej. Daje do doskonałe możliwości przetwarzania tych genotypów w pętli.

Jak kodować genotyp ? Ustalamy wszystkie cechy obiektu jaki chcemy poszukiwać za pomocą programowania genetycznego. Np. szukamy zwierzę(może być hipotetyczne) które jest najbardziej niebezpieczne. Dla takich cech jak wielkość,masa, czy jest drapieżne,zwinność,kolor,węch,wzrok,czy jest jadowite itp. wpisujemy w tablicę 0 lub 1. Tworzymy kilkanaście (np.15) takich genotypów. Odpowiadają one właściwością żyjącym obecnie zwierzętom takim jak tygrys, lew, niedzwiedz,czarna mamba, łasica,wilk itp.
Uruchamiamy nasz program genetyczny.

-------------------------------------------------------------

Selekcja( obliczanie funkcj celu)
Z utworzonych początkowo genotypów wybieramy 5 , czyli mamy selekcje.
Najlepszy przechodzi do następnego pokolenia bez zmian.
Mutacja
Dowolny gen w dowolnym chromosomie podlega losowej zmianie z 0 na 1 lub odwrotnie.
Krzyżowanie
Następnie tniemy każdy z 5 chromosonów i krzyżujemy je.
Np. 1/2,1/3,1/4,1/5 i 2/3,2/4,2/5 i 3/4,3/5 i 4/5 + jeden najlepszy = 11 Otrzymujemy 11 nowych chromosonów po krzyżowaniu. Teraz musimy je poddać selekcji i wybrac 5 najlepszych , powracamy więc do początku algorytmu.

-------------------------------------------------------------

Opisywany tu algorytm ma ten defekt że za każdym razem musimy sami dokonać selekcji najlepszych genotypów, ewentualnie przyjąć że chromoson który będzie miał najwiecej jedynek jest najlepszy. Po kilku czy kilkunastu pokoleniach otrzymamy chromoson który będzie opisywał jakieś hipotetyczne zwierzę z innej planety które będzie wielkości lwa, zwinności łasicy, jadowite jak czarna namamba itd. Oczywiście to tylko nieudolny przykład.

-------------------------------------------------------------

Efektywność programowania genetycznego można zademonstrować na przykładzie poszukiwania najlepszego projektu turbiny silnika odrzutowego. W tym problemie występuje około 100 zniennych. Są możliwe miliardy potencjalnych rozwiązań. Ocena jednego projektu trwa ok. 30 s. Tradycyjne szukanie najlepszego rozwiązania mogłoby zająć wieki. Doświadczony inżynier potrzebuje roku , aby opracować projekt turbiny , natomiast algorytm genetyczny w ciągu kilku dni " stworzył" projekt trzy razy lepszy.

-------------------------------------------------------------

Innym przykładem jest opracowywanie najlepszego skrzydła do jednego z samolotów produkowanych w Europie. W grę wchodziły miliony kombinacji. Zrobiono więc chromosony kilkudziesięciu skrzydeł samolotowych, włączono program genetyczny, zamknięto firme i wszyscy poszli do domu. Gdzieś po kilku dniach otrzymano skrzydło którego parametry jak najbardziej zadowalały inżynierów.

-------------------------------------------------------------

Nie brakuje jednak krytyków ewolucyjnych metod obliczeniowych. Komputerowe konstrukcje ewoluują w sposób przypominający dobór naturalny i często rozwiązują problemy za pomocą metod, których nie rozumieją nawet ich twórcy. Nie znamy ścisłej teorii matematycznej, określającej możliwości tych metod, a zatem nie mamy żadnej gwarancji poprawności wyników.
Ludzi interesuje pytanie, co działa i dlaczego działa.
Nature obchodzi jednak tylko to , co działa. W naturze przekazywane jest tylko to co przeżywa, co słabe to ginie.

---