Liniowa Miara Różnorodności dla Problemów Permutacyjnych - LMRPP
Założenia
W podrozdziale 2.3.1 wykazano, iż istniejące miary różnorodności nie uwzględniają specyfiki zagadnienia TSP lub nie spełniają kryteriów wydajnościowych. Przy tworzeniu nowej miary przyjęto następujące założenia:
1. Miara powinna opierać się na genotypie osobnika.
2. Miara powinna być odpowiednia dla zagadnień permutacyjnych.
3. Złożoność obliczeniowa powinna być liniowo zależna od rozmiaru populacji O(N).
4. Miara powinna być znormalizowana, czyli mieścić się w przedziale [0,1]. Spełnienie tego założenia umożliwi porównywanie algorytmów o różnych parametrach.
Ponieważ miara może być stosowana zarówno do całej populacji, jak i podpopulacji, w kolejnym podrozdziale terminy te mogą być używane zamiennie.
Definicja
Dla każdego miasta wyznaczany jest iloraz liczby różnych połączeń z tego miasta występujących w danej populacji (lub podpopulacji) do liczby wszystkich możliwych połączeń. Miara LMRPP jest równa średniej z tych ilorazów. Oznaczenia:
MPOP Miara różnorodności populacji.
Mi Miara różnorodności połączeń z miasta i.
n Rozmiar problemu (np. liczba miast w zagadnieniu TSP).
N Liczebność populacji.
LPi Liczba różnych połączeń z miasta i.
MPOP jest średnią arytmetyczną z miar liczonych dla każdego miasta (Mi)
W obrębie jednego chromosomu każde miasto ma połączenie z dwoma innymi miastami. Niech różnorodność w populacji równa się zero wtedy, gdy wszystkie chromosomy są jednakowe. Wówczas w obrębie całej populacji dla każdego miasta i istnieją tylko dwa miasta, z którymi to miasto ma połączenie (LPi=2). Niech zaś różnorodność dla miasta i będzie maksymalna wtedy, gdy w obrębie populacji istnieje z niego połączenie do każdego innego miasta. Liczba tych miast wynosi n - 1. Zatem LPi ∈ < 2, n - 1>, więc zakres zmienności LP liczy n - 3 stany. Stąd znormalizowana miara dla pojedynczego miasta wynosi
Należy pamiętać, że gdy spełniona jest nierówność
2N < n - 1 (3.3)
wtedy miara nigdy nie może równać się 1, ponieważ nie ma wystarczającej ilości osobników aby pokryć wszystkie możliwe połączenia. Brano pod uwagę wersję, w której miara MPOP = 1 wtedy, gdy LP = min(n - 1,2N), co odpowiada warunkowi, dla którego miasto posiada maksymalną możliwą liczbę połączeń na jaką pozwala liczebność populacji. Jednak z uwagi na klarowność uznano tę wersję za gorszą. Jednym z argumentów jest fakt, że podczas pracy z tą miarą, zmieniając liczebność oraz rozmiar zagadnienia, niedostateczny rozmiar populacji mogłoby umknąć uwadze. Z faktu, że miara równa się 1 nie musiałby wynikać fakt o dużym "zapasie" genetycznym populacji. Pozostano więc przy pierwotnej wersji miary.
Zaproponowana miara spełnia kryteria wymienione w podsekcji 3.1.1:
1. LMRPP jest miarą genotypową i ściśle określa "bogactwo genetyczne" zbioru rozwiązań.
2. Miara może być stosowana do zagadnień permutacyjnych, ponieważ nie ma znaczenia, na której pozycji znajduje się miasto w danym chromosomie.
3. Podczas jednego cyklu obliczania miary każdy chromosom jest przeglądany tylko raz, więc złożoność zależy liniowo od rozmiaru populacji O(N).
4. Miara jest unormowana - zmienia sie w przedziale [0,1].
komentarze
Copyright © 2008-2010 EPrace oraz autorzy prac.