Algorytmy Wielopopulacyjne - Model Wyspowy (IslandModel)
W pierwszym podrozdziale opisany zostanie proces wyłaniania się modelu wyspowego. W dalszej części zawarty jest przegląd algorytmów wielopopulacyjnych z podziałem na cztery główne parametry:
1. Topologia połączeń
2. Częstość migracji
3. Liczebność migracji
4. Metoda wyboru osobników migrujących
Początki algorytmów wielopopulacyjnych
Już w 1931 roku genetyk Sewall Wright w swojej pracy poświęconej dryfowi genetycznemu stwierdził: "(...) Z tego wynika, iż podział gatunku na lokalne rasy stanowi najefektywniejszy mechanizm prób i błędów na polu kombinacji genów".
Pierwsze równoległe implementacje algorytmów genetycznych zostały stworzone w latach 80-tych. Nie różniły się jednak one w znaczącym stopniu od klasycznych wersji algorytmu - służyły jedynie przyspieszeniu obliczeń poprzez użycie kilku maszyn i systemu współdzielenia pamięci. Zaczęto jednak zauważać, że pewne równoległe implementacje mogą doprowadzić do zmniejszenia całkowitej ilości obliczeń lub wręcz do wytworzenia "nowej jakości" w procesie ewolucyjnym.
Ważnym etapem w rozwoju modeli równoległych była praca Punctuated eąuilibria: a pa-rallel genetic algorithm (Cohoon i inni, [6]). Autorów zainspirowała teoria punktualizmu (ang. punctuated eąuilibrium) zaproponowana w 1972 roku przez paleontologów Stephena Jay Goulda oraz Niles"a Eldridge"a w celu wyjaśnienia gwałtownych zmian w populacjach. Teoria ta głosi, iż gatunki mają wrodzoną odporność na niewielkie zmiany genetyczne i zachowują pewną stabilność. Dopiero rzadki, złożony przypadek pozwala na utworzenie się nowego gatunku. Jest to przeciwieństwo gradualizmu, który zakłada kontinuum zmian. Współczesna biologia odrzuca gra-dualizm i nie pozostawia żadnych konkurencyjnych hipotez wobec punktualizmu.
Zespół pod przywództwem Cohoona opracował model, w którym cała populacja dzieli się na podpopulacje (wyspy, ang. islands, demes), w których ewolucja zachodzi w izolacji od reszty osobników. Każda z podpopulacji przechodzi inną trajektorię ewolucji i może zbiec się w innym ekstremum. Pomaga to w zapobieganiu przedwczesnej zbieżności. Co pewien okres podpopulacje wymieniają się kilkoma osobnikami w procesie migracji, co znacznie przyspiesza znalezienie rozwiązania. Model ten okazał się niezwykle skuteczny i górował nie tylko nad sekwencyjnym, ale także nad rozproszonym algorytmem bez migracji.
Wang i inni przebadali pięć różnych równoległych architektur rozwiązując problem TSP ([43]):
1. Równoległe wykonywanie szeregowego algorytmu bez komunikacji.
2. Model z migracją najlepszego osobnika zachodzącą co 5 generacji, przy czym wyspa docelowa zmienia się cyklicznie co migrację. Wysłany osobnik zastępuje najgorszego w docelowej podpopulacji.
3. Podział przestrzeni rozwiązań i przydzielenie każdego podprzedziału do innej wyspy. W pozostałych aspektach to podejście nie różni się od modelu 1.
4. Optymalizacja fragmentów rozwiązań za pomocą heurystyk i łączenie ich w większą całość.
5. Model 4 poszerzony o migracje.
Najbardziej skuteczny okazał się model ostatni. Badanie dowiodło efektywności mechanizmu migracji. Uzupełnienie modeli 1 i 4 o migrację skutkowało zarówno poprawą jakości rozwiązań, jak i skróceniem czasu obliczeń. Zdecydowanie najgorzej wypadł model 3.
Topologia połączeń
Borovska i Lazarova w [4] przebadały topologie w kształcie okręgu z migracjami w jedną lub dwie strony (Rys. 2.2b, 2.2c) oraz topologię, w której centralny proces wybiera osobniki z wszystkich wysp i wysyła je do pozostałych (Rys. 2.2a). Jest to więc połączenie "każdy z każdym". Drugą badaną zmienną był rodzaj osobników przeznaczonych do migracji - najlepsze lub losowe. Zarówno pod względem jakości rozwiązania, jak i przyspieszenia obliczeń w architekturze wieloprocesorowej (ang. speedup) najlepsze wyniki uzyskano dla dwukierunkowej migracji najlepszych chromosomów po okręgu.
Rysunek 2.1: Topologie przebadane przez Borovskąi Lazarovą.
Cantú-Paz w [5] wprowadza pojęcie stopnia wyspy (ang. degree). Stopień określa liczbę sąsiadów, czyli wysp, do których wysyłane są osobniki. Proponuje trzy różne topologie, w których każda wyspa ma stopień równy 2. Nadał im nazwy: drabina, okrąg 1+2 oraz okrąg 2+3. Zostały one przedstawione na rysunku 2.2.
Rysunek 2.2: Topologie przebadane przez Cantú-Paz.
Cantú-Paz dowodzi, że to stopień wysp determinuje dynamikę całej populacji, a nie konkretna topologia. Autor oblicza optymalny stopień dla topologii złożonej z ośmiu wysp. Wyniki teoretyczne zestawia z wynikami eksperymentalnymi. Wynika z nich, że, aby zminimalizować czas konwergencji, wyspy powinny być stopnia 2 lub 3.
Whitley w swoich badaniach nad optymalizacją funkcji ([44]) rozdzielił 5000 kodowanych binarnie osobników pomiędzy różną ilość wysp. Zauważył, iż optymalna liczba wysp może być zależna od instancji testowej. Większa granulacja dawała lepsze efekty dla problemów zwodniczych. Dla instancji o bardziej równomiernej przestrzeni rozwiązań nie zauważono istotnego wpływu granulacji na jakość rozwiązań.
Sekaj w [34] dokonał przeglądu sześciu topologii. Oprócz opisanej wcześniej topologii w kształcie okręgu prezentuje dwie topologie w kształcie siatki oraz trzy hierarchiczne topologie, w których migracje odbywają się zawsze w jednym kierunku i kończą się na jednej wyspie. Autor wskazał te ostatnie jako najbardziej skuteczne.
Częstość migracji
Zagadnieniu częstości migracji poświęcono relatywnie niewiele uwagi. W wielu pracach znajduje się wzmianka o interwałach w wysyłaniu migrantów, lecz najczęściej pomija się fakt, iż ze wzrostem częstości wysyłania stałej liczby migrantów rośnie całkowita liczba migrujących osobników. Zdaniem autora pracy należy oddzielić badania nad częstością migracji od badań nad rozmiarem całkowitego strumienia migracji.
Skolicki oraz De Jong przeprowadzili badanie wpływu interwałów między migracjami oraz ich liczebnością na przebieg obliczeń ([36]). Stwierdzili, iż z uwagi na skomplikowaną strukturę algorytmów genetycznych, trudno wyciągać ogólne wnioski dla wszystkich implementacji modeli wyspowych. Przeprowadzili oni badania nad częstością migracji zakładając stały strumień migrantów. Wyniki wskazały, że częstość migracji odgrywa, w stosunku do pozostałych parametrów, nieznaczną rolę.
Liczebność migracji
Prace Grosso [15], Tanese [37] oraz Skolickiego i De Jonga [36] empirycznie potwierdzają następujące tezy:
1. Algorytmy wielopopulacyjne uzyskują lepsze rezultaty gdy występuje migracja.
2. Zbyt intensywne lub zbyt słabe migracje pogarszają efekty.
Wynika stąd, że istnieje pewna optymalna intensywność migracji, która leży między skrajnymi wartościami.
Skolicki i De Jong, odnosząc się przy tym do innych badań, stwierdzili, że 10% rozmiaru wyspy to niepotrzebnie duża liczebność. Jednak zdecydowanie negatywny skutek ujawnił się dopiero przy liczebności bliskiej liczebności samej wyspy.
W [19] zaproponowano dynamiczne dostrajanie intensywności migracji. Zdaniem autorów następujący algorytm uzyskuje przewagę nad algorytmem o stałej migracji. Decyzja o zwiększeniu lub zmniejszeniu intensywności migracji zależy od jej wpływu na jakość najlepszego uzyskanego rozwiązania.
Wygeneruj N podpopulacji P1, P2,..., PN
generacja ← 1
while generacja ≤ maxGeneracji do
for all Pi do
Oceń wszystkie osobniki w Pi
Wykonaj operatory krzyżowania i mutacji
Zastąp poprzednią generację potomkami
end for
generacja ← generacja + 1
if generacja % interwał == 0 then
Policz przyrosty wartości przystosowania (fitness increase) FIi,t najlepszego osobnika w Pi
end if
if FIi,t> FIi,t-1 then
zwiększ intensywność migracji do Pi
else if FIi,t < FIi,t-1 then
zmniejsz intensywność migracji do Pi
else
nie zmieniaj migracji
end if
end while
Metoda wyboru osobników migrujących
Selekcja preferująca lepiej przystosowanych migrantów może znacząco zwiększyć napór selekcyjny. Działanie jest dodatkowo spotęgowane sytuacją, gdy osobniki są kopiowane, a nie przemieszczane między podpopulacjami. Używając losowego wyboru można zrezygnować z presji selekcyjnej przy migracji.
Danzinger i Kidney w [9] zaproponowali wykorzystanie nie tylko wartości przystosowania, ale także różnorodności do selekcji osobników. Użyli mieszanej wagi, aby zwiększyć szansę na migrację zróżnicowanych osobników.
Borovska i Lazarova uzyskały lepszy wynik przy wyborze osobników najlepszych niż przy wyborze losowym [4]. Dotyczyło to wszystkich rozpatrywanych topologii.
komentarze
Copyright © 2008-2010 EPrace oraz autorzy prac.