Większość rzeczywistych zastosowań metod ewolucyjnych nie ogranicza się do zastosowania klasycznego, binarnego algorytmu genetycznego. Niniejszy rozdział poświęcony jest metodom ewolucyjnym wykorzystującym metody kodowania lepiej dostosowane do specyfiki rozwiązywanego problemu. Omówione też zostaną metody łączenia algorytmów ewolucyjnych z prostymi, skutecznymi heurystykami i wykorzystanie mechanizmów ewolucji do tworzenia programów.
Algorytmy ewolucyjne zaliczane są do grupy tzw. metaheurystyk, czyli uniwersalnych metod rozwiązywania szerokiej klasy problemów. Ceną za ich uniwersalność są często gorsze wyniki niż te uzyskiwane przez specjalizowane algorytmy zaprojektowane do określonego zadania. Jeśli np. funkcja celu jest liniowa, algorytm genetyczny działa skutecznie, jednak jeszcze skuteczniejszą i szybszą metodą jest określenie optymalnej wartości każdego bitu z osobna; podobnie np. sortowanie łatwiej wykonać specjalizowanym algorytmem niż algorytmem genetycznym (choć to ostatnie też jest możliwe).
Lekarstwem na - szkodliwą z punktu widzenia skuteczności - nadmierną uniwersalność algorytmów ewolucyjnych jest:
Spośród wielu możliwych metod ewolucyjnych, zaprezentowany na poprzednich wykładach algorytm genetyczny jest najczęściej przytaczany i analizowany. Decydują o tym głównie jego prostota i względy historyczne. Z drugiej jednak strony, jak wykazują badania, większość praktycznych zastosowań algorytmów ewolucyjnych opiera się na innych niż binarne sposobach kodowania. Zmiana sposobu kodowania (reprezentacji) punktów przestrzeni stanów może przybierać różne formy. Jednym z prostszych przykładów jest zastosowanie do przykładowych rozwiązań (np. do wektorów binarnie zakodowanych liczb) przekształcenia poprawiającego własności kodowania. Np. jeśli mamy zoptymalizować funkcję f(x,y) zdefiniowaną na pewnym kole, możemy albo dopuszczać (x,y) pochodzące z kwadratu zawierającego to koło (ale wówczas osobniki, które wyjda poza koło, muszą być eliminowane), albo zmienić parametryzację na biegunową (x,y) -> (a,r). W przypadku problemów kombinatorycznych wygodniej jest przechowywać w chromosomie np. permutacje, drzewa czy nawet bardziej złożone struktury, oczywiście odpowiednio modyfikując algorytmy krzyżowania i mutacji.
Jeżeli stosujemy nieklasyczne metody reprezentacji, powinniśmy ustalić operatory genetyczne tak, żeby miały pewne pożyteczne własności:
Kodowanie permutacji
W pewnych zastosowaniach kodowanie binarne jest mniej naturalne niż inne sposoby kodowania. Na przykład w problemie komiwojażera najwygodniej jest trasy przedstawiać jako permutacje miast, które są (bez żadnego dodatkowego przekodowania) traktowane jako chromosomy. Alternatywne rozwiązanie, w którym te permutacje kodujemy łańcuchami binarnymi, jest trudniejsze i kosztowniejsze.
Algorytm genetyczny może działać bezpośrednio na osobnikach złożonych z permutacji. Nasz chromosom będzie składał się z kolejnych liczb od 1 do n, bez powtórzeń, np. {1,6,3,4,5,2}. Jedyny problem stanowią operatory genetyczne (mutacja i krzyżowanie): należy je tak zaprojektować, by zawsze w wyniku dawały legalną permutację. Próba bezpośredniego zastosowania operatorów binarnych skończyłaby się tym, że np. z osobnika {1,2,3,4} i {2,4,1,3} w wyniku krzyżowania powstałby nieprawidłowy osobnik {1,2,1,3}.
Mutacja w przypadku algorytmów genetycznych z kodowaniem permutacyjnym polega na wykonaniu losowej transpozycji genów, czyli wybraniu losowej pary pozycji i zamianie leżących tam wartości:
W przypadku kodowania permutacji nie jest możliwe użycie klasycznego operatora krzyżowania (wynik krzyżowania nie byłby zwykle permutacją). W literaturze opisano kilka różnych metod krzyżowania, których skuteczność zastosowania zależna jest od problemu; są to np. PMX (Partially Matched Crossover), CX (Cycle Crossover), OX (Order Crossover), UOX (Uniform Order-based Crossover). Skupimy się na jednej z wersji algorytmu OX, gdyż jest to jedna z najprostszych metod. W pierwszym kroku losowane jest położenie sekcji dopasowania (jednakowej w obu osobnikach), przy czym początek sekcji dopasowania jest ustalony na początku chromosomu. Następnie sekcje dopasowania obu osobników rodzicielskich pozostawiane są bez zmian, natomiast pozostałe części chromosomów przekształcane są tak, by występujące w nich wartości liczbowe ustawione były w takiej kolejności, w jakiej występowały przed krzyżowaniem u drugiego osobnika rodzicielskiego:
Załóżmy, że dla rozważanego przez nas problemu istnieje wydajny, deterministyczny algorytm przybliżony (heurystyczny). Algorytmy takie, często oparte na schemacie zachłannym, dają zwykle tylko jeden wynik (nieoptymalny), ale za to działają szybko i wykorzystują naszą wiedzę o naturze problemu. Zaletą algorytmów ewolucyjnych jest z kolei niedeterminizm działania: jeśli poczekamy dłużej na wynik, będzie on lepszy. Jeśli da się szybki algorytm heurystyczny sparametryzować tak, by w zależności od pewnych parametrów wejściowych dawał różne (a przy tym dość dobre) wyniki, możemy zalety tych dwóch podejść połączyć w rozwiązaniu hybrydowym. Powinniśmy tylko upewnić się, że zawsze istnieje taki zestaw parametrów wejściowych dla części heurystycznej, by w wyniku mogło powstać rozwiązanie optymalne (zadanie znalezienia takich parametrów pozostawimy algorytmowi ewolucyjnemu).
Przykład - minimalne pokrycie krawędziowe grafu.
Znaleźć w danym grafie G=(V,E) taki minimalny zbiór wierzchołków, aby każda krawędź w grafie stykała się z przynajmniej jednym z wybranych wierzchołków.
Jak wiadomo, jest to problem NP-trudny. Algorytm heurystyczny poszukujący pokrycia krawędziowego w grafie może działać następująco: rozpoczynamy od wylosowania kolejności badania wierzchołków, a potem dołączamy je kolejno do pokrycia (o ile nowy wierzchołek pokrywa którąkolwiek niepokrytą krawędź) - por. przykład poniżej.
Powyższy algorytm generuje zwykle niewielkie pokrycie (zwłaszcza w wersji zachłannej, gdy rozpoczynamy od wierzchołków mających najwięcej wychodzących krawędzi). O tym, czy pokrycie to jest minimalne globalnie, decyduje kolejność wybierania wierzchołków. Warto zauważyć, że dla dowolnego lokalnie minimalnego pokrycia istnieje permutacja do niego prowadząca - jest to permutacja odwiedzająca na początku te wierzchołki, które należą do docelowego pokrycia.
Algorytm hybrydowy oparty na tej heurystyce zawiera algorytm genetyczny, którego osobniki są permutacjami wierzchołków grafu. Permutacja taka oceniana jest poprzez uruchomienie powyższego algorytmu heurystycznego i rozpatrywanie wierzchołków w kolejności zgodnej z daną permutacją. Oceną permutacji jest jakość pokrycia uzyskanego po zatrzymaniu się algorytmu - w tym przypadku, ponieważ zależy nam na jak najmniejszym pokryciu, może to być f(x)=N-px, gdzie N to liczba wierzchołków grafu, px to liczba wierzchołków pokrycia znalezionego przez algorytm heurystyczny przy permutacji x. Ewolucja powinna spowodować pojawienie się osobników (permutacji) dających wysokie wartości funkcji celu, a więc generujących małe pokrycia.
Zaletą algorytmów hybrydowych jest to, że każdy rozpatrywany osobnik jest dobrym, spełniającym warunki zadania rozwiązaniem (np. pokryciem krawędziowym grafu). Dalsza ewolucja oznacza przeszukiwanie zbioru dobrych rozwiązań w celu znalezienia najlepszego, przy czym zawsze (nawet w pierwszym kroku) możemy przerwać poszukiwania i wykorzystać znalezione rozwiązania. Gdybysmy użyli w problemie pokrycia grafu kodowania binarnego (klasycznego algorytmu genetycznego), gdzie jeden bit oznacza jeden wierzchołek obecny lub nieobecny w pokryciu, to okazałoby się, że wiele ciągów zerojedynkowych koduje zbiory nie będące pokryciami.
Wadą algorytmów hybrydowych jest ich zwykle dłuższy czas działania. W jednym kroku musimy nie tylko przepowadzić selekcję, uruchomic mutację i krzyżowanie, ale też wielokrotnie uruchamiać dodatkowy algorytm heurystyczny, by policzyć funkcję dopasowania.
Zaprezentowany w poprzednim rozdziale algorytm hybrydowy stanowi pewien przełom metodologiczny, w porównaniu z klasycznym algorytmem genetycznym. O ile ten ostatni po prostu szukał rozwiązania problemu, o tyle metody hybrydowe szukają raczej przepisu (algorytmu) uzyskania rozwiązania. Najprostszym przykładem takiego przepisu jest permutacja z przykładu powyżej. W podobnym kierunku idą zastosowania związane z projektowaniem strategii, których przykład będzie tematem niniejszego rozdziału, a jeszcze dalej - programowanie genetyczne (omówione w jednym z następnych rozdziałów), w którym kod genetyczny to po prostu zapis pewnego algorytmu (programu) w prostym języku.
Przykład - dylemat więźnia (iterowany)
W więzieniu siedzi (w osobnych celach) dwóch uczestników napadu na bank. Każdy z nich ma podczas przesłuchania do wyboru dwie strategie: wyprzeć się wszystkiego lub obciążyć całą winą towarzysza. Jeśli jeden z więźniów zdradzi drugiego, ten drugi dostanie 10 lat, a pierwszy wyjdzie na wolność jako świadek koronny. Jeśli obaj będą milczeć, dostaną po 2 lata za pomniejsze przestępstwa. Jeśli obaj zdradzą (przyznając się przy tym do winy), dostaną po 6 lat. Jak ma się zachować więzień?
Wersja iterowana: zakładamy, że z tym samym towarzyszem siedzimy w więzieniu po raz kolejny i pamiętamy, jak zachowywał się on (i my) podczas poprzednich pobytów.
Dylemat w tym przypadku polega na tym, że patrząc indywidualnie bardziej opłaca się zdradzić, natomiast wspólne działanie (milczenie z obu stron) pozwala na minimalizację ogólnej straty. Jednak nie mamy pewności, że milcząc (współpracując z kamratem) nie wystawimy się na kosztowną stratę, o ile kolega nas zdradzi. Jedna ze znanych (co nie oznacza - optymalna) strategii to "wet za wet": przy pierwszej okazji milczymy, przy każdej następnej - powtarzamy zachowanie kolegi z poprzedniego razu. Jak algorytm genetyczny może pomóc w szukaniu innych strategii?
Strategia to przepis (algorytm) mówiący, jak się zachować w dowolnej sytuacji, jaka może się zdarzyć w grze. W naszym przypadku jest to funkcja, która na wejściu dostaje historię poprzednich przypadków, a na wyjściu daje odpowiedź "zdrada"/"współpraca", oznaczającą zalecane zachowanie. Załóżmy, że pamiętamy ostatnie dwie "gry" w postaci dwóch par złożonych z symboli "z" i "w" (np. "zw" = ja zdradziłem, partner milczał). Wszystkich możliwych historii (np. "zw zz") jest 16. Do tego dochodzą 4 możliwości w przypadku, gdy gra toczy się dopiero jedną rundę, oraz dodatkowy przypadek mówiący, że właśnie zaczynamy grę. Łącznie w grze może wystąpić 21 różnych historii i dla każdej z nich musimy określić, jak zachowamy się tym razem.
Nasza strategia to 21 reguł postaci “zw zz => z”, “ww ww => w” itp. Da się ją zakodować na 21 bitach (same prawe strony reguł, gdyż lewe zawsze są ustalone). Wystarczy więc znaleźć optymalny łańcuch 21 bitów, interpretowany jako strategia postępowania - wystarczy zastosować do tego klasyczny algorytm genetyczny.
Jedyna konieczna modyfikacja związana jest z selekcją osobników. Zamiast klasycznej funkcji przystosowania możemy w celu oceny osobników urządzić turniej w ramach populacji (gra "każdy z każdym", po kilka-kilkanascie rozgrywek dla każdej pary). Jako wartość osobnika bierzemy sumę punktów zdobytych w turnieju, liczoną jako np. odwrotność całkowitego czasu spędzonego w więzieniu.
Powyższy schemat może być stosowany do wielu najprostszych gier, jednak bardziej skomplikowane zwykle miewają zbyt wiele możliwych sytuacji, aby dało się zastosować algorytm genetyczny. Np. w przypadku gry w go możemy oszacować liczbę sytuacji na planszy jako 3361 (pole może być zajęte przez pionek biały lub czarny lub być puste; gra odbywa się na planszy 19x19).
Oprócz prostych ciągów binarnych i bardziej skomplikowanych struktur kombinatorycznych, zawartość chromosomu mogą stanowić programy komputerowe. Oczywiście wiele jeszcze nam brakuje do sytuacji, w której nowe oprogramowanie konsumenckie bedzie hodowane, a nie pisane, jednakże w pewnych najprostszych sytuacjach ewolucyjne (samoistne) tworzenie programów jest realne. Warunkiem jest odpowiednie ograniczenie składni i wielkości programu, a także możliwość eksperymentalnego zbadania jego skuteczności.
Przykład: napisać program działania automatu mobilnego wyposażonego w czujniki i urządzenia wyjściowe, którego zadaniem będzie przejście labiryntu. Automat może dodatkowo mieć pewne rejestry wewnętrzne (pamięć) zapamiętujące informacje pomocnicze. Dopuszczalny język programowania robota ma strukturę drzewa, w którym polecenia wykonujemy poczynając od korzenia. Liście drzewa zawierają komendy do wykonania lub predykaty (testy do przeprowadzenia):
Węzły drzewa stanowią instrukcje sterujące wykonaniem programu. Gdy program dochodzi do węzła, wykonuje kolejno instrukcje w wychodzących z niego gałęziach. Sposób ich wykonania zależny jest od rodzaju węzła:
Zadaniem algorytmu programowania genetycznego jest stworzenie programu - dozwolonej składniowo kombinacji (w postaci drzewa) operacji i warunków. Ocena osobnika (programu) polega na symulacji jego działania w danym środowisku testowym. W przypadku opisywanego robota byłby to zestaw (możliwie szeroki) losowo wygenerowanych labiryntów, w których testowany osobnik byłby kolejno umieszczany. Następnie przeprowadzamy symulację i badamy, jak dalego od wyjścia był robot po np. 1000 krokach programu. Wynik ten traktujemy jako wartość funkcji celu.
Opisany powyżej przykład to tylko jeden z licznych możliwych sposobów kodowania. W praktyce każdy problem wymaga indywidualnego podejścia, zaprojektowania dopuszczalnego języka, nierzadko też specjalnych operatorów genetycznych. Inne przykłady problemów i sposobów kodowania:
Operatory genetyczne przypadku programowania genetycznego są bardzo różnorodne i zwykle dopasowane do specyfiki problemu. Mutacje to zwykle losowe zmiany treści węzła, zamiana liścia na węzeł z dalszymi odgałęzieniami, skasowanie fragmentu drzewa lub dodanie losowego poddrzewa, a nawet zdefiniowanie pewnego fragmentu drzewa jako nowej, nazwanej funkcji (podprogramu) i wykorzystywanie jej w innych osobnikach. Krzyżowanie polega najczęściej na zamianie miejscami losowo wybranych węzłów z osobników rodzicielskich, razem z odpowiednimi poddrzewami.
Programowanie genetyczne zwykle wiąże się z symulacją wygenerowanego programu i oceną skutków jego działania. Jest to proces czasochłonny. Dodatkowo, ze względu na znaczny stopień skomplikowania osobników, typowa wielkość populacji to kilka tysięcy sztuk. Wszystko to sprawia, że programowanie genetyczne wymaga ogromnych mocy obliczeniowych - systemy wykorzystywane w praktyce nierzadko składają się z klastra komputerów pracującego przez wiele dni nad jednym problemem. Tak jest np. w przypadku opisanego wyżej symulatora układów elektronicznych, za pomocą którego opracowano i opatentowano już kilka nowatorskich rozwiązań.
Przedstawiono metody ewolucyjne, w których ewolucji nie podlega wprost przykładowe rozwiązanie pewnego problemu, a raczej przepis (algorytm) na jego osiągnięcie. Metody hybrydowe wykorzystują proste heurystyki, w szybki sposób rozwiązujące problemy kombinatoryczne, połączone z algorytmem genetycznym sterującym ich działaniem. Algorytmy kodowania stratategii i programowanie genetyczne to z kolei metody, w których pewne obiekty sterowane są zawartymi w genach algorytmami i muszą poradzić sobie w zmieniającym się otoczeniu, a ocena osobnika polega na symulacji jego działania lub interakcji z innymi osobnikami.
Zalecana literatura:
algorytm hybrydowy - połączenie algorytmu heurystycznego (np. zachłannego) z algorytmem genetycznym ustalającym parametry części heurystycznej
kodowanie permutacji - w przypadku algorytmu genetycznego: metoda polegająca na tym, że chromosomem danego osobnika jest permutacja. Mutacja i krzyżowanie tak zbudowanych osobników wymaga użycia specjalnych operatorów.
metaheurystyka - ogólny schemat konstruowania metod optymalizacji, uniwersalny dla wielu różnych problemów; np. algoryty ewolucyjne
programowanie genetyczne - algorytm ewolucyjny, w którym osobniki opisane są chromosomami zawierającymi program (zwykle w uproszczonym języku, w formie drzewa) lub inną złożoną strukturę, np. wyrażenie logiczne; ocena osobnika polega na symulacji zastosowania programu w zmiennym środowisku testowym
strategia - sposób postępowania, funkcja która każdej sytuacji przypisuje decyzję odnośnie dalszego działania; np. funkcja wskazująca dla każdej możliwej sytuacji na planszy sposób wykonania kolejnego posunięcia
12.1. Sprawdzić, czy warunki, jakie powinien spełniać operator mutacji i krzyżowania (opisane na końcu pierwszego rozdziału), są spełnione przez klasyczne (binarne) operatory genetyczne.
12.2. Jak można efektywnie zakodować strategię gry w kółko i krzyżyk?