Algorytmy genetyczne

Konkurs Daj Się Poznać właśnie wystartował, więc skoro postanowiłem wziąć w nim udział, to należy Ci się obszerna informacja cóż takiego mam zamiar przygotować i o czym będę pisał przez następne 10 tygodni, a może i dłużej. Na pierwszy ogień idą algorytmy genetyczne!

W tym poście chciałbym dostarczyć Ci co nieco wiedzy na temat bardzo ciekawego zagadnienia jakim są algorytmy genetyczne, abyś już później mógł sprawnie się poruszać w bibliotece easyGALib i kolejnych informacjach na jej temat. Życzę miłej lektury!

Algorytmy genetyczne

W wielu dziedzinach życia staramy się naśladować naturę i efekty tego widzimy na co dzień, chociażby patrząc na nieustannie przelatujące nad naszymi głowami samoloty. Z drugiej strony można by pomyśleć, że najnowsze technologie, smartfony i inne komputery są dalekie od tej koncepcji, bo nic takiego w świecie przyrody nie widzimy – nic bardziej mylnego. Tendencja ta nie jest obca informatyce, gdzie znajdujemy takie wynalazki, jak algorytmy genetyczne, inteligencję roju, czy też systemy immunologiczne. Wszystkie z nich możemy ogólnie zakwalifikować jako algorytmy ewolucyjne, które charakteryzują się specyficznym podejściem do rozwiązania danego problemu, gdyż robią to za pomocą genów! Te z kolei zawarte są w populacji osobników, które w danym momencie mogą być lepiej bądź gorzej dopasowane do oczekiwanego wyniku. Zadaniem algorytmu genetycznego jest więc wybieranie najlepszych jednostek i takie ich modyfikowanie i łączenie, by kolejne generacje były lepsze od poprzednich. Ocenia to z kolei funkcja dopasowania, która liczbowo przedstawia jakość danej populacji, czy danego osobnika. Końcowo, jeżeli uzyskamy zadaną granicę działania algorytmu, zwracany jest najlepszy zestaw genów, który jest rozwiązaniem naszego problemu. Brzmi jak eksperymenty na małych i słodkich zwierzątkach? Wspaniale!

Zasada działania algorytmu genetycznego

Jak można obrazowo przedstawić zasadę działania takiego algorytmu? Najprościej będzie na takim oto schemacie blokowym:

Działanie zaczynamy od zakodowania osobnika. W tym miejscu musimy wybrać prostą i zrozumiałą prezentację naszego problemu, ale taką która będzie umożliwiać operacje na genach, np. krzyżowanie. Następnie następuje inicjalizacja populacji, po czym wybierane są osobniki o najlepszych genach. Przedstawiciele wybierani są przy pomocy kilku różnych metod, np. metody ruletki.

Kolejnym etapem działania algorytmu jest krzyżowanie, tj. łączenie osobników z poprzedniej generacji. Oczywiście nikt nie zagwarantuje nam lepszych wyników, lecz przy odpowiednio dobrej puli możemy liczyć na ich poprawienie, coś jak w teorii Darwina.

Następnie dokonywana jest mutacja, dzięki której możemy uniknąć zbyt wczesnego zatrzymania algorytmu, poprzez brak możliwości dojścia do oczekiwanego rezultatu. Można to porównać do zmian w genotypie człowieka na przestrzeni wieków, który umożliwił na przykład dostosowanie się do różnych warunków atmosferycznych otoczenia. Mutacja nie może być jednak zbyt silna, gdyż istnieje możliwość że uszkodzi poprawny genotyp.

Końcowo, tak jak pokazuje schemat, sprawdzamy czy populacja spełnia nasze oczekiwania dotyczące dopasowania i czy czasem nie osiągnęliśmy już zadanej maksymalnej ilości generacji, na której chcemy poprzestać obliczenia. W chwili gdy taka sytuacja następuje, nasz algorytm może zwracać najlepiej dopasowany osobnik.

Zalety i możliwości wykorzystania algorytmów genetycznych

Algorytmy genetyczne mają bardzo wiele zalet. Pierwszą z nich jest ich uniwersalność, gdyż możemy je ponownie wykorzystywać w różnych problemach, zmieniając jedynie obliczenia funkcji dopasowania. Co więcej, nie musimy znać danego zagadnienia, czy praw rządzących rozwiązywanym problemem. Wystarczy nam jedynie wiedza które z przedstawianych rozwiązań będzie dla nas lepsze. Dodatkowo uruchamiając ten sam algorytm genetyczny kilka razy, możemy dojść do różnych rozwiązań, gdyż za każdym razem populacja inicjowana jest losowo. Z drugiej strony możemy to potraktować też jako wadę, gdyż nigdy nie mamy pewności, że dany wynik jest optymalny. Owszem, będzie on do niego zbliżony, ale nie zawsze dane rozwiązanie będzie najlepsze z istniejących.

Algorytmy genetyczne sprawdzają się i są wykorzystywane wszędzie tam, gdzie człowiek nie jest w stanie przygotować jednoznacznego przepisu na rozwiązanie problemu z różnych powodów. Może to być na przykład zbyt duży stopień skomplikowania zagadnienia, bądź brak wystarczającej ilości danych. Algorytmy genetyczne spotkamy więc w ekonomii, projektowaniu układów elektronicznych, czy w technologiach wykorzystywanych w kosmosie. Przykładem może być antena statku kosmicznego NASA pokazana powyżej, zaprojektowana przez algorytm genetyczny w taki sposób, aby miała jak najlepsze parametry w danym środowisku.

Mam nadzieję, że udało mi się zaciekawić Cię tematem algorytmów genetycznych. W następnym poście dowiesz się jak mam zamiar wykorzystać je w projekcie easyGALib i co z jego pomocą będziesz w stanie zdziałać!

Gdybyś chciał poczytać coś więcej na temat algorytmów genetycznych, warto zaglądnąć do poniższych wykładów:

http://www.michalbereta.pl/dydaktyka/alg_imm/klasyczny_algorytm_genetyczny.pdf

http://edu.pjwstk.edu.pl/wyklady/nai/scb/wyklad10/w10.htm