Następna grupa metod sztucznej inteligencji - algorytmy ewolucyjne

Obrazek anonsujący ten wpis nawiązuje do metafory, przyjętej we wszystkich moich wpisach z tej serii, według której, że opisywane metody sztucznej inteligencji są przedstawiane jako wyspy. Postanowiłem przyjąć taką metaforę, bo poszczególne metody sztucznej inteligencji są od siebie wzajemnie izolowane. Nie da się łatwo przejść od jednej grupy metod do drugiej, więc całość dziedziny sztucznej inteligencji przypomina archipelag - i tak właśnie jest tu omawiana. W poprzednich wpisach udawało mi się znaleźć właściwe zdjęcia wysp, które pozwalały mi obrazowo zaprezentować najważniejsze cechy opisywanych grup metod sztucznej inteligencji. Z tym wpisem mi się to nie udało, bo nie znalazłem zdjęcia wyspy, która by się kojarzyła z ewolucją. Może ktoś z Czytelników mi coś podsunie?

Zrobiłem więc montaż dwóch rysunków, który od biedy można uznać za metaforę tego, że na pewnej wyspie zaszła ewolucja - od dinozaura do człowieka. Ale zadowolony z tego obrazka nie jestem...

Metafora metaforą, ale przejdźmy do konkretów. Specjaliści sztucznej inteligencji działają na dwa sposoby: jedni usiłują całkiem sami wykreować narzędzia informatyczne pozwalające komputerom na inteligentne zachowanie, natomiast drudzy chętnie podglądają Naturę i tworzą swoje systemy skwapliwie naśladując występujące w niej inteligentne obiekty, albo procesy, które same z siebie inteligentne nie są, ale prowadzą do takich wyników, jakie moglibyśmy uzyskać za pomocą inteligentnych programów. Niniejszy wpis dotyczy takiego właśnie "zapożyczenia": naśladowania w systemach informatycznych naturalnego procesu ewolucji. Procesu tego nie będę próbował tu opisywać, bo to złożona i miejscami kontrowersyjna materia, opowiem natomiast o tym, co informatycy "wyciągają" z wiedzy o naturalnej ewolucji i jakie uzyskują wyniki.

Zwolennicy algorytmów ewolucyjnych doszli już dość dawno do wniosku, że zamiast samemu pracowicie poszukiwać najlepszego rozwiązania problemu informatycznego - lepiej pozwolić, żeby komputer sam sobie to rozwiązanie wyhodował! Rozwiązania "hodowane" przez komputer podlegają przy tym doskonaleniu w wyniku procesu automatycznej ewolucji, przy czym często się zdarza, ze rozwiązanie uzyskane na drodze takiej sztucznej ewolucji (symbolizowanej na rysunku przez uproszczony fragment odcinka DNA) jest lepsze, niż rozwiązanie, które by potrafił wymyślić człowiek.

Jak taką automatyczną ewolucję przeprowadzić?

Pierwszą czynnością, jaką trzeba wykonać, jest opisanie poszukiwanego rozwiązania w postaci tak zwanego chromosomu. W biologii termin ten oznacza formę organizacji materiału genetycznego wewnątrz komórki, natomiast w algorytmach ewolucyjnych jest to łańcuch symboli opisujących poszczególne cechy składające się w sumie na poszukiwane rozwiązanie. Jeśli na przykład wyobrazimy sobie, że dla rozwiązania jakiegoś problemu trzeba dobrać 8 różnych cech i z każdą z tych cech związana jest decyzja, czy dana cecha w rozwiązaniu ma wystąpić, czy nie - to chromosom będzie miał postać łańcucha 8 pozycji binarnych, gdzie wpisanie jedynki oznacza, że w rozważanym rozwiązaniu cecha ta ma występować, a wpisanie zera oznacza, że dana cecha w rozwiązaniu występować nie powinna.

W pokazanym wyżej przykładzie cechy miały charakter binarny - występowały, lub nie. Jednak w praktycznych zastosowaniach algorytmów ewolucyjnych rozważa się także sytuacje, gdy cecha może mieć wiele wartości, z których trzeba wybrać jedną. Brane są pod uwagę także sytuacje, gdy cecha może być liczbą, której najlepszą wartość trzeba wskazać.

Abstrakcyjne mówienie o cechach jakichś ogólnych rozwiązań jest trochę niewygodne, więc wprowadźmy poglądowy przykład. Wyobraźmy sobie, że poszukujemy kształtu ryby najlepiej dostosowanej do konkretnego środowiska. Ja wiem, że Przyroda ten problem rozwiązała przed milionami lat, ale zabawmy się przez chwilę w kreatora nowych gatunków ryb i wyobraźmy sobie, że mamy możliwość wybierania następujących cech tworzonej ryby (podaję także symbole, które będą kodowały określone decyzje dotyczące wybranej wartości rozważanej cechy):

- kształtu (P - podłużny, O - okrągły)
- ogona (M - mały, D - duży)
- koloru (C - czerwony, N - niebieski, Z - zielony, żółty)
- obecności lub braku dolnych płetw - (T - są, N - brak)
- obecności lub braku górnych płetw - (T - są, N - brak)
- obecności lub braku zębów - (T - są, N - brak)
- obecności lub braku wąsów - (T - są, N - brak)

Dla podkreślenia analogii między informatycznymi metodami ewolucyjnymi a ewolucją biologiczną poszczególne cechy nazywamy genami, chociaż oczywiście w biologii geny wyglądają inaczej.

Obejrzyjmy to na obrazku pokazującym, jak określona zawartość chromosomu determinuje wygląd zdefiniowanej ryby.

Uwaga: rysunek powyższy (i kilka dalszych) pochodzi z popularnego artykułu na temat algorytmów genetycznych, zamieszczonego wiele lat temu w jakimś czasopiśmie - chyba w "Świecie Nauki". Niestety robiąc dla potrzeb dydaktycznych kopie tych rysunków, nie zarejestrowałem nazwiska autora i tytułu pracy. A szkoda, bo rysunki są bardzo fajne, więc uhonorowanie trudu i talentu rysownika byłoby ze wszech miar właściwe. Gdyby zatem ktoś z PT Czytelników rozpoznał te obrazki i mógł mi wskazać informacje na temat ich źródła - to z przyjemnością wskażę tu właściwego autora, nie chcę bowiem udawać, że sam to wymyśliłem i narysowałem :-) .

Wracając do opisu algorytmu ewolucyjnego zaczniemy opis jego działania od czynności, która inicjuje większość podobnych algorytmów - mianowicie stworzenia pierwszej losowej populacji. W celu jej stworzenia generujemy pewną liczbę chromosomów z losowo wybieranymi genami. Takie przykładowe losowo stworzone chromosomy skojarzymy z odpowiadającymi im kształtami ryb - i w ten sposób powstanie pierwsze pokolenie rozważanej populacji.

Ryby każdego pokolenia podlegają ocenie. W populacji ryb kryterium oceny mogłaby być ilość zdobytego pożywienia, ale przypominam, że przykład z rybami to tylko zabawa. W rzeczywistych algorytmach ewolucyjnych "osobnikami" są różne rozwiązania postawionego problemu, przy czym zwykle można ustalić, jak dobre są poszczególne rozwiązania (na przykład, jaki zysk otrzymujemy przy wybraniu takich, a nie innych wartości rozważanych cech).

Istota ewolucji polega na tym, że osobniki które uzyskały wyższą ocenę, mają większą szansę na "spłodzenie" potomstwa. Zwykle realizuje się to w następujący sposób. Wyobrażamy sobie mechanizm losujący w postaci "ruletki". Na kole tej "ruletki" wydziela się dla poszczególnych "osobników" sektory - tym większe, im wyższą ocenę dany "osobnik" zdobył. Na pokazanym niżej rysunku widać, że w rozważanym przykładzie największy sukces odniosła ryba w kolorze zielonym, więc jej sektor jest największy. Dwa dalsze miejsca zajęły dwie ryby w kolorze czerwonym. Ale nawet największy "nieudacznik" - ryba w kolorze żółtym - jakiś tam swój sektor ma. Niewielki, ale jednak niezerowy!

Chcąc wylosować osobnika do rozrodu uruchamia się koło ruletki, które wiruje coraz wolniej, aż wreszcie zatrzymuje się. Po zatrzymaniu koła wskaźnik typowania osobnika pokazuje na sektor przypisany do jakiegoś konkretnego "osobnika" - i to on zostaje "ojcem". Kolejne losowanie wytypuje "matkę" - i te dwa wybrane osobniki spłodzą potomków.

Łatwo się domyślić, że szanse na zostanie "ojcem" czy "matką" mają głównie te "osobniki", które miały wysokie oceny. Ale ci z mniejszymi sukcesami też nie są całkiem bez szans...

Płodzenie potomka polega w algorytmach ewolucyjnych na wymieszaniu genów pochodzących od "matki" i "ojca". Zwykle odbywa się to tak, że na chromosomie wyznacza się (losowo) miejsce przecięcia i jedno z "dzieci" otrzymuje pierwszą część chromosomu "matki" i drugą część chromosomu "ojca" - a drugie "dziecko" otrzymuje pozostałe dwie części. Ilustruje to rysunek.

Obejrzyjmy także, jak to może wyglądać w rozważanym przykładzie z rybami.

Obok losowego wyłaniania "rodziców" dla kolejnego "pokolenia osobników" oraz losowego mieszania ich genów, w algorytmie ewolucyjnym działa dodatkowy mechanizm, jakim jest mutacja. Dzięki niej osobnik potomny może mieć cechę, jakiej nie miał żaden z jego osobników rodzicielskich, ani nawet żaden z osobników poprzedniego pokolenia. W przytaczanym tu przykładzie żadna ryba z pierwszego pokolenia nie miała wąsów. A tymczasem u potomka jednej pary rodzicielskiej takie wąsy się pojawiły, bo nastąpiła mutacja (losowa zmiana wartości) jednego genu!

Jeśli ten zmutowany osobnik osiągnie wysokie oceny - to zapewne przekaże tę nową cechę swemu potomstwu. Ale jeśli mutant będzie źle przystosowany - to zginie bezpotomnie, bo w kolejnym pokoleniu dokonywana jest także selekcja premiująca najlepiej przystosowanych osobników i eliminująca tych przystosowanych źle.

Celem stosowania algorytmów ewolucyjnych jest poszukiwanie najlepszego rozwiązania jakiegoś problemu. Obserwując przebieg sztucznej ewolucji, pokazany na rysunku poniżej, widzimy, że w kolejnych pokoleniach uzyskiwana jakość rozwiązania jest coraz lepsza, chociaż wyniki poszczególnych osobników (oznaczone kółkami) w każdym pokoleniu są mocno zróżnicowane. Widać też "wymieranie" niektórych osobników (strzałki kończące się znakiem #).

Gdy proces sztucznej ewolucji wyczerpie swoje możliwości i przestanie dostarczać w kolejnych pokoleniach coraz lepszych rozwiązań - należy go przerwać. Zwykle najlepsze rozwiązanie uzyskane tą drogą jest już użyteczne w praktyce. Gdy jest inaczej, to nie ma rady - trzeba poszukać innej metody ...