Zagnieżdżony algorytm ewolucyjny
- Szczegóły
- Kategoria: Artykuły
Wersja internetowa bez przypisów, oparta na: Paweł Rośczak, Zagnieżdżony algorytm ewolucyjny, [w:] Współczesne tendencje rozwojowe badań operacyjnych, Prace Naukowe Akademii Ekonomicznej im. Oskara Langego we Wrocławiu, Nr 1167, red. J. Siedlecki, Wydawnictwo Akademii Ekonomicznej im. Oskara Langego we Wrocławiu, Wrocław 2007, s. 232–243, http://www.rosczak.com/index.php/pl/embedded/, 2012-01-31.
Streszczenie
Artykuł podejmuje problem optymalizacji parametrów działania algorytmu ewolucyjnego. W zagnieżdżonym algorytmie ewolucyjnym parametry działania algorytmu podstawowego są optymalizowane przez algorytm drugiego rzędu. Pozwala to uniknąć sytuacji, w której arbitralny dobór parametrów działania algorytmu spowalnia proces poszukiwania rozwiązania optymalnego lub uniemożliwia znalezienie rozwiązania dopuszczalnego.
Summary
Article undertake optimization problem of evolutionary algorithms execution parameters. In embedded evolutionary algorithm execution parameters of primary algorithm are optimized by secondary algorithm. It allows to avoid situation where arbitrary choice of algorithm execution parameters delays search process of optimal solution or prevents finding acceptable solution.
1. Wstęp
Algorytmy ewolucyjne są skutecznymi narzędziami optymalizacji, opartymi na teorii ewolucji oraz zasadach doboru naturalnego. Wykorzystanie typowego algorytmu genetycznego wiąże się z koniecznością określenia wartości szeregu parametrów, związanych z poszczególnymi operatorami. Wspomniane parametry w wydatny sposób wpływają na efektywność procesu optymalizacji. Ich wartości dobierane są na podstawie zaleceń pochodzących z wyników badań lub za pomocą metody prób i błędów. Wykorzystanie algorytmu genetycznego do optymalizacji parametrów działania innego algorytmu ewolucyjnego wydaje się być naturalną konsekwencją dążenia do zalgorytmizowania procesu wyznaczania wartości parametrów oraz w konsekwencji znacznego podniesienia jego wydajności.
Tradycyjny algorytm genetyczny posiada także szereg innych niekorzystnych właściwości określanych zazwyczaj jako jego cechy, a nie wady. Analiza sposobu jego działania oraz propozycje ewentualnych usprawnień są dodatkowym motywem dla poszukiwania nowych, wydajniejszych odmian algorytmów ewolucyjnych.
2. Typowy algorytm genetyczny
Algorytm genetyczny w wersji klasycznej korzysta z trzech podstawowych operatorów: krzyżowania, mutacji oraz reprodukcji, nazywanego także operatorem selekcji.
- Operator krzyżowania tworzy nowe osobniki potomne na podstawie par osobników rodzicielskich. Jego intensywność jest określona przez prawdopodobieństwo krzyżowania, którego typowa wielkość wynosi 0,5. Warto dodać, że w literaturze przedmiotu często spotyka się również wartości większe, np. 0,95, oraz mniejsze np. 0,25. Z operatorem krzyżowania wiąże się także założenie dotyczące ilości punktów krzyżowania genotypów rodzicielskich, która to wartość nie zawsze podlega parametryzacji. Najczęściej wykorzystuje się krzyżowania jednopunktowe, ale można się także spotkać z zastosowaniem krzyżowania wielopunktowego, często w postaci dwupunktowej.
- Operator mutacji wykonuje losowe zaburzenie genotypu, wprowadzając do populacji nowego osobnika. Jego działanie jest uzależnione od wielkości prawdopodobieństwa mutacji, którą to wartość zazwyczaj dobiera się z przedziału od 0,01 do 0,001. Parametr ten określa szanse mutacji pojedynczego genu w zestawieniu genotypów należących do wszystkich osobników z całej populacji. Z powodu takiego ujęcia procesu mutacji ustalenie prawdopodobieństwa mutacji na wartości wyższe od 0,1 zazwyczaj prowadzi do sytuacji, w której algorytm genetyczny nabiera właściwości typowych dla błądzenia losowego.
- Operator selekcji wybiera osobniki przechodzące do następnego pokolenia. Z typowym operatorem reprodukcji nie wiąże się żaden stały parametr liczbowy. Pojawiało się jednak szereg propozycji dotyczących metody dokonywania selekcji, które prowadzą do odmiennych algorytmów działania operatora.
Obok operatorów i parametrów wymienionych wyżej występuje także szereg innych technik stosowanych rzadziej lub dodawanych do algorytmów genetycznych w miarę rozwoju badań. Różnorodność propozycji prowadzi do pytania, jakie są najlepsze, czyli najbardziej efektywne, postaci operatorów oraz wartości parametrów?
Podstawową zaletą typowego algorytmu genetycznego jest jego prostota oraz łatwość w oprogramowaniu. Ceną za taki stan rzeczy jest oczywiście szereg niepożądanych właściwości, do których należy:
- tendencja do gubienia przez algorytm najlepszego dotychczasowego rozwiązania w trakcie jego działania,
- dominowanie populacji przez osobniki o dużej wartości funkcji przystosowania, co często prowadzi do zatrzymywania optymalizacji w ekstremum lokalnym funkcji celu zamiast w ekstremum globalnym,
- najczęściej stosowana w reprodukcji reguła ruletki cechująca się dużym rozrzutem losowym i przez to osłabiająca powiązanie selekcji z wielkością przystosowania poszczególnych osobników,
- mała kontrola nad operatorem mutacji i brak możliwości zintensyfikowania rozmiarów mutacji na poziomie osobnika, rozumianej jako ilość mutowanych genów w pojedynczym genotypie.
Tradycyjny algorytm genetyczny nie pozwala na kontrolowanie intensywności mutacji na poziomie pojedynczego genotypu. W celu zwiększenia kontroli nad operatorem mutacji dokonałem rozbicia prawdopodobieństwa mutacji na prawdopodobieństwo mutacji genotypu oraz prawdopodobieństwo mutacji genu w genotypie. Zaletą takiego rozwiązania jest duża dowolność w określaniu formy mutacji, w tym np. możliwość wymuszenia silnych zaburzeń losowych genotypu, zachodzących w niewielkim odsetku osobników należących do populacji. W praktyce zaproponowane rozwiązanie nie wprowadza do algorytmu niczego nowego, a jedynie zwiększa poziom parametryzacji, i dlatego w powyższym tekście będzie dalej traktowane jako cześć tradycyjnego algorytmu genetycznego.
3. Algorytm genetyczny ze zmienną wielkością populacji
W celu wyeliminowania wad tradycyjnego algorytmu genetycznego zastosowałem algorytm ewolucyjny ze zmienną wielkością populacji. Operator krzyżowania i mutacji stosuje się w takim przypadku na osobnikach klonowanych, czyli kopiach osobników z populacji wyjściowej, które powiększają populację wynikową. Efektem działania zmodyfikowanych operatorów jest zachowanie osobnika wylosowanego do krzyżowania lub mutacji razem z nowymi osobnikami wygenerowanymi przez wspomniane operatory. Dzięki takiemu rozwiązaniu populacja nie traci w sposób losowy żadnych informacji, a osobniki rodzicielskie stają do rywalizacji z osobnikami potomnymi.
Podstawową zaletą wykorzystania klonowania oraz zmiennej wielkości populacji jest fakt, iż algorytm nie gubi w trakcie krzyżowania oraz mutacji osobnika o największej wartości funkcji przystosowania, czyli nie traci najlepszego rozwiązania. Do wad takiego podejścia można zaliczyć przede wszystkim wzrost stopnia komplikacji programu komputerowego.
Rozwiązanie tradycyjne, korzystające ze stałego rozmiaru tablicy z osobnikami, najprawdopodobniej było efektem ograniczonych zasobów pamięci operacyjnej komputerów oraz dążeniem do jej jak najbardziej efektywnego wykorzystania. Obecnie jednak rozmiar pamięci operacyjnej uległ i nieustannie ulega zwiększeniu, przez co jej mniej efektywne wykorzystanie nie stanowi bariery.
4. Algorytm genetyczny z regułą turnieju
Operator selekcji, oparty na początkowo stosowanej regule ruletki, cechuje się dużym rozrzutem losowym faktycznej liczby kopii osobników przechodzących do kolejnej populacji w stosunku do oczekiwanej liczby kopii, ściśle powiązanej z wartością funkcji przystosowania. Prawdopodobieństwo wylosowania każdego z genotypów maleje wraz ze wzrostem liczebności populacji. Może to prowadzić do utraty najlepszego dotychczasowego osobnika, czyli pogorszenia się jakości rozwiązania problemu optymalizacyjnego. Badania wykazały, że reguła ruletki jest najmniej efektywną metodą selekcji. W zamian zaleca się stosownie innych metod opartych na wartości oczekiwanej oraz metodzie turnieju.
W opisywanym algorytmie zastosowałem operator selekcji oparty na regule turniejów, wykorzystany jednak w nieco odmiennym charakterze. Operator selekcji nie dokonuje wyboru osobników przechodzących do nowej populacji, ale redukuje jej rozmiar do zadanej wielkości. Warto przypomnieć, że wykorzystanie operatorów krzyżowania i mutacji razem z klonowaniem osobników oraz użycie zmiennego rozmiaru populacji powoduje zwiększenie liczby osobników, która jest redukowana do zadanego poziomu za pomocą opisywanego operatora selekcji.
Efektem takiego podejścia jest algorytm, który nie gubi w trakcie działania najlepszego rozwiązania i zmniejsza rozrzut losowy operatora selekcji do bezpiecznych wielkości. Prawdopodobieństwo przetrwania najlepiej przystosowanego osobnika wynosi wówczas 1, a prawdopodobieństwo przetrwania najgorzej przystosowanego – 0.
5. Reguła turnieju z prawdopodobieństwem zajścia turnieju
Kolejnym problemem związanym z wykorzystaniem algorytmów genetycznych jest realne ryzyko zdominowania populacji przez osobnika o wysokiej wartości funkcji przystosowania, ale nie stanowiącego rozwiązania optymalnego. W takim przypadku proces optymalizacji zatrzymuje się w ekstremum lokalnym funkcji dopasowania i nie jest w stanie w dalszych generacjach zbliżyć się do ekstremum globalnego.
Powyższy problem jest poważną wadą algorytmów ewolucyjnych i dlatego doczekał się kilku udanych metod, które przeciwdziałają zdominowaniu populacji i gwarantują lub podtrzymują jej różnorodność.
- Model ze ściskiem zaproponowany przez K. A. De Jonga w 1975 roku zakłada zastępowanie starszych osobników przez młodsze. Kryterium wyboru jest maksymalne podobieństwo osobnika nowego oraz usuwanego. Pomysł nawiązuje do rywalizacji o ograniczone zasoby, jaka zachodzi w przypadku podobnych osobników zamieszkujących nisze ekologiczne. Niestety metoda stosowana jest dla populacji o stałym rozmiarze.
- Skalowanie wartości funkcji przystosowania było wykorzystywane już od wczesnych prac z zakresu algorytmów genetycznych. Przeglądu różnych procedur skalowania dokonała S. Forest w roku 1985. Rozwiązania te są względnie proste i skuteczne. Niestety nie zabezpieczają one procedury optymalizacyjnej przed zdominowaniem populacji przez osobnika o wysokiej, ale nie najwyższej wartości funkcji przystosowania. Dostarczają one jedynie sposobów osłabiania lub wzmacniania tendencji do dominowania.
- Uniwersalnym i skutecznym sposobem na eliminację zjawiska przedwczesnego zdominowania populacji jest stosowanie funkcji współudziału opisanej przez D. E. Goldberga i J. Richardsona w roku 1987. Metoda zakłada modyfikację wartości funkcji przystosowania przy wykorzystaniu odległości pomiędzy danym osobnikiem a wszystkimi pozostałymi osobnikami w populacji. Odległość pomiędzy genotypami oblicza się przy użyciu metryki euklidesowej. W efekcie duża liczba podobnych do siebie osobników zaniża sobie wzajemnie wartości funkcji przystosowania i zmniejsza szanse na przetrwanie. Metoda posiada jednak zasadniczą wadę praktyczną, ponieważ konieczność wyznaczania odległości pomiędzy wszystkimi punktami w populacji, dla każdej generacji, wymaga dużych mocy obliczeniowych.
Do rozwiązania problemu i zabezpieczania populacji przed zdominowaniem wykorzystałem współczynnik podobieństwa genotypów stających do turnieju w ramach operatora selekcji. Współczynnik podobieństwa określa prawdopodobieństwo zajścia turnieju pomiędzy wybranymi osobnikami. W przypadku osobników identycznych osiąga wartość 1, w przypadku genotypów będących swoimi przeciwieństwami wartość 0, a w przypadkach pośrednich wielkości z przedziału (0; 1). W efekcie stosowania reguły turnieju ze współczynnikiem podobieństwa jako prawdopodobieństwem zajścia turnieju do rywalizacji stają przede wszystkim osobniki podobne do siebie. Jest to zasadnicza zaleta rozwiązania, które przy względnej prostocie oprogramowania i małym nakładzie mocy obliczeniowych przeciwdziała zdominowaniu populacji i zapewnia jej różnorodność.
6. Oddzielne operatory reprodukcji i selekcji
W typowym algorytmie genetycznym operator selekcji, nazywany także operatorem reprodukcji, wykonuje kopiowanie osobników z populacji wyjściowej do następnej populacji wynikowej. W procesie tym zarówno zwiększa się liczbę osobników najlepiej przystosowanych, jak i redukuje ilość lub całkowicie usuwa osobniki najgorzej przystosowane.
W celu uzyskania większej kontroli nad tymi w zasadzie dwiema różnymi operacjami rozdzieliłem opisaną wyżej operację na dwa osobne operatory:
- Operator reprodukcji wykonuje klonowanie osobników, czyli kopiuje osobniki z populacji wyjściowej do wynikowej. Jego intensywność jest uzależniona od zadanego prawdopodobieństwa reprodukcji.
- Operator selekcji redukuje rozmiar populacji do zadanej wielkości, usuwając z populacji osobniki najgorzej przystosowane.
Zaletą rozdzielenia operatorów jest powstanie opisywanego wcześniej mechanizmu redukcji rozmiaru populacji po operacjach krzyżowania i mutacji na osobnikach klonowanych. Ponadto pojawia się możliwość parametryzacji algorytmu, która np. pozwala na ograniczenie wpływu reprodukcji w ramach przeciwdziałania zdominowaniu populacji.
7. Zagnieżdżony algorytm ewolucyjny
Dobór parametrów działania algorytmu genetycznego najczęściej ma charakter silnie uznaniowy, weryfikowany za pomocą metody prób i błędów. Mając na uwadze fakt, iż optymalizacja genetyczna jest wyjątkowo uniwersalnym i elastycznym narzędziem, warto podjąć próbę sformalizowania i algorytmizacji procesu wyznaczania parametrów działania algorytmu ewolucyjnego przez zastosowanie innego algorytmy genetycznego.
W zagnieżdżonym algorytmie ewolucyjnym parametry działania algorytmu podstawowego są optymalizowane za pomocą nadrzędnego algorytmu genetycznego (zob. rys. 1). Wykorzystanie takiej metody pozwala oczekiwać lepszego doboru parametrów działania algorytmu genetycznego i potencjalny wzrost efektywności jego działania. Oczywiście opisane rozwiązanie jest obarczone wadą typową dla większości wymienionych modyfikacji, ponieważ powoduje zwiększenie poziomu złożoności programu komputerowego oraz wzrost zużycia mocy obliczeniowych.
Rys. 1. Zmodyfikowany, zagnieżdżony algorytm genetyczny
Źródło: opracowanie własne
8. Porównanie podstawowego oraz zagnieżdżonego algorytmu genetycznego
Do porównania efektywności zagnieżdżonego algorytmu ewolucyjnego z algorytmem genetycznym w wersji tradycyjnej wykorzystałem trzy różne testowe funkcje przystosowania. Pierwsza z nich jest prostą funkcją jednomodalną, a dwie kolejne funkcjami wielomodalnymi o narastającej ilości ekstremów lokalnych (zob. rys. 2, 3 i 4). Dzięki wykorzystaniu funkcji testowych możliwe było wyznaczanie ekstremów globalnych przed rozpoczęciem eksperymentu. Zadanie optymalizacyjne polegało na odszukaniu maksymalnej wartości funkcji w zadanym przedziale. Proces tworzenia kolejnych generacji był zatrzymywany po odszukaniu zapisanej w programie wartości maksymalnej, czyli zakończeniu optymalizacji sukcesem, lub po wykonaniu 64 generacji. Populacja składała się z 64 osobników oraz 32 populacji podstawowych w przypadku wersji zagnieżdżonej.
W eksperymencie porównano algorytm genetyczny w wersji prostej oraz zagnieżdżonej. Dodatkowo każda z wersji obejmuje algorytm w postaci tradycyjnej oraz zmodyfikowanej. Forma zmodyfikowana zawiera usprawnienia opisane w teksie, czyli zmienny rozmiar populacji oraz zastosowanie reguły turnieju z prawdopodobieństwem zajścia turnieju. W sumie eksperymentowi poddano cztery różne wersje algorytmu.
Rys. 2. Funkcja testowa z 1 maksimum: y = 2 + 2 • sin(x • pi / 64); 0 ≤ x ≤ 64. Maksimum globalne y = f(x): x = 32; y = 4.
Źródło: opracowanie własne
| Tradycyjny, podstawowy algorytm genetyczny | Tradycyjny, zagnieżdżony algorytm genetyczny | Zmodyfikowany, podstawowy algorytm genetyczny | Zmodyfikowany, zagnieżdżony algorytm genetyczny | |
|---|---|---|---|---|
| Rozmiar populacji podstawowej | 64 | 64 | 64 | 64 |
| Rozmiar populacji nadrzędnej | - | 32 | - | 32 |
| Liczba uruchomień | 10 | 10 | 10 | 10 |
| Uruchomienia zakończone sukcesem | 0 | 1 | 8 | 10 |
| Maksymalna liczba generacji | 64 | 64 | 64 | 64 |
| Średnia liczba generacji | 64,0 | 58,9 | 33,4 | 6,4 |
| Średnia wartość funkcji przystosowania | 3,9999 | 3,9999 | 4,0000 | 4,0000 |
Źródło: opracowanie własne
Rys. 3. Funkcja testowa z 8 maksimami: y = 2 + 2 • sin(x • pi / 64) + sin(x • pi / 4); 0 ≤ x ≤ 64. Maksimum globalne y = f(x): x = 33,9845; y = 4,9904.
Źródło: opracowanie własne
| Tradycyjny, podstawowy algorytm genetyczny | Tradycyjny, zagnieżdżony algorytm genetyczny | Zmodyfikowany, podstawowy algorytm genetyczny | Zmodyfikowany, zagnieżdżony algorytm genetyczny | |
|---|---|---|---|---|
| Rozmiar populacji podstawowej | 64 | 64 | 64 | 64 |
| Rozmiar populacji nadrzędnej | - | 32 | - | 32 |
| Liczba uruchomień | 10 | 10 | 10 | 10 |
| Uruchomienia zakończone sukcesem | 5 | 10 | 10 | 10 |
| Maksymalna liczba generacji | 64 | 64 | 64 | 64 |
| Średnia liczba generacji | 42,7 | 5,9 | 8,2 | 1,3 |
| Średnia wartość funkcji przystosowania | 4,9880 | 4,9904 | 4,9904 | 4,9904 |
Źródło: opracowanie własne
Rys. 4. Funkcja testowa z 64 maksimami: y = 2 + 2 • sin(x • pi / 64) + sin(x • pi / 4) + sin(x • 2 • pi); 0 ≤ x ≤ 64. Maksimum globalne y = f(x): x = 34,2459; y = 5,9689.
Źródło: opracowanie własne
| Tradycyjny, podstawowy algorytm genetyczny | Tradycyjny, zagnieżdżony algorytm genetyczny | Zmodyfikowany, podstawowy algorytm genetyczny | Zmodyfikowany, zagnieżdżony algorytm genetyczny | |
|---|---|---|---|---|
| Rozmiar populacji podstawowej | 64 | 64 | 64 | 64 |
| Rozmiar populacji nadrzędnej | - | 32 | - | 32 |
| Liczba uruchomień | 10 | 10 | 10 | 10 |
| Uruchomienia zakończone sukcesem | 3 | 7 | 10 | 10 |
| Maksymalna liczba generacji | 64 | 64 | 64 | 64 |
| Średnia liczba generacji | 60,1 | 24,3 | 11,5 | 4,2 |
| Średnia wartość funkcji przystosowania | 5,9603 | 5,9687 | 5,9689 | 5,9689 |
Źródło: opracowanie własne
W przypadku wszystkich trzech funkcji testowych uzyskałem wyniki prowadzące do podobnych wniosków. Najniższą efektywność, rozumianą jako liczbę prób zakończonych sukcesem oraz średnią ilość potrzebnych generacji, uzyskał algorytm genetyczny w wersji podstawowej. Zdecydowanie lepsza okazała się jego wersja zagnieżdżona. Zmodyfikowany algorytm ewolucyjny był przeciętnie lepszy od wymienionych wcześniej, a jego wersja zagnieżdżona odszukiwała maksimum globalne najszybciej i ze 100% skutecznością.
9. Wyniki optymalizacji parametrów działania algorytmu genetycznego
Optymalizacja parametrów działania algorytmu genetycznego dostarczyła ciekawych wyników końcowych wyznaczających zgodnie z założeniami ich najlepsze wielkości. Uzyskane wartości parametrów cechowały się dużym rozrzutem, co wymusiło użycie charakterystyk statystycznych w postaci wartości średniej oraz odchylenia standardowego.
| Parametr | Tradycyjny, zagnieżdżony algorytm genetyczny | Zmodyfikowany, zagnieżdżony algorytm genetyczny | ||
|---|---|---|---|---|
| Wartość średnia | Odchylenie standardowe | Wartość średnia | Odchylenie standardowe | |
| Prawdopodobieństwo krzyżowania | 0,61 | 0,23 | 0,77 | 0,14 |
| Prawdopodobieństwo mutacji genotypu | 0,30 | 0,16 | 0,42 | 0,21 |
| Prawdopodobieństwo reprodukcji | - | - | 0,67 | 0,12 |
| Liczba punktów krzyżowania | 4,90 | 2,02 | 4,30 | 2,00 |
| Prawdopodobieństwo mutacji genu w genotypie | 0,57 | 0,21 | 0,52 | 0,33 |
Źródło: opracowanie własne
Zgodnie z wynikami uzyskanymi z 10 prób optymalna wartość prawdopodobieństwa krzyżowania oraz mutacji jest wyższa w przypadku zmodyfikowanego algorytmu genetycznego o zmiennej wielkości populacji. Obserwacje potwierdzają właściwości opisanych modyfikacji algorytmu, które miały na celu wyeliminowanie tracenia istotnych informacji z populacji oraz umożliwienie rywalizacji międzypokoleniowej.
W wyniku optymalizacji najwyższą wartość przyjmował parametr związany z prawdopodobieństwem krzyżowania, co jest zgodne z teorią algorytmów genetycznych przypisującą największe znaczenie operatorowi krzyżowania.
Pewnym zaskoczeniem w stosunku do zaleceń pojawiających się w literaturze przedmiotu jest wysokie prawdopodobieństwo mutacji oraz wskazanie na przewagę krzyżowania wielopunktowego, osiągającego wielkość 4–5 miejsc krzyżowań na genotyp.
10. Zastosowania zagnieżdżonego algorytmu genetycznego
Poszukiwanie lepszych i bardziej wydajnych odmian algorytmów ewolucyjnych często jest wymuszone bardzo złożonym charakterem zadania optymalizacyjnego oraz ogromnymi rozmiarami przestrzeni rozwiązań.
Przykładem takiego problemu jest optymalizacja lokalizacji masztów radiowych telefonii komórkowej. Duża liczba parametrów, takich jak zasięg masztu, gęstość zaludnienia, warunek pokrycia sygnałem określonego terytorium często utrudnia wyznaczenie nawet rozwiązania dopuszczalnego.
Innym problemem konsumującym ogromne zasoby mocy obliczeniowych komputerów jest optymalizowanie struktury sieci neuronowej, czyli określanie liczby warstw oraz ilości neuronów w warstwach. Algorytm genetyczny może być w tym przypadku jedyna sformalizowaną, sprawną i dobrze uzasadnioną teoretycznie procedurą poszukiwania najlepszej struktury. Niestety długi czas wykonywania obliczeń neuronowych wymaga algorytmu optymalizacji o podwyższonej efektywności.
11. Podsumowanie
Tradycyjny algorytm genetyczny jest obarczony szeregiem niepożądanych właściwości obniżających jego efektywność. Dodatkowo wymaga on dość arbitralnego określenia wartości podstawowych parametrów jego działania.
W celu podniesienia efektywności oraz wykorzystania optymalnych wartości parametrów zaproponowałem oraz przetestowałem zmodyfikowany, zagnieżdżony algorytm ewolucyjny. Modyfikacje obejmowały m.in. wprowadzanie populacji o zmiennej liczbie osobników, zastosowanie operatorów krzyżowania i mutacji na sklonowanych genotypach, użycie reguły turnieju z prawdopodobieństwem zajścia turnieju oraz optymalizację parametrów działania algorytmów genetycznych przez nadrzędny algorytm ewolucyjny.
Na postawie wyników uzyskanych z eksperymentu na trzech różnych funkcjach testowych można stwierdzić, że zaproponowane modyfikacje podnoszą efektywność optymalizacji, w tym przeciwdziałają zdominowaniu populacji oraz utracie osobników o najwyższej wartości funkcji przystosowania.
Ponadto wykorzystanie zagnieżdżonego algorytmu genetycznego zmniejsza liczbę generacji potrzebnych do odszukania rozwiązania optymalnego.
Zagnieżdżony algorytm genetyczny jest jednak bardziej złożony i wymaga większych mocy obliczeniowych, przez co porównywanie go z algorytmem tradycyjnym jest bardzo utrudnione.
Optymalizowane parametry działania algorytmu genetycznego charakteryzują się dużym rozproszeniem.
Wyniki wskazują na przewagę krzyżowania w wielu punktach oraz wyższych prawdopodobieństw mutacji. Wyznaczone prawdopodobieństwo krzyżowania ma średnio największą wartość spośród innych porównywalnych parametrów, co sugeruje jego dominującą rolę.
Nowa wersja algorytmu ewolucyjnego jest zdecydowanie bardziej efektywna od podejścia tradycyjnego i nie wykazuje niepożądanych właściwości, takich jak gubienie najlepszego rozwiązania.
Literatura
Goldberg E. D., Algorytmy genetyczne i ich zastosowanie, tłum. K. Grygiel, Wydawnictwo Naukowo-Techniczne, Warszawa 2003.
Mitchell M., An Introduction to Genetic Algorithms, The MIT Press, London 1999.
Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, tłum. Z. Nahorski, Wydawnictwo Naukowo-Techniczne, Warszawa 2003.
Rutkowska D., Rutkowski L., Piliński M., Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, Wydawnictwo Naukowe PWN, Warszawa i in. 1999.
Zieliński J. S. (red.), Bartkiewicz W., Czajka R., Gontar Z., Jęczkowska B., Pamuła A., Inteligentne systemy w zarządzaniu, Wydawnictwo Naukowe PWN, Warszawa 2000.
