Badanie 1. Topologia.
Przebadano łącznie 11 różnych topologii (tab. 5.2). Tworząc różne topologie poczyniono następujące założenia:
1. Liczebność całej populacji jest równa 2000, co skutkuje różną liczebnością podpopulacji.
2. Całkowity strumień migracji jest stały. Liczbę tę przyjęto na 64, czyli 3,2% całej populacji.
Tablica 5.1: Wpływ topologii na względną różnicę jakości - D (por. wzór 4.3).
| Instancje | n-1 | n-8 | n-16 | o-8-a | o-8-b | o-l6-a | o-l6-b | h-8421 | h-931 | h-441 | hip-16 |
| eil51 | 6.71 | 4.46 | 6.48 | 3.57 | 5.40 | 4.88 | 6.38 | 5.35 | 4.93 | 5.54 | 4.93 |
| berlin52 | 7.79 | 5.77 | 4.50 | 7.45 | 8.41 | 8.02 | 4.84 | 5.62 | 5.60 | 6.09 | 6.66 |
| st70 | 7.64 | 7.32 | 11.17 | 7.79 | 7.61 | 6.19 | 8.36 | 7.26 | 9.69 | 5.48 | 6.52 |
| eil76 | 8.92 | 9.37 | 13.05 | 6.62 | 9.07 | 8.40 | 7.84 | 9.85 | 7.77 | 11.08 | 8.88 |
| pr76 | 5.36 | 6.19 | 10.03 | 5.29 | 7.21 | 6.61 | 6.19 | 7.01 | 6.85 | 6.29 | 6.06 |
| rat99 | 11.87 | 15.18 | 19.60 | 13.10 | 13.82 | 8.29 | 8.55 | 19.08 | 16.05 | 13.67 | 12.14 |
| kroAlOO | 8.36 | 14.16 | 20.80 | 7.58 | 10.98 | 6.87 | 8.79 | 15.16 | 18.67 | 12.26 | 7.89 |
| kroBlOO | 9.28 | 13.84 | 19.35 | 11.56 | 9.46 | 8.20 | 5.91 | 16.30 | 15.14 | 13.16 | 8.51 |
| kroClOO | 10.97 | 14.35 | 25.79 | 8.59 | 10.54 | 8.51 | 13.58 | 15.96 | 14.90 | 12.02 | 10.83 |
| kroDlOO | 10.20 | 11.82 | 19.69 | 8.82 | 10.75 | 9.91 | 7.65 | 15.56 | 16.28 | 13.41 | 11.41 |
| kroElOO | 11.10 | 13.46 | 19.44 | 8.16 | 6.50 | 7.67 | 7.14 | 12.99 | 16.48 | 9.70 | 8.80 |
| rdlOO | 10.87 | 13.02 | 22.76 | 9.30 | 11.63 | 9.96 | 10.83 | 16.62 | 18.67 | 11.38 | 11.26 |
| eillOl | 10.75 | 13.26 | 17.71 | 10.11 | 10.43 | 9.89 | 9.67 | 15.33 | 13.90 | 12.21 | 8.46 |
| linl05 | 8.42 | 13.83 | 28.38 | 10.65 | 10.53 | 5.38 | 9.25 | 21.09 | 21.18 | 11.96 | 7.36 |
| prl07 | 9.04 | 10.78 | 16.80 | 6.34 | 7.91 | 10.13 | 8.21 | 11.16 | 12.28 | 7.62 | 10.54 |
| prl24 | 7.58 | 28.42 | 35.74 | 6.15 | 6.93 | 5.88 | 6.16 | 27.10 | 33.61 | 22.72 | 5.46 |
| bierl27 | 9.21 | 15.97 | 25.70 | 10.21 | 9.54 | 9.00 | 7.50 | 21.70 | 16.97 | 14.11 | 9.42 |
| chi 30 | 12.60 | 20.06 | 31.45 | 10.53 | 10.04 | 9.57 | 9.46 | 28.07 | 27.63 | 18.71 | 10.33 |
| prl36 | 11.38 | 19.71 | 31.92 | 11.61 | 13.93 | 10.49 | 10.89 | 28.28 | 25.51 | 20.61 | 13.34 |
| prl44 | 10.41 | 37.63 | 59.98 | 10.59 | 13.46 | 7.66 | 6.48 | 46.31 | 47.04 | 39.04 | 6.79 |
| chl50 | 15.28 | 31.45 | 46.54 | 11.05 | 9.52 | 12.43 | 14.14 | 40.11 | 38.71 | 29.76 | 10.60 |
| kroA150 | 13.15 | 35.93 | 45.25 | 10.96 | 11.91 | 10.99 | 11.28 | 38.08 | 36.72 | 29.16 | 9.88 |
| kroB150 | 12.26 | 28.51 | 46.10 | 10.23 | 11.30 | 12.07 | 11.69 | 39.01 | 41.27 | 23.71 | 10.77 |
| ul59 | 17.31 | 40.22 | 57.07 | 15.76 | 14.15 | 14.99 | 10.85 | 48.18 | 44.52 | 33.70 | 13.93 |
| Średnia | 10.27 | 17.70 | 26.47 | 9.25 | 10.04 | 8.83 | 8.82 | 21.30 | 21.27 | 15.97 | 9.20 |
Tablica 5.2: Testowane topologie.
Przesłanką dla stworzenia modeli hierarchicznych było założenie, że podpopulacje z wyższych poziomów przekazywałyby produkty ewolucji podpopulacjom z poziomów niższych, w których dokonywałaby się ich rywalizacja. Model h-8421 przypomina strukturą turniej w systemie pucharowym - do najniższego poziomu dochodzi typ osobnika, który przetrwał każdą z walk toczących się poziomach wyższych. Model jednopopulacyjny oraz modele podpopulacji niezależnych służą weryfikacji opinii, że model z migracjami jest od nich lepszy.
Wyniki znajdują się w tabeli 5.1. Założenia co do skuteczności modeli hierarchicznych okazały się błędne. Najgorsze wyniki otrzymano właśnie dla tych modeli (h-8421, h-931, h-441) oraz dla modeli niezależnych wysp (n-8, n-16). W modelach hierarchincznych przepływ migracji odbywa się tylko w jedną stronę. To sprawia, że zewnętrzne podpopulacje, nieotrzymując żadnych osobników, przeszukują mniejszą część przestrzeni rozwiązań i w konsekwencji zbiegają się do wielu lokalnych minimów. Za to modele o dużej liczbie połączeń zbiegają się do jednego rozwiązania suboptymalnego (Rys. 5.1).
Modele niezależnych wysp (n-8, n-16) nie różnią się niczym od wielokrotnego wykonywania algorytmu jednopopulacyjnego o mniej licznej populacji. To, że pojedyncza populacja (model n-1) radzi sobie lepiej, wynika z faktu, iż posiada większą ilość osobników, co pozwala jej w sumie przeglądać większą przestrzeń rozwiązań. Mała podpopulacja "grzęźnie" w lokalnym minimum, z którego nie jest się w stanie wydostać (Rys. 5.2a). Ta zależność staje się bardziej widoczna wraz ze wzrostem stopnia złożoności problemu.
Z drugiej strony modele z migracjami wykazują większą skuteczność dla złożonych problemów (ponad 100 miast) wtedy, gdy są bardziej rozdrobnione. Potwierdza to wnioski Whitley"a dotyczące granulacji populacji (por. 2.2.2). Topologie w kształcie okręgu osiągnęły najlepsze rezultaty, a zwyciężył model z 16 wyspami z wyspami o stopniu 2 (o-16-b). Można wnioskować, iż większe rozdrobnienie sprzyja eksploatacji nisz, a podwójne połączenia pomagają utrzymać jedność populacji.
Można także zauważyć wpływ liczby połączeń na czas konwergencji. Model hip-16 (hiper-sześcian) posiada aż 4 połączenia na wyspę. To sprawia, że szybciej się zbiega w minimum. Najszybszy czas konwergencji wystąpił w modelu n-1 składającego się z pojedycznej populacji.
Rysunek 5.1: Konwergencja na przykładzie różnych topologii. Każda linia na wykresie określa przystosowanie najlepszego osobnika w danej podpopulacji.
(a) Model podpopulacji niezależnych (n-16).
(b) Model hierarchiczny (h-8421).
komentarze
Copyright © 2008-2010 EPrace oraz autorzy prac.