Nasza Loteria SR - pasek na kartach artykułów

Algorytmy genetyczne, czyli jak stworzyć w komputerze sztuczną ewolucję

profesor Ryszard Tadeusiewicz
Prof. Ryszard Tadeusiewicz
Prof. Ryszard Tadeusiewicz fot. archiwum
Pełny tytuł tego felietonu powinien brzmieć: "Masz problem? Zamiast się z nim zmagać, wyhoduj sobie rozwiązanie!". Jednak tak długiego nagłówka niepodobna umieścić w "Gazecie", dlatego wybrałem z niego najistotniejszą część, mając nadzieję, że Czytelnicy zechcą sprawdzić, o co chodzi z tą hodowlą i dzięki temu poznają kolejną ciekawostkę związaną ze sztuczną inteligencją.

Ciekawostką tą są metody związane z programowaniem ewolucyjnym, którego najpowszechniej używaną postacią są tak zwane algorytmy genetyczne. Istotą tych metod jest stworzenie w komputerze sztucznej ewolucji, w której poszczególne programy rozwiązujące postawione zadanie traktowane są jako "osobniki". Każdy osobnik (tę nazwę będziemy dalej pisać bez cudzysłowu, ale stale mamy świadomość, że chodzi w istocie o programy w komputerze) ma sobie właściwy sposób rozwiązywania problemu sformułowanego przez użytkownika, przy czym zasadnicze elementy tego sposobu działania osobnika zawarte są w jego "chromosomie", najczęściej mającym formę wektora binarnego, czyli długiego napisu umieszczonego w pamięci komputera i zawierającego tylko zera lub jedynki. Szczegóły zależne są oczywiście od rozwiązywanego zadania, ale na ogół jest tak, że "0" oznacza, iż dany program nie ma jakiejś właściwości, a "1" wskazuje, że tę cechę posiada.

Osobniki te rywalizują z sobą, a miarą sukcesu ewolucyjnego jest sprawność rozwiązywania postawionego zadania. Te osobniki, które rozwiązują zadanie lepiej, mają większą szansę, by wydać potomstwo, przy czym (UWAGA! dalszego ciągu nie powinny czytać dzieci poniżej 18 lat!) owo rozmnażanie ma charakter seksualny. Okazuje się, że to jest najlepszy sposób rozmnażania także w przypadku osobników bytujących wyłącznie w komputerze i żyjących z tego, że rozwiązują jakieś postawione przez użytkownika zadanie!

Modelowane w komputerze osobniki łączą się w pary na zasadzie losowej, przy czym o tym, kto się z kim skrzyżuje (i ile razy) decyduje mechanizm ruletki. Na kole ruletki każdy osobnik ma tym więcej sektorów (a więc tym większą szansę wygrania i spłodzenia "potomka") im lepiej rozwiązywał postawione zadanie. Oznacza to, że najwięcej potomków będą miały najskuteczniejsze osobniki.
Wylosowane osobniki łączą się w pary i wymieniają swój materiał genetyczny (fragmenty opisanych wyżej chromosomów), w wyniku czego powstaje osobnik mający część cech odziedziczonych po jednym z rodziców, a część po drugim. Dodatkowo w ten proces czasami (ale rzadko!) ingeruje mutacja, to znaczy przypadkowa zmiana chromosomu, powodująca, że potomek może mieć cechę, której nie obserwowano u żadnego z rodziców.

Po wydaniu potomstwa pokolenie rodziców wymiera (niektórzy bezpotomnie, a inni pozostawiając po sobie licznych, na ogół silnie zróżnicowanych potomków) - i cały cykl zaczyna się od nowa.
Proces sztucznej ewolucji rozpoczyna się od utworzenia populacji początkowej zawierającej osobniki, których chromosomy zawierają całkiem przypadkowe zestawy 0 i 1. Każdy osobnik ma inny chromosom, więc taka populacja próbuje rozwiązywać postawiony problem na bardzo wiele różnych sposobów. Na początku większość tych sposobów jest bez sensu, w wyniku czego odpowiednie osobniki szybko wymierają. Niektóre jednak rozwiązują rozważany problem sensownie, więc to głównie ich chromosomy podlegają losowym mutacjom i krzyżują się między sobą. Dzięki temu każda korzystna cecha jest w toku tej ewolucji wydobywana i dodatkowo doskonalona. Po pewnym czasie przerywamy tę hodowlę i bierzemy najlepszego osobnika z populacji. Dla ogromnej liczby zadań jest to bardzo skuteczna metoda znajdowania najlepszego rozwiązania, a jednocześnie jest raczej łatwa do zastosowania, więc opisane tu metody cieszą się sporym powodzeniem.

Algorytm genetyczny jest zależny od wielu czynników losowych (chromosomy w populacji początkowej, dobór osobników rodzicielskich, mutacje itd.), więc rozwiązania uzyskiwane w kolejnych przebiegach różnią się od siebie. Nie zawsze są to niewielkie rozbieżności, często może pojawić się kilka całkowicie odmiennych rozwiązań. Takie zjawisko sygnalizuje, że rozważane zagadnienie ma więcej niż jedno rozwiązanie. Klasyczny algorytm genetyczny tymczasem zmierza zawsze w kierunku tylko jednego z rozwiązań, a inne warianty są z populacji wypierane. Pojawia się zatem potrzeba takiej modyfikacji algorytmu genetycz- nego, aby było możliwe jednoczesne poszukiwanie różnych wariantów rozwiązania. Najprostsze podejście polega na zastosowaniu modelu wyspowego: populacja zostaje podzielona na ustalone podpopulacje, które ewoluują oddzielnie. Co jakiś czas dopuszczone jest krzyżowanie się osobników pochodzących z różnych podpopulacji (osobnik przepłynął na sąsiednią wyspę w poszukiwaniu żony). Efektem działania takiego genetycznego algorytmu wyspowego będzie zatem zbiór rozwiązań, spośród których można wybrać to o najlepszej jakości.

Zobacz zdjęcia ślicznych Małopolanek! Wybierz z nami Miss Lata Małopolski 2011!

Głosuj na najlepsze schronisko Małopolski

Mieszkania Kraków. Zobacz nowy serwis

Codziennie rano najświeższe informacje z Krakowa prosto na Twoją skrzynkę e-mail. Zapisz się do newslettera!

Dołącz do nas na Facebooku!

Publikujemy najciekawsze artykuły, wydarzenia i konkursy. Jesteśmy tam gdzie nasi czytelnicy!

Polub nas na Facebooku!

Dołącz do nas na X!

Codziennie informujemy o ciekawostkach i aktualnych wydarzeniach.

Obserwuj nas na X!

Kontakt z redakcją

Byłeś świadkiem ważnego zdarzenia? Widziałeś coś interesującego? Zrobiłeś ciekawe zdjęcie lub wideo?

Napisz do nas!
Wróć na gazetakrakowska.pl Gazeta Krakowska