Rozproszona platforma algorytmów.pdf

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 Algorytmw

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 Algorytmw Ewolucyjnych

zostaþa napisana przeze mnie samodzielnie.

RwnoczeĻ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 dbr osobistych chronionych prawem

cywilnym.

Ponadto praca nie zawiera informacji i danych uzyskanych w sposb

nielegalny i nie byþa wczeĻniej przedmiotem innych procedur urzħdowych

zwiĢzanych z uzyskaniem dyplomw lub tytuþw zawodowych uczelni wyŇszej.

Seweryn Hejnowicz

Spis treĻci

Wstħp ......................................................................................................................... 8

I. Wprowadzenie do algorytmw ewolucyjnych ........................................................ 10

1. Czym sĢ algorytmy ewolucyjne?................................................................... 10

2. Dlaczego algorytmy ewolucyjne?.................................................................. 10

3. Podstawowe pojħcia..................................................................................... 11

4. Zastosowania algorytmw 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. Rwnolegþa i rozproszona architektura komputerowa.......................... 25

2. Przykþadowa taksonomia.............................................................................. 28

2.1. RŇne klasyfikacje i modele................................................................. 28

2.2. Zrwnoleglenie 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 zrwnoleglony algorytm ewolucyjny.................................... 33

2.6. Model Master-Slave z dynamicznĢ reorganizacjĢ subpopulacji........... 33

2.7. Podsumowanie..................................................................................... 35

III. Rozproszona platforma ewolucyjna..................................................................... 36

1. ZaþoŇenia oglne projektu............................................................................. 36

2. Budowa systemu........................................................................................... 38

2.1. Architektura.......................................................................................... 38

2.2. Koncepcja rozproszonych obiektw..................................................... 39

2.3. Interfejsy komunikacji RPE z uŇytkownikiem ....................................... 40

2.4. Algorytm ewolucyjny - model tworzenia prb 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 rwnowaŇ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 pakietw Javy............................ 58

4.3. RMI jako implementacja koncepcji rozproszonych obiektw w Javie... 61

IV. Graficzne Ļrodowisko szybkiego rozwoju algorytmw ewolucyjnych .................. 63

1. ZaþoŇenia oglne........................................................................................... 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

6.1. Mutacja ................................................................................................ 72

6.2. KrzyŇowanie......................................................................................... 72

VI. Eksperymenty, testy, wnioski .............................................................................. 75

1. Porwnanie implementacji sekwencyjnej z rozproszonĢ............................... 75

2. SkalowalnoĻę modelu wyspowego i obliczanie przyĻpieszenia dziaþania..... 77

3. Testy algorytmu dynamicznego rwnowaŇenia narzutu obliczeniowego na

platformach....................................................................................................... 79

VII. Podsumowanie................................................................................................... 80

Literatura .................................................................................................................. 82

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: