Algorytmy Genetyczne

tapety.joe

Algorytmy genetyczne to pewien rodzaj algorytmów, które przeszukują płaszczyznę możliwych rozwiązań problemu w celu odnalezienia wystarczająco dobrego, które spełniać będzie określone z góry założenia. Zwykle problemy, do których wykorzystywane są algorytmy genetyczne należą do klasy NP-trudnych, oznacza to, że przy istniejących zasobach nie jesteśmy w stanie w skończonym czasie znaleźć rozwiązania optymalnego. Odnalezienie rozwiązania wystarczająco dobrego jest opcją maksymalną, natomiast akceptowalną o ile wszelkie założenia są spełnione.

Ogólnie rzecz biorąc, każda czynność do wykonania może być przedstawiona jako rozwiązywanie zadania. Idąc dalej, rozwiązywanie zadania można rozumieć jako przeszukiwanie przestrzeni możliwych rozwiązań. Biorąc pod uwagę fakt, że zawsze dążymy do wybrania „najlepszego” rozwiązania, możemy uznać to zadanie za proces optymalizacji. W niewielkich przestrzeniach rozwiązań klasyczne metody pełnego przeszukiwania są wystarczające i możemy sobie na nie pozwolić. Natomiast w większych przestrzeniach niezbędnym jest zastosowanie bardziej specjalistycznych metod opartych na sztucznej inteligencji. Wśród tej grupy metod znajdują się algorytmy genetyczne. Są to algorytmy stochastyczne, których sposób przeszukiwania przestrzeni rozwiązań naśladuje pewne procesy naturalne – dziedziczenie genetyczne oraz darwinowską walkę o przeżycie. Bazują one na procesie ewolucji w naturze, w ramach którego każdy gatunek zmierza się z problemem lepszej adaptacji do skomplikowanego i zmiennego środowiska. „Wiedza”, którą każdy gatunek zgromadził, wbudowana jest w układ chromosomów jego osobników.[1]

Koncepcja leżąca u podstaw algorytmów genetycznych polega na odzwierciedleniu tego, co robi natura. Można to przedstawić na przykładzie świata zwierząt, np. antylop. Niektóre z nich są szybsze, zwinniejsze i sprytniejsze od innych. Te osobniki mają większe szansę umknięcia przed lwem, czy innymi drapieżnikami. Wobec tego przeżywa ich większa ilość. Oczywiście, niektóre z wolniejszych, mniej zwinnych i głupszych antylop również przeżyją, bo mają szczęście, ale to te sprytniejsze antylopy, w stosunkowo większym stopniu, są odpowiedzialne za przedłużenie gatunku. Ocalała populacja antylop wydaje potomstwo, które jest wielką mieszaniną materiału genetycznego. Niektóre głupsze antylopy krzyżują się ze sprytnymi, niektóre sprytne ze sprytnymi, niektóre szybsze z wolnymi itd. Dodatkowo od czasu do czasu natura dorzuca tzw. „dziką kartę”, wprowadzają jakąś mutację do materiału genetycznego antylop. Urodzone w wyniku takiego procesu antylopy będą (średnio) szybsze, zwinniejsze i sprytniejsze niż te z populacji początkowej, ponieważ to szybsze i sprytniejsze osobniki umknęły przed drapieżnikami. W naturze taki proces zachodzi w ramach każdego gatunku, dzięki czemu ogólna równowaga zostaje zachowana. Również lwy i inne drapieżniki z pokolenia na pokolenie są coraz szybsze i mądrzejsze. W przeciwnym razie z biegiem czasu antylopy nie dawałyby się już złapać.

Algorytmy genetyczne krok po kroku naśladują procedurę przedstawioną powyżej. Dodatkowo do ich opisu używa się nomenklatury zapożyczonej z genetyki naturalnej. Mamy do czynienia z osobnikami (lub genotypami, strukturami) w populacji. Osobniki te często są również nazywane łańcuchami lub chromosomami. Chromosomy składają się z genów (cech, znaków, dekoderów), które są uszeregowane liniowo. Każdy gen determinuje dziedziczność jednej lub wielu cech. Geny o określonym typie są umieszczone w pewnych miejscach chromosomu, zwanych pozycją. Każda cecha osobnika (np. kolor oczu) objawia się w różny sposób – mówi się, że gen jest w kilku stanach, zwanych allelami (wartościami cechy).

Każdy genotyp reprezentuje potencjalne rozwiązanie problemu czy zadania (znaczenie chromosomu, tzn. jego fenotyp, jest zewnętrznie definiowane przez użytkownika). Proces ewolucyjny, który zachodzi w populacji chromosomów, odpowiada przeszukaniu przestrzeni (zbioru) potencjalnych rozwiązań. Przeszukanie to musi jednocześnie skorzystać z najlepszych dotychczasowych rozwiązań oraz jak najszerzej przebadać przeszukiwaną przestrzeń, co w sposób oczywisty wydaje się sprzeczne[2]. Metoda wzrostu to przykład strategii, która oparta jest na najlepszym dotychczasowym rozwiązaniu i w której próbujemy to rozwiązanie poprawić. Natomiast typowym przykładem strategii, w której przeszukiwana jest przestrzeń, nie zwracając uwagi na jej obiecujące regiony, jest przeszukiwanie losowe. Algorytmy genetyczne należą do klasy ogólniejszych metod przeszukiwania (niezależnych od dziedziny), które charakteryzują się utrzymaniem możliwie najlepszej równowagi pomiędzy szerokim przebadaniem przestrzeni oraz korzystaniem z wcześniejszych wyników.

Jednym z głównych obszarów zastosowania algorytmów genetycznych jest optymalizacja. Już w latach 80-tych trudno było znaleźć nowoczesną publikację inżynierską, matematyczną, ekonomiczną, fizyczną, z zakresu nauk społecznych czy zarządzania, która nie zawierałaby w swoim indeksie pojęcia „optymalizacja”. Jeżeli nawet abstrahujemy od punktu widzenia specjalistów, to powszechnie występującym zadaniem jest wybór najlepszej lub, zgodnie z definicją Leibniza, optymalnej możliwości spośród wielu możliwych rozwiązań.[3] W czasie ostatnich trzydziestu pięciu lat znaczenie optymalizacji wzrosło jeszcze bardziej. Istnieje grupa istotnych zadań optymalizacji kombinatorycznej o dużej skali oraz zadań inżynierskich z wieloma ograniczeniami, które przy użyciu obecnych komputerów można rozwiązać jedynie w sposób przybliżony.

Jednym z narzędzi, czy metod, które nadają się do rozwiązania tak skomplikowanych zadań są właśnie algorytmy genetyczne. Należą one do grupy algorytmów probabilistycznych, aczkolwiek różnią się w znacznym stopniu od algorytmów czysto losowych, ponieważ łączą w sobie elementy przeszukiwania bezpośredniego i stochastycznego. W rezultacie algorytmy genetyczne są również bardziej niezawodne niż powszechnie używane algorytmy przeszukiwania bezpośredniego. Dodatkowym ważnym atutem takich metod, opartych na rozwiązaniach genetycznych, jest fakt, że zachowują one całkowitą populację potencjalnych rozwiązań, podczas gdy inne metody przetwarzają tylko jeden punkt badanej przestrzeni.

Algorytm genetyczny dokonuje wielokierunkowego przeszukania poprzez przekształcenie populacji potencjalnych rozwiązać oraz prowadzi do zebrania informacji genetycznej i jej wymiany pomiędzy tymi kierunkami. W ten sposób populacja podlega symulowanej ewolucji, dzięki której w każdym kolejnym pokoleniu stosunkowo „dobre” rozwiązania (osobniki) reprodukują się, a te stosunkowo „złe” wymierają. Aby dokonać rozróżnienia pomiędzy rozwiązaniami, korzystamy z funkcji celu (oceny), która pełni rolę środowiska.

Struktura prostego algorytmu genetycznego przedstawia się tak samo jak struktura każdego programu ewolucyjnego (patrz Rysunek 1 w rozdziale 1). W iteracji t algorytm ten zachowuje populację potencjalnych rozwiązań (chromosomów) P(t) = {xt1, …, xtn}. Dla każdego rozwiązania xti ocenia się wartość jego „dopasowania”. Następnie w iteracji t + 1 formowana jest nowa populacja poprzez wybór najlepiej dopasowanych osobników. Niektóre z osobników tej nowej już populacji podlegają zmianą przy użyciu krzyżowania i mutacji, dzięki czemu tworzone są nowe osobniki (rozwiązania).

Krzyżowanie polega na połączeniu cech dwóch chromosomów rodzicielski w chromosomach dwóch potomków. Dzieje się to poprzez wymianę odcinków ich chromosomów (rodzicielskich). Przykładowo, jeśli osobniki rodzicielskie reprezentowani są przez wektory pięcioelementowe np. (ax, bx, cx, dx, ex) oraz (ay, by, cy, dy, ey), to krzyżowanie chromosomów po trzecim genie doprowadzi do potomków (ax, bx, cx, dy, ey) oraz (ay, by, cy, dx, ex). Zatem podstawowym zadaniem operatora krzyżowania jest mieszanie materiału genetycznego z nadzieją, że w rezultacie otrzymamy potomka, który odziedziczy mieszankę lepszych genów pochodzą od obojga rodziców. Jeżeli cel ten zostanie osiągnięty, to drugi potomek odziedziczy gorsze geny, aczkolwiek to nie będzie nas martwić, ponieważ taki osobnik zostanie odrzucony podczas porównania poziomu „dopasowania” poszczególnych rozwiązań[4]. Intuicyjnie krzyżowanie można interpretować jako wymianę informacji genetycznej pomiędzy potencjalnymi rozwiązaniami.

Mutacja z kolei polega na losowej zmianie genu (lub genów) wybranego chromosomu, z prawdopodobieństwem równym częstości mutacji. Podczas gdy krzyżowanie będzie prowadzić do kumulacji najlepszego materiału genetycznego w kolejnych pokoleniach, mutacja odpowiada za to, aby ogólny zasób materiału genetycznego w populacji był stale urozmaicony[5]. Operator mutacji można intuicyjnie rozumieć jako wprowadzenie pewnej dodatkowej zmienności w populacji.

Algorytm genetyczny, podobnie jak każdy program ewolucyjny, powinien dla każdego szczególnego zadania zawierać 5 następujących elementów:

  • podstawową reprezentację dla potencjalnych rozwiązań zadania,
  • sposób, w jaki tworzona będzie początkowa populacja potencjalnych rozwiązań,
  • funkcję celu (oceny), która pełnić będzie rolę środowiska i oceniać będzie poziom „dopasowania” poszczególnych rozwiązań,
  • podstawowe operatory, które wpływać będą na to, jak będzie wyglądać populacja potomstwa,
  • wartości różnych parametrów, które będą używane w algorytmie genetycznym (wielkość populacji, prawdopodobieństwo użycia operatorów mutacji i krzyżowania itp.).[6]

[1] Davis L., Steenstrup M., „Genetic Algorithms and Simulated Annealing: An Overview”, Morgan Kaufmann Publishers, San Mateo 1987, s. 1-11.

[2] Booker L.B., “Improving Search in Genetic Algorithms” w „Genetic Algorithms and Simulated Annealing”, Morgan Kaufmann Publishers, San Mateo 1987, s. 61-73.

[3] Schwefel H. -P., “Numerical Optimization for Computer Models”, John Wiley, Chichester, UK, 1981.

[4] Gwiazda T. D., „Algorytmy genetyczne kompendium – tom I: operator krzyżowania dla problemów numerycznych”, Wydawnictwo Naukowe PWN, Warszawa 2007, s. 25.

[5] Tamże, s.26.

[6] Spłocharski J., Spłocharski M, “Generowanie grafiku pracy oddziału szpitalnego
z wykorzystaniem algorytmów genetycznych”, Warszawa 2015