praca inzynierska rozproszona platforma algorytmów

Bielska Wyższa Szkoła Biznesu i Informatyki im. J. Tyszkiewicza
Wydział Informatyki i Zarządzania
Kierunek Informatyka
PRACA INŻYNIERSKA
Seweryn Hejnowicz
Rozproszona Platforma
Implementacji Algorytmów
Ewolucyjnych
Promotor pracy:
dr Maciej Smołka
Recenzent pracy:
prof. dr hab. inż. Robert Schaefer
Bielsko-Biała 2004
Bielsko-Biała, 08-04-2004
Seweryn Hejnowicz
Bielska Wyższa Szkoła Biznesu i Informatyki im. J. Tyszkiewicza
Informatyka
OŚWIADCZENIE
Świadom odpowiedzialności prawnej oświadczam, że złożona praca
inżynierska pt.: Rozproszona Platforma Implementacji Algorytmów Ewolucyjnych
została napisana przeze mnie samodzielnie.
Równocześnie oświadczam, że praca ta nie narusza praw autorskich w
rozumieniu ustawy z dnia 4 lutego 1994 roku o prawie autorskim i prawach
pokrewnych (Dz. U. 1994 nr 24 poz. 83) oraz dóbr osobistych chronionych prawem
cywilnym.
Ponadto praca nie zawiera informacji i danych uzyskanych w sposób
nielegalny i nie była wcześniej przedmiotem innych procedur urzędowych
związanych z uzyskaniem dyplomów lub tytułów zawodowych uczelni wyższej.
Seweryn Hejnowicz
2
Spis treści
Wstęp ......................................................................................................................... 8
I. Wprowadzenie do algorytmów ewolucyjnych ........................................................ 10
1. Czym są algorytmy ewolucyjne?................................................................... 10
2. Dlaczego algorytmy ewolucyjne?.................................................................. 10
3. Podstawowe pojęcia ..................................................................................... 11
4. Zastosowania algorytmów ewolucyjnych ...................................................... 12
5. Budowa algorytmu ewolucyjnego.................................................................. 12
5.1. Prosty algorytm genetyczny, a prosty algorytm ewolucyjny ................. 12
5.2. Zdefiniowanie problemu ....................................................................... 14
5.3. Kodowanie oraz budowa chromosomu ................................................ 14
5.4. Generowanie populacji początkowej .................................................... 15
5.5. Funkcja przystosowania (fitness) ......................................................... 16
5.6. Zdefiniowanie operacji genetycznych................................................... 16
5.7. Selekcja ............................................................................................... 19
5.8. Warunek stopu..................................................................................... 20
5.9. Parametry algorytmu............................................................................ 21
5.10. Podsumowanie................................................................................... 22
6. Algorytm ewolucyjny z ustalonym stanem..................................................... 22
II. Współbieżne algorytmy ewolucyjne...................................................................... 24
1. Wprowadzenie .............................................................................................. 24
1.1. Niedogodności modeli sekwencyjnych................................................. 24
1.2. Dlaczego współbieżność?.................................................................... 25
1.3. Równoległa i rozproszona architektura komputerowa.......................... 25
2. Przykładowa taksonomia .............................................................................. 28
2.1. Różne klasyfikacje i modele................................................................. 28
2.2. Zrównoleglenie globalne model Master-Slave................................... 29
2.3. Model subpopulacyjny z migracją ........................................................ 30
2.4. Model subpopulacyjny z nakładaniem bez migracji.............................. 32
2.5. Masywnie zrównoleglony algorytm ewolucyjny .................................... 33
2.6. Model Master-Slave z dynamiczną reorganizacją subpopulacji ........... 33
2.7. Podsumowanie..................................................................................... 35
III. Rozproszona platforma ewolucyjna..................................................................... 36
3
1. Założenia ogólne projektu............................................................................. 36
2. Budowa systemu........................................................................................... 38
2.1. Architektura.......................................................................................... 38
2.2. Koncepcja rozproszonych obiektów ..................................................... 39
2.3. Interfejsy komunikacji RPE z użytkownikiem ....................................... 40
2.4. Algorytm ewolucyjny - model tworzenia prób losowych (populacji)...... 42
2.5. Wyspa - środowisko wykonania algorytmu ewolucyjnego.................... 44
2.6. Topologie ............................................................................................. 45
2.7. Platforma - współbieżne środowisko działania wysp............................ 47
2.8. Konsola platformy ................................................................................ 48
2.9. Platforma główna - koordynator systemu ............................................. 48
3. Realizacja zadań systemu ............................................................................ 50
3.1. Sekwencyjna implementacja algorytmu ............................................... 50
3.2. Rozproszona implementacja algorytmu ............................................... 50
3.3. Dystrybucja klas algorytmu w systemie................................................ 51
3.4. Synchroniczna realizacja migracji ........................................................ 52
3.5. Asynchroniczna realizacja migracji ...................................................... 53
3.6. Dynamiczne równoważenie narzutu obliczeniowego na platformach... 54
3.7. Detekcja zakończenia działania algorytmu .......................................... 56
3.8. Bezpieczeństwo platform ..................................................................... 56
3.9. Odporność na awarie ........................................................................... 57
4. Szczegóły implementacyjne.......................................................................... 57
4.1. Implementacja projektu na platformie Java.......................................... 57
4.2. Odwzorowanie projektu w strukturze pakietów Javy............................ 58
4.3. RMI jako implementacja koncepcji rozproszonych obiektów w Javie... 61
IV. Graficzne środowisko szybkiego rozwoju algorytmów ewolucyjnych .................. 63
1. Założenia ogólne........................................................................................... 63
2. Opis interfejsu użytkownika........................................................................... 63
V. Implementacja przykładowego algorytmu problem komiwojażera..................... 68
1. Zdefiniowanie problemu komiwojażera ......................................................... 68
2. Struktura oraz kodowanie chromosomu........................................................ 68
3. Funkcja przystosowania................................................................................ 68
4. Implementacja interfejsu Individual ............................................................... 69
5. Implementacja interfejsu Results .................................................................. 71
6. Operatory genetyczne................................................................................... 72
4
6.1. Mutacja ................................................................................................ 72
6.2. Krzyżowanie......................................................................................... 72
VI. Eksperymenty, testy, wnioski .............................................................................. 75
1. Porównanie implementacji sekwencyjnej z rozproszoną............................... 75
2. Skalowalność modelu wyspowego i obliczanie przyśpieszenia działania ..... 77
3. Testy algorytmu dynamicznego równoważenia narzutu obliczeniowego na
platformach ....................................................................................................... 79
VII. Podsumowanie................................................................................................... 80
Literatura .................................................................................................................. 82
5
Spis Ilustracji
Rysunek I-1 schemat blokowy modeli SGA/SEA...................................................... 13
Rysunek I-2 przykład - zakodowany binarnie chromosom........................................ 15
Rysunek I-3 binarne krzyżowanie maskowe............................................................. 17
Rysunek I-4 binarna mutacja maskowa.................................................................... 17
Rysunek I-5 binarna mutacja jednopunktowa........................................................... 18
Rysunek I-6 binarne krzyżowanie jednopunktowe.................................................... 18
Rysunek I-7 schemat blokowy modelu Steady State................................................ 23
Rysunek II-1 luzno zintegrowany system wieloprocesorowy .................................... 26
Rysunek II-2 ściśle zintegrowany system wieloprocesorowy.................................... 26
Rysunek II-3 schemat architektury typu SISD .......................................................... 27
Rysunek II-4 schemat architektury typu SIMD.......................................................... 27
Rysunek II-5 schemat architektury typu MIMD ......................................................... 28
Rysunek II-6 zrównoleglenie globalne model Master-Slave .................................. 30
Rysunek II-7 model Stepping-Stone Rysunek II-8 model wyspowy .................... 32
Rysunek II-9 model subpopulacyjny z nakładaniem bez migracji............................. 32
Rysunek II-10 masywnie zrównoleglony algorytm ewolucyjny z topologią siatki 2D. 33
Rysunek II-11 model Master-Slave z dynamiczną reorganizacją subpopulacji......... 34
Rysunek III-1 schemat warstwowej struktury RPE ................................................... 38
Rysunek III-2 rozproszona architektura RPE............................................................ 39
Rysunek III-3 diagram interfejsów rozproszonych obiektów ..................................... 40
Rysunek III-4 diagram zależności interfejsów Individual oraz Results...................... 42
Rysunek III-5 diagram zależności klas w warstwe logiki algorytmu .......................... 43
Rysunek III-6 diagram klas wyspy ............................................................................ 45
Rysunek III-7 topologie połączeń wysp w RPE: a) pierścień, b) siatka 2D, c) pełny
graf .................................................................................................................... 45
Rysunek III-8 diagram klas zarządzających migracją oraz topologii......................... 46
Rysunek III-9 diagram klas platformy ....................................................................... 47
Rysunek III-10 konsola platformy ............................................................................. 48
Rysunek III-11 diagram klas platformy głównej ........................................................ 49
Rysunek III-12 diagram interakcji dla sekwencyjnej implementacji algorytmu.......... 50
Rysunek III-13 diagram rozproszonej implementacji algorytmu................................ 51
6
Rysunek III-14 diagram dystrybucji klas algorytmu w systemie................................ 52
Rysunek III-15 schemat przedstawiający synchroniczną migrację ........................... 52
Rysunek III-16 schemat przedstawiający asynchroniczną migrację ......................... 53
Rysunek III-17 diagram stanów dla menedżera emigracji ........................................ 54
Rysunek III-18 diagram interakcji algorytmu DLB..................................................... 55
Rysunek III-19 diagram wdrożenia RPE................................................................... 58
Rysunek IV-1 okno główne graficznej aplikacji zintegrowanej z RPE....................... 64
Rysunek IV-2 okno konfiguracji czasu wykonania oraz projektu .............................. 65
Rysunek IV-3 okno konfiguracji modeli ewolucyjnych .............................................. 65
Rysunek IV-4 okno konfiguracji Modelu Wyspowego ............................................... 66
Rysunek IV-5 okno konfiguracji platform i wysp ....................................................... 67
Rysunek V-1 Diagram klasowy (Individual) dla problemu komiwojażera.................. 69
Rysunek V-2 Diagram klasowy (Results) dla problemu komiwojażera ..................... 71
Rysunek V-3 diagram klas odpowiedzialnych z mutację w problemie komiwojażera 72
Rysunek V-4 diagram klas odpowiedzialnych z krzyżowanie w problemie
komiwojażera .................................................................................................... 74
Rysunek VI-1 wykres obrazujący przyrost szybkości działania algorytmu................ 78
7
Wstęp
W pracy tej zostanie przedstawiony projekt oraz implementacja przykładowej
rozproszonej platformy ewolucyjnej. Platforma ta, będzie pewnym rozproszonym
środowiskiem implementacji oraz działania algorytmów ewolucyjnych. Opierając się
na fakcie niezmienności i uniwersalności pewnych koncepcji, schematów oraz modeli
ewolucyjnych, jesteśmy w stanie oddzielić istotę oraz mechanizmy działania
algorytmu od szczegółów implementacyjnych właściwych rozwiązywanemu
problemowi. W ten sposób użytkownik platformy uwolniony zostanie od żmudnego
pisania kodu, tworzenia interfejsów graficznych oraz robienia innych rzeczy, których
realizacja za każdym razem jest de facto taka sama.
Rozproszona platforma ewolucyjna zapewni użytkownikowi możliwość
napisania, załadowania, konfiguracji oraz implementacji dowolnego algorytmu (przy
minimalnym nakładzie pracy) zgodnie z najpopularniejszymi modelami tworzenia
kolejnych prób losowych. W zależności od wyboru przez użytkownika sposobu
kodowania w swoich algorytmach, tymi modelami będą: prosty algorytm ewolucyjny
(genetyczny) oraz algorytm ewolucyjny (genetyczny) z ustalonym stanem
(ang. Steady State).
Kolejnym bardzo ważnym aspektem funkcjonalnym platformy będzie
możliwość implementacji algorytmu w sposób współbieżny. Odkąd algorytmy
ewolucyjne zaczęły być wykorzystywane do przeszukiwania coraz to większych,
wręcz ogromnych obszarów potencjalnych rozwiązań, pojawiły się pewne problemy
złożoności obliczeniowej i związanym z nią narzutem czasowym. Dodając do tego
kosztowną obliczeniowo (dla pewnych problemów) funkcję ewaluacji rozwiązań,
otrzymujemy poważne ograniczenie, które dla pewnych rozpatrywanych problemów
(np. optymalne sterowanie) okazuje się krytyczne. Współbieżność jest tutaj pewnym
lekarstwem.
Już pierwsi badacze zauważyli współbieżną naturę algorytmów ewolucyjnych.
Tak jak w rzeczywistości wiele istnień równolegle bierze udział w procesach
ewolucyjnych, tak i adaptacja tych procesów w tej grupie algorytmów spowodowała
możliwość łatwego i naturalnego ich zrównoleglenia. Rozproszona platforma
ewolucyjna będzie umożliwiała implementacje algorytmów w oparciu o jeden z takich
8
modeli współbieżnych. Będzie to popularny model subpopulacyjny z migracją zwany
rozproszonym algorytmem ewolucyjnym lub potocznie modelem wyspowym.
Cała teoria przedstawiona w pracy, a dotycząca algorytmów genetycznych
i ewolucyjnych, została opracowana na podstawie trzech książek: Podstawy
genetycznej optymalizacji globalnej prof. Roberta Schaefera [SCHA02], Algorytmy
Genetyczne i ich zastosowania Davida Goldberga [GOLD98] oraz Algorytmy
Genetyczne + struktury danych = programy ewolucyjne Zbigniewa Michalewicza
[MICH99].
Teoria dotycząca współbieżnych algorytmów ewolucyjnych opracowana
została na podstawie różnych publikacji dostępnych w Internecie. Każdorazowo
dołączana jest informacja o publikacji na podstawie której został opracowany
konkretny fragment pracy.
9
I. Wprowadzenie do algorytmów
ewolucyjnych
1. Czym są algorytmy ewolucyjne?
Obok strategii ewolucyjnych, programowania ewolucyjnego, programowania
genetycznego i algorytmów genetycznych, algorytmy ewolucyjne (dalej AE) należą
do systemów rozwiązywania zadań opartych o zasady ewolucji i dziedziczności.
AE można uważać za stochastyczne techniki poszukiwań optymalnych
rozwiązań, stosowanych do rozwiązywania szczególnie trudnych, wielomodalnych
problemów optymalizacji ciągłej oraz dyskretnej. Tworzone losowo w każdej iteracji
populacje rozwiązań (próby losowe) powstają w pewien inteligentny sposób (w
oparciu o teorię doboru naturalnego i zasadę dziedziczności), co odróżnia je od tych
algorytmów stochastycznych, które wykorzystują w tym celu jednostajny rozkład
prawdopodobieństwa [SCHA02].
2. Dlaczego algorytmy ewolucyjne?
Zaproponowane przez Hollanda w [HOLL75] algorytmy genetyczne (dalej AG)
zakładały binarne kodowanie rozwiązań oraz dwa operatory: binarną mutację oraz
binarne krzyżowanie. Podejście takie wynikało z dobrze sprecyzowanej teorii
o schematach i hipotezie bloków budujących, które pozwalały na teoretyczną analizę
algorytmów genetycznych. Binarne kodowanie wymagało jednak często bardzo
kłopotliwych zabiegów, a binarne operatory często nie pozwalały na uwzględnienie
pewnych nietrywialnych ograniczeń, charakterystycznych dla konkretnych zadań.
Uniwersalność binarnych operatorów stawała się więc często kłopotliwa i bez
pewnych algorytmów naprawy AG stawał się mało skuteczny [MICH99].
Te i inne ograniczenia AG wpłynęły na powstanie szeregu mutacji , które
zakładały nie tylko różne od binarnego kodowanie, ale definiowały również wiele
specyficznych dla konkretnych zadań operatorów genetycznych. Tą grupę
algorytmów będziemy nazywać algorytmami ewolucyjnymi. AE, kosztem utraty
oparcia w teorii o schematach Hollanda, zyskały jednak znaczną wartość praktyczną.
10
3. Podstawowe pojęcia
Istnieje pewien zbiór podstawowych pojęć charakteryzujący algorytmy
ewolucyjne. Większość z nich zaczerpnięta została z nauk biologicznych. Te pojęcia
to:
" genotyp pewien rodzaj kodu przeznaczony do reprezentowania rozwiązania
w postaci łańcucha symboli
" chromosom jeden zakodowany łańcuch symboli
" osobnik jest to chromosom (jeden lub więcej), dla którego jesteśmy
w stanie policzyć jego przystosowanie
" gen jedna cecha w chromosomie
" allel wartość genu: liczba binarna, rzeczywista lub bardziej złożone struktury
" locus - pozycja genu w chromosomie
" fenotyp zdekodowany genotyp, czyli zestaw cech stanowiący jedno
z rozwiązań z przeszukiwanej przestrzeni
" funkcja przystosowania (fitness) funkcja oceniająca osobnika. Pozwala
określić, w jakim stopniu dane rozwiązanie jest dobre
" problem jest to problem, jaki musi rozwiązać algorytm ewolucyjny.
Przedstawiany jest w postaci funkcji celu
" populacja zbiór osobników stanowiący próbę losową w danej iteracji
algorytmu
" selekcja jest to pewien schemat selekcji osobników (na podstawie funkcji
fitness) przeznaczonych do reprodukcji
" krzyżowanie - operacja łącząca zgodnie z pewnym schematem genotypy
dwóch lub więcej osobników. Wynikiem tej operacji jest powstanie jednego
lub więcej nowych rozwiązań-potomków
" mutacja operacja polegająca na losowym zaburzeniu genotypu danego
osobnika
11
4. Zastosowania algorytmów ewolucyjnych
Istnieje wiele zastosowań AE. Do najważniejszych można zaliczyć:
" optymalizacja globalna: optymalne przepływy w sieciach energetycznych,
komputerowych, marketingowych
" optymalne projektowanie
" optymalna aproksymacja: aproksymacja funkcji
" uczenie maszynowe
" problem generalizacji: klasyfikacja i rozpoznawanie wzorców, klasteryzacja
" systemy hybrydowe: zastosowanie w sieciach neuronowych - optymalne
projektowanie oraz uczenie
5. Budowa algorytmu ewolucyjnego
5.1. Prosty algorytm genetyczny, a prosty algorytm ewolucyjny
Terminy prosty algorytm genetyczny (ang. SGA Simple Genetic Algorithm)
oraz prosty algorytm ewolucyjny (ang. SEA Simple Evolutionary Algorithm)
odnoszą się do pewnego modelu tworzenia kolejnych populacji rozwiązań
(prób losowych) w każdej iteracji AE. Oba modele zakładają istnienie jednej
operacji selekcji oraz dwóch operatorów genetycznych krzyżowania oraz
mutacji. SGA jest podstawowym modelem dla algorytmów genetycznych, a SEA dla
algorytmów ewolucyjnych. Schemat blokowy, przedstawiony poniżej, jest wspólny
dla obu.
12
Wygeneruj populację
początkową p
Określ przystosowanie
wszystkich osobników w p
czy koniec ?
[ TAK ]
[ NIE ]
Wyselekcjonuj 2
osobniki do rozrodu
Wykonaj operacje
genetyczne
Dodaj potomków do
nowej populacji p'
[ NIE ]
czy p' pełne ?
[ TAK ]
zastąp bierzacą
populację p populacją p'
Rysunek I-1 schemat blokowy modeli SGA/SEA
AE zaczyna się wygenerowaniem w pewien sposób początkowej populacji p
rozwiązań (osobników). Taki zbiór jest następnie oceniany funkcją przystosowania
(fitness). Jeżeli spełniony został warunek stopu, to wykonanie algorytmu zostaje
zakończone, a rozwiązaniem staje się najlepszy osobnik z populacji. Jeżeli jednak
warunek stopu nie zaszedł, formowana jest, zgodnie z modelem SGA/SEA, nowa
populacja. Operacja ta polega cyklicznym losowaniu pary osobników (zgodnie z
odpowiednim rozkładem prawdopodobieństwa), na których wykonuje się operatory
genetyczne mutacji i krzyżowania (operacja mieszania), a powstałego osobnika
(osobników) umieszcza się w populacji p . Proces powtarza się do momentu, gdy
populacja potomków p zawiera odpowiednią liczbę osobników, np. równą liczbie
13
osobników w p. Następnie osobniki z p przenoszone są do p, po czym algorytm
wraca do fazy oceniania osobników w populacji p.
Widać więc wyraznie, że koncepcje AE są dosyć proste. Każdy AE zaczyna
się wygenerowaniem populacji początkowej, oceny oraz generowaniu następnych
prób losowych. Właśnie sposób generowania tych prób sprawia, że AE można
dostosować do konkretnych problemów. Model SGA/SEA jest jednym z
podstawowych takich sposobów, aczkolwiek rozwiązuje on wiele z rzeczywistych
problemów optymalizacji. Jeżeli jednak problem wymaga bardziej rozbudowanych
mechanizmów, to oczywiście takie mechanizmy można stworzyć. Nie ma tutaj
ograniczeń ani w sposobie selekcji, kodowaniu ani w postaci i ilości operatorów
genetycznych.
5.2. Zdefiniowanie problemu
Każdy rozpatrywany przez AE problem przedstawiany jest w postaci funkcji
celu. Zadaniem algorytmu będzie znalezienie jednego lub wielu optimów globalnych
tej funkcji.
5.3. Kodowanie oraz budowa chromosomu
Kluczowym elementem w AE jest wybór sposobu, w jaki parametry funkcji celu
będą zakodowane. Algorytmy genetyczne są szczególnym przypadkiem AE
i zakładają kodowanie binarne, co ma swoje wady i zalety. Jak zostało już
powiedziane, takie podejście gwarantuje możliwość formalnego badania dynamiki
algorytmu w oparciu o twierdzenie o schematach i hipotezę bloków budujących
oraz używanie uniwersalnych, binarnych operatorów genetycznych. Wad takiego
podejścia jest kilka. Jedną z nich jest częsta niemożność uwzględnienia pewnych
nietrywialnych ograniczeń, które muszą spełnić generowane rozwiązania. Objawia
się to w postaci spadku wydajności AG, który zamiast przeszukiwać zbiory
poprawnych rozwiązań, zajmuje się naprawianiem (lub usuwaniem) rozwiązań
niepoprawnych. Dla zadań z ciągłą dziedziną dochodzi problem znacznego wzrostu
przeszukiwanej przestrzeni rozwiązań (w zależności od żądanej dokładności), a dla
dziedzin dyskretnych problem niewykorzystywania niektórych kombinacji bitowych,
co prowadzi do marnotrawienia zasobów.
14
Dla AE nie ma żadnych ograniczeń, co do kodowania. Możemy za każdym
razem dostosować kodowanie do konkretnego problemu. Dozwolone są
reprezentacje rzeczywiste, zmiennopozycyjne, macierzowe, drzewiaste, grafowe
bądz jakiekolwiek inne.
Po wyborze kodowania parametry funkcji celu będą razem zestawiane liniowo
w pewien zakodowany łańcuch znaków - genotyp. Jeden konkretny łańcuch
znaków to chromosom. Każdy element tego łańcucha nazywać będziemy genem, a
pozycję genu w ciągu znaków - locusem. Każdy gen będzie występował w pewnym
stanie np. dla kodowania binarnego będą to dwa stany {0,1}, a dla rzeczywistego
10 {0..9}. Mówimy, że stan genu jest jego allelem (cechą). Znaczeniem genotypu
(postacią zdekodowaną) będzie zestaw cech fenotyp, stanowiący rozwiązanie
danego problemu.
Istnieje rozróżnienie, co do budowy chromosomu z uwagi na znaczenie
pozycji genu. Dla klasycznego podejścia każdy gen ma na stałe przypisaną pozycję
w chromosomie, a operatory genetyczne powodują jedynie zmianę poszczególnych
alleli, nie zmieniając pozycji genu. Inne podejścia to permutacyjne oraz drzewiaste.
W tych podejściach operatory genetyczne nie operują na allelach tylko na genach,
zmieniając ich pozycje w chromosomie. Takie podejście (permutacyjne) stosuje się
np. w rozwiązaniu Problemu Komiwojażera (patrz rozdz.V).
Rysunek I-2 przykład - zakodowany binarnie chromosom
5.4. Generowanie populacji początkowej
Najprostszą metodą generowania początkowej populacji rozwiązań jest
metoda losowa. Dla każdego osobnika w populacji początkowej jego genotyp
generowany jest zgodnie z jednostajnym rozkładem prawdopodobieństwa.
Jeżeli jednak znamy przybliżone rejony, w których znajdują się szukane
optima globalne, możemy tą wiedzę wykorzystać i stworzyć populację w ten
sposób, aby osobniki z większym prawdopodobieństwem skupiły się w tych
rejonach.
15
5.5. Funkcja przystosowania (fitness)
Funkcja przystosowania fitness pełni w AE rolę, jaką pełni środowisko w
procesach ewolucyjnych zachodzących w rzeczywistości. To środowisko weryfikuje
przystosowanie danego osobnika do określonych warunków. Funkcja
przystosowania będzie więc mówić w jakim stopniu dany osobnik (rozwiązanie) jest
dobre. Na tej podstawie pewne osobniki będą miały większą szansę na wydanie
potomstwa, a inne mniejszą, co pozwoli na propagowanie dobrego materiału
genetycznego między epokami.
Dla algorytmów klasy SGA/SEA definiuje się jedną funkcję przystosowania,
aczkolwiek są problemy optymalizacyjne (optymalizacja wielokryterialna), gdzie
osobniki oceniane są na kilka sposobów.
5.6. Zdefiniowanie operacji genetycznych
SEA/SGA zakładają istnienie dwóch operatorów genetycznych: mutacji
i krzyżowania. Krzyżowanie ma za zadanie z dwóch osobników stworzyć jednego
lub kilku potomków, których genotypy powstaną z genotypów rodziców np. poprzez
wymianę fragmentów genotypu. Mutacja natomiast polega na losowym zaburzeniu
genotypu danego osobnika. Jej zadaniem jest utrzymywanie jak największej
różnorodności w populacji, co ma być sposobem obrony przed przedwczesną
zbieżnością. Mutacja powoduje, że w każdej iteracji algorytmu zawsze jest możliwe
pojawienie się osobnika z całej przeszukiwanej przestrzeni rozwiązań.
Dla kodowania binarnego dwa najpopularniejsze rodzaje operatorów genetycznych
to: mutacja i krzyżowanie maskowe oraz mutacja i krzyżowanie jednopunktowe /
wielopunktowe.
Operatory maskowe zakładają losowe wygenerowanie pewnej maski binarnej o
długości równej długości chromosomu.
Po krzyżowaniu powstają 2 nowe osobniki. Jeden posiada genotyp matki
skrzyżowany z genotypem ojca (na podstawie maski), a drugi posiada genotyp ojca
skrzyżowany z genotypem matki. Krzyżowanie polega na zamianie alleli na
pozycjach, które określiła maska.
16
Rysunek I-3 binarne krzyżowanie maskowe
Zadaniem mutacji jest natomiast negacja tych alleli, które zostały określone przez
maskę. Zakłada się, że mutacja maskowa będzie dotyczyć każdego osobnika,
aczkolwiek prawdopodobieństwo wystąpienia 1 w masce będzie bardzo małe.
Rysunek I-4 binarna mutacja maskowa
Operatory jednopunktowe mają z kolei następujące zasady:
Jednopunktowa mutacja polega na zanegowaniu jednego, ustalonego na drodze
losowania, genu u każdego osobnika z pewnym niewielkim prawdopodobieństwem.
17
Rysunek I-5 binarna mutacja jednopunktowa
Krzyżowanie jednopunktowe natomiast zakłada wylosowanie pozycji w genotypie
i zamienieniu tych fragmentów dwóch genotypów, które znajdują się po danej
pozycji. Potomek pierwszy będzie posiadał fragment genotypu ojca plus nabyty
fragment genotypu matki. Potomek drugi natomiast będzie posiadał fragment
genotypu matki plus nabyty fragment genotypu ojca.
Rysunek I-6 binarne krzyżowanie jednopunktowe
Binarne operatory genetyczne są uniwersalne i można je stosować w niezmienionej
postaci we wszystkich algorytmach, dla których zostało wybrane właśnie to
kodowanie. Natomiast dla algorytmów z kodowaniem innym niż binarny trzeba
zdefiniować zupełnie różne wersje tych operatorów. Dla kodowania rzeczywistego
18
definiuje się mutację normalną1 oraz krzyżowanie arytmetyczne [SCHA02]. Inny
przykład operatorów można znalezć w dalszej części pracy, gdzie przedstawiono
algorytm ewolucyjny rozwiązujący problem komiwojażera.
5.7. Selekcja
AE zakłada istnienie pewnego schematu selekcjonowania osobników do
reprodukcji. Taki schemat powinien zapewniać większe prawdopodobieństwo
wydania potomstwa dla osobników lepiej przystosowanych, a mniejsze dla gorzej
przystosowanych. Istnieje kilka takich schematów [SCHA02]. W tej pracy
przedstawione zostaną trzy podstawowe:
" selekcja proporcjonalna (ruletkowa):
Metoda selekcji proporcjonalnej, zwaną ruletkową, polega na przydzieleniu
każdemu osobnikowi przedziału na ruletce, proporcjonalnie do jego
przystosowania. Z tego faktu wynika to, że osobniki najlepiej przystosowane
będą posiadać przedziały większe od osobników gorzej przystosowanych.
Selekcja polega na rzuceniu piłeczki na ruletkę . Największe szanse na
wylosowanie mają osobniki najlepiej przystosowane (czyli te, które mają
największe przedziały na ruletce). Proporcje przedziałów obliczamy z
następującego wzoru.
Fitness (oi )
Pr oi=
n
"Fitness (o )
j
j=1
Gdzie oi to osobnik, dla którego wyznaczamy przedział.
Selekcja proporcjonalna nadaje się do stosowania w tych algorytmach, dla
których jesteśmy w stanie określić proporcje dla każdego osobnika. Da się to
1
Mutacja normalna odbywa się zgodnie z normalnym rozkładem prawdopodobieństwa (rozkład
Gaussa).
19
zrobić, gdy funkcja fitness posiada przeciwdziedzinę dodatnią, a zadanie
algorytmu polega na jej maksymalizowaniu 2
" selekcja turniejowa (turniej stochastyczny):
Selekcja turniejowa polega na wyselekcjonowaniu w pewien sposób
zbioru s osobników, stanowiących grupę turniejową. Do reprodukcji zostaje
wybrany najlepszy osobnik z grupy turniejowej. Przyjmuje się, że wielkość
grupy turniejowej jest niewielka, a losowanie osobników do tej grupy odbywa
się z jednostajnym rozkładem prawdopodobieństwa, bez zwrotów. Ze względu
na uniwersalność tej metody, która potrzebuje jedynie wiedzy na temat
lepszości danego osobnika nad innym, z powodzeniem może być
implementowana w takim systemie jak prezentowana w tej pracy rozproszona
platforma ewolucyjna - z definicji ogólna, pozwalająca na rozwiązywanie
dowolnych problemów minimalizacji, maksymalizacji przy ujemnej bądz
dodatniej funkcji celu
" selekcja rangowa:
Selekcja rangowa zakłada ustawienie wszystkich osobników w
kolejności: od najlepszego do najgorszego. Każdej pozycji na liście będzie
przypisane pewne prawdopodobieństwo. Im wyższa pozycja na liście, tym
większe prawdopodobieństwo wyboru
5.8. Warunek stopu
Warunek stopu będzie określał moment, w którym AE powinien zakończyć
swoje działanie.
Istnieje kilka możliwych warunków stopu np.:
" została osiągnięta zadana liczba iteracji algorytmu
2
Selekcję proporcjonalną można stosować również przy minimalizacji funkcji przystosowania.
Wymagany jest jednak warunek znajomości maksymalnej wartości tej funkcji. Proporcje wyznaczamy
wtedy ze wzoru :
MAX -Fitness (oi )
Pr oi=
n
)
"Fitness (o j
j=1
20
" została osiągnięta zadana liczba ewaluacji osobników (obliczenie funkcji
fitness)
" został osiągnięty moment stagnacji AE, czyli moment, w którym
produkowane są już tylko rozwiązania takie same bądz sobie podobne.
Oznaczać to będzie, że AE zatrzymał się już na optimum globalnym lub
którymś z optimów lokalnych
5.9. Parametry algorytmu
Bardzo ważną rzeczą jest wybór dobrych parametrów dla każdego algorytmu.
Do tych parametrów należą:
" rozmiar populacji początkowej
Nie może to być wartość ani za mała, ani za duża. Gdy osobników jest
niewiele, to algorytm może stracić różnorodność genetyczną zbyt wcześnie, co
skończy się zatrzymaniem algorytmu na którymś z optimów lokalnych. Z kolei
za duża liczba może niepotrzebnie zwiększyć narzut obliczeniowy, przez co
algorytm stanie się mało wydajny
" prawdopodobieństwo mutacji
Dla operatora maskowego oznacza to prawdopodobieństwo
wystąpienia jedynki na każdej pozycji w masce. Natomiast dla operatora
jednopunktowego oznacza prawdopodobieństwo, z jakim dany osobnik będzie
mutowany. W obu przypadkach wartość ta powinna być niewielka np. 0.005
" prawdopodobieństwo krzyżowania:
Jest to prawdopodobieństwo, z jakim wystąpi krzyżowanie. Dla
operatora maskowego ma ono takie samo znaczenie jak w przypadku
mutacji maskowej. Natomiast prawdopodobieństwo dla krzyżowania
jednopunktowego znaczy to, czy dana operacja zajdzie czy nie. Z tego faktu
wynika to, że wartość dla operatora jednopunktowego powinna być dosyć
duża np. 0.6
21
5.10. Podsumowanie
Działanie AE jest nieskomplikowane. Algorytm zaczyna się od wygenerowania
populacji początkowej rozwiązań, oceniania tych rozwiązań oraz generowania
rozwiązań potomnych. Na potrzeby AE określić trzeba jednakże sposób tworzenia
tych rozwiązań.
Modele SGA/SEA są jednymi z podstawowych. Mimo swojej prostoty
rozwiązują one jednakże wiele z rzeczywistych problemów optymalizacyjnych.
Z racji tego, że będą one podstawowe dla prezentowanej w tej pracy rozproszonej
platformy ewolucyjnej, zostały opisane bardzo dokładnie i szczegółowo.
6. Algorytm ewolucyjny z ustalonym stanem
Jak zostało powiedziane wcześniej, AE są technikami stochastycznymi
w których generowanie kolejnych prób losowych odbywa się poprzez adaptację
pewnych procesów zachodzących w naturze. Modele SGA/SEA zakładają
adaptację tych procesów poprzez istnienie operacji selekcji oraz dwóch operatorów
genetycznych: mutacji oraz krzyżowania.
Obecnie istnieje wiele innych modeli adaptacyjnych, które mają za zadanie
zwiększyć efektywność działania AE. W tym podrozdziale zostanie przedstawiony
jeden taki algorytm zwany algorytmem ewolucyjnym z ustalonym stanem
(ang. Steady State).
Algorytm ewolucyjny z ustalonym stanem zakłada ciągły schemat
reprodukcyjny, w przeciwieństwie do schematów generacyjnych, gdzie w pewnych
dyskretnych punktach jest formowana cała nowa populacja, która zastępuje starą.
Ciągłość oznacza to, że w każdej iteracji algorytmu tworzony jest jeden potomek,
który zastępuje od razu najsłabszego, pod warunkiem, że jest od niego lepiej
przystosowany.
Więcej informacji można znalezć w [WRIG01].
22
Wygeneruj populację
początkową p
Określ przystosowanie
wszystkich osobników w p
czy koniec ?
[ TAK ]
[ NIE ]
Wyselekcjonuj 2
osobniki do rozrodu
Wykonaj operacje
genetyczne
określ przystosowanie
powstałego potomka
czy potomek lepiej
zastąp najgorszego osobnika
[ NIE ]
[ TAK ]
przystosowany od
w populacji potomkiem
najgorszego w
populacji ?
Rysunek I-7 schemat blokowy modelu Steady State
23
II. Współbieżne algorytmy ewolucyjne
1. Wprowadzenie
1.1. Niedogodności modeli sekwencyjnych
Sekwencyjne implementacje AE (SAE) sprawdziły się w wielu zastosowaniach
jako wydajne techniki przeszukiwania dużych zbiorów rozwiązań. Okazało się
jednakże, że nie wszędzie możliwe jest ich efektywne wykorzystanie. Składa się na
to kilka czynników:
" szybkość najbardziej czasochłonną operacją AE jest najczęściej
obliczanie funkcji przystosowania dla osobników. Dla niektórych problemów
czas obliczenia przystosowania jest tak duży, że sekwencyjna
implementacja AE staje się niepraktyczna. Jako przykład można podać
problem uczenia sieci neuronowej. Każdy osobnik w populacji reprezentuje
przykładową sieć neuronową. W każdej iteracji, dla każdego osobnika,
musimy obliczyć jego przystosowanie. Obliczanie przystosowania polega na
przeprowadzeniu egzaminu sieci przy użyciu ciągu uczącego w celu
obliczenia błędu. Jeżeli ciąg uczący jest długi (a z reguły jest), to proces
obliczania przystosowania zajmuje znaczną ilość czasu działania algorytmu.
Sekwencyjne implementacje AE okazują się tutaj niewystarczające
" pamięć dla niektórych problemów (np. programowania ewolucyjnego)
rozmiar populacji musi być duży. Oznacza to duże wymagania pamięciowe
AE, który musi przechowywać dużą ilość osobników (najczęściej ze
skomplikowanym kodem). I w tym wypadku sekwencyjna implementacja AE
staje pod znakiem zapytania
" skuteczność największą bolączką AE jest przedwczesna zbieżność. Dla
niektórych problemów, z duża przestrzenią przeszukiwania, SAE działa
niezbyt dobrze, wyznaczając rozwiązania przeciętne, bądz złe.
Przedwczesna zbieżność wynika m.in. z faktu, że SAE (jednopopulacyjne)
mają pojedynczą trajektorię poszukiwania rozwiązania. Jeżeli SAE wpadnie
w pułapkę ewolucyjną, to nie ma większych szans na jej opuszczenie
24
Opisane wady SAE sprawiły, że powstała spora grupa nowych adaptacji
pod nazwą współbieżnych algorytmów ewolucyjnych (WAE), pozbawiona
niedogodności ich sekwencyjnych odpowiedników.
1.2. Dlaczego współbieżność?
Już pierwsi badacze zauważyli współbieżną naturę AE. Tak jak w
rzeczywistości wiele istnień równolegle bierze udział w procesach ewolucyjnych,
tak i adaptacja tych procesów do AE spowodowała możliwość łatwego i
naturalnego ich zrównoleglenia. WAE nie dotyczą problemy o których traktował
punkt poprzedni. Wynika to z następujących czynników:
" Naturalnym środowiskiem ich implementacji jest środowisko rozproszone lub
równoległe. Objawia się to znacznym przyspieszeniem działania algorytmu,
które eliminuje problemy złożonej czasowo ewaluacji osobników
" Rozproszona (bądz równoległa) implementacja w systemach z rozproszoną
pamięcią operacyjną eliminuje problem wielkości populacji oraz wielkości kodu
osobników
" Większość WAE posiada więcej niż jedną trajektorię poszukiwania
rozwiązania (modele wielopopulacyjne). Oznacza to, że jeżeli jedna populacja
wpadnie w pułapkę ewolucyjną, to jest wielce prawdopodobne, że materiał
genetyczny pochodzący z innej populacji pomoże jej tą pułapkę opuścić.
Wynika z tego, że wielopopulacyjne WAE są w stanie dać dużo lepsze wyniki
(nawet ich sekwencyjne symulacje). Wielopopulacyjne modele są również w
stanie wyznaczyć kilka lub wszystkie optima, nie tylko jedno jak w przypadku
modeli jednopopulacynych, co ma duże znaczenie w optymalizacji
wielomodalnej
1.3. Równoległa i rozproszona architektura komputerowa
Zanim zdefiniujemy podstawowe modele WAE, przedstawione zostanie
środowisko ich implementacji. Naturalnym środowiskiem będzie w tym przypadku
pewne wieloprocesorowe środowisko rozproszone lub równoległe, pozwalające na
współbieżne przetwarzanie.
25
Istnieje wiele klasyfikacji takich wieloprocesorowych systemów. Najogólniej
można je podzielić na systemy wieloprocesorowe luzno zintegrowane (ang. loosely-
coupled, dalej LC) i ściśle zintegrowane (ang. tightly-coupled, dalej TC).
Systemy typu LC to najczęściej heterogeniczne sieci komputerowe.
Poszczególne jednostki przetwarzania w takim systemie wieloprocesorowym
posiadają odrębne pamięci operacyjne, a komunikacja między nimi następuje
poprzez operacje wysyłania komunikatów (ang. message-passing).
Rysunek II-1 luzno zintegrowany system wieloprocesorowy
Systemy typu TC, to z kolei równoległe maszyny wieloprocesorowe ze
współdzieloną pamięcią. Wszystkie procesory wymieniają informacje między sobą
poprzez wspólny interfejs pamięciowy.
Rysunek II-2 ściśle zintegrowany system wieloprocesorowy
Inną klasyfikacje wprowadza Flynn. Dzieli on architektury komputerowe na
cztery grupy:
" SISD - jedna instrukcja, jeden strumień danych
" SIMD - jedna instrukcja, wiele strumieni danych
26
" MISD - wiele instrukcji, jeden strumień danych
" MIMD - wiele instrukcji, wiele strumieni danych
Poza architekturą MISD, pozostałe są bardzo popularne, szeroko eksploatowane i
projektowane.
" SISD
Jest to architektura typowej jednoprocesorowej maszyny typu PC. Taka
architektura pozwala na zrównoleglenie na poziomie instrukcji (np. pipelining),
które jednakże jest przezroczyste dla programisty
Rysunek II-3 schemat architektury typu SISD
" SIMD
Jest to architektura wieloprocesorowa, gdzie wszystkie procesory pracują nad
przetwarzaniem jednej instrukcji każdy w swojej własnej, lokalnej pamięci
operacyjnej. Taka architekturę stosuje się najczęściej do przetwarzania
dużych, regularnych struktur danych. Gdy dane są nieregularne, pojawia się
problem chwilowej bezczynności poszczególnych procesorów
Rysunek II-4 schemat architektury typu SIMD
" MIMD
W tej wieloprocesorowej architekturze wszystkie procesory pracują wspólnie
nad danym problemem, dzięki zapewnieniu pewnego zewnętrznego
27
połączenia między nimi. Różne programy mogą ładować różne dane do
różnych procesorów. Oznacza to wykonywanie przez procesory różnych
instrukcji w różnym czasie (przeważnie zakłada się jednak pewien stopień
synchronizacji między nimi)
Rysunek II-5 schemat architektury typu MIMD
2. Przykładowa taksonomia
2.1. Różne klasyfikacje i modele.
Istnieje wiele poziomów na jakich AE mogą zostać zrównoleglone. Te poziomy
to: populacja (selekcja), osobnik oraz funkcja przystosowania. Modele
zrównoleglające AE na poziomie populacji (selekcji) zakładają istnienie wielu
populacji, gdzie na każdej z nich selekcja odbywa się równolegle (niezależnie). Inne
podejście to zrównoleglenie na poziomie osobnika lub funkcji przystosowania
(globalne3). Takie modele zakładają istnienie wspólnej selekcji, a zrównoleglona
jest ewaluacja osobników i/lub wykonywanie operatorów genetycznych.
Innym podejściem jest klasyfikacja WAE ze względu na paradygmat
zrównoleglenia. Każdy z WAE będzie tutaj zaliczał się do jednej z dwóch kategorii:
modelu gruboziarnistego (ang. coarse-grained) lub drobnoziarnistego (ang. fine-
grained). Oba terminy odnoszą się do liczby wykonywanych operacji na
poszczególnych węzłach obliczeniowych w stosunku do natężenia komunikacji
między nimi. Model gruboziarnisty zakłada znaczny czas przetwarzania na
poszczególnych węzłach w stosunku do natężenia komunikacji. W modelu
3
Globalne oznacza tutaj to, że każdy osobnik z populacji może wziąć udział w reprodukcji z każdym
innym. Zapewnione jest to dzięki wspólnej selekcji.
28
drobnoziarnistym z kolei jest na odwrót. Komunikacja jest znaczna w stosunku do
ilości przetwarzania.
Tego typu klasyfikacji można wymienić więcej. Wszystkie jednakże mają
pewne wady - są niekompatybilne oraz nie obejmują wszystkich opracowanych do
tej pory modeli. Dosyć dokładną informacje na ten temat można znalezć w pracy
Ericka Cantu-Paz [CANTUa].
Próbę zunifikowania modeli WAE i przedstawienia nieco odmiennej klasyfikacji
podjęli się Nowostawski oraz Poli w [NOWO99a]. Podzielili oni WAE na 8 klas ze
względu na:
" sposób, w jaki organizowana jest mutacja oraz ewaluacja osobników
" organizację populacji (istnienie jednej lub wielu populacji)
" sposób wymiany osobników w modelach wielopopulacyjnych
" sposób organizacji selekcji (selekcja lokalna lub globalna)
Nieco zmodyfikowana wersja tej taksonomii zostanie przedstawiona w niniejszej
pracy.
2.2. Zrównoleglenie globalne model Master-Slave
Model ten, zwany modelem Master-Slave, modelem rozproszonej ewaluacji
lub globalnym zrównolegleniem, został opracowany i zaimplementowany jako jeden
z pierwszych. Zakłada on istnienie jednej populacji oraz globalnej selekcji, a
zrównoleglenie następuje na poziomie ewaluacji osobników i/lub operacji
genetycznych.
W systemie występują dwa rodzaje procesów: proces master oraz wiele
procesów typu slave4. Master odpowiada za kierowanie całym algorytmem włącznie
z selekcją. W wykonywaniu operacji ewaluacji osobników i/lub wykonywania
operacji genetycznych wyręczają go procesy typu slave, które wykonują te
czynności niezależnie, w sposób równoległy.
Podstawowymi operacjami, które zostają tutaj zrównoleglone, są ewaluacja
oraz mutacja, gdyż całą wymaganą wiedzę do ich przeprowadzenia zawiera
osobnik. Nie ma tutaj potrzeby żadnej komunikacji oraz informacji na temat całej
populacji.
4
W idealnej sytuacji liczba procesów slave równa się liczbie osobników w populacji
29
Gdy master czeka na powrót wszystkich osobników z procesów slave przed
rozpoczęciem następnej epoki, to mówimy, że omawiany model jest synchroniczny.
Oprócz szybkości, model ten ma dokładnie takie same właściwości jak zwyczajny,
sekwencyjny AE5. Takie rozwiązanie posiada jednakże jedno tzw. wąskie gardło
mianowicie master musi czekać na najwolniejszego slave a, co w praktyce (w
heterogenicznym systemie) oznacza znaczne opóznienia.
Naprzeciw temu problemowi wychodzi wersja asynchroniczna. Master czeka
tylko na pewną frakcję osobników zanim dokona selekcji i przejdzie do następnej
epoki. Takie podejście zmienia jednakże dynamikę działania algorytmu w stosunku
do zwykłego AE.
Model Master-Slave jest modelem bardzo popularnym i szeroko
implementowanym. Wynika to z faktu, że wersja synchroniczna nie zmienia
dynamiki samego AE, co sprawia, że algorytm może być analizowany i badany na
takich samych zasadach co zwykłe, sekwencyjne odpowiedniki (przy znacznym
zwiększeniu szybkości działania). Do tego dochodzi fakt, że model może być
implementowany zarówno w systemach typu TC, jak i LC.
Rysunek II-6 zrównoleglenie globalne model Master-Slave
2.3. Model subpopulacyjny z migracją
Model ten, zwany rozproszonym algorytmem ewolucyjnym lub modelem
5
Znaczy to, że przeszukuje zbiór rozwiązań w dokładnie taki sam sposób, z wszystkimi tego zaletami
i wadami.
30
wyspowym, często utożsamiany jest z gruboziarnistym paradygmatem
zrównoleglania. Zakłada on podział całej populacji na mniejsze frakcje (demy),
które następnie wysyłane są do procesów zwanych wyspami, gdzie każdy z nich
niezależnie wykonuje AE na swojej części populacji. Taki model nie różniłby się
niczym od sytuacji równoległego wykonania wielu niezależnych od siebie (być
może z różnymi parametrami) algorytmów, gdyby nie operacja migracji.
Migracja powoduje, że zgodnie z pewnym schematem pewne osobniki migrują
z jednej wyspy na drugą, zasilając tamtejszą populację nowym materiałem
genetycznym. Takie podejście powoduje fundamentalną różnicę w stosunku do
sekwencyjnego, jednopopulacyjnego AE, który posiadał tylko jedną trajektorię
poszukiwania rozwiązania. Podstawowe parametry jakie musimy przekazać
algorytmowi to:
" częstość migracji (ang. migration interval) - częstotliwość z jaką osobniki
będą migrować z jednej wyspy na drugą. Jeżeli wszystkie wyspy wchodzą w
fazę migracji w tym samym czasie, to algorytm jest synchroniczny. Jeżeli zaś
każda z wysp ma inną częstość migracji, to algorytm jest asynchroniczny
" wielkość migracji (ang. migration rate) - ilość osobników jaka będzie
migrować
" schemat emigracji - sposób w jaki osobniki będą selekcjonowane do
opuszczenia wyspy (najlepsze, losowe, najgorsze)
" schemat imigracji - sposób w jaki osobniki emigrujące będą zastępować
osobniki zamieszkujące docelową wyspę (najlepsze, losowe, najgorsze)
" topologia - schemat połączeń między wyspami. Dwie najpopularniejsze to
pełny graf (model wyspowy) oraz pierścień (model stepping-stone)
" struktura wysp - heterogeniczna lub homogeniczna. Dla struktury
homogenicznej wszystkie wyspy mają takie same parametry algorytmu
wykonywanego na każdej z nich. Natomiast dla struktury heterogenicznej te
parametry mogą się różnić
" polityka migracji - sposób w jaki osobniki migrują zgodnie z zadaną
topologią. Np. dla modelu wyspowego (pełny graf) można wyróżnić
następując polityki: wysyłanie osobników do wszystkich wysp, jednej wyspy
(wybranej na drodze losowania) lub do tych wysp, gdzie jest to wskazane
31
(np. do wysp, które osiągnęły stan degeneracji wyczerpania materiału
genetycznego)
Rysunek II-7 model Stepping-Stone Rysunek II-8 model wyspowy
Model ten z powodzeniem implementuje się w systemach typu LC.
2.4. Model subpopulacyjny z nakładaniem bez migracji
Omawiany w tym punkcie model jest odpowiednikiem modelu wyspowego na
architektury klasy TC. Istnieje jedna populacja (składowana we współdzielonej
pamięci), która jest dzielona pomiędzy dostępne procesory na zasadzie
nakładających się obszarów (ang. overlapping areas), na których każdy procesor
równolegle uruchamia odrębny AE. Model zakłada brak migracji, aczkolwiek jej
funkcjonalność zapewniana jest przez to, że jeden osobnik może należeć do więcej
niż jednego obszaru, co oznacza, że może brać udział w więcej niż jednej
reprodukcji na epokę.
Rysunek II-9 model subpopulacyjny z nakładaniem bez migracji
32
2.5. Masywnie zrównoleglony algorytm ewolucyjny
Model ten otrzymamy gdy zwiększymy znacznie liczbę nakładających się
obszarów w modelu z nakładaniem. Z reguły przyjmuje się, że obszar obejmuje
tylko jednego osobnika oraz jego sąsiadów (zgodnie z zadaną topologią). Taki
model często nazywa się modelem drobnoziarnistego zrównoleglenia, a
implementuje się go na masywnie zrównoleglonych architekturach komputerowych.
Schemat modelu można zobaczyć na obrazku poniżej 6
Rysunek II-10 masywnie zrównoleglony algorytm ewolucyjny z topologią siatki 2D
2.6. Model Master-Slave z dynamiczną reorganizacją subpopulacji
Model ten (zwany dynamicznymi demami ang. Dynamic Demes, dalej DD),
został przedstawiony przez Nowostawskiego oraz Poli w [NOWO99b], jako próba
połączenia najlepszych cech dwóch innych modeli: modelu Master-Slave i modelu
subpopulacyjnego.
Oba wymienione modele mają pewne wady. model Master-Slave (dalej M-S),
w wersji synchronicznej, posiada wąskie gardło w postaci czekania na
najwolniejszego slave a. Model subpopulacyjny z kolei jest słabo skalowalny. DD
wydaje się nie cierpieć na żaden z tych problemów.
Tak samo jak w modelu M-S, DD zakłada istnienie procesów slave, które
utożsamiane są z osobnikami. W najlepszej sytuacji na jednego osobnika powinien
przypadać jeden slave, który odpowiedzialny jest za ewaluację oraz wykonywanie
operatorów genetycznych mutacji oraz krzyżowania7.
6
Na schemacie z przyczyn organizacyjnych zaznaczone są jedynie niektóre obszary
7
Krzyżowanie będzie dokonywane poprzez wysłanie ID procesu Slave (osobnika) do innego Slave a.
33
Drugim rodzajem procesów są procesy typu master, których może być więcej
niż jeden (w przeciwieństwie do modelu M-S). Każdy master utożsamiany jest z
jedną subpopulacją, na której równolegle wykonuje selekcję oraz zarządza
reprodukcją.
Kluczowym elementem tego modelu jest dynamiczna reorganizacja
subpopulacji. Każdy osobnik może w danym cyklu zmienić swoją populacje na inną,
co gwarantuje podobne efekty jak w przypadku modeli subpopulacyjnych. Dokonuje
się tego wprowadzając do systemu trzeci typ procesów counter. Counter
gromadzi ID tych procesów slave, które już dokonały ewaluacji oraz operacji
genetycznych na swoich osobnikach. Z tych procesów counter formuje nowe
populacje dla oczekujących masterów. Aby proces ten zachodził w sposób
kontrolowany, wprowadza się tzw. czynnik nakładania (ang. overlapping factor).
Czynnik ten mówi counterowi ile miejsc w nowej populacji (dla danego mastera) jest
zarezerwowanych dla osobników ze starej populacji, a ile dla osobników z
sąsiedniego mastera. W ten sposób organizuje się subpopulacje w logiczny
pierścień, w którym krąży nowy materiał genetyczny.
D-D ma wiele zalet. Nadaje się zarówno do implementacji AE z czasochłonną
(zmniejszając liczbę masterów) jak i szybką ewaluacją osobników (zwiększając
liczbę masterów). W ten sposób D-D może pracować zarówno w postaci drobno-
jak i grubo- ziarnistej.
Taki model najefektywniej implementuje się na architekturze typu MIMD,
aczkolwiek można sobie wyobrazić implementację w systemie LC.
Rysunek II-11 model Master-Slave z dynamiczną reorganizacją subpopulacji
34
2.7. Podsumowanie
W tym rozdziale zostały pokazane różne modele i sposoby zrównoleglenia AE.
Nie był to jednak wyczerpujący przegląd dostępnych technik, a jedynie zarysowanie
problemu.
Z punktu widzenia projektowanej w tej pracy rozproszonej platformy
ewolucyjnej, szczególnie ważne będą te modele, które można efektywnie
zaimplementować w systemie luzno zintegrowanym, jakim jest sieć komputerowa.
Takim modelem będzie model subpopulacyjny z migracją, który będzie stanowił
podstawę rozproszonej implementacji algorytmów ewolucyjnych w projektowanym
w tej pracy środowisku.
35
III. Rozproszona platforma ewolucyjna
1. Założenia ogólne projektu
Głównym powodem tworzenia rozproszonej platformy ewolucyjnej (dalej RPE)
jest uzyskanie narzędzia będącego swego rodzaju rozproszonym środowiskiem
implementacji algorytmów ewolucyjnych. Narzędzie to będzie na tyle ogólne, aby
pozwalało na implementację dowolnego algorytmu rozwiązującego dowolny
problem optymalizacyjny (należący do pewnej klasy) maksymalizacji oraz
minimalizacji przy rzeczywistej funkcji celu.
Takie podejście wymaga wydzielenia tych fragmentów algorytmu, które ściśle
zależą od rozwiązywanego problemu i przekazania odpowiedzialności za ich
implementację użytkownikowi. Pozostałe fragmenty to mechanizmy i schematy
właściwe konkretnym modelom ewolucyjnym, które zasilane parametrami z
zewnątrz mogą być wykorzystywane przez system w niezmiennej postaci.
Do użytkownika należeć będzie implementacja następujących elementów:
" budowa i kod chromosomu czyli określenie postaci, w jakiej
przedstawiane będą rozwiązania problemu
" funkcja oceny czyli dostarczenie systemowym modelom ewolucyjnym
możliwości oceny rozwiązań, co ma znaczenie w sytuacji stosowania
schematu selekcji promującego osobników lepiej przystosowanych
" operacje genetyczne czyli dostarczenie mechanizmów rekombinacji
właściwych wybranej strukturze chromosomu i jego kodzie
" ewaluacja osobników czyli obliczenie nowego przystosowania
" generowanie początkowego genotypu
" odczyt parametrów algorytmu
" zapis fenotypów do pliku
Tak określone operacje będą zgrupowane w pewien interfejs logicznie
interpretowany jako osobnik. Osobnik to bowiem posiada swój genotyp na którym
36
wykonywane są operacje genetyczne. Osobnik również jest oceniany jako przydany
lub nieprzydatny w rozwiązywaniu danego problemu.
Idąc dalej tym tokiem myślenia system będzie dostarczać pewnych
mechanizmów tworzenia populacji z dostarczanych przez użytkownika osobników.
Mechanizmy te, będą w danym kroku algorytmu przekształcać bieżącą populację w
populacją nową, w oparciu o pewien schemat selekcji, promując przy tym
osobników lepiej przystosowanych. System będzie dostarczał dwa takie modele:
prosty algorytm ewolucyjny oraz algorytm ewolucyjny z ustalonym stanem.
Takie rozwiązanie, czyli oddzielenie logiki działania algorytmu od jego
fizycznej postaci, daje możliwość łatwej rozbudowy systemu o nowe modele
ewolucyjne, dostarczające różnorodne sposoby tworzenia populacji w oparciu o
różnorakie schematy selekcji.
Mając określone, wspomniane wyżej, modele tworzenia populacji z
osobników, system będzie dostarczać pewnych niskopoziomowych mechanizmów
implementacji algorytmów. Mechanizmy te, będą od początku do zakończenia
sterować działaniem algorytmu zgodnie z sobie właściwymi zasadami. RPE, na
tym poziomie, będzie rozróżniała dwa typy takich mechanizmów, rozumianych jako
mechanizmy implementacji sekwencyjnej oraz mechanizmy implementacji
rozproszonej, dostarczając użytkownikowi po jednym modelu z każdej z tych grup.
Użytkownik będzie mógł zaimplementować swój algorytm zgodnie z
jednopopulacyjnym modelem sekwencyjnym lub zgodnie z wielopopulacyjnym
rozproszonym algorytmem ewolucyjnym znanym jako model wyspowy.
Również i w tym punkcie oddzielenie logiki implementacji algorytmu od logiki
działania algorytmu daje łatwe możliwości rozbudowy systemu o nowe modele
implementacji rozproszonej takie jak chociażby model Master-Slave z dynamiczną
reorganizacją subpopulacji.
Reasumując, RPE jest warstwowym systemem wdrażania, implementacji i
wykonania algorytmów, opierającym się na pewnych modelach właściwych danej
warstwie: warstwie postaci algorytmu, warstwie logiki (tworzenie nowych populacji) i
warstwie implementacji (działanie algorytmu).
37
Jako język programowania przeznaczony do implementacji projektu, wybrano
język Java w wersji 1.4.0.
Rysunek III-1 schemat warstwowej struktury RPE
2. Budowa systemu
2.1. Architektura
Aby zrealizować założone w punkcie poprzednim wymagania
implementacyjne, naturalnym wydaje się, aby RPE była pewnym systemem
rozproszonym, rozumianym jako zbiór połączonych ze sobą węzłów obliczeniowych
(nazywanych dalej platformami). Wszystkie platformy będą koordynowane i
nadzorowane przez specjalny węzeł-koordynator zwany platformą główną.
Platforma główna będzie stanowić centralny punkt wejścia dla użytkownika
pozwalając na przeprowadzenie całego procesu implementacji, wdrożenia i
uruchomienia dowolnego algorytmu zgodnego z interfejsem platformy.
38
Rysunek III-2 rozproszona architektura RPE
2.2. Koncepcja rozproszonych obiektów
RPE będzie systemem zaprojektowanym i zaimplementowanym przy użyciu
narzędzi zorientowanych obiektowo. Podstawowym problemem i niedogodnością
przy obiektowym projektowaniu systemu rozproszonego jest zaprojektowanie
warstwy komunikacyjnej tegoż systemu, rozumianej jako zespół protokołów i
mechanizmów pozwalających nawiązać komunikację w sieci. Protokoły i
mechanizmy te, ze względu na swoją niskopoziomowość muszą zostać
przekształcone na obiektowe struktury, co może okazać się operacją mało
elastyczną, niewygodną i czasochłonną. Znacznie lepszym pomysłem jest
zastosowanie pewnej implementacji koncepcji rozproszonych obiektów,
pozwalającej projektantowi zaprojektować w pełni obiektowo rozproszony system,
abstrahując od spraw lokalizacji obiektów i komunikacji miedzy nimi.
Najpopularniejsze implementacje tej koncepcji to: CORBA, Java RMI, DCOM oraz
.NET Remoting.
Analizę obiektową RPE rozpoczniemy od wydzielenia interfejsów zdalnych
obiektów. Patrząc na rysunek powyżej (rozproszona architektura RPE) widzimy, że
aplikacja będzie podzielona na dwa moduły: platformę i platformę główną,
39
uruchamiane w środowisku rozproszonym. Wprowadzmy do systemu dwa pierwsze
interfejsy zdalnych obiektów: Platform i MainPlatform. Obiekty implementujące te
interfejsy będą w ogólności zarządzać swoimi modułami i zapewniać obustronną
komunikację sieciową. Kolejne dwa interfejsy: Island i Counter wiążą się już logiką
warstwy implementacji RPE. W modelu wyspowym jednostki przetwarzania
algorytmów nazywane są wyspami, a obiekt przeznaczony do ich synchronizacji -
licznikiem (ang. counter).
Remote
(from rmi)
<>
<>
<> <>
Platform
Island
Counter MainPlatform
shutdown()
getImigrantsQueue()
waitForOthers() updateIslandReference()
start()
emigrantsSend()
finished()
runOfAlgorithmCompleted()
prepare()
getBestIndividual()
register()
stop()
isActive()
unregister()
setNeighbours()
updateNeighbourReference()
getCounter()
removeIsland()
getHistory()
criticalErrorOccured()
ping()
prepare()
getClass()
DLBresponse()
setNeighbours()
removeIsland()
DLBrequest()
ping()
updateResults()
getBestIndividual()
CounterImpl MainPlatformImpl IslandImpl PlatformImpl
(from MainPlatform) (from MainPlatform) (from Platform) (from Platform)
Rysunek III-3 diagram interfejsów rozproszonych obiektów
2.3. Interfejsy komunikacji RPE z użytkownikiem
Kolejnym krokiem będzie określenie interfejsów warstwy postaci algorytmu:
Individual oraz Results. Individual, to podstawowy interfejs, który musi zostać
zaimplementowany przez każdy algorytm użytkownika - albo bezpośrednio przez
konkretną klasę, albo pojawiając się u szczytu hierarchii dziedziczenia pewnej
struktury klas. Individual definiuje wszystkie potrzebne operacje opisane w punkcie
pierwszym niniejszego rozdziału, rozumianych jako operacje na osobniku :
40
getFitness() pobiera aktualną wartość przystosowania osobnika, init() inicjuje
algorytm parametrami, generateInitialGenotype() generuje początkowy genotyp,
evaluate() oblicza nową wartość przystosowania, storeResults() zapisuje wyniki
do strumienia, którego uchwyt przekazany jest jako parametr, showResults()
wyświetla wyniki oraz clone() zwraca głęboką kopię obiektu.
Oprócz opisanych wyżej funkcjonalności, osobniki dodatkowo muszą spełniać
jeszcze dwie inne: muszą być serializowalne oraz porównywalne. Pierwsza z tych
funkcjonalności wiąże się z koniecznością przesyłania obiektów-osobników przez
sieć (podczas implementacji rozproszonej). Dokonać tego można poprzez
rozszerzenie interfejsu Individual o interfejs Serializable.
Druga z funkcjonalności porównywalność, wynika z konieczności
porównywania osobników w momencie stosowania schematów selekcji
promujących osobników lepiej przystosowanych. System nie może wprost polegać
na bezwzględnej wartości przystosowania zwracanej przez getFitness()� gdyż
znaczenie tej wartości w różnych algorytmach jest inne przy problemie
minimalizacji im mniejsza wartość, tym lepiej; przy problemie maksymalizacji im
większa tym lepiej. Problem ten rozwiązujemy przekazując użytkownikowi
możliwość zdefiniowania pewnej relacji znanej jako relacja naturalnego porządku,
poprzez zaimplementowanie interfejsu Comparable i jego metody
compareTo(Object i). Metoda ta, powinna zwracać liczbę ujemną, jeżeli obiekt na
rzecz którego metoda jest wywoływana jest w relacji naturalnego porządku z
obiektem przekazanym jako parametr. Osobnik1 będzie w relacji naturalnego
porządku z osobnikiem2, jeżeli jest od niego gorzej przystosowany.
Klasa osobnika, oprócz implementowania interfejsu Individual, może
implementować pewne interfejsy operacji genetycznych, pochodzące z warstwy
logiki algorytmu. W aktualnej wersji systemu te interfejsy to Crossable i Mutable
i oznaczają kolejno: krzyżowalność osobnika i jego mutowalność (interfejsy te
definiują odpowiednie metody: crossover(Individual i, double probability) oraz
mutate(double probability))
Drugi interfejs, przeznaczony do zaimplementowania przez użytkownika, to
Results. Results będzie implementował obiekt przeznaczony do interpretowania
(najczęściej wyświetlania) częściowych wyników przysyłanych przez węzły
obliczeniowe podczas działania algorytmu. Metody jakie należy zaimplementować
to: init(), showResults() oraz updateResults().
41
Aby dodać osobnikom pewną identyfikowalność (możliwość zidentyfikowania
osobnika co do wyspy, z której pochodzi i pewnego numeru sekwencyjnego)
wprowadzamy do systemu klasę dekoratora (wzorzec projektowy Decorator) pod
nazwą IdentificableIndividual.
Exception
<>
<>
Comparable (from lang)
Serializable
(from lang)
(from io)
compareTo() EAException
<> EAException()
Individual
<>
<>
Results
getFitness()
-individual
1
1
init()
init() generateInitialGenotype()
showResults() evaluate()
updateResults() storeResults()
showResults()
clone()
IdentificableIndividual
runID : int
island : Island
init()
compareTo()
clone()
1
1
getFitness()
generateInitialGenotype()
evaluate()
storeResults()
showResults()
Rysunek III-4 diagram zależności interfejsów Individual oraz Results
2.4. Algorytm ewolucyjny - model tworzenia prób losowych (populacji)
Kolejną warstwą, jak zostało powiedziane na początku tego rozdziału, będzie
tzw. warstwa logiki algorytmu. W warstwie tej definiujemy podstawowe modele
i mechanizmy pozwalające na tworzenie i przekształcanie populacji osobników
dostarczanych przez warstwę poprzednią. Te modele to: prosty algorytm
ewolucyjny oraz algorytm ewolucyjny z ustalonym stanem. Oba te modele
wykorzystują schemat selekcji zwany turniejem stochastycznym (przybliżonym w
punkcie 5.7 rozdziału pierwszego).
Aby istniała możliwość łatwej rozbudowy tej warstwy o nowe modele,
wprowadzamy do systemu klasę abstrakcyjną nazwaną EvolutionaryAlgorithm
(kierując się logiką wzorca projektowego Facade), stanowiącą bazę dla wszystkich
42
konkretnych modeli ewolucyjnych. Oprócz szeregu chronionych pól, będących
parametrami algorytmu, klasa ta definiuje dwie podstawowe metody abstrakcyjne
(do zaimplementowania przez klasy konkretne: SimpleEvolutionaryAlgorithm
i SteadyStateAlgorithm) isNextEpoch() mówiąca czy warunek stopu algorytmu
został spełniony oraz nextEpoch() powodującej przejście do następnej epoki.
Działanie algorytmu na tym poziomie można przedstawić za pomocą poniższego
pseudokodu:
EvolutionaryAlgorithm algorithm = //tworzymy konkretny model
While( algorithm.isNextEpoch() ){
algorithm.nextEpoch();
}
W tworzeniu modeli będzie wykorzystywany obiekt-fabryka (zaimplementowany
jako modyfikacja wzorca projektowego Abstract Factory oraz jako Singleton),
a proces dynamicznego ładowania klas użytkownika będzie nadzorował specjalny
ładowacz klas - EAClassLoader.
Serializable
ClassLoader
(from lang)
(from io)
EvolutionaryAlgorithm
SecureClassLoader
crossoverProbability : double
(from security)
mutationProbability : double
stopCondition : int
EAFactory
maxQuantityOfIterations : int
$ eaFactory : EAFactory
iteration : int
EAClassLoader
stagnationPeriod : int
$ instance createAlgorithm()
individualName : String
getInstance()
input : java.lang.String[]
findClass()
bestFitness : java.util.List
-eaClassLoader <>
getPermissions()
populationSize : int
prepare()
tournametGroupSize : int
isPrepared()
avgFitness : java.util.List
EAClassLoader()
getInstance()
isNextEpoch()
createNewInstance()
nextEpoch()
generateInitialPopulation()
getIndividuals()
replaceIndividuals()
SimpleEvolutionaryAlgorithm
select()
getCurrentPopulationSize()
SteadyStateAlgorithm
nextEpoch()
sum : double
SimpleEvolutionaryAlgorithm() 1
1
nextEpoch()
1
1
-currentPopulation
SteadyStateAlgorithm()
1..n
1..n
-auxiliaryPopulation
generateInitialPopulation()
1..n
1..n
Individual
Rysunek III-5 diagram zależności klas w warstwe logiki algorytmu
43
2.5. Wyspa - środowisko wykonania algorytmu ewolucyjnego
Podstawą rozproszonej implementacji algorytmów ewolucyjnych w RPE
będzie, jak zostało powiedziane wcześniej, model wyspowy. Podstawową klasą
reprezentującą wyspę jest IslandImpl implementująca zdalny interfejs Island.
Obiekty tej klasy będą obiektami zdalnymi, co ma swoje następstwa w
sposobie przesyłania takich obiektów jako parametrów lub wartości zwracanych
metod. Różnica między obiektami lokalnymi a zdalnymi polega między innymi na
tym, że obiekty zdalne zawsze przesyłane są poprzez zdalną referencję i nie ma
możliwości zserializowania takiego obiektu. Aby uzyskać funkcjonalność serializacji
zdalnego obiektu, co będzie miało znaczenie w sytuacji zastosowania algorytmu
dynamicznego równoważenia narzutu obliczeniowego na platformach, dynamicznie
zmieniającego położenie wysp zdalnych obiektów - w systemie, zastosujemy
model delegacji. Cały stan wyspy tzn. parametry oraz wykonywany na niej algorytm
będzie odłączony od zdalnego obiektu i włączony do lokalnego, serializowalnego
obiektu typu LocaleIsland. Wszystkie wywołania metod zależnych od stanu wyspy
tzn.: prepare(), setNeighbours(), getBestIndividual(), getHistory() oraz
updateNeighbourReference() będą delegowane do tegoż lokalnego obiektu.
Każda wyspa implementować będzie również interfejs Runnable, co pozwoli
platformie na współbieżne uruchomienie algorytmów na wszystkich wyspach,
każdej w osobnym wątku. Cała synchronizacja między wątkami będzie odbywać się
na zasadzie wywołań metod synchronizowanych8
Aby umożliwić wymianę osobników między wyspami, każda z nich będzie
utrzymywać specjalna kolejkę (struktura thread-safe), do której przybywające
osobniki będą dodawane asynchronicznie. Wyspa wchodząc w odpowiedni stan
będzie odbierać osobników i modyfikować populację wykonywanego na niej
algorytmu.
8
Wywołanie metody synchronizowanej polega na założeniu przez wątek wywołujący blokady na
obiekt, którego metoda jest wywoływana. Żaden inny wątek w tym czasie nie może wywołać żadnej
innej metody synchronizowanej tego obiektu, czekając w kolejce aż blokada zostanie zdjęta.
44
1
1 -remoteReference
-neighbours
Island
EvolutionaryAlgorithm
0..n
0..n
(from RMI) (from EvolutionaryTools)
Serializable
1
1
(from io)
<>
1
1 -eAlgorithm
1 1
1 1
Runnable
(from lang)
IslandImpl LocaleIsland
updateInterval : int topology : int
run()
DLBrequestor : Platform migrationModel : int
migrationPolicy : int
getImigrantsQueue() migrationInterval : int
updateNeighbourReference() migrationRate : int
stop() emigrationScheme : int
-platform -islands distributeNewReference() imigrationScheme : int
-localeIsland
emigrantsSend() history : double[][][]
PlatformImpl
setNeighbours() currnetRun : int
n
n
1 1 1
1 1 1
prepare() UID : java.lang.String
getHistory()
getBestIndividual() prepare()
updateEmigrantsQueue() setNeighbours()
#island
setNeighbours() LocaleIsland()
ping() getBestIndividual()
1
1
getBestIndividual() getHistory()
generateInitialPopulation() updateNeighbourReference()
-distributedModel
1
1
1
1
DistributedModel
1
1
n
n
n
n
-bestIndividuals
-imigrantsQueue
Individual
(from EvolutionaryTools)
Rysunek III-6 diagram klas wyspy
2.6. Topologie
Model wyspowy zakłada istnienie węzłów obliczeniowych wysp połączonych
między sobą w określoną topologię. RPE będzie dostarczała implementacji trzech
topologii: pierścienia, siatki 2D oraz pełnego grafu.
Rysunek III-7 topologie połączeń wysp w RPE: a) pierścień, b) siatka 2D, c) pełny graf
45
W systemie wspomniane topologie będą reprezentowane przez klasy: Ring, Grid2D
oraz FullGraph, implementujące wspólny interfejs Topology.
Obiekty typu Topology będą wykorzystywane przez obiekty przeznaczone do
przeprowadzania emigracji osobników (zastosowanie wzorca projektowego Bridge).
System zakłada dwa rodzaje takich obiektów: SynchronousDistributedModel
przeprowadzający emigrację w sposób synchroniczny oraz
AsynchronousDistributedModel - przeprowadzający emigrację w sposób
asynchroniczny. Obie klasy dziedziczą po wspólnej abstrakcyjnej klasie bazowej
DistributedModel, a instancje tych klas będą tworzone za pomocą odpowiedniej
fabryki DistributedModelFactory.
Island
(from RMI)
1
1
1
1
Serializable
-endPointIsland -sourceIsland
(from io)
1
1
1
1
IslandImpl
EmigratingIndividuals 1
1
#island
individuals : Individual[]
-distributedModel
1
1
EmigratingIndividuals()
DistributedModel DistributedModelFactory
<>
$ dmFactory : DistributedModelFactory
emigration()
distributeNewReference() <> createDistributedModel()
setTopology() getInstance()
1
1
bridge
-topology
AsynchronousDistributedModel
SynchronousDistributedModel
queue : java.util.LinkedList
1
1
synchronize() run()
<>
SynchronousDistributedModel() AsynchronousDistributedModel()
Topology
Runnable
emigration() emigrationFailed()
emigration()
getNeighbours()
(from lang)
Grid2D FullGraph
Ring
Grid2D() FullGraph()
Ring()
getNeighbours() getNeighbours()
getNeighbours()
1
1
1 1
1 1
-island
1
1
-island
-island
IslandImpl
1
1
1
1
Rysunek III-8 diagram klas zarządzających migracją oraz topologii
46
2.7. Platforma - współbieżne środowisko działania wysp
Środowiskiem działania wysp będzie platforma. Do najważniejszych zadań
platformy należą:
" zapewnienie wyspom współbieżnego środowiska działania
" udostępnienie wspólnego dla wszystkich wysp menedżera emigracji.
Menedżer będzie w sposób asynchroniczny obsługiwał żądania wysp
dotyczące wysłania grupy osobników na inną wyspę (w sytuacji
działania algorytmu w postaci asynchronicznej)
" zapewnienie mechanizmu dynamicznego równoważenia narzutu
obliczeniowego, polegającego na dynamicznym przemieszczaniu wysp
między platformami
-neighbours
IslandImpl
0..n
0..n
-islands
n
n
Platform
(from RMI)
-platform
MainPlatfor
Counter
1
1
m
PlatformImpl
(from RMI)
(from RMI)
dynamicLoadBalancing : boolean
$ params : HashMap
1
1
-counter
-mainPlatform
1
1
islandCounter : int
shutdown()
start()
prepare()
stop()
1
1
1
1
connect()
disconnect()
1
1
main()
setNeighbours()
finished()
dynamicLoadBalancing()
1
1
removeIsland()
ping()
getPolicy()
DLBresponse()
EmigratingIndividuals
DLBrequest()
1
1
-platform -emigrationManager
-platform
1
1
1
1
1
1
EmigrationManager
PlatformShutdownHook
queue : LinkedList
-$console
1
1
Thread
run() (from lang)
Console
put()
PlatformShutdownHook()
run()
Rysunek III-9 diagram klas platformy
47
2.8. Konsola platformy
Platforma będzie udostępniała graficzny interfejs administracyjny. W
zależności od trybu systemu operacyjnego, w jakim przyjdzie działać platformie,
użytkownik będzie miał do wyboru: konsolę tekstową (platforma uruchamiana z
parametrem console=textwindow) lub konsolę graficzną (platforma uruchamiana z
parametrem console=guiwindow). Konsola graficzna widoczna jest na rysunku
poniżej. Przycisk connect służy do nawiązania połączenia, przycisk try to connect
stara się cyklicznie nawiązywać połączenie (do momentu nawiązania połączenia),
przycisk clear czyści okienko z komunikatami, a przycisk disconnect przerywa
połączenie.
Rysunek III-10 konsola platformy
2.9. Platforma główna - koordynator systemu
Aby sprawnie zarządzać platformami wprowadzamy do systemu platformę
główną. Do najważniejszych zadań platformy głównej należą:
" udostępnienie platformom serwisu odnajdywania i ładowania klas algorytmu
" zarządzanie platformami
" udostępnienie zdalnego obiektu typu Counter przeznaczonego do
synchronizacji wysp
48
" zapewnienie środowiska implementacji algorytmu zgodnie z modelem
sekwencyjnym
" zapewnienie prostych i wygodnych mechanizmów integracji platformy
głównej z dowolną aplikacją stanowiącą graficzny interfejs dla użytkownika.
Mechanizmy te będą opierać się na koncepcji słuchaczy i odbiorców
zdarzeń. Koncepcja ta polega na tym, że aplikacja zewnętrzna będzie zdolna
zarejestrować w platformie głównej pewne obiekty słuchaczy, które odbierać
będą wiadomości o odpowiednich zdarzeniach generowanych przez
platformę główną (wzorzec projektowy Command).
Island
Platform
n
n
MainPlatform
AlgorithmModel
(from RMI)
(from RMI) -platforms (from RMI) Counter
1
1
n
n
-islands
(from RMI)
1
1
-counter
-bestIndividuals
MainPlatformImpl
Individual 1..n history : double[][][]
1..n
1
1
1
1 evolutionaryModel : int
(from EvolutionaryTools)
execQuantity : int
currentRun : int
<>
appendMode : boolean
PlatformStructureListener
EvolutionaryAlgorithm
startTime : long
1
1
(from EvolutionaryTools) results : Results
platformAttached()
-eAlgorithm updateInterval : int
1
1 platformDetached()
updateIslandReference()
runOfAlgorithmCompleted()
-classLoader 1
1
URLClassLoader
register()
(from net) -eventListenerList
1
1 unregister()
1
1
criticalErrorOccured()
1 n
1 n
getClass()
EventListener
stopAlgorithm()
runAsSequential() (from util)
runAsDistributed()
Runnable
getBestIndividual()
1
1
-mainPlatform getAlgorithmHistoryFromSequential()
(from lang)
<>
getAlgorithmHistoryFromDistributed()
AlgorithmStateListener
shutdownPlatform()
CounterImpl
removeIsland()
1
1 algorithmStarted()
counter : int hasNonActivePlatforms()
algorithmFinished()
islandCounter : int removeNonActivePlatforms()
algorithmInterrupted()
islandCollector : Timer updateResults()
warningOccured()
messages : LinkedList createResultsObject()
lock : Integer
CounterImpl()
PlatformStructureEvent
finished()
waitForOthers() <> platform : DEFramework.RMI.Platform
startCollector() date : java.util.Date
ActionListener
stopCollector()
(from event)
run() PlatformStructureEvent()
internalFinished()
CollectingProcedure
1
1
1
1
EventObject
(from util)
-collectingProcedure actionPerformed()
klasa wewnetrzna
AlgorithmStateEvent
w stosunku do
<> message : java.lang.String
CounterImpl
date : java.util.Date
AlgorithmStateEvent()
Rysunek III-11 diagram klas platformy głównej
49
3. Realizacja zadań systemu
3.1. Sekwencyjna implementacja algorytmu
Sekwencyjna implementacja algorytmów jest nieskomplikowana. Użytkownik
konfiguruje swój algorytm za pomocą interfejsu graficznego, po czym go
uruchamia. W pierwszej kolejności:
a) wywoływana jest metoda platformy głównej runAsSequential() z
odpowiednimi parametrami
b) platforma główna pobiera odpowiedni model tworzenia populacji
c) generowane jest zdarzenie uruchomienia algorytmu
d) algorytm uruchamiany jest w osobnym wątku
mainPlatform : factory : algorithm : threadRunner : event : listener :
MainPlatformImpl EAFactory EvolutionaryAlgorithm Thread AlgorithmStateEvent AlgorithmStateListener
: user
runAsSequential( )
listener
createAlgorithm( ) kontrolowany
przez klasę
<> interfejsu
fireAlgorithmStarted( )
<>
algorithmStarted( )
<>
start( )
run( )
Rysunek III-12 diagram interakcji dla sekwencyjnej implementacji algorytmu
W momencie zakończenia działania algorytmu, generowane jest odpowiednie
zdarzenie, a aplikacja sterująca platformą główną może pobrać wyniki.
3.2. Rozproszona implementacja algorytmu
Implementacja rozproszona z kolei ma przebieg następujący:
a) wywołujemy metodę runAsDistributed() platformy głównej
b) organizujemy platformy w pierścień
50
c) na każdej platformie tworzymy odpowiednia ilość wysp
d) organizujemy wyspy w określoną topologię
e) konfigurujemy wyspy
f) uruchamiamy algorytm na wszystkich platformach
g) generujemy odpowiednie zdarzenia
mainPlatform : platforms : islandRunner : islands : localeIsland : factory : algorithm : event : listener :
: user MainPlatformImpl Platform Thread IslandImpl LocaleIsland EAFactory EvolutionaryAlgorithm AlgorithmStateEvent AlgorithmStateListener
listener
kontrolowany
runAsDistributed( )
setNeighbours( ) przez klasę
interfejsu
dla każdej
platformy
prepare( )
<>
<>
setNeighbours( )
setNeighbours( )
dla każdej
wyspy
prepare( )
prepare( )
getInstance( )
createAlgorithm( )
<>
start( )
<>
dla każdej
start( )
platformy
run( )
dla każdej
wyspy
fireAlgorithmStarted( )
<>
algorithmStarted( )
Rysunek III-13 diagram rozproszonej implementacji algorytmu
3.3. Dystrybucja klas algorytmu w systemie
Jednym z głównych zadań platformy głównej jest zapewnienie platformom
serwisu klas algorytmu. Specjalne ładowacze klas na platformach łączą się z
platformą główną, która szuka oraz odczytuje pliki z klasami i zwraca ich bajtową
postać. Aby proces ten był łatwy, po stronie platformy głównej do szukania klas
wykorzystywany będzie obiekt typu URLClassLoader, szukający klas po adresach
URL, które definiuje użytkownik za pomocą interfejsu graficznego. Zwalnia nas to
między innymi od konieczności obsługi formatu JAR, który używany jest do
gromadzenia i kompresji klas Javy.
51
Localeisland / algorithm : individuals : class : Class eaClassLoader : mainPlatform : class2 : Class urlClassLoader :
mainPlatform EvolutionaryAlgorithm Individual EAClassLoader MainPlatform URLClassLoader
generateInitialPopulation( )
loadClass( )
getClass( )
forName( )
loadClass( )
defineClass( )
tworzymy
populacje
newInstance( )
Rysunek III-14 diagram dystrybucji klas algorytmu w systemie
3.4. Synchroniczna realizacja migracji
RPE zakłada dwojaki sposób zorganizowania fazy migracji osobników między
wyspami. Pierwszy z nich to podejście synchroniczne. Każda wyspa wchodząc w
fazę migracji blokuje swoje działanie na zdalnym obiekcie typu Counter. Jeżeli
Counter stwierdzi zablokowanie wszystkich wysp w systemie, zwalnia blokadę i
wszystkie wyspy w tym czasie wykonują podfazę emigracji. Po jej zakończeniu
następuję ponowna synchronizacja, a po niej podfaza imigracji, czyli odbioru
osobników.
Rysunek III-15 schemat przedstawiający synchroniczną migrację
52
3.5. Asynchroniczna realizacja migracji
Podejście asynchroniczne z kolei zakłada brak jakiejkolwiek synchronizacji
między wyspami. Wyspa, jeżeli wchodzi w fazę migracji, przekazuje jedynie
imigrantów specjalnemu menedżerowi emigracji, który zajmuje się bezpośrednim
doręczeniem osobników.
Rysunek III-16 schemat przedstawiający asynchroniczną migrację
Oczywiście menedżer musi być tak zaprojektowany, aby wyspa nie musiała czekać
aż menedżer dostarczy osobników. Możemy tego dokonać uruchamiając menedżera
w osobnym wątku. Menedżer będzie posiadał kolejkę imigrantów, którą w sposób
asynchroniczny będzie obsługiwał. Jeżeli kolejka w danym momencie będzie pusta,
menedżer będzie zawieszał swoje działanie do momentu pojawienia się nowych
imigrantów.
Tak rozumianego menedżera emigracji obrazuje stanowy diagram
przedstawiony poniżej:
53
start
entry/ stwórz obiekt menadżera
do/ stwórz kolejkę
exit/ uruchom menadżera
działanie menedżera emigracji
start
start
zatrzymany
zatrzymany
aktywny
aktywny
start
start
start
sprawdzanie kolejki
sprawdzanie kolejki
sprawdzanie kolejki
[ jeżeli kolejka pusta ] / wait
entry/ sprawdz rozmiar kolejki
entry/ sprawdz rozmiar kolejki
entry/ sprawdz rozmiar kolejki
[ jeżeli kolejka nie pusta ]
pobieranie osobników z kolejki
pobieranie osobników z kolejki
pobieranie osobników z kolejki
element dodany / notify
entry/ pobierz osobników z kolejki
entry/ pobierz osobników z kolejki
entry/ pobierz osobników z kolejki
exit/ usuń osobników z kolejki
exit/ usuń osobników z kolejki
exit/ usuń osobników z kolejki
wysyłanie osobników
wysyłanie osobników
wysyłanie osobników
entry/ zlokalizuj docelową wyspę
entry/ zlokalizuj docelową wyspę
entry/ zlokalizuj docelową wyspę
do/ prześlij osobników na wyspę
do/ prześlij osobników na wyspę
do/ prześlij osobników na wyspę
koniec
Rysunek III-17 diagram stanów dla menedżera emigracji
3.6. Dynamiczne równoważenie narzutu obliczeniowego na platformach
Jak dowiedzieliśmy się wcześniej, na każdej platformie będzie wykonywać się
określona ilość wysp. Pojawia się w tym miejscu pytanie o sposób przydzielania
wysp platformom. Jedyne, co użytkownik może zrobić, to skorzystać z wiedzy na
temat mocy obliczeniowej komputera, na którym uruchomiona jest platforma i
przypisać stosowną ilość wysp w zależności od mocy maszyny. Raz przydzielone
do platformy wyspy pozostają na niej do końca działania algorytmu (statyczny
algorytm równoważenia narzutu obliczeniowego). Decyzja człowieka jest jednakże
obarczona błędem; poza tym użytkownik nie może wiedzieć, która platforma i w
jakim czasie zakończy swoje działanie, gdyż ewolucja na każdej z wysp może
postępować inaczej. Złe rozdzielenie wysp może spowodować znaczny spadek
wydajności algorytmu (część z platform może być przez pewien czas bezczynna).
Aby zaradzić takiej sytuacji dostarczmy potrzebny i bardzo przydatny
mechanizm dynamicznego równoważenia narzutu obliczeniowego na platformach
(ang. DLB - Dynamic Load Balancing), który dynamicznie przemieszcza wyspy
54
między platformami. Ten bardzo prosty koncepcyjnie algorytm został zaczerpnięty z
pracy [MAHO98]. Algorytm działa następująco:
1. jeżeli platforma zakończy całą pracę, to wyślij żądanie o pracę do
pierwszego sąsiada
2. jeżeli sąsiad nie ma pracy, to wyślij żądanie do drugiego sąsiada
3. jeżeli któraś z platform ma pracę, pobierz wyspę z tej platformy
i wznów jej działanie
Opierając system na koncepcji rozproszonych obiektów musimy w tym momencie
pamiętać o aktualizacji zdalnych referencji wysp, które zmieniły swoje położenie w
systemie. Implementacja tego algorytmu została pokazana na diagramie poniżej.
lastActiveIsland : platform1 : newIsland : runner : Thread distrModel : platform2 : island : mainPlatform : islands : Island localeIsland :
IslandImpl PlatformImpl IslandImpl DistributedModel Platform IslandImpl MainPlatform LocaleIsland
finished( )
DLBrequest( )
setDLBrequestor()
ostatnia
aktywna
stop( )
wyspa na
platformie1
kończy swoja
pracę
DLBresponse( )
<>
distributeNewReference( )
distributeNewReference( )
updateIslandReference( )
updateNeighbourReference( ) updateNeighbourReference( )
do
wszystkich
sąsiadów
wyspy
updateEmigrantsQueue( )
getImigrantsQueue( )
removeIsland( )
start( )
run( )
Rysunek III-18 diagram interakcji algorytmu DLB
55
3.7. Detekcja zakończenia działania algorytmu
Każdy węzeł obliczeniowy (wyspa) posiada wiedzę tylko na temat swojej
własnej populacji, wiedząc niewiele lub nic o pozostałych. Aby algorytm (w sensie
globalnym) zakończył swoje działanie, należy wprowadzić pewien mechanizm
detekcji. Można wyróżnić dwa podejścia: scentralizowane i zdecentralizowane.
Działanie zdecentralizowanego mechanizmu detekcji wzorowane jest na pewnych
zasadach rządzących siecią Token Ring. Mechanizm polega na tym, że:
1. jeżeli na pewnej platformie (specjalnie wyszczególnionej) wszystkie
wyspy zakończą swoje działanie, generowany jest specjalny
znacznik-token, który posyłany jest do następnej platformy (zgodnie
z topologią pierścienia)
2. jeżeli każda inna platforma zakończy przetwarzanie wszystkich
wysp, czeka
3. jeżeli któraś z platform wyszczególnionych w punkcie 2 otrzyma
token to:, jeżeli jest bezczynna, przesyła token dalej; jeżeli pracuje,
przetrzymuje znacznik do momentu zakończenia pracy
4. jeżeli znacznik powróci do platformy wyszczególnionej w punkcie 1,
to oznacza bezczynność wszystkich platform, czyli zakończenie
działania algorytmu
Drugie podejście (scentralizowane) polega na wyszczególnieniu specjalnego
węzła-koordynatora, który zlicza bezczynne platformy. Jeżeli licznik wskaże ilość
bezczynnych platform równą całkowitej ilości platform, znaczy to zakończenie
działania algorytmu.
Z racji istnienia w RPE platformy głównej, udostępniającej zdalny obiekt typu
Counter, w detekcji zakończenia działania algorytmu wykorzystamy podejście
scentralizowane, gdzie obiekt typu Counter oprócz swoich normalnych zadań
będzie zliczał bezczynne węzły obliczeniowe.
3.8. Bezpieczeństwo platform
Zakładając potencjalne wdrożenie RPE w pewnym rozproszonym środowisku,
gdzie poszczególnymi węzłami obliczeniowymi mogą zarządzać różni
administratorzy, należy szczególną uwagę zwrócić w stronę bezpieczeństwa.
56
Rozważmy następującą sytuację: użytkownik instaluje RPE na domowym
komputerze. Jako że wdrażany algorytm wymaga intensywnych obliczeń,
użytkownik postanawia zaimplementować swój algorytm zgodnie z modelem
rozproszonym. Użytkownik nie ma dostępu do sieci lokalnej, ale jego znajomy
administrator taki dostęp posiada. Użytkownik prosi administratora o zainstalowanie
platform RPE w sieci, po czym uruchamia swój algorytm...
Grozba polega na tym, że algorytm użytkownika może wykonywać dowolne
operacje jak każdy inny program w systemie. Aby ustrzec się przed niepożądanymi
skutkami działania algorytmów, nakładamy na ich implementacje pewne restrykcje,
zbliżone do tych, jakie nakładane są na aplety Java uruchamiane w przeglądarce
internetowej. Dokonuje tego obiekt ładowacza klas typu EAClassLoader, który z
racji tego, że dziedziczy po SecureClassLoader, ma możliwości nakładania
restrykcji na ładowane klasy (mechanizm menedżerów bezpieczeństwa i pozwoleń
w Javie).
3.9. Odporność na awarie
Implementowany w RPE model wyspowy należy do grupy modeli
gruboziarnistych, które z racji tego, że zakładają długi okres obliczeń na
poszczególnych węzłach w stosunku do komunikacji między nimi, są w znacznym
stopniu wrażliwe na awarie tychże węzłów. Jeżeli w trakcie działania algorytmu
awarii ulegnie dany węzeł, to przepada cała subpopulacja ewoluująca na tym
węzle. Jest to znaczny uszczerbek na wydajności algorytmu.
Zakładając niewielkie koszty wymierne takich awarii (autor nie przewiduje
komercyjnych zastosowań systemu), RPE nie będzie wprowadzać żadnych
mechanizmów (czasochłonnych i niełatwych w implementacji) odzyskiwania
utraconych danych. Jedyne, co RPE będzie gwarantowała w sytuacji awarii węzła,
to bezproblemową kontynuację działania algorytmu z pozostałymi węzłami.
4. Szczegóły implementacyjne
4.1. Implementacja projektu na platformie Java
Jako język implementacji projektu posłuży nam język Java w wersji 1.4.0. Java
jest językiem, którego kod jest w pełni przenośny i zdolny do uruchomienia pod
57
dowolnym systemem operacyjnym, dla którego istnieje maszyna wirtualna Javy.
Taka funkcjonalność idealnie współgra z założeniami RPE, która jako system
rozproszony może być uruchomiona pod wieloma systemami operacyjnymi
równocześnie. Również użytkownik, pisząc kod swoich algorytmów abstrahuje od
szczegółów związanych z ich wdrożeniem. Klasy użytkownika będą
rozpowszechniane między platformami niezależnie od systemu operacyjnego na
jakich działają.
4.2. Odwzorowanie projektu w strukturze pakietów Javy
W tym podrozdziale przedstawiony zostanie fragment dokumentacji
wygenerowanej narzędziem javadoc. Wszystkie pakiety przydzielone zostaną do
zbiorów JAR, tak jak jest to widoczne na diagramie wdrożenia załączonym poniżej.
jfreechart-0.9.15.jar
jcommon-0.9.0.jar
DEFmainPlatform.jar
DEFplatform.jar DEFcore.jar
klasa startowa
DEFramework.class
EvolutionaryTools
Platform RMI GUI MainPlatform DEFramework
Rysunek III-19 diagram wdrożenia RPE
Wykaz pakietów:
- Pakiet DEFramework.EvolutionaryTools
Zawiera klasy niezbędne w konstrukcji oraz implementacji Algorytmów
Ewolucyjnych.
Interface Summary
AlgorithmConstants Wyliczenie określające rodzaj algorytmu
Crossable Definiuje interfejs dla osobników krzyżowalnych
Individual Interfejs przeznaczony do implementacji przez użytkownika.
58
IndividualConstants Wyliczenie określające rodzaj osobników
Mutable Definiuje interfejs dla osobników mutowalnych
Drugi z interfejsów przeznaczony do implementacji przez
Results
użytkownika(opcjonalnie).
Wyliczenie definiujące różne możliwości zakończenia
StopCondition
algorytmu.
Class Summary
Klasa odpowiedzialna za dynamiczne ładowanie klas
EAClassLoader
algorytmu użytkownika z platformy głównej Framework'u.
Fabryka tworząca modele kreowania prób losowych
EAFactory (populacji) w algorytmie ewolucyjnym (zaimplementowana
jako Singleton)
EvolutionaryAlgorithm Klasa abstrakcyjnego algorytmu ewolucyjnego.
Klasa dekoratora, której zadaniem będzie "wyposażenie"
IdentificableIndividual osobnika w numer określający jego pochodzenie - tzn.
algorytm, z którego pochodzi (w ramach konkretnej wyspy).
Klasa tworząca próby losowe zgodnie z modelem Prostego
SimpleEvolutionaryAlgorithm
Algorytmu Ewolucyjnego
Klasa tworząca próby losowe zgodnie z modelem Algorytmu
SteadyStateAlgorithm
Ewolucyjnego Z Ustalonym Stanem
Exception Summary
EAException Wyjątek zgłaszany przez wykonywany algorytm.
- Pakiet DEFramework.MainPlatform
Zawiera klasę Platformy głównej, Counter'a, potrzebne interfejsy Słuchaczy
oraz wykorzystywane przez nie klasy zdarzeń.
Interface Summary
AlgorithmModel
Wyliczenie określające różne modele algorytmu
Interfejs, którego implementujące obiekty będą nasłuchiwać
AlgorithmStateListener
zdarzeń związanych z wykonywanym algorytmem
IslandStructure
Wyliczenie określające strukturę wysp
Interfejs, którego implementujące obiekty będą nasłuchiwać
PlatformStructureListener
zmian w strukturze platform systemu.
Class Summary
Określa właściwości zdarzenia związanego ze zmianą stanu
AlgorithmStateEvent
wykonywanego algorytmu
Klasa implementująca zdalny interfejs Counter, pełniący rolę
CounterImpl
m. in. w synchronizacji wysp oraz detekcji zakończenia
59
działania algorytmu w odniesieniu globalnym.
MainPlatformImpl
Platforma główna.
Określa właściwości zdarzenia związanego ze zmianą
PlatformStructureEvent
struktury platform systemu
- Pakiet DEFramework.Platform
Zawiera wszystkie klasy potrzebne w konstrukcji oraz działaniu platformy
Interface Summary
Interfejs definiujący zestaw stałych przydatnych w
ParallelModelConstants
charakteryzowaniu Rozproszonego Algorytmu Ewolucyjnego.
Topology Interfejs reprezentujący topologię
Class Summary
AsynchronousDistributedModel Asynchroniczna specjalizacja modelu rozproszonego,
Console Klasa reprezentująca okienko konsoli
Klasa odpowiedzialna za nasłuchiwanie zdarzeń związanych z
Console_actionAdapter
akcją.
ConsolePrintStream Klasa odpowiedzialna za drukowanie tekstu do konsoli
Abstrakcyjna klasa bazowa definiująca interfejs dla
DistributedModel
konkretnych "modeli rozproszonych".
DistributedModelFactory fabryka tworzaca obiekty typu DistributedModel
Struktura zawierająca emigrujących osobników oraz
EmigratingIndividuals
docelową wyspę
Klasa pozwalająca na wysyłanie osobników do innych wysp
EmigrationManager
w sposób asynchroniczny
FullGraph Reprezentuje topologię pełnego grafu
Grid2D Reprezentuje topologię dwuwymiarowej siatki.
IslandImpl Podstawowa implementacja wyspy.
Klasa "delegata", który wyręcza wyspę (IslandImpl) od
LocaleIsland
wykonywania większości operacji.
PlatformImpl Implementacja zdalnego interfejsu Platform.
Wątek rejestrowany w maszynie wirtualnej i odpalany w
PlatformShutdownHook momencie wyłączenia platformy w sposób inny niż poprzez
graficzną konsolę.
Reprezentuje topologię dla modelu Stepping-Stone
Ring
(topologię połączeń pierścienia)
SynchronousDistributedModel Synchroniczna specjalizacja modelu rozproszonego
60
- Pakiet DEFramework.RMI
Definiuje wszystkie potrzebne zdalne interfejsy RMI
Interface Summary
Interfejs definiujący metody Counter'a dostępne poprzez
Counter
mechanizm zdalnego wywoływania metod - RMI
Interfejs definiujący metody wyspy dostępne poprzez
Island
mechanizm zdalnego wywoływania metod - RMI
Interfejs definiujący metody platformy głównej dostępne
MainPlatform
poprzez mechanizm zdalnego wywoływania metod - RMI
Interfejs definiujący metody platformy dostępne poprzez
Platform
mechanizm zdalnego wywoływania metod - RMI
Class Summary
Implementacja Interfejsu Dostawcy Usługi (Service Provider
CustomRMIClassLoaderSpi Interface) dla dynamicznego ładowacza klas -
RMIClassLoader'a.
4.3. RMI jako implementacja koncepcji rozproszonych obiektów w Javie
W punkcie 2.2 niniejszego rozdziału przybliżona została koncepcja
rozproszonych obiektów. Jak zostało tam powiedziane, koncepcja ta ma kilka
implementacji, jedną z nich jest Java RMI. RMI w odróżnieniu od CORBA narzuca
nam odgórnie język programowania Java jako język implementacji interfejsów
zdalnych obiektów. Takiego ograniczenia nie wprowadza CORBA, gdzie interfejsy
piszemy w specjalnym języku definiowania interfejsów IDL, a ich implementacje
dostarczamy w dowolnych językach. Powodów, dla których wybieramy technologię
RMI jest kilka:
" RPE jest systemem w całości napisanym w Javie
" RMI jest technologią prostą i wygodną w stosowaniu
" pisanie interfejsów zdalnych obiektów w Javie pozwala nam uwzględnić
typy podstawowych bibliotek Javy jako typy zwracane oraz jako
parametry metod (czego nie możemy zrobić w IDL u)
Każdy zdalny obiekt RMI musi implementować swój zdalny interfejs
rozszerzający Remote. Dla takiego obiektu generujemy kompilatorem rmic
specjalne namiastki (ang. Stub) klas, które zajmują się szeregowaniem i
61
rozszeregowywaniem parametrów przekazywanych bądz zwracanych poprzez
zdalne wywołanie metody.
Technologia ta, pozwala nam zorganizować komunikację między modułami
rozproszonymi w sieci w sposób zbliżony do komunikacji, jaka zachodzi pomiędzy
obiektami lokalnymi.
62
IV. Graficzne środowisko szybkiego
rozwoju algorytmów ewolucyjnych
1. Założenia ogólne
Aby umożliwić użytkownikowi wygodną pracę z RPE, dostarczymy pewien
graficzny system zintegrowany z platformą główną systemu. Do najważniejszych
funkcjonalności aplikacji należą:
" zapewnienie sprawnych i wygodnych mechanizmów tworzenia oraz
zarządzania projektami
" zapewnienie edytora języka programowania Java o pewnych
podstawowych funkcjonalnościach jak: kolorowanie składni języka Java
czy możliwości kompilowania kodu przez dołączany z zewnątrz
kompilator javac
" zapewnienie mechanizmów zarządzania oraz konfiguracji platform RPE
" możliwość konfiguracji modeli ewolucyjnych warstwy logiki algorytmu
oraz modeli warstwy implementacji (model wyspowy)
" graficzna prezentacja wyników
Aplikacja została napisana z użyciem następujących bibliotek: oficjalnej
biblioteki graficznej Java Swing, darmowej biblioteki tworzenia wykresów jFreeChart
(http://www.jfree.org/jfreechart/index.html) oraz darmowej biblioteki look&feel
Kunststoff (http://www.incors.org/).
2. Opis interfejsu użytkownika
Na załączonym poniżej obrazku widać okno główne aplikacji podzielone na
trzy części. W lewej górnej części znajduje się menedżer projektu pozwalający
zarządzać jego zawartością. W prawej górnej części znajduje się panel z zakładkami
wyświetlający zawartość plików projektu. W zależności od rodzaju pliku można taki
plik: jedynie przeglądać bądz przeglądać/edytować. Dolna część okna obejmuje
panel z komunikatami.
63
Rysunek IV-1 okno główne graficznej aplikacji zintegrowanej z RPE
Kolejny rysunek przedstawia okno konfiguracji czasu wykonania oraz
konfiguracji projektu. Konfigurację czasu wykonania (panel oznaczony algorithm
runtime configuration) rozpoczynamy od wyboru modelu implementacji algorytmu
model sekwencyjny / rozproszony. Dalej ustawiamy model ewolucyjny: prosty
algorytm ewolucyjny / algorytm ewolucyjny z ustalonym stanem; warunek stopu:
minięcie określonej ilości iteracji / osiągnięcie fazy stagnacji algorytmu, okres
stagnacji, maksymalną ilość iteracji, wielkość populacji, ilość wykonań algorytmu oraz
interwał pomiędzy operacją wysyłania częściowych wyników z węzłów
obliczeniowych
Konfiguracja projektu (panel oznaczony project properties) obejmuje
określenie: nazwy klasy algorytmu implementującej interfejs Individual, nazwy klasy
algorytmu implementującą interfejs Results (opcjonalnie), plików: wejściowego /
wyjściowego oraz ścieżek do pozostałych klas algorytmu (panel oznaczony classpath
management).
64
Rysunek IV-2 okno konfiguracji czasu wykonania oraz projektu
Rysunek następny obejmuje konfigurację modeli ewolucyjnych: prostego algorytmu
ewolucyjnego (panel oznaczony Simple Evolutionary Algorithm) oraz algorytmu
ewolucyjnego z ustalonym stanem (panel oznaczony Steady State Algorithm). Dla
obu modeli ustawiamy prawdopodobieństwa: krzyżowania oraz mutacji.
Rysunek IV-3 okno konfiguracji modeli ewolucyjnych
65
Kolejny rysunek przedstawia okno konfiguracji modelu wyspowego.
Ustawiamy kolejno: parametry migracji (panel migration parameters) - częstość
migracji (migration interval) i wielkość migracji (migration rate); model migracji (panel
migration model) - model synchroniczny (synchronous) oraz asynchroniczny
(asynchronous); strukturę wysp (panel island structure) - struktura homogeniczna
(homogeneous) oraz struktura heterogeniczna (heterogeneous); schemat emigracji
osobników (panel emigration selection scheme) osobniki emigrujące: najlepsze,
losowe, najgorsze; schemat zastępowalności rodzimych osobników przez imigrantów
(panel imigration replacement scheme) - zastępowanie osobników: najlepszych,
losowych, najgorszych; algorytm dynamicznego równoważenia narzutu
obliczeniowego na platformach (panel dynamic load balancing) włączony,
wyłączony; polityka migracji (panel migration policy) do wszystkich sąsiadów (all
neighbours), do losowego sąsiada (random neighbour); topologia pełny graf (full
graph), pierścień (ring), siatka 2D (2D Grid).
Rysunek IV-4 okno konfiguracji Modelu Wyspowego
Rysunek ostatni obejmuje konfigurację platform oraz wysp. Każdej platformie
przypisujemy określoną liczbę wysp wpisywaną w pole tekstowe oznaczone jako
number of islands. Dla każdej wyspy jesteśmy w stanie określić odrębne parametry
66
modeli ewolucyjnych oraz parametr częstość migracji. Parametry te, będą używane
w momencie wyboru przez użytkownika trybu asynchronicznego (parametr częstość
migracji) oraz struktury wyspy - heterogenicznej.
Rysunek IV-5 okno konfiguracji platform i wysp
67
V. Implementacja przykładowego
algorytmu problem komiwojażera
1. Zdefiniowanie problemu komiwojażera
Załóżmy pewien pełny graf o zbiorze n węzłów (miast), gdzie z każdym
połączeniem wiąże się pewny nieujemny koszt przejścia. Rozwiązanie problemu
komiwojażera będzie polegało na wyznaczeniu cyklu Hamiltona tego grafu przy
minimalnym koszcie (najkrótszej drodze).
Formalnie problem komiwojażera posiada przestrzeń rozwiązań będącą
zbiorem permutacji n miast, gdzie każda z tych permutacji stanowi rozwiązanie
problemu. Optymalne rozwiązanie to taka permutacja, dla której koszt jest minimalny.
Rozmiar przestrzeni rozwiązań określa się jako n!, przez co problem uchodzi za
NP-trudny.
Dokładne opracowanie tego zagadnienia, na którym opiera się niniejszy
rozdział, znajduje się w [MICH99].
2. Struktura oraz kodowanie chromosomu
Jedną z możliwych reprezentacji chromosomu jest reprezentacja wektorowa o
trzech różnych postaciach: przyległościowej, porządkowej oraz ścieżkowej.
Wykazano, że reprezentacja ścieżkowa jest najbardziej naturalną oraz najbardziej
efektywną. W reprezentacji ścieżkowej chromosom rozumiemy jako wektor n
elementowy, gdzie każdy element tego wektora to jedno miasto. Przykładowy wektor:
123456789
oznacza trasę o następujących przejściach : 1->2, 2->3, 3->4, 4->5, 5->6, 6->7, 7->8,
8->9, gdzie 1,2,3,...,n to numery miast.
3. Funkcja przystosowania
Funkcją przystosowania w problemie komiwojażera będzie funkcja postaci:
f (m1, m2 , m3,..., mn )
68
zwracająca całkowity kosz trasy wyznaczonej przez miasta m1 do mn. Im długość
trasy będzie krótsza, tym osobnik będzie lepiej przystosowany.
4. Implementacja interfejsu Individual
Jak zostało powiedziane w rozdziałach wcześniejszych, chcąc
zaimplementować algorytm na platformie, należy w pierwszej kolejności stworzyć
klasą implementują interfejs Individual. Dla pewnych prostych problemów, jak na
przykład problemu optymalizacji funkcji, taka klasa może okazać się w zupełności
wystarczająca. Dla bardziej złożonego problemu, jak problem komiwojażera, należy
jednakże rozważyć pewną strukturę klas, która u szczytu swojej hierarchii
dziedziczenia będzie posiadać wspomniany interfejs Individual.
Przykładowe rozwiązanie pokazane jest na diagramie poniżej
Individual
Mutable
Crossable
(from EvolutionaryTools)
(from EvolutionaryTools)
(from EvolutionaryTools)
TravelingSalesman
getFitness()
init()
<> <>
generateInitialGenotype()
Mutation -mutationManager -crossoverManager
Crossover
evaluate()
storeResults()
1 1 1 1
1 1 1 1
mutate() crossover()
showResults()
clone()
compareTo()
mutate()
crossover()
PathRepTravelingSalesman
generateInitialGenotype()
evaluate()
storeResults()
clone()
init()
showResults()
Rysunek V-1 Diagram klasowy (Individual) dla problemu komiwojażera
Na diagramie widoczne są następujące klasy : klasa abstrakcyjna
TravelingSalesman, jej specjalizacja PathRepTravelingSalesman oraz pięć
interfejsów: Individual, Mutation, Crossover, Crossable, Mutable.
69
Powodem, dla którego nie wyprowadzamy wprost z interfejsu Individual
gotowej klasy osobnika, jest chęć zapewnienia pewnej bazy dla różnych
komiwojażerów z różnymi reprezentacjami chromosomów. Na diagramie widoczna
jest jedna taka specjalizacja: PathRepTravelingSalesman, która reprezentuje
komiwojażera z reprezentacją ścieżkową.
Metody, które na poziomie klasy TravelingSalesman muszą pozostać
abstrakcyjne (zależą od konkretnej reprezentacji chromosomu) to: evaluate(),
generateInitialGenotype(), clone() oraz storeResults(). Pozostałe metody są w
domyślnej postaci implementowane przez TravelingSalesman.
Pozostałe na diagramie interfejsy to: Mutation, Crossover oraz Mutable,
Crossable. Implementacja interfejsów Mutable, Crossable mówi o krzyżowalności
i mutowalności osobnika, a interfejsy Mutation, Crossover stanowią bazę dla różnych
implementacji tychże operacji (zastosowanie wzorca projektowego Strategy). Jak
zostanie pokazane w dalszej części rozdziału, każda z reprezentacji chromosomu
posiada swoje własne wersje tych operatorów. Wszystkie klasy reprezentujące owe
operacje będą posiadały u szczytu swojej hierarchii dziedziczenia interfejsy Mutation
i Crossover. Wywołanie przez systemowe procedury ewolucyjne metod mutate() oraz
crossover() z interfejsów Mutable, Crossable (implementowanych przez
TravelingSalesman), będzie delegowane przez TravelingSalesman do odpowiednich
obiektów typu Crossover oraz Mutation (korzystamy tutaj z polimorficznego
wywołania metod w Javie).
Opisaną sytuacją można przedstawić za pomocą poniższego pseudokodu:
public abstract class TravelingSalesman implements Individual, Mutable, Crossable {
Mutation mutationManager;
Crossover crossoverManager;
java.util.List genotype;
public void mutate( double probability ){
mutationManager.mutate( genotype );
}
public Individual crossover( Individual i, double probability ){
crossoverManager.crossover( genotype, (( TravelingSalesman )i ).genotype );
//zwracamy potomka : this lub i
}
}
70
Za inicjację obiektów mutationManager oraz crossoverManager odpowiedzialne są
specjalizacje klasy TravelingSalesman w naszym wypadku będzie to klasa
PathRepTravelingSalesman, która tworzyć będzie obiekty mutacji i krzyżowania
właściwe reprezentacji ścieżkowej. Należy jeszcze powiedzieć, że wywołujemy
metody mutate() i crossover() z interfejsów Mutation i Crossover dla ich efektu
ubocznego (modyfikacji parametrów-genotypów).
5. Implementacja interfejsu Results
Drugim z interfejsów (opcjonalny) przeznaczonych do implementacji przez
użytkownika jest Results. Obiekt użytkownika implementujący ten interfejs
przeznaczony będzie do wyświetlania częściowych wyników przysyłanych z węzłów
obliczeniowych. Również i w tym przypadku prosta implementacja Results nie
wystarczy. W zamian można zaproponować poniższy diagram.
Results
(from EvolutionaryTools)
TravelingSalesmanResult
-nodePanels
CitiesViewPanel
init()
showResults()
1 n
1 n
updateResults()
PathRepTravelingSalesmanResult
updateResults()
Rysunek V-2 Diagram klasowy (Results) dla problemu komiwojażera
Jak widać na diagramie, nie wyprowadzamy gotowej klasy wprost z Results, lecz
wprowadzamy specjalizację pod nazwą PathRepTravelingSalesmanResult, która
obsługuje aktualizacje wyników (poprzez nadpisanie metody updateResults() ) w
sposób właściwy dla ścieżkowej reprezentacji chromosomu.
71
6. Operatory genetyczne
6.1. Mutacja
Jak zostało powiedziane wcześniej, każda z reprezentacji wektorowych
chromosomu : przyległościowa, porządkowa oraz ścieżkowa posiada swoje własne
wersje operatorów mutacji oraz krzyżowania. Na diagramie poniżej przedstawiono
strukturę klas odpowiedzialnych za mutację dla reprezentacji ścieżkowej. Cztery
obsługiwane rodzaje mutacji to: przestawienie losowa zamiana dwóch miast,
wstawianie losowe przestawienie jednego miasta, inwersja odwrócenie
kolejności miast wskazanych przez dwa punkty cięcia oraz przemieszczenie
losowe przemieszczenie podtrasy.
<>
Mutation
mutate()
<>
PathRepMutation
InsertMutation SwapMutation InvertMutation DisplacementMutation
mutate() mutate() mutate() mutate()
Rysunek V-3 diagram klas odpowiedzialnych z mutację w problemie komiwojażera
6.2. Krzyżowanie
Dla reprezentacji ścieżkowej wyróżniamy trzy podstawowe rodzaje
krzyżowania :
" z częściowym odwzorowaniem (PMX) nowego potomka tworzy się z dwóch
rodziców w taki sposób, że wybieramy podtrasę danego rodzica, uzupełniając
pozostałe wolne miejsca miastami z drugiego rodzica, tak dalece jak to tylko
możliwe (nie ma konfliktu). Jeżeli wystąpi konflikt, to miasto na konfliktowej
pozycji ustawiamy korzystając z przygotowanego ciągu odwzorowań (mapy
72
wymiany miast). Wezmy na przykład dwóch rodziców (punkty cięcia
oznaczone przez | ), takich, że:
r1=(123|456|789) r2=(918|273|645)
Potomków otrzymujemy zamieniając podtrasy ograniczone punktami cięcia,
tak, że:
(krok 1) p1=(xxx|273|xxx) p2=(xxx|456|xxx)
Miejsca oznaczone x wypełniamy miastami z danego rodzica, tak dalece jak
nie wystąpi konflikt:
(krok 2) p1=(1xx|273|x89) p2=(918|456|xxx)
Pozostałe miejsca wypełniamy miastami, korzystając z przygotowanego ciągu
odwzorowań, stanowiącego mapę wymiany miast w kroku pierwszym. Ciąg
odwzorowań jest następujący: 4<->2, 5<->7, 6<->3. Wobec tego ostatecznie
potomkowie mają postać:
(krok 3) p1=(146|273|589) p2=(918|456|327)
" z porządkowaniem (OX) nowego potomka tworzy się z dwóch rodziców w
taki sposób, że wybieramy podtrasę jednego rodzica i uzupełniamy pozostałe
miejsca miastami od drugiego z nich, w taki sposób, aby zachować wzajemne
uporządkowanie tychże miast. Wezmy na przykład dwóch rodziców, takich,
że:
r1=(123|456|789) r2=(918|273|645)
W pierwszym kroku pozostawiamy u obu potomków podtrasy z rodziców,
ograniczone punktami cięcia | :
p1=(xxx|456|xxx) p2=(xxx|273|xxx)
Dla pierwszego potomka tworzymy uporządkowany ciąg miast z drugiego
rodzica, w taki sposób, że odczytujemy miasta po kolei poczynając od
drugiego punktu cięcia. W ten sposób dostajemy następujący ciąg miast
(zachowując ich uporządkowanie):
6 4 5 9 1 8 2 7 3
Z tego ciągu usuwamy te miasta, które posiada już pierwszy potomek miasta
4 5 i 6. Po tym kroku ciąg ma następującą postać:
9 1 8 2 7 3
Taki ciąg doklejamy do pierwszego potomka poczynając od drugiego punktu
cięcia. Po tej operacji potomek pierwszy ma następującą postać:
73
p1=(273|456|918)
Potomka drugiego tworzymy analogicznie.
" cykliczne (CX) - nowego potomka tworzy się z dwóch rodziców w taki sposób,
że każde miasto wraz z jego pozycją pochodzi od jednego z rodziców. Wezmy
na przykład dwóch rodziców, takich, że:
r1=(123456789) r2=(412876935)
Pierwszego potomka tworzymy w sposób następujący: w pierwszej kolejności
bierzemy miasto na pozycji pierwszej rodzica pierwszego:
p1=(1xxxxxxxx)
Następne miasto bierzemy z pozycji pierwszej r2 4. Miasto to, wstawiamy do
p1 na takiej pozycji, na której wybrane miasto 4 znajduje się w r1:
p1=(1xx4xxxxx)
Miasto 4 wskazuje w r2 na miasto 8. Ponownie wstawiamy to miasto na takiej
pozycji, na jakiej znajdowało się w r1:
p1=(1xx4xxx8x)
Algorytm wyboru miast kontynuujemy do momentu uzyskania cyklu (2
wskazuje w r2 na 1, które znajduje się już w p1):
p1=(1234xxx8x)
W takim wypadku pozostałe miejsca wypełniamy miastami z r2:
p1=(123476985)
Potomka drugiego tworzymy analogicznie.
<>
Crossover
crossover()
<>
PathRepCrossover
PMXCrossover OXCrossover CXCrossover
crossover() crossover() crossover()
Rysunek V-4 diagram klas odpowiedzialnych z krzyżowanie w problemie komiwojażera
74
VI. Eksperymenty, testy, wnioski
1. Porównanie implementacji sekwencyjnej z rozproszoną
Przedstawiona w tej pracy rozproszona platforma ewolucyjna posłuży nam w
tym rozdziale do przeprowadzenia pewnych eksperymentów związanych z różnymi
kwestiami implementacji rozproszonej oraz sekwencyjnej. Testy te mają charakter
bardzo ogólny i starają się jedynie przybliżyć lub potwierdzić testy już
przeprowadzone, wykazując przy tym, że RPE spełnia swoje zadania jako
rozproszone środowisko implementacji algorytmów ewolucyjnych.
Pierwszym testem, jaki przeprowadzimy, będzie porównanie wydajności
implementacji sekwencyjnej z rozproszoną. W przeprowadzeniu testu będziemy
używać algorytmu rozwiązującego problem komiwojażera dla 26 miast z
następującymi parametrami:
dla modelu sekwencyjnego definiujemy:
" model tworzenia populacji: Prosty Algorytm Ewolucyjny
" warunek stopu: stagnacja
" okres stagnacji: 50 epok
" wielkość populacji: 500 osobników
" prawdopodobieństwo mutacji: 0,005
" prawdopodobieństwo krzyżowania: 0,5
dla modelu rozproszonego dodatkowo definiujemy:
" wielkość migracji: 3 osobniki
" częstość migracji: 5 epok
" model migracji: asynchroniczny
" schemat selekcji osobników do migracji: osobniki najlepsze
" schemat zastępowania osobników przez imigrantów: osobniki najgorsze
" topologia: jednokierunkowy pierścień
" ilość wysp: 5
75
Symulacja została przeprowadzona na komputerach Pentium IV 1500 MHz z
256 MB pamięci RAM połączonych 100 megabitowym interfejsem sieciowym,
przeznaczając każdej wyspie osobny procesor. Wyniki zostały uśrednione z 50
uruchomień algorytmu:
dla implementacji sekwencyjnej:
" czas działania algorytmu: 149 sekund
" długość wyznaczonej trasy: 2445
dla implementacji rozproszonej:
" czas działania algorytmu: 44 sekundy
" długość wyznaczonej trasy: 2860
Wniosek1:
Tak jak się spodziewaliśmy, czas działania algorytmu zaimplementowanego w
postaci rozproszonej jest o wiele krótszy niż czas działania algorytmu
zaimplementowanego w postaci sekwencyjnej. O tym, jaki jest związek między
ilością wysp i komunikacją, a szybkością działania algorytmu będzie traktował
podrozdział następny. W tym miejscu możemy jedynie stwierdzić, że różnica
między czasami jest znacząca.
Wniosek2:
Znalezione przez algorytm sekwencyjny rozwiązanie okazało się jednakże w
tym teście lepsze. Możemy mniemać, że ma to związek ze złym doborem
parametrów algorytmu rozproszonego, szczególnie wielkości populacji, która
po rozbiciu na demy, okazała się niewystarczająca. Również parametry:
wielkość migracji oraz częstość migracji wydają się być niewłaściwe.
Test miał za zadanie pokazać, że bardzo trudno jest wskazać optymalne
parametry algorytmu rozproszonego znajdującego rozwiązania takie same (bądz
lepsze) od algorytmu sekwencyjnego. Cantu-Paz w [CANTUa] podaje, że badacze
nie byli w stanie do tej pory wskazać takich parametrów w sposób teoretyczny.
Pytania, na które nie znaleziono do tej pory odpowiedzi są następujące:
76
" jaki jest poziom komunikacji (wielkość migracji, częstość migracji) między
wyspami, aby algorytm rozproszony zachowywał się jak algorytm
sekwencyjny?
" jaki jest poziom takiej komunikacji, aby algorytm rozproszony działał lepiej?
" jaki jest koszt takiej komunikacji?
" czy koszt tej komunikacji jest na tyle niewielki, aby implementacja rozproszona
była opłacalna?
2. Skalowalność modelu wyspowego i obliczanie przyśpieszenia
działania
W podrozdziale poprzednim test pokazał, że implementacja rozproszona z
pięcioma wyspami wymagała ponad trzykrotnie mniej czasu na zakończenie obliczeń
niż implementacja sekwencyjna. Badacze wykazali, że pomiędzy ilością wysp,
wybraną topologią, natężeniem komunikacji a czasem działania algorytmu istnieją
pewne związki, które postaramy się w tym miejscu przybliżyć. Pewne teoretyczne
rozważania na ten temat można znalezć w pracy Cantu-Paz a i Goldberg a
[CANTUd],
Przyśpieszenie algorytmu (ang. speedup) wyrażamy jako stosunek szybkości
działania algorytmu sekwencyjnego do szybkości działania algorytmu rozproszonego:
Tserial
Speedup=
Tparallel
gdzie Tserial, to czas działania algorytmu sekwencyjnego, na który składa się:
Tserial =Tcomp = (Tgo + Tse + Tev)*Ps*En
gdzie Tgo = czas wykonania operacji genetycznych, Tse = czas selekcji, Tev = czas
ewaluacji, Ps = ilość osobników w populacji oraz En = liczba epok. Tparallel
wyrażamy jako:
Tparallel = Tcompp + Tcomm
77
gdzie Tcompp = czas obliczeń na węzle p, a Tcomm to czas potrzebny na
komunikację z innymi węzłami (przy założeniu homogenicznego środowiska działania
wysp). Za [CANTUd] przyjmujemy:
Tcomm = Crł
Współczynniki C oraz ł zależą od czynników takich jak topologia oraz cechy
sprzętowe węzłów obliczeniowych. Możliwe jest, aby ł była stała (ł = 0), wtedy czas
komunikacji sieciowej jest niezależny od liczby węzłów r np. w przypadku topologii
pierścienia.
Do naszego eksperymentu wykorzystamy parametry algorytmu z testu
poprzedniego, zmieniając przy tym topologię na pełny graf oraz politykę migracji na:
do wszystkich sąsiadów. Eksperyment ma na celu pokazać, w jaki sposób przyrasta
szybkość algorytmu w stosunku do ilości wysp (każda wyspa ma do dyspozycji
osobny procesor). Wyniki zostały przedstawione na wykresie poniżej.
Rysunek VI-1 wykres obrazujący przyrost szybkości działania algorytmu
Na wykresie można zauważyć, że szybkość algorytmu wzrasta (zależność
zbliżona do logarytmicznej) do momentu, gdy liczba wysp równa się 8. Przy
dodawaniu każdej następnej wyspy przyrost ten będzie się zmniejszał. Wynika to z
78
tego, że ł przy topologii pełnego grafu nie jest stała i sprawia, że koszt komunikacji
rośnie wykładniczo w stosunku do ilości węzłów. W sytuacji, gdy ł nie jest stała
istnieje możliwość wskazania optymalnej ilości węzłów, przy których przyrost
szybkości algorytmu jest największy [CANTUd].
3. Testy algorytmu dynamicznego równoważenia narzutu
obliczeniowego na platformach
W rozdziale przedstawiającym cechy projektu RPE, został pokrótce omówiony
algorytm dynamicznego równoważenia narzutu obliczeniowego na platformach.
Algorytm ten został wykorzystany w pracy [MAHO98] przy optymalnym projektowaniu
złożonych struktur wielowarstwowych. Autor wykazał przydatność omawianego
algorytmu i zauważył kilka jego podstawowych własności. Spostrzeżenia są
następujące:
1. jeżeli liczba procesorów P równa się liczbie subpopulacji S, to algorytm
dynamicznego równoważenia narzutu nie daje lepszych rezultatów od
algorytmu statycznego, co jest w miarę oczywiste. Jeżeli dany procesor Pi
skończy pracę, to pozostaje bezczynny, gdyż każdy inny procesor przetwarza
tylko jedną populację
2. jeżeli Pkorzyści. Korzyści te, są tym większe im S/P jest większe. Dodatkowo
algorytm przynosi lepsze rezultaty, jeżeli stosunek najmniejszej liczby epok
potrzebnej do zakończenia działania do największej ilości tychże epok (przy
stagnacyjnym kryterium stopu) jest duża
Mając na uwadze opisane wyżej cechy algorytmu, przeprowadzimy test
stwierdzający jego przydatność. Parametry algorytmu zostały zaczerpnięte z testu
pierwszego przy następującym rozłożeniu wysp na czterech platformach : 4-1-4-1.
Dodatkowo ustawiamy częstość migracji na 0, aby mierzyć dokładnie czas działania
algorytmu, a nie czas migracji.
Otrzymane wyniki są następujące:
" czas działania algorytmu bez DLB 107 sekund
" czas działania algorytmu z DLB 70 sekund
79
VII. Podsumowanie
Rozproszona platforma ewolucyjna, jest warstwowym, rozproszonym
środowiskiem implementacji algorytmów ewolucyjnych, stworzonym przy użyciu
wysokopoziomowych, obiektowo zorientowanych narzędzi projektowania oraz
implementacji. Rozproszona platforma ewolucyjna, nie jest systemem stworzonym w
sposób gwarantujący optymalne wykorzystanie zasobów sprzętowych.
Wykorzystanie wysokopoziomowego języka programowania Java, mimo ogromnej
ilości zalet, których nie sposób tu wszystkich wymienić, odbija się w pewnej mierze
na wydajności systemu. Również użycie technologii RMI, jako podstawy warstwy
komunikacyjnej systemu, przy całej swej prostocie, funkcjonalności i elastyczności
powoduje spadek wydajności, co odbija się na szybkości działania samych
algorytmów.
Czy użycie takich niskopoziomowych technologii jak C/C++, PVM czy MPI
dałoby lepsze rezultaty? W pewnym sensie tak. System działałby szybciej,
aczkolwiek cały proces tworzenia byłby nieporównywalnie bardziej skomplikowany,
mozolny i narażony na wystąpienie błędów oraz niedociągnięć.
Jak można zauważyć w [UHRU], gdzie autorzy przeprowadzali testy
porównujące wysokopoziomowe, oparte na języku Java i technologii CORBA,
agentowo zorientowane podejście przy rozwiązywaniu równań liniowych w problemie
CAE, przy zastosowaniu algorytmu SBS (ang. Subdomain-By-Subdomain) z
rozwiązaniem niskopoziomowym opartym o C i PVM, rozwiązanie wysokopoziomowe
okazało się tylko 4-5 razy wolniejsze. Jest to na tyle niewielka różnica, że
rozwiązanie wysokopoziomowe okazało się w generalnym rozrachunku znacznie
lepszym pomysłem.
Dodać do tego należy, że CORBA, z racji obsługi wielu języków, stwarza
większy narzut czasowy niż monojęzykowa RMI. Z tego faktu z kolei wynika, że
niewielkim kosztem wydajności, oparta na RMI rozproszona platforma ewolucyjna
okazuje się systemem względnie szybkim, elastycznym i nadającym się do dalszej
rozbudowy i łatwej pielęgnacji.
W dalszej perspektywie można sobie wyobrazić następujące zmiany w systemie:
80
" dodanie nowych modeli tworzenia populacji w warstwie logiki systemu
" reorganizacja warstwy postaci algorytmu w celu umożliwienia implementacji
szerszej gamy algorytmów np. algorytmów optymalizacji wielokryterialnej
" rozbudowa warstwy implementacji o nowe modele np. model Master-Slave z
dynamiczną reorganizacją subpopulacji
" rozbudowa graficznej aplikacji zintegrowanej z platformą główną
Bardziej radykalnym krokiem byłoby zorganizowanie warstwy implementacji
systemu na jeszcze wyższym poziomie niż RMI i modele rozproszone przytoczone w
tej pracy. Można sobie wyobrazić rozproszoną platformę ewolucyjną jako dalece
dynamiczny system wieloagentowy, gdzie specjalistyczne, inteligentne jednostki-
agenci brałyby udział w przeprowadzeniu procesu ewolucji np. przy zastosowaniu
modelu wspinaczy i szperaczy. Na dzień dzisiejszy istnieje wiele darmowych
narzędzi, za pomocą których taki system można by było zbudować, dając jako
przykład, związaną nierozerwalnie z Javą, wieloagentową platformę Jade.
Autor wyraża nadzieję, że rozproszona platforma ewolucyjna spełni
wymagania potencjalnych użytkowników i chociaż w minimalnym stopniu wspomoże i
ułatwi proces implementacji ich algorytmów ewolucyjnych. Autor dokonał wszelkich
starań, aby system był w jak największym stopniu pozbawiony usterek i
niedociągnięć, których niestety w żadnym systemie wykluczyć całkowicie nigdy nie
można.
81
Literatura
[ABRA92] Abramson D., Abela J., A Parallel Genetic Algorithm for Solving
the School Timetabling Problem , 15 Australian Computer Science Conference,
Hobart, Feb 1992.
[ALBA99a] Alba E., Troya J. M., An Analysis of Synchronous and
Asynchronous Parallel Distributed Genetic Algorithms with Structured and
Panmictic Islands , Parallel and Distributed Processing, J. Rolim et al. (eds.),
Lecture Notes in Computer Science 1586, pp. 248-256. Springer-Verlag, 1999.
[ALBA99b] Alba E., Troya J. M., A Survey of Parallel Distributed Genetic
Algorithms , Complexity 4(4):31-52, 1999.
[BELD95] Belding T. C.: The Distributed Genetic Algorithm Revisited . In
Eshelman L. J. (ed.): Proceedings of the Sixth International Conference on
Genetic Algorithms. Morgan Kaufmann, San Francisco, CA (1995) 114-121.
[BOCK02] Bockman B. : MPIGALib: A Library for Island Model Parallel Genetic
Algorithms , Submitted To: Tosh Kakar Advisor: David Wolf CSCE499 (Senior
Capstone) CSCE Department Pacifc Lutheran University May 28, 2002.
[CAMP] Camp G. : Parallel/Distributed Evolutionary Computation The influence
of spatial interaction in evolutionary behaviour .
[CANTUa] Cantu-Paz E. : A Survey of Parallel Genetic Algorithms , Calculateurs
Paralleles.Vol. 10, No. 2. Paris: Hermes.
[CANTUb] Cantu-Paz E., Goldberg D. E. : Efficient Paralell Genetic Algorithms:
Theory and Practise .
[CANTUc] Cantu-Paz E. : Designing Effcient and Accurate Parallel Genetic
Algorithms , IlliGAL Report No. 99017, July 1999.
[CANTUd] Cantu-Paz E., Goldberg D. : Predicting speedups of idealized
bounding cases of Parallel Genetic Algorithms .
[CORC94] Corcoran A. L., Wainwright R. L. : A Parallel Island Model Genetic
Algorithm for multiprocessor scheduling problem , proceedings of the 1994 ACM /
SIGAPP Symposium on Applied Computing March 6-8, 1994, pp.483-487, ACM
Press.
[ECKE00] Eckel B. : Thinking in Java , Helion 2000.
82
[GOLD98] Goldberg D. E. : Algorytmy genetyczne i ich zastosowania . WNT,
Warszawa 1996, 1998.
[GORD93] Gordon W. S., Whitley D. : Serial and Parallel Genetic Algorithms as
function Optimizers , Technical report CS-93-114, September 16, 1993
[HIRO] Hiroyasu T., Miki M., Hamasaki M., A New Model of Distributed Genetic
Algorithm for Cluster Systems: Dual Individual DGA .
[HOLL75] Holland J. H. Adaptation in Natural and Artifical Systems . Univ. of
Michigan Press, Ann. Arbor, 1975.
[HORS03] Horstman C. S., Cornell G. : Core Java techniki zaawansowane ,
Helion 2003.
[LEVI94] Levine D. : A Parallel Genetic Algorithm for the Set Partioning
Problem , PhD thesis, Illinois Institute of technology, Chicago, 1994. Departament
of Computer Science.
[MATS97] Matsumura T., Nakamura M., Miyazato D., Onaga K., Okech J.
: Effects of Chromosome Migration on a Parallel and Distributing Genetic
Algorithm , proc. Of the 1997 International Symposium on Parallel Archtectures,
Algoritchms and Networks (I-SPAN 1997) , pp.357-361, 1997.
[MATS98] Matsumura T. : A Parallel and Distributed Genetic Algorithm on
Loosely-coupled Multiprocessor systems , master thesis, Graduate School of
Engineering, Electrical and Information Engineering, University of Ryukyus, 1998.
[MAHO98] McMahon M. T. : A Distributed Genetic Algorithm with migration for
the design of composite laminate structures , Thesis submitted to the Faculty of
the Virginia Polytechnic Institute and State University in partial fulfillment of the
requirements for the degree of MASTER OF SCIENCE in Computer Science and
Applications, 1998.
[MICH99] Michalewicz Z. : Algorytmy genetyczne + struktury danych =
programy ewolucyjne , WNT, Warszawa 1996,1999.
[MIKI] Miki M., Hiroyasu T., Hatanaka K. : Parallel Genetic Algorithms with
Distributed-Environment Multiple Population Scheme .
[MUHL] Muhlenbein H. : Asynchronous parallel search by the parallel genetic
algorithm .
[NOWO99a] Nowostawski M., Poli R. : Review and Taxonomy of Parallel
Genetic Algorithms , Technical Report CSRP-99-11, May 1999.
83
[NOWO99b] Nowostawski M., Poli R. : A Highly Scalable Parallel Genetic
Algorithm Based On Dynamic Deme Reorganisation , Technical Report CSRP-
99-12, May 1999.
[POLI] Poli R. : Some Steps Towards a Form of Parallel Distributed Genetic
Programming .
[SCHA02] Schaefer R. : Podstawy genetycznej optymalizacji globalnej ,
Uniwersytet Jagielloński, wydanie I. Kraków 2002.
[TOMA] Tomassini M. : Parallel and Distributed Evolutionary Algorithms : A
Review .
[TONG] Tongchim S. : Coarse-Grained Parallel Genetic Algorithm for Solving
the Timetable Problem .
[UHRU] Uhruski P., Grochowski M., Schaefer R. : Multi-agent Computing
System in a Heterogeneous Network . Institute of Computer Science,
Jagiellonian University, Kraków, Poland.
[VERT] Vertanen K. : Genetic Adventures in Parallel: Towards a Good Island
Model under PVM .
[WHIT98] Whitley D., Rana S., Heckendorn B. : The Island Model Genetic
Algorithm : on Separability, Population Size and Convergence , November 4,
1998.
[WHIT97] Whitley D., Rana S., Heckendorn B. : Island Model Genetic
Algorithms and Linearly Separable Problems , Proc. Of AISB 1997Workshop on
Evolutionary Computing, Manchaster 1997, s 112-129.
[WRIG01] Wright H., Rowe J. : Continious Dynamical System Models of Steady
State Genetic Algorithms , appeard in Foundations of Genetic Algorithms 6,
edited byWorthy N. Martin and William M. Spears, Morgan Kaufmann, 2001, pp.
209-226.
[ZHAK] Zhaksilikov M., Harris F. C. JR. : Comparison of Different
Implementations of Genetic Algorithms .
84

Wyszukiwarka

Podobne podstrony:
06 Praca inzyniera
Utlenianie stopów typu Fe Cr Al PRACA INŻYNIERSKA
Praca inżynierska
PRACA INŻYNIER SYSTEM ALARMOWY
praca inzynierska
praca inżynierska do sprawdzenia(1)
PRACA PRZEJŚCIOWA OPTYMALIZACJA PROCESÓW ENERGETYCZNYCH POPRZEZ ZASOTOWANIE NOWOCZESNYCH ALGORYTMÓ
I1 Prototypowanie algorytmów sterowania pracą elastycznej linii w środowisku PLC S7 300
tworzenie aplikacji w jezyku java na platforme android
Automatyka okrętowa – praca kontrolna 2
cmd=hrk praca&serwis=1
CSharp Introduction to C# Programming for the Microsoft NET Platform (Prerelease)
Automatyka okrętowa – praca kontrolna 4
praca w nadgodzinach

więcej podobnych podstron