Algorytmy ewolucyjne (ang. Evolutionary Algorithms) – nazwa ogólna, obejmująca metody szczegółowe: algorytmy genetyczne, programowanie genetyczne, strategie ewolucyjne Cecha wspólna: wykorzystanie schematu wzorowanego na teorii doboru naturalnego i ewolucji.
Podstawowe pojęcia 1) Osobnik - podstawowa jednostka podlegająca ewolucji, przebywający 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. 2) Fenotyp - zbiór cech podlegających ocenie funkcji przystosowania modelującej środowisko. 3) Genotyp - opis osobnika zawarty w jego genach. 4) Populacja - zespół osobników zamieszkujących wspólne środowisko i konkurujących o jego zasoby. 5) Chromosom – uporządkowany ciąg genów (genotyp), zakodowany osobnik 6) Gen – pojedynczy element genotypu (w szczególności chromosomu) 7) Allel – wartość danego genu (wartość, wariant cechy) 8) Generacja – kolejna iteracja w AG
9) Pokolenie – nowo utworzona populacja (w wyniku generacji)
Fenotyp a genotyp Zmianom (mutacja, krzyżowanie) podlega genotyp osobnika, podczas gdy selekcji poddawane są fenotypy.
@ Istotą ewolucji jest połączenie zjawiska losowych, nie ukierunkowanych zmian genotypu ze ściśle ukierunkowaną presją środowiska na fenotyp.
Podstawowe zasady: 1) Genotyp danego osobnika w czasie jego życia nie ulega zmianie, natomiast ulega on modyfikacjom podczas rozmnażania się. Zmiany te mogą wynikać albo z niewielkich, losowych mutacji, albo ze zmieszania (krzyżowania) cech osobników rodzicielskich. 2) Zmiany w genotypie powodują zmiany fenotypu osobników potomnych, co wpływa na stopień ich przystosowania do środowiska. 3) Zmiany w genotypie maja charakter przypadkowy. Zmiany korzystne dla osobnika zdarzają się równie często, jak niekorzystne. 4) Osobniki są oceniane poprzez porównanie ich przystosowania do danego środowiska. Lepiej przystosowane rozmnażają się, te gorzej giną.
Algorytmy genetyczne – idea działania Teoria opracowana przez Hollanda w 1975 r. Koncepcje AG zaczerpnięte z nauk przyrodniczych opisujących zjawiska doboru naturalnego i dziedziczenia. 1) Idea przetrwania osobników najlepiej dostosowanych w danym środowisku, osobniki gorzej przystosowane są stopniowo eliminowane. 2) Osobniki, które przetrwają - przekazują informację genetyczną swoim potomkom podczas krzyżowania i mutacji. 3) Krzyżowanie informacji genetycznej otrzymanej od “rodziców” prowadzi do sytuacji, w której kolejne pokolenia są przeciętnie coraz lepiej dostosowane do warunków środowiska; mamy więc tu do czynienia ze swoistym procesem optymalizacji.
Algorytmy genetyczne – podstawy 1) Proces genetyczny postrzegany jest jako proces optymalizacyjny, w którym osobniki najlepiej dostosowane do środowiska mają największe szanse przeżycia i utworzenia potomków. 2) Nośnikiem informacji o cechach indywidualnych osobnika jest kod genetyczny (chromosom): kod ten determinuje budowę osobnika i jego rozwój, a w szczególności - jego dopasowanie do środowiska naturalnego. 3) Istnieje silna zależność między chromosomem osobnika a jego żywotnością i zdolnością do przekazywania genotypu kolejnym pokoleniom.
Podstawowe elementy AG 1) genetyczna reprezentacja potencjalnych rozwiązań zadania (kodowanie chromosomu)
2) sposób generowania populacji początkowej potencjalnych rozwiązań 3) postać funkcji przystosowania, która gra rolę środowiska i ocenia rozwiązania według ich dopasowania 4) sposób doboru rodziców i stosowane operatory genetyczne (krzyżowanie, mutacja (inwersja)) 5) sposób selekcji następnego pokolenia.
Kodowanie chromosomów 1) binarne, w których allel przyjmuje wartości binarne: 0 oraz 1, zastosowanie: optymalizacja funkcji
2) całkowitoliczbowe (naturalne), w których allel przyjmuje wartości z określonego zbioru liczb całkowitych (konieczne jest podanie dolnej i górnej granicy tego zbioru) a) permutacyjne – geny w chromosomie stanowią permutację liczb naturalnych od 1 do n, gdzie n – rozmiar chromosomu (zastosowanie: problemy szeregowania, problem komiwojażera) 3) rzeczywiste, w których allel obejmuje wartości z określonego zbioru liczb rzeczywistych, przy uwzględnieniu określonego poziomu dokładności
Kodowanie binarne – co można zapisać w 16 bitowym chromosomie 1) liczba naturalna z zakresu 0..65535 będąca kandydatem na pewne optimum jakiejś funkcji 2) reprezentacja dwóch liczb naturalnych z zakresu 0..255 będących kandydatami na optimum funkcji dwuargumentowej 3) liczba rzeczywista z przedziału <-2, 4> pamiętana z dokładnością 0,0001 4) 2^16 różnych cech przedmiotów (kolory, kształty)
AG – kodowanie potencjalnych rozwiązań W celu rozwiązania konkretnego zadania, należy zakodować przestrzeń stanów (czyli wszystkie potencjalne rozwiązania) jako liczby binarne, całkowite, rzeczywiste itp. W pewnych zastosowaniach kodowanie binarne jest mniej naturalne, niż inne sposoby kodowania. Algorytm genetyczny może działać na osobnikach złożonych z permutacji. Jedyny problem stanowią operatory genetyczne (mutacja i krzyżowanie): należy je tak zaprojektować, by zawsze w wyniku dawały „legalne” permutacje.
Sposób generowania populacji początkowej 1) Populacja początkowa powinna być zróżnicowana najczęściej losowe generowanie chromosomów o liczbie równej rozmiarowi populacji 2) Można włączyć część rozwiązań o dobrej jakości; część chromosomów w populacji początkowej znaleziona przy użyciu innych algorytmów heurystycznych lub przy użyciu AG we wcześniejszych obliczeniach
Funkcja przystosowania (ang. fitness) w AG Funkcja oceny, miara jakości dowolnego osobnika (fenotypu, rozwiązania) w populacji. Często przyjmowana jest funkcja celu rozważanego problemu optymalizacji. W klasycznym AG funkcja fitness jest nieujemnym kryterium oceny. Wartości funkcji fitness dla osobników w danej populacji są podstawą do sformułowania metody selekcji z tej populacji najlepiej przystosowanych osobników do tzw. puli rodzicielskiej tzn. populacji na której przeprowadzane są operacje genetyczne
Selekcja nowej populacji 1) Selekcja polega na losowaniu ze zwracaniem osobników z populacji bazowej do populacji rodzicielskiej. 2) W wersji klasycznej AG, cała populacja rodziców jest wymieniana przez potomstwo. Rozmiar populacji jest stały w kolejnych generacjach 3) Ostatnie badania wykazują, że lepiej wymieniać tylko część populacji. Ma to uzasadnienie w naturze.
4) Technika wyboru osobników, które „mają pecha” i zostaną usunięte z populacji może być różna: najczęściej stosuje się wybór losowy lub deterministyczny najgorszych osobników. 5) Powinna być tak zorganizowana, że osobniki z wyższym przystosowaniem mają większe prawdopodobieństwo wprowadzenie jednego lub więcej potomków do następnego pokolenia. 6) Dla każdego wybranego podciągu tworzymy dokładną replikę. Zostaje ona włączona do pokolenia pośredniego, stanowiącego pulę rodzicielską do dalszych operacji genetycznych. 7) Selekcja jest odpowiednikiem darwinowskiej zasady doboru naturalnego. 8) Metody selekcji: koła ruletki, rankingowa, turniejowa
Selekcja – metoda koła ruletki Symulacja działania koła ruletki 1) Każdy chromosom ma przydzielony wycinek koła o wielkości proporcjonalnej do wartości jego funkcji przystosowania 2) Reprodukcja przez n-krotne losowanie osobników ze starej populacji do nowo tworzonej populacji 3) Często stosowane tzw. skalowanie funkcji przystosowania w celu poprawy wyników np..do zwiększenia prawd. selekcji lepszych chromosomów w porównaniu z gorszymi. 4) Obliczenie dla każdego chromosomu prawdopodobieństwa selekcji p_i wg wzoru: pi = Fi / F 5) Obliczenie dla chromosomu dystrybuanty q_i wg wzoru qi= suma od i do j-1 Pj
6) Wybór odpowiednich chromosomów do dalszych etapów na podstawie wskazań generatora liczb losowych; generowane jest tyle liczb losowych z przedziału (0, 1) ile jest chromosomów w populacji, następnie dla każdej wylosowanej liczby r sprawdzamy, który chromosom i spełnia warunek: qi-1 < r < qi ten znaleziony chromosom o numerze i wybrany zostanie do nowo tworzonej populacji. 7) W wyniku selekcji metodą ruletki pewne chromosomy mogą zostać wybrane więcej niż jeden raz, a inne mogą nie przetrwać.
Selekcja rankingowa Uszeregowanie wszystkich osobników populacji zgodnie z rosnącą wartością funkcji przystosowania. Każdemu osobnikowi jest przydzielana pewna ilość tzw. szans (najprostszym sposobem rozdziału szans jest przyznanie osobnikowi najsłabszemu jednej szansy, natomiast najsilniejszemu n szans tzw. ranking liniowy).Prawdopodobieństwo wylosowania do nowej populacji zależy od pozycji osobnika w rankingu, przy czym zachowana jest zasada promowania osobników najsilniejszych. Badania wykazują, że ta technika często zbyt różnicuje osobniki bliskie pod względem dopasowania. Często jednak lepsza od koła ruletki
Selekcja turniejowa Losowo jest wybierana grupa osobników (w najprostszym przypadku para) z aktualnej populacji. Najlepszy osobnik z tej grupy turniejowej jest wstawiany do nowo tworzonej populacji. Turnieje są organizowane aż do utworzenia całej nowej populacji. Dany osobnik może uczestniczyć w wielu turniejach. W turnieju probabilistycznym, z pary (lub n) wylosowanych osobników wygrywa najlepszy z prawdopodobieństwem 0,5<p<1,0.
Szczególne strategie reprodukcji 1) Strategia elitarna (elityzm) a) ochrona najlepszych chromosomów w kolejnych iteracjach (w algorytmie klasycznym najlepszy chromosom może nie przejść do kolejnej generacji) b) pewna liczba chromosomów elitarnych najlepiej przystosowanych przechodzi do następnej generacji, pozostałe chromosomy wybierane w drodze losowej selekcji
2) Częściowa wymiana populacji a) część populacji przechodzi bez zmian (nie jest poddana krzyżowaniu, mutacji) do następnej generacji


AG – krzyżowanie (ang. crossover) polega na wymianie materiału genetycznego pomiędzy losowo dobranymi parami osobników z bieżącej populacji. W wyniku krzyżowania powstają nowe chromosomy, które wejdą w skład kolejnej populacji (pokolenia). Chromosomy powstałe w wyniku krzyżowania często są lepiej przystosowane niż ich rodzice. Proces krzyżowania w praktyce polega na: a) wybraniu dwóch łańcuchów rodzicielskich b) następnie wylosowaniu punktu krzyżowania c) na koniec połączeniu fragmentów chromosomów z obu rodziców względem danego punktu d) łańcuchy rodzicielskie wybiera się uwzględniając prawdopodobieństwo krzyżowania p_k.
Wyróżniamy dwa krzyżowania: a) jednopunktowe (1PX) b) dwupunktowe (2PX)
AG – mutacja polega na zmianie wartości losowo wybranych genów. (z 0 na 1, z 1 na 0 dla kodowania binarnego). Mutacja zachodzi zwykle z niewielkim prawdopodobieństwem p_m < 0.1. Zadaniem operatora mutacji jest zapewnienie zmienności chromosomów (np. zapobiega powstaniu całej populacji identycznych osobników) i tym samym stworzenie możliwości wyjścia procedury optymalizacji z optimum lokalnego funkcji przystosowania.
AG – inwersja Działa na pojedynczym chromosomie odwracając kolejność alleli w wybranym fragmencie (między dwoma losowo wybranymi pozycjami). Traktowana w badaniach jako szczególny rodzaj mutacji. Stosowana w rozszerzonych wersjach AG. Potomek 1 0 1 1 0 1 1 0 1 1 1 1 0. Potomek po inwersji 1 0 1 1 0 1 0 1 1 1 1 1 0
Problem optymalizacji funkcji w AG 1) Znalezienie ekstremum jest możliwe bez analizy przebiegu optymalizowanej funkcji
2) Czas przeszukiwań bardzo krótki, a wyniki bardzo dobre 3) Możliwość znalezienia ekstremum dla funkcji wielu zmiennych
4) Przestrzeń stanów: wszystkie możliwe wartości zmiennych (argumentów) optymalizowanej zmiennej w analizowanych przedziałach przy przyjętej dokładności 5) Wielkość przestrzeni stanów: iloczyn minimalnej liczby różnych wartości przyjmowanych przez poszczególne zmienne 6) Funkcja celu: optymalna (minimalna, maksymalna) wartość funkcji
Binarne kodowanie liczb rzeczywistych Dowolna liczba rzeczywista x z przedziału <a, b> z dokładnością m miejsc po przecinku: 1) Minimalna liczba bitów do zachowania takiej dokładności: a) b-a jednostkowych przedziałów, w każdym 10^m różnych wartości
b) Zatem łącznie (b-a)·10^m różnych wartości c) Dla minimalnej liczby bitów n zachodzą nierówności 2^n-1 < (b-a)·10^m <2ⁿ zatem n=log2[b-a)*10^m] 2) Kodowanie dowolnej liczby rzeczywistej x: x= ((b-a) / 2^n-1)* dzies +a gdzie dzies - wartość dziesiętna
n-bitowej liczby binarnej
AG – zastosowania Optymalizacja – wyznaczenie spośród dopuszczalnych rozwiązań danego problemu rozwiązania najlepszego za względu na przyjęte kryterium jakości (np. koszt, zysk, niezawodność). Dla wielu problemów optymalizacji znalezienie dokładnego rozwiązania może zajmować bardzo dużo czasu zwłaszcza dla NP-trudnych tj. problem komiwojażera TSP (ang. Traveling Salesman Problem), problemy szeregowania zadań (ang. Scheduling Problems). Praktyczne zastosowania: wytyczanie trasy połączeń kablowych, zadania transportowe, produkcja płytek obwodów drukowanych, optymalizacja wag sieci neuronowych
Problemy krzyżowania, mutacji przy kodowaniu permutacyjnym Operatory genetyczne nie mogą zaburzać kodowania dla danego problemu tzn. po wymianie materiału genetycznego nowe ciągi powinny dać się odkodować – powinny dalej reprezentować potencjalne rozwiązania. Konieczność stosowania wyspecjalizowanych operatorów dla kodowania permutacyjnego:
1) Przykładowe operatory krzyżowania (1PX, 2PX, PMX, DOX, LOX, PBX, PPX) 2)Przykładowe operatory mutacji: (Zamień, Zamień sąsiednie, Wstaw, Inwersja)
PMX (Partially-Matched Crossover) W krzyżówce PMX tworzy się potomka, wybierając podciąg od jednego rodzica i pozostawiając porządek i pozycje z drugiego rodzica tak długo jak jest to możliwe. Dwa losowe punkty cięcia służą jako granice dla operatorów wymieniających. Tworzona jest mapa wymiany, która zawiera pary odpowiadających sobie elementów w obu rodzicach : R1 = (1, 2, 3 | 4, 5, 6 | 7, 8, 9) R2 = (2, 4, 1 | 7, 8, 3 | 9, 5, 6) Mapa wymiany ma postać: M=(1-2, 2-4, 3-1, 4-7, 5-8, 6-3, 7-9, 8-5, 9-6) Po wymianie sekcji kojarzenia otrzymujemy parę potomków: P1 = (x, x, x | 7, 8, 3 | x, x, x) P2 = (x, x, x | 4, 5, 6 | x, x, x). Pozostałe geny są uzupełniane z odpowiedniego rodzica, a w przypadku wartości powtarzających się – geny są wstawiane zgodnie z mapą wymiany. W rezultacie otrzymujemy parę potomków: P1 = (1, 2, 6, 7, 8, 3, 4, 5, 9) P2 = (2, 7, 1, 4, 5, 6, 9, 8, 3).
Krzyżowanie jednopunktowe 1PX (One Point Crossover) - osobnik potomny powstaje przez skopiowanie genów od pierwszej pozycji do punktu krzyżowania od jednego z rodziców a brakujące geny są uzupełniane w kolejności ich występowania u drugiego z rodziców. Pkt krzyżowania wybrany losowo. Z rodziców: R1 = (1, 2, 3 | 4, 5, 6, 7, 8, 9) R2 = (2, 4, 1 | 7, 8, 3, 9, 5, 6) Powstają: P1 = (1, 2, 3 | 4, 7, 8, 9, 5, 6) P2 = (2, 4, 1 | 3, 5, 6, 7, 8, 9)
Krzyżowanie dwupunktowe 2PX (Two Point Crossover) - osobnik potomny powstaje przez skopiowanie genów od jednego z rodziców (poza fragmentem chromosomu między dwoma wylosowanymi punktami krzyżowania) i uzupełnieniu brakujących genów w kolejności ich występowania u drugiego z rodziców. Z rodziców: R1 = (1, 2, 3 | 4, 5, 6, 7 | 8, 9) R2 = (2, 4, 1 | 7, 8, 3, 9 | 5, 6) Powstają: P1 = (1, 2, 3 | 4, 7, 5, 6 | 8, 9) P2 = (2, 4, 1 | 3, 7, 8, 9 | 5, 6)
Mutacja - reprezentacja permutacyjna Wykonywana na całych chromosomach (a nie na genach jak w repr. binarnej) - mutowane średnio p_mut osobników (a nie genów)
Typy mutacji: 1) Mutacja typu Zamień (ang. Swap) - zamiana miejscami dwóch losowo wybranych genów pochodzących z dwóch różnych pozycji (1, 2, 3, 4, 7, 5, 6, 8, 9) (1, 2, 3, 6, 7, 5, 4, 8, 9) 2) Mutacja typ Zamień sąsiednie (ang. Swap adjacent) - zamiana miejscami dwóch losowo wybranych sąsiednich genów (1, 2, 3, 4, 7, 5, 6, 8, 9) (1, 2, 3, 7, 4, 5, 6, 8, 9) 3) Mutacja typu Wstaw (ang. Insert) – wstawienie losowo wybranego genu w losowo wygenerowaną pozycję (1, 2, 3, 4, 7, 5, 6, 8, 9) (1, 2, 6, 3, 4, 7, 5, 8, 9) 4) Inwersja - odwrócenie fragmentu chromosomu (1, 2, 3, 4, 7, 5, 6, 8, 9) (1, 2, 3, 6, 5, 7, 4, 8, 9)
Cechy algorytmów genetycznych 1) nie przetwarzają bezpośrednio parametrów zadania lecz ich postać zakodowaną
2) prowadzą poszukiwania korzystając z wielu rozwiązań (populacji), a nie jednego jak np. algorytmy symulowanego wyżarzania czy tabu search 3) stosują techniki przeszukiwania przestrzeni rozwiązań: jednoargumentowe (mutacja, inwersja), wieloargumentowe (krzyżowanie) 4) korzystają z przekształconej funkcji celu (najczęściej nieujemnej maksymalizowanej funkcji przystosowania)
5) stosują probabilistyczne, a nie deterministyczne reguły wyboru rozwiązań 6) nie gwarantują znalezienia optimum globalnego, jednak znajdują rozwiązania wystarczająco dobre w akceptowalnym czasie 7) znajdują zastosowanie tam, gdzie nie jest znany sposób dokładnego rozwiązania problemu (zbyt długi czas działania alg. wyczerpującego, dokładnego), ale znany jest sposób oceny jakości rozwiązania (funkcja oceny) 8) przydatne dla problemów, dla których nie istnieją techniki specjalizowane. Gdy techniki takie istnieją, można osiągnąć poprawę ich działania poprzez ich połączenie z AG 9) uniwersalność – użycie AG dla innego problemu jest możliwe często po zmianie jedynie funkcji celu, czasem kodowania
AG – słabe strony 1) Metoda jest uniwersalna, wiec nie tak skuteczna, jak algorytmy specjalizowane 2) Dobre wyniki jedynie przy prawidłowym zakodowaniu problemu i odpowiednim dobraniu funkcji celu. 3) Dobór parametrów mutacji i krzyżowania – trudny, wymaga eksperymentów 4) AG jest algorytmem zrandomizowanym, więc nie ma pewności znalezienia rozwiązania optymalnego, czasem „pechowe” rozwiązania o niskiej jakości

Schemat blokowy GA