1. Biologiczne przeslanki algorytmów genetycznych.

AG jest to algorytm poszukiwania jak najlepszych rozwiązań danego zadania w przestrzeni alternatywnych rozwiązań. Sposób działania AG bazuje (został zaczerpnięty) z biologii - z Darwinowskiej teorii ewolucj i łączy w sobie ewolucyjną zasadę przeżycia osobników najlepiej przystosowanych (powielanie) oraz systematyczną, choć losową wymianę informacji (krzyżowanie). W każdym kroku AG (pokoleniu) powstaje (rodzi się) nowy zespół ciągów binarnych (sztucznych organizmów, członków populacji) powstały poprzez wykonanie na poprzednim pokoleniu pewnych operacji, które mają odpowiedniki w przyrodzie (teorii ewolucji). Są zatem próbą przeniesienia praw ewolucji na model matematyczny, informatyczny.

Centralnym tematem w badaniach nad AG jest odpornośc tj. kompromis pomiędzy efektywnoscią a zdolnoscią do przetrwania w zmieniających się warunkach. Jeśli potrafimy skonstruować odporny system techniczny, to wówczas w przyszlości mozemy zminimalizować lub całkiem wyeliminować jego przeróbki konieczne do dostosowania go do nowych wymagań. Twórcy systemów inżynierskich, komputerowych, czy ekonomicznych mogą tylko podziwiac odporność, łatwość przstosowania i wydajność systemów biologicznych. Innymi słowy tam gdzie odpornosc jest cechą pożądaną, przyroda radzi sobie lepiej niż dzieła człowieka. Nie jest to jednak jedyna przesłanka do przyjęcia metod AG. Istnieja teoretyczne i empiryczne dowody na skuteczność i doporność AG w poszukiwaniu rozwiązań w skomplikowanych przestrzeniach.

2. Podstawowoe prawidlowości ewolucji naturalnej.

Założenia teorii ewolucji (z wiki):

Teoria ewolucji jest teorią naukową, wyjaśniającą mechanizm i przebieg procesu ewolucji biologicznej. Zasadniczymi założeniami współczesnej Teorii Ewolucji są:

Wnioskiem wypływającym z tych założeń jest konieczność zmiany częstości występowania genów w populacji, taka, że geny (allele) warunkujące korzystniejsze cechy zwiększą swoje występowanie.

Zapis genetyczny osobnika - genotyp.

Jednostki informacyjne, które po zdekodowaniu oznaczają cechy osobnikach - geny.

Ogół uzewnetrzniających się cech osobnika (np. wzrost, masa mięsniowa, kolor wlosów) - fenotyp.

Po poddaniu genotypu procesowi dekodowania uzyskujemy fenotyp.

Punkty z wykładu:

3. Ogólna struktura prostego AG.

Na wykładzie było tak:

Natomiast w necie i w książce występuje taka wersja:

4. Kodowanie problemu - ontologie szczegółowe

Pierwszym zadaniem, gdy decydujemy sie rozwiązać jakiś problem za pomocą AG jest przetłumaczenie go na język jakim posłóguja się algorytmy genetyczne tzn. wybranie soposobu reprezentacji genów, zestawu cech i porządku ich występowania w genotypie, długości genotypu, liczebności populacji, funckji oceny. Należy dążyć do wyboru minimalnej ilości cech, ale w ten sposób by można było jednoznacznie dekodować genotyp tzn. jednoznacznie zidentyfikować osobnika (rozwiązanie) na podstawie chromosomu. Do określania jakości, przystosowania danego osobnika służy tzw. funkcja oceny.

Wyróżniamy następujące sposoby reprezentacji genów:

5. Moduł populacji (strategie, koło ruletki)

Wyróżnić możemy następujące strategie generowania populacji pierwotnej:

Wyróżnic możemy następujące strategie selekcji osobników przechodzących do nastepnego pokolenia:

, gdzie F jest funkcją przystosowania.

Łatwo widać, że osobniki, które są bardziej przystosowane będą miały w tej strategii wyższe p-stwo wylosowania.

Strategia ta nosi nazwę koła ruletki, ponieważ przypisanie p-stwa wylosowania konkretnym osobnikom można widzieć jako przydzielenie im odpowiednio długiego łuku na kole ruletki, zaś losowanie jako kręcenie kołem ruletki.

6. Moduł populacji - funkcje oceny

Funkcja oceny jest to funkcja operująca na chromosomie i określająca miarę przystosowania danego osobnika. Jest ona ściśle związana z istotą rozwiązywanego problemu. Jej wybór znacząco wplywa na powodzenie AG.

Przykład z wykładu to funkcja Hollanda: ??

7. Moduł rozrodu - operatory genetyczne krzyżowania (krzyżowanie jedno- i wielopunktowem krzyżowanie jednolite)

Krzyżowanie jet operacją, która z 2 osobników rodzicielskich tworzy 2 osobniki potomne, różne od rodzicielskich. Potomkowie są kombinacją osobników rodzicielskich.

Krzyżowanie jednopunktowe - wybieramy losowo jeden punkt krzyżowania, który dzieli rodziców na dwie częsci. Potomek 1 składa się z lewej częsći rodzica 1 i z prawej rodzica 2, a potomek drugi z prawej części rodzica 1 i z lewej rodzica 2.

Krzyżowanie wielopunktowe - wybieramy losowo 1 lub więcej punktów krzyżowania - uogólnienie jednopunktowego, pozwala na większe zróżnicowanie materiału genetycznego potomków i szybsze uzyskanie zmienności rozrodu. Przyklad:

[110 | 0100 | 10101] --------> [110000110101]

[101 | 0001 | 11010] --------> [101010011010]

Krzyżowanie jednolite - losujemy wzorzec tj. chromosom o długości równej długości chromosomow z populacji określający sposób krzyżowania tj. sposób w jaki będziemy pobierac materiał genetyczny od rodziców, co ilustruje przykład:

wzorzec: [1001010101110]

rodzic 1: [1111000010010]

rodzic 2: [0010110111101]

potomek 1: [0110010111100]

potomek 2: [1001100010011]

Gdy we wzorcu występuje jeden to do potomka 1 wpisujemy bit z rodzica 2, a do potomka 2 bit z rodzica 1, gdy wystepuje zero to do potomka 1 wpisujemy bit z rodzica 1, do potomka 2 z rodzica 2

Proces krzyżowania zachowuje nastepujące zależności:

To skoleji implikuje następujące fakty:

8. Moduł rozrodu - operatory genetyczne modyfikujące chromosom (mutacja, inwersja).

Mutacja jest procesem w wyniku, którego następują losowe zmiany materiału genetycznego. Ma ona znaczenie drugorzędne. Stosuje się ją, poniważ czasem zdaża się tak, że powielanie i krzyżowanie wyeleminują bezpowrotnie jakiś obiecujący material genetyczny i aby nie nie była to strata bezpowrotna stosuje się mutację, która stanowi polise ubezpieczeniową na wypadek utraty ważnego składnika rozwiązania.

W przypadku chromosomów binarnych mutacja polega na albo na wylosowaniu dwóch różnych genów i wymianie ich wartości, albo na wylosowaniu genu i zanegowaniu jego wartości.

W przypadku chromosomów dyskretnych stosuje się permutacje.

W przypadku ch. ciągłych stosuje się losowe zmiany przypadkowych genów - najcześciej zmiany te maja rozklad normalny.

Częstość występowania mutacji w procesie ewolucji określa współczynnik mutacji - należy dobierać go tak aby był rzędu 0,01 ~ 0,0001.

Proces mutacji można np. Przeprowadzac tak, że dla każdego genu losujemy bieżący wspołczynnik mutacji i jeśli jest on mniejszy od współczynnika mutacji wówczas dokonujemy mutacji, poza tym nie.

Inwersja podobnie jak mutacja powoduje losowe zmiany mat. gen. Należy ją stosować tylko dla osobników najsłabiej przystosowanych. Chromosom jest dzielony na 2 części, następnie w jednej z nich (wybór losowy) dokonujemy lustrzanego odbicia.

Przykład: 0010|1101 ---> 01001101

Tylko rzadkie stosowanie op. modyfikujących daje porządane, pozytywne rezultaty. Nie ostrożne stosowanie może doprowadzić do niszczenia wartościowego materiału genetycznego.

9. Schematy genetyczne, tw. Hollanda.

Schemat jest to wzorzec opisujący zbiór wszystkich ciągów podobnych ze względu na ustalone pozycje.

Dla danego alfabetu A, schematy konstruuje sie nad alfabetem A + {*}. Jeśli A = {0, 1}, to schematy bedziemy konstruowac w oparciu o alfabet {0, 1, *}. Niech teraz bedzie dany schemat *00*. Opisuje on wszystkie ciągi binarne długości 4, które mają 0 na 2 i 3 pozycji, a cyfry na 1 i 4 pozycji są dowolne.

Rzędem schematu nazywamy liczbę ustalonych pozycji schematu (rząd naszego przykładowego schematu wynosi zatem 2).

Rozpiętość schematu to odległość pomiędzy skrajnymi ustalonymi literami schematu.

Przystosowaniem schematu nazywamy średnie przystosowanie chromosomów pasujących do schematu.

Tw Hollanda (o schematach)

Schematy o niskiej rozpiętości, o niskim rzędzie i o przystosowaniu powyżej średniej wykazują wykładniczo rosnącą liczbę pasujących chromosomów w kolejnych krokach AG.

10. Metody odświeżania populacji („dolewanie nowej krwi”).

Gdy AG jest zbyt szybko zbieżny do niezadowalającego rozwiązania, wówczas dopuszcza się zastosowanie mechanizmów nie mających odpowiedników w ewolucji biologicznej. Metodami odświeżania populacji są:

11. Koncepcja technik zaawansowanych.

Do tej pory w AG używaliśmy tylko najprostszych mechanizmów zaczerpniętych z ewolucji biologicznej, podczas gdy w rzeczywistości w przyrodzie są one bardziej złożone. Źródła technik zaawnsowanych to osiągniecia genetyki, uogólnienia metod bilogicznych, nowe mechanizmy (inwencja twórcza). Techniki zaawansowane stosuje sie w celu wzmocnienia odporności elemntarnych AG. Rozpoznanie, analiza i implementacja technik zaawansowanych to obecnie bardziej owocny kierunek udoskonalania AG. Do omawianych technik należą takie mechanizmy jak: wielochromosomalność, poliploidalność, wielorodzicielstwo, wprowadzenie płci, hybrydowość - w dalszych pkt. zostaną opisane szczegółowo.

12. Wielochromosomalny aparat genetyczny i wielorodzicielstwo.

W prostym AG stosowaliśmy reprezentacje osobnika złożona z jednego łańcucha - chromosomu. Techniki zawansowane wprowadzają reprezentację osobnika za pomocą wielu chromosomów. Każdy z nich reprezentuje jedną odmienną cechę (np. kolor włosów) lub grupę cech. Metoda ta została zaczerpnięta z genetyki, np. u człowieka mamay 23 pary chromosomów

Wielorodzicielstwo jest uogólnieniem rodzicielstwa stosowanego w elementarnym AG, w którym proces krzyżowania polegał na skonstruowaniu 2 nowych osobników na podstawie dwóch rodzicielskich. Tu natomiast może być wielu rodziców - potomek dostaje geny od każdego rodzica. Pociąga to za sobą konieczność redefiniowania operatora krzyżownia (krzyżowanie diagonalne):

13. Homologiczność reprezentacji genetycznej - diploidalny schemat Hollsteina.

W elementarnym AG stosujemy najprostszy rodzaj genotypu o haploidalnej liczbie chromosomów. W przyrodzie występuje on u najniższych form życia, a formy bardziej zaawansowane mają genotypy o diploidalnej liczbie chromosomów. Haploidalność oznacza występowanie tylko jednego chromosomu reprezentującego jakieś cechy osobnicze. Diploidalność oznacza natomiast istnienie dwóch homologicznych chromosomów odpowiadających za tę samą cechę fenotypu. Natomiast poliploidalność jest uogólnieniem tych dwóch poprzednich i oznacza, że w genotypie występuje wiele chromosomów reprezentujących pewną cechę fenotypu. Mamy tu zatem do czynienia ze zwielokrotnieniem informacji genetycznej. Powstaje teraz pytanie, który z homologicznych chromosomów przekładać się ma na cechę fenotypu. Mechanizm rozstrzygający tę kwestię nazywamy dominowaniem. Występują w nim dwa rodzaje genów: recesywne i dominujące. Wybór genu (alelu) odbywa się na danym miejscu (locus) według następujących reguł - jeśli w homologicznej parze wystepują:

Rozważmy przykład dwóch chromosomów:

a B c d E

a B C d e

Duża litera oznacza gen dominujący, mała recesywny. Po wykonaniu operacji dominowania otrzymamy:

a B C d E

Gen dominujący przejawia się zarówno w stanie homo- jak i heterozygotycznym, natomiast gen recesywny tylko w stanie homozygotycznym.

Jest wiele hipotez tłumaczących występowanie tego zjawiska w przyrodzie. Z punktu widzenia AG najbardziej interesująca jest ta: dominowanie stanowi mechanizm do zapamiętywania tych aleli, które w przeszłości były użyteczne, a teraz są tylko osłaniane przed mechanizmem selekcji, po to aby w przyszłości, gdy być może zmieni się środowisko naturalne i będą przydatne, mogły stać się dominującymi.

Już w niektórych wczesnych zastosowaniach AG stosowano poliploidalność. Przyjrzyjmy się diploidalnemu schematowi Hollsteina (1971, badania nad optymalizacją funkcji). Zamiast pojedynczego genu binarnego używamy dwóch genów: funkcyjnego i modyfikatora. Funckyjny w zwykły sposób używamy do kodowania pewnej cechy - może zatem przyjmować wartości 0 lub 1. Modyfikator zaś przyjmuje wartości M lub m. Sposób działania dominacji ilustruje tabela:

Z tabeli tej widać, że jeśli w którymś z homologicznych genów występuje modyfikator M, to wtedy 0 jest dominujące.

Żeby wszystko było jasne rozpatrzmy jeszcze przykład:

[0m, 1M, 1m, 0M, 0m]

--> [1, 0, 1, 0, 1]

[1m, 0m, 1m, 1M, 1m]

14. Rola płci (przykład Goldberga)

Aby zobrazować korzyści płynące z podziału osobników na pewne podgrupy (tzw. płcie) rozważmy przykład Goldberga.

Niech n oznacza ułamek czasu jaki osbnik poświęca na opiekę nad potomstwem, zaś h ułamek czasu jaki poświęca zdobywaniu pożywienia. Musi on też poświęcić pewien ułamek czasu na organizację - niech czas ten wynosi anh, gdzie a jest pewnym współczynnikiem. Wszystkie podane liczby musza spelniac zależność:

(*) n + h + anh = 1

Możemy teraz wyrazić przeżywalność potomstwa poprzez funkcję n i h:

S(n,h) = nh

Maksymalizujac funkcję S, przy warunku (*) otrzymamy:

Rozważmy teraz parę osobników I i II, którzy poświęcają odpowiednio (n_I, h_I) i (n_II, h_II) czasu na opiekę i polowanie (dzielą sie obowiązkami), tak że:

n_i + h_i + a_in_ih_i = 1, dla i = I, II

Funkcja przeżywalności potomstwa będzie teraz miała postać:

S(n_I, h_I, n_II, h_II) = ½ * (n_I+n_II)(h_I+h_II)

Maksymalizujac S ze wzgledu na powyższe warunki mamy:

Powyższy model, choć b. uproszczony, ilustruje zalety kooperacji i specializacji, którym służy zróżnicowanie płciowe. Dokładnie jeszcze nie zbadano efektów wprowadzenia płciowości do AG, ale prawdopodobnie wykażą przewagę nad zwykłymi mechanizmami w zagadnieniach wymagających kooperacji i specializacji.

15. Hybrydowe AG (AG wspierane wiedzą)

Hybrydyzacja polega na połączeniu, „skrzyżowaniu” AG z metodami szczegółowymi pewnego problemu (techniki lokalne). Pozwala to na szybsze uzyskanie zbieżności AG. Aby nie zaburzac zbytnio ogólności AG stisuje się modularyzację: moduł AG i moduł lokalny. Np. AG pracuje aż do osiągniecia znacznego stopnia zbieżności populacji, po czym uruchamiane są obliczenia lokalne, startujace z jakichś 5-10% najlepszych punktów ostatniego pokolenia.

Operacje wspomagane wiedzą - w zależności od konkretnego problemu „wspomagamy” operacje genetyczne krzyżowania i/lub mutacji kierując się specyfiką rozwiązywanego problemu. Podobnie jak hybrydyzacja ma to na celu przyśpieszenie zbieżności AG.

16. Zastosowania AG (z wiki)

Algorytmy genetyczne znajdują zastosowanie tam, gdzie nie jest dobrze określony lub poznany sposób rozwiązania problemu, ale znany jest sposób oceny jakości rozwiązania. Przykładem jest np. problem komiwojażera, gdzie należy znaleźć najkrótszą drogę łączącą wszystkie miasta, tak by przez każde miasto przejść tylko raz. Ocena jakości proponowanej trasy jest błyskawiczna, natomiast znalezienie optymalnej trasy kwalifikuje się do klasy problemów NP zupełnych. Przy zastosowaniu podejścia ewolucyjnego dobre rozwiązanie można znaleźć bardzo szybko, ale oczywiście pewni możemy być jedynie uzyskania rozwiązań sub-optymalnych, co wynika z formalnie opisanej trudności problemów klasy NP. Algorytmy genetyczne równie dobrze radzą sobie w znajdowaniu przybliżeń ekstremów funkcji, których nie da się obliczyć analitycznie.

Algorytmy genetyczne wykorzystywane są również do zarządzania populacją sieci neuronowych. Projektowanie maszyn bądź obwodów elektrycznych jest doskonałym polem dla wykazania się algorytmów genetycznych. Inżynierowi podczas tworzenia nowych pomysłów nie chodzi o znalezienie najlepszego możliwego rozwiązania. Wystarczy tylko przybliżone spełnienie granicznych warunków oraz optymalizacja projektu. Algorytmy genetyczne w odróżnieniu od człowieka nie działają schematycznie. Program nie zna wcześniejszych projektów i dlatego czasami wykazuje się pewną inwencją. Co więcej człowiek często opiera się na bardzo przybliżonych modelach, które dają fałszywy obraz problemu. Algorytm genetyczny może przeanalizować złożony model / zagadnienie i znaleźć rozwiązanie, na które człowiek by nie wpadł.

Algorytmy genetyczne można wykorzystać do projektowania obwodów elektrycznych. Ocena każdego osobnika opiera się na ilości elementów oraz własnościach elektrycznych, które łatwo jest obliczyć. Główna różnica tkwi w algorytmie budowy osobnika na podstawie genomu. Ma on postać instrukcji dla programu, który na jego podstawie buduje obwód elektryczny. Najpierw mamy proste połączenie wejścia z wyjściem. Następnie program dodaje i usuwa połączenia i elementy. Zbudowany tak obwód jest oceniany na podstawie prostych zależności fizycznych. Podobny algorytm genetyczny zbudował samodzielnie filtr drabinkowy. Analogiczne podejście można zastosować przy projektowaniu anten. Różnica tkwi w tym, że wirtualny budowniczy porusza się w trójwymiarowej przestrzeni i ustawia metalowe elementy odbijające fale.

Jednym z nowszych pomysłów jest wykorzystanie algorytmów genetycznych w połączeniu z układami FPGA (field-programmable gate arrays). Mają one postać chipów, które można błyskawicznie zaprogramować, aby zmienić strukturę zawartego w nich obwodu elektrycznego. Algorytmy genetyczne badają zwykle zachowanie symulowanych pokoleń. Dzięki układom FPGA możliwe jest ewoluowanie prawdziwych obwodów elektrycznych. Są one wpisywane do chipa, a następnie ich właściwości elektryczne są mierzone rzeczywistym obwodem testowym. W ten sposób ewolucja może wykorzystać wszystkie fizyczne własności rzeczywistego układu elektrycznego.

Okazało się, że regulatory stosowane w automatyce również można udoskonalić dzięki zastosowaniu algorytmów genetycznych. Najpopularniejszy algorytm sterowania czyli PID, można wyobrazić sobie jako pewien zestaw połączonych ze sobą członów różniczkujących i całkujących. Odpowiedni algorytm genetyczny może zbudować taki układ analogicznie do obwodu elektrycznego. Korzystając z tej metody John R. Koza opracował nowe wersje PID-a [1].

Stworzono ponadto eksperymentalny system, zbudowany na bazie algorytmów genetycznych, który sam produkuje roboty, poddaje ocenie fizycznego środowiska i optymalizuje pod kątem jak najlepszego poruszania się w tym środowisku. Projekt nosi nazwę Golem.

Niestety, aby ewolucja mogła zajść potrzeba bardzo dużo czasu. W praktyce oznacza to, konieczność badania populacji tysięcy układów, na przestrzeni setek pokoleń. Moc obliczeniowa dzisiejszych komputerów jest zbyt mała, aby sprostać takiemu zdaniu w rozsądnym czasie. Z tego powodu wykorzystuje się klastry komputerów. Na każdym przebywa pewna populacja układów. Co pewien czas, część z nich migruje do innego komputera, aby polepszyć uzyskiwane wyniki. Jednak rozwój techniki komputerowej spowoduje, że za kilka lat algorytmy genetyczne będą mogły trafić pod strzechy.

Algorytmy genetyczne zapewniają skuteczne mechanizmy przeszukiwania dużych przestrzeni rozwiązań. Ponieważ grupowanie należy do tej kategorii zadań to oczywiste jest, że algorytmy genetyczne stosowane są w grupowaniu. Algorytmy genetyczne są bardziej niezależne od wstępnej inicjalizacji oraz mniej skłonne do znajdowania lokalnych rozwiązań w miejsce optymalnych. Przykładem może być zagadnienie grupowania w którym w miejsce klasycznych algorytmów z powodzeniem stosuje się algorytmy genetyczne.