Badanie 2. Częstość migracji.
Do badania częstości migracji wybrano model o-16-b, który uzyskał najlepszy wynik w badaniu pierwszym. Aby wskazać wpływ częstości migracji, przyjęto stałą liczbę migrujących osobników w ilości 64 osobników na generację. Jeśli migracje występują k razy rzadziej, odpowiednio k razy wzrasta jej liczebność.
Tablica 5.3: Wpływ częstości migracji na względną różnicę jakości - D.
| Instancje | 1 | 2 | 3 | 5 | 10 | 15 | 25 |
| eil51 | 6.38 | 5.59 | 7.32 | 5.45 | 5.96 | 4.41 | 3.19 |
| berlin52 | 4.84 | 6.60 | 8.70 | 6.33 | 6.89 | 6.34 | 7.18 |
| st70 | 8.36 | 9.21 | 6.49 | 8.77 | 6.22 | 5.69 | 5.72 |
| eil76 | 7.84 | 7.47 | 8.40 | 8.62 | 8.29 | 8.25 | 6.39 |
| pr76 | 6.19 | 3.65 | 6.14 | 6.25 | 5.97 | 3.82 | 2.48 |
| rat99 | 8.55 | 11.76 | 11.81 | 10.67 | 10.64 | 9.84 | 9.93 |
| kroAlOO | 8.79 | 10.48 | 9.51 | 10.73 | 5.92 | 8.10 | 8.18 |
| kroBlOO | 5.91 | 6.71 | 8.63 | 7.31 | 6.58 | 7.88 | 5.74 |
| kroClOO | 13.58 | 10.42 | 7.10 | 11.04 | 8.29 | 10.05 | 5.65 |
| kroDlOO | 7.65 | 10.83 | 8.28 | 7.90 | 10.32 | 7.36 | 8.57 |
| kroElOO | 7.14 | 8.05 | 8.70 | 10.72 | 9.15 | 7.94 | 8.49 |
| rdlOO | 10.83 | 12.43 | 10.21 | 11.33 | 10.00 | 13.61 | 8.05 |
| eillOl | 9.67 | 9.44 | 10.11 | 8.59 | 9.13 | 8.81 | 9.48 |
| lin105 | 9.25 | 8.15 | 9.81 | 8.14 | 6.94 | 7.57 | 6.98 |
| prl07 | 8.21 | 5.89 | 6.81 | 4.77 | 8.36 | 7.01 | 7.08 |
| prl24 | 6.16 | 4.99 | 6.77 | 8.43 | 5.05 | 6.68 | 6.62 |
| bierl27 | 7.50 | 10.25 | 12.01 | 8.48 | 7.33 | 7.71 | 8.99 |
| chi 30 | 9.46 | 9.80 | 10.38 | 10.29 | 10.53 | 10.79 | 11.41 |
| prl36 | 10.89 | 12.27 | 8.83 | 10.94 | 9.67 | 8.57 | 10.16 |
| prl44 | 6.48 | 6.45 | 7.75 | 7.71 | 5.46 | 12.28 | 14.80 |
| chl50 | 14.14 | 13.54 | 13.25 | 13.86 | 13.35 | 13.25 | 17.80 |
| kroA150 | 11.28 | 9.74 | 12.09 | 8.92 | 11.20 | 12.50 | 15.52 |
| kroB150 | 11.69 | 11.22 | 9.70 | 11.19 | 11.39 | 11.53 | 16.45 |
| ul59 | 10.85 | 13.01 | 19.04 | 17.64 | 15.51 | 17.98 | 23.98 |
| Średnia | 8.82 | 9.08 | 9.49 | 9.34 | 8.67 | 9.08 | 9.54 |
Najlepsze wyniki uzyskano dla migracji o okresie 10 generacji. Jednak różnice w obrębie badanych modeli są niewielkie i trudno wyznaczyć trend, który definitywnie określiłby optymalną częstość. Wyniki te pokrywają się więc z wnioskami zawartymi w [36], że, dla stałego strumienia migrantów, częstość migracji nie wpływa znacząco na najlepsze uzyskane rozwiązanie.
Badania wskazują jednak na to, iż częstość ma znaczący wpływ na szybkość konwergencji. Krótkie odstępy między migracjami skracają całkowity czas obliczeń (Rys. 5.3). Wiąże się to prawdopodobnie z faktem, iż w stosunku do częstych migracji, rzadsze migracje:
1. Są liczebniejsze.
2. Następują po dłuższej konwergencji, więc zawierają jednostki bardziej zróżnicowane w stosunku do jednostek podpopulacji docelowej, niż gdyby migracje występowały częściej.
Te dwa czynniki sprawiają, iż populacja jest silniej wytrącana z osiągniętego poziomu równowagi. Na wykresach różnorodności widoczne "kolce" są tego dowodem (Rys. 5.2). Dlatego czas zbiegania się do minimum jest dłuższy.
Rysunek 5.2: Wpływ częstości migracji na przebieg średniej różnorodności na przykładzie instancji pr76.
(a) Migracje co jedną generację.
(b) Migracje co dziesięć generacji.
(c) Migracje co dwadzieścia pięć generacji.
Ponadto należy wziąć pod uwagę relatywny nakład obliczeniowy wynikający z migracji. Jeśli stanowi on znaczącą część obliczeń, może bardziej opłacać się ustawić większy interwał.
Rysunek 5.3: Zależność sumarycznego czasu obliczeń od częstości migracji
komentarze
Copyright © 2008-2010 EPrace oraz autorzy prac.