Algorytmy Genetyczne

Czym tak właściwie jest algorytm genetyczny?

Aby odpowiedzieć na to pytanie, musimy najpierw wiedzieć co to algorytm. Algorytm to zestaw czynności konieczny do rozwiązania jakiegoś problemu lub osiągnięcia konkretnego celu. Algorytm genetyczny jest to metoda optymalizacji bazująca na zasadach genetyki i selekcji naturalnej. Stara się on upodobnić do ludzkiej ewolucji. Z każdą następną generacją staje się bardziej zbliżony do swojego celu i daje nam lepsze wyniki.

Zasada działania

Inicjacja początkowej populacji osobników

Ocena każdego z osobników

Selekcja najlepszych osobników

Krzyżowanie osobników i mutacja

Wracamy do punktu nr. 2

Inicjalizacja

Zadaniem naszego algorytmu będzie znalezienie drogi pomiędzy miastami, tak aby pierwsze miasto było startem i końcem podróży. Im krótsza droga tym lepiej.

Tworzymy początkową populację. Miasta w każdej z tras są ułożone losowo i nie mogą się powtarzać.

Ocena

Każda z tras zostaje oceniona. Sumowane są odległości między połączeniami miast. Dzięki temu wiemy, która z tras jest najkrótsza. W pierwszej generacji jako iż trasy tworzone są losowo efekty nie są zadawalające.

#	Nazwa Osobnika	Ocena (dystans w km)
1	Trasa 1	3821 km
2	Trasa 2	5213 km
3	Trasa 3	4853 km

Selekcja

Teraz gdy już wiemy jak nasze osobniki (trasy) wypadają, musimy wybrać te, które zostaną włączone do naszej grupy rozrodczej. Ważne aby wybrane zostały osobniki, które zostały ocenione jak najlepiej.

Mamy parę typów selekcji:

Metoda koła ruletki

Wyobraźmy sobie koło ruletki podzielone na wiele obszarów. Każdy z osobników dostaje własny obszar. Im lepiej wypada w ocenie tym większą część dostaje. Następnie kręcimy kołem. W zależności gdzie zatrzyma się wskaźnik, dany osobnik dostanie się do grupy rozrodczej. Dzięki temu lepsze osobniki mają większą szansę na ich wylosowanie.

Metoda turniejowa

Populacja dzielona jest na dowolnie liczne grupy. Następnie najlepsze osobniki z grup są wybierane. Proces jest powtarzany, aby wybrać następnego rodzica.

Metoda rankingowa

Osobniki układa się w ranking w zależności od ich oceny np. jak w konkursie. Do grupy rozrodczej wchodzi dana ilość najlepszych osobników. Ta metoda często jest używana gdy wszystkie osobniki z danej populacjii mają podobne wyniki.

Metoda losowa

Osobniki które wejdą do grupy rozrodczej są wybierane losowo. Ocena nie ma tu znaczenia. Ta metoda jest rzadko używana, przez jej małą efektywność.

Krzyżowanie

Krzyżowanie jest analogiczne do rozmnażania w biologii. Cechy obu rodziców mieszają się ze sobą, tym samym dając nam nowe pokolenie o wspólnych cechach. Weźmiemy losowy segment genów (miast) o losowej długości z osobnika 1, a resztę dopełnimy genami z osobnika 2, tak aby się nie powtórzyły.

Mutacja

Teraz gdy mamy nowo powstałe osobniki, powinny one mieć cechy wspólne rodziców. Jednak możemy ustalić współczynnik mutacji, który zmieni ich geny. Mutacja zapewnia różnorodność nowo powstałych osobników. W naszym przypadku mutacja zamieni pozycje 2 genów między sobą.

Powtarzanie

Proces zostaje powtórzony x razy. Jeśli algorytm został skonstruowany poprawnie, każde następne pokolenia dadzą nam lepsze efekty. Dla nas będzie to coraz krótsza droga.

Zakończenie działania

W pewnym momencie działania naszego algorytmu, musimy wiedzieć czy otrzymaliśmy najlepsze możliwe lub wystarczająco dobre rozwiązanie. Istnieje kilka metod zakańczania działania naszego algorytmu:

Nie ma żadnych popraw przez x generacji
Gdy osiągniemy maksymalną liczbę generacji
Gdy osiągniemy wcześniej zdefiniowaną wartość

Zastosowania

Teraz gdy wiemy już co to algorytmy genetyczne i jak działają, możemy zadać sobie pytanie - No dobra, ale jakie zastosowania mogą mieć w realnym świecie? - Otóż zastosowań w życiu codziennym jest multum, problemy te są zazwyczaj bardzo złożone.

Przykłady zastosowań algorytmów genetycznych w realnym świecie:

Planowanie i harmonogramowanie procesów przemysłowych

Problemy związane z harmonogramowaniem procesów przemysłowych, są zazwyczaj skomplikowane i trudne do rozwiązania. Algorytm przydziela zasoby do kolekcji zadań, określa kolejność wykonywanych czynności.

Robotyka

Algorytm genetyczny może tworzyć projekty robotów, szukać opytmalnych części do danego użytku. Dzięki algorytmowi możemy poznać nowe projekty robotów, które będą nam służyć w przyszłości.

Wyznaczanie trasy podróży

Tak jak pokazałem w części tłumaczącej zasadę działania algorytmów genetycznych, nasz algorytm może wyszukiwać optymalną trasę podróży. Dzięki temu unikniemy korków i dotrzemy najszybszą możliwą trasą do celu.

Jak możemy zauważyć, zastosowanie algorytmów genetycznych charakteryzuje się dużą różnorodnością. Poza przykładami które wymieniłem istnieje jeszcze wiele innych dziedzin, które wykorzystują algorytmy genetyczne m.in. medycyna, chemia, biotechnologia, branża gier komputerowych. Jedynym naszym ograniczeniem jest nasza wyobraźnia!