Badanie 4. Metoda wyboru osobników migrujących.
Najlepszy model uzyskany w badaniu 3 przetestowano z następującymi metodami wyboru migrantów:
Wybór losowy (ang. Random Selection) Wybór dowolnego osobnika zachodzi z jednakowym
prawdopodobieństwem.
Selekcja turniejowa (ang. Tournament Selection) Selekcja turniejowa o rozmiarze r odbywa się
poprzez losowych wybranie r osobników i wybór najlepszego spośród nich.
Selekcja proporcjonalna (ang. Fitness Proportionate Selection) Również znana pod nazwą
"Selekcja ruletkowa". Wybór danego osobnika odbywa się z prawdopodobieństwem równym ilorazowi jego wartości przystosowania oraz sumy przystosowania wszystkich osobników.
Tablica 5.5: Wpływ selekcji na względną różnicę jakości.
| Instancja | Wybór losowy | Selekcja turniejowa (rozm. 2) | Selekcja turniejowa (rozm. 4) | Selekcja turniejowa (rozm. 7) | Selekcja proporcjonalna | Wybór najlepszego |
| eil51 | 4.23 | 4.84 | 4.23 | 3.57 | 4.55 | 5.82 |
| berlin52 | 4.95 | 7.30 | 5.18 | 6.57 | 7.08 | 3.84 |
| st70 | 4.06 | 6.28 | 8.12 | 4.09 | 5.51 | 7.17 |
| eil76 | 6.80 | 7.32 | 6.43 | 8.03 | 8.07 | 7.96 |
| pr76 | 3.59 | 9.38 | 4.85 | 5.59 | 4.75 | 5.02 |
| rat99 | 8.84 | 8.51 | 11.30 | 9.12 | 10.97 | 8.70 |
| kroA100 | 8.90 | 9.46 | 9.15 | 10.13 | 5.14 | 9.43 |
| kroB100 | 6.01 | 6.86 | 6.17 | 8.13 | 9.87 | 8.50 |
| kroC100 | 8.80 | 8.61 | 8.41 | 12.18 | 7.32 | 11.68 |
| kroD100 | 7.89 | 10.45 | 8.53 | 10.16 | 7.30 | 7.86 |
| kroE100 | 5.67 | 7.23 | 8.19 | 6.98 | 10.32 | 9.21 |
| rd100 | 8.78 | 10.14 | 8.22 | 10.41 | 9.43 | 9.63 |
| eil101 | 8.68 | 10.81 | 9.70 | 10.02 | 9.89 | 8.74 |
| lin105 | 8.78 | 7.43 | 10.84 | 5.52 | 8.32 | 8.18 |
| pr107 | 6.96 | 8.93 | 9.60 | 6.69 | 9.62 | 6.18 |
| pr124 | 5.48 | 6.02 | 4.85 | 8.11 | 6.18 | 6.87 |
| bier127 | 10.52 | 8.22 | 9.85 | 8.97 | 7.32 | 8.26 |
| ch130 | 7.91 | 9.47 | 9.03 | 8.06 | 8.74 | 9.63 |
| pr136 | 9.94 | 10.56 | 9.43 | 11.17 | 10.08 | 10.07 |
| pr144 | 5.09 | 7.88 | 8.19 | 6.83 | 6.88 | 7.17 |
| ch150 | 12.27 | 12.54 | 12.41 | 13.04 | 11.36 | 11.70 |
| kroA150 | 9.55 | 12.25 | 11.98 | 12.03 | 11.98 | 10.32 |
| kroB150 | 10.46 | 10.92 | 9.07 | 10.02 | 11.45 | 10.45 |
| u159 | 15.51 | 14.28 | 16.13 | 15.19 | 13.36 | 14.98 |
| Średnia | 7.90 | 8.99 | 8.74 | 8.78 | 8.56 | 8.64 |
Zdecydowanie najlepiej wypadła selekcja losowa. Przewaga selekcji losowej widoczna jest szczególnie w prostszych przypadkach. Ponieważ wybór losowy nie wywiera presji selekcyjnej, średni czas konwergencji jest dłuższy niż w przypadku innych metod. Algorytm przeszukuje zatem większą część przestrzeni rozwiązań.
Rysunek 5.5: Zależność sumarycznego czasu obliczeń od rodzaju selekcji migrantów
W niniejszym algorytmie głównym źródłem naporu selekcyjnego jest jednak selekcja odbywająca się między generacjami, po krzyżowaniu. Mając zatem do dyspozycji parametry obu selekcji, można sterować naporem na wiele sposobów.
komentarze
Copyright © 2008-2010 EPrace oraz autorzy prac.