Koncepcja algorytmów genetycznych

Proces ewolucji biologicznej polega na zmianie cech organizmów wraz z biegiem pokoleń. Dzięki temu organizmy lepiej przystosowują się do otoczenia, co zwiększa ich szanse na przetrwanie. Co jednak łączy ewolucję biologiczną z algorytmami genetycznymi?

Naukowcy zbadali mechanizmy zachodzące w populacji organizmów, przyczyniające się do przebiegu ewolucji. Krzyżowanie się najsilniejszych osobników i losowe mutacje genów sprawiają, że następne pokolenia mogą być lepiej przystosowane do przetrwania w warunkach naturalnych. Okazuje się, że procesy te można również wykorzystać w informatyce – do efektywnego przeszukiwania zbioru rozwiązań danego problemu.

Zanim jednak omówimy działanie algorytmów genetycznych, musimy zapoznać się z następującymi pojęciami:

• gen – podstawowa jednostka przechowująca informację na temat pewnej szczególnej cechy organizmu; może to być wartość boolowska, liczba całkowita albo rzeczywista;

• chromosom – jest to zbiór liczb lub bitów reprezentujących poszczególne geny;

• osobnik – zbiór chromosomów; każdy osobnik jest reprezentantem pewnego rozwiązania danego problemu;

• populacja – jest to zbiór osobników; w kolejnych cyklach ewolucji rodzice są zastępowani przez swoje dzieci;

• funkcja przystosowania – funkcja pozwalająca, by dany osobnik określił swoje przystosowanie z punktu widzenia rozwiązywanego problemu; zakładamy, że wyższa wartość funkcji oznacza, że dany osobnik jest lepiej przystosowany.

Zasada działania algorytmów genetycznych

Na początku działania algorytmu genetycznego generujemy pierwszą populację organizmów. Każdy z osobników zostaje poddany ocenie na bazie jego przystosowania do danych warunków. W kolejnym kroku przeprowadzana jest selekcja osobników. Najlepsi z nich są krzyżowani, a następnie tworzona jest nowa populacja. Algorytm możemy przeprowadzać do momentu, w którym nie uzyskamy zadowalającego nas rozwiązania.

Opisany proces przedstawia schemat blokowy:

RhDHviGJST2Mq

Ilustracja przedstawia schemat blokowy.
1: Zielony okrąg Start.
2: Fioletowy prostokąt, Wybór początkowej populacji rozwiązań.
3: Fioletowy prostokąt, Ocena przystosowania osobników.
4: Niebieski romb, Warunek końca.
Dla nie w kroku 4.
5: Fioletowy prostokąt, Selekcja osobników.
6. Fioletowy prostokąt, Operatory genetyczne.
7: Fioletowy prostokąt, Powstawanie nowej populacji.
8: krok 3.
Dla tak w kroku 4.
5: Fioletowy prostokąt, Zapamiętanie najlepszego rozwiązania.
6. Czerwony okrąg, STOP.

Zalety i wady algorytmów genetycznych

Algorytmy genetyczne mogą być użyte do rozwiązywania problemów, dla których klasyczne algorytmy optymalizacyjne nie są skuteczne. Często są to problemy źle uwarunkowane lub trudne do sformułowania matematycznego.

Dodatkowo, większość klasycznych algorytmów optymalizacyjnych stosuje deterministycznądeterminizmdeterministyczną procedurę dojścia do optymalnego rozwiązania. Mają one tendencję do utknięcia w rozwiązaniu suboptymalnym i ich skuteczność zależy od punktu startowego poszukiwań.

Główną zaletą algorytmów genetycznych jest, że stosują probabilistycznealgorytm probabilistycznyprobabilistyczne, a nie deterministyczne reguły wyboru. Nie przetwarzają bezpośrednio parametrów zadania, a jedynie jego zakodowaną postać oraz prowadzą poszukiwania, zaczynając od pewnej losowej populacji, a nie od pojedynczego punktu. Dodatkowo metoda ta jest stosunkowo szybka. Znalezienie rozwiązania często jest możliwe, po przejrzeniu zaskakująco niewielkiej przestrzeni rozwiązań.

Jednak duży wpływ na działanie algorytmów genetycznych ma prawidłowe zakodowanie problemu oraz odpowiednie dobranie funkcji przystosowania. Nie ma uniwersalnego sposobu mówiącego, jak powinien wyglądać cały proces, więc jest to często kwestia intuicji i doświadczenia. Nigdy nie mamy pewności, czy znaleźliśmy rozwiązanie optymalne, ponieważ algorytmy genetyczne są algorytmami probabilistycznymi.

Przykładowe zastosowania algorytmów genetycznych

Dzięki swojej wydajności i prostocie algorytmy genetyczne znalazły szerokie zastosowanie w wielu dziedzinach.

Zostały one wykorzystane w przemyśle lotniczym do optymalizacji konstrukcji skrzydła samolotu, poprzez minimalizację jego ciężaru oraz oporu aerodynamicznego. Na przełomie wieków XX oraz XXI trwały prace nad projektami samolotów naddźwiękowych. Jednym z nich był model NEXST‑1. Japońskie Narodowe Laboratorium Kosmiczne (National Aerospace Laboratory of Japan) wraz ze swoimi inżynierami przygotowało projekt skrzydeł, który porównano z wynikami uzyskanymi przez naukowców wykorzystujących algorytmy genetyczne. Projekty stworzone z wykorzystaniem algorytmów oceniono wyżej.

Algorytmy genetyczne są również stosowane do konstrukcji strategii inwestycyjnych na giełdzie oraz do modelowania finansowego.

W przemyśle używa się tego typu algorytmów do harmonogramowania i szeregowania zadań. Dzięki nim powstały lepiej zoptymalizowane taśmy produkcyjne.

Algorytmy genetyczne są również wykorzystywane do wyznaczania punktów startowych dla deterministycznych algorytmów optymalizacyjnych. Dzięki temu przeszukiwanie przestrzeni rozwiązań nie jest aż tak losowe i eliminujemy problem związany z doborem punktu startowego poszukiwań.

Algorytmy genetyczne znalazły również zastosowanie przy projektowaniu sztucznych sieci neuronowych. Mogą być wykorzystywane do wyznaczenia liczby iteracji uczenia, czy liczności neuronów w poszczególnych warstwach. Są stosowane w rozwiązywaniu rzeczywistych problemów w różnych dziedzinach i pozwalają na pokonanie trudności związanych ze stosowaniem klasycznych metod optymalizacyjnych.

Słownik