skanuj0009 (253)

Dla problemu komiwojażera (i innych jemu podobnych) wymyślono kilka rodzajów krzyżowań, które zawsze dają rozwiązania dopuszczalne, jak np:

• Krzyżowanie z częściowym odwzorowaniem (PMX)

Wybiera się losowo pewną podtrasę w obu rodzicach i przekazuje się ją do potomka (podtrasa pierwszego rodzica trafia do drugiego potomka i na odwrót):

Rodzic pierwszy: 1-2-3-4-5, rodzic drugi: 2-4-3-5-1, pozostawiana podtrasa: miasta od 2 do 4:

Pierwsze dziecko: x-4-3-5-x, drugie dziecko x-2-3-4-x.

Teraz uzupełnia się te trasy tak żeby nie powstał konflikt (dwa takie same miasta w trasie):

Pierwsze dziecko: l-4-3-5-x, drugie dziecko x-2-3-4-l (do dzieci nie można dodać miasta 5 (do pierwszego) ani 2 (do drugiego) ponieważ pojawiłyby się dwa takie same miasta w trasie).

Następnie tworzone są odwzorowania (na podstawie wymienianych podtras): 2<->4, 3<->3, 4<->5 i za ich pomocą uzupełniane są dzieci. W pierwszym brakuje piątki, więc na to miejsce wstawiamy miasto nr 2 (5<->4 i 4<->2), natomiast w drugim brakuje dwójki, więc wstawimy 5 (2<->4 i 4<->5).

Wygenerowane w ten sposób dzieci będą wyglądały następująco:

Pierwsze: 1-4-3-5-2, drugie 5-2-3-4-1.

• Krzyżowanie z porządkowaniem (OX)

Potomków tworzy się na podstawie podtras pobranych z rodziców (podtrasa pierwszego dziecka pobierana jest z drugiego rodzica natomiast podtrasa drugiego dziecka z pierwszego). Następnie uzupełnia się trasy miastami pobranymi z drugiego rodzica z zachowaniem porządku z pominięciem miast już wykorzystanych:

Rodzic pierwszy: 3-2-1-4-5, rodzic drugi: 2-4-3-5-1, pozostawiana podtrasa: miasta od 2 do 4:

Pierwsze dziecko: x-4-3-5-x, drugie dziecko x-2-l-4-x

Uuzupełniamy pierwsze dziecko: x-4-3-5-2 (ominęliśmy 5 i 3 ponieważ te miasta już występują) -> 1-4-3-5-2; i drugie dziecko: x-2-l-4-3 (ominęliśmy 1, 2 i 4 ponieważ te miasta już występują) -> 5-2-1-4-3.

W przypadku drugiej reprezentacji ('mniej naturalnej') taka zabawa jest niepotrzebna ponieważ standardowe operatory krzyżowania x-punlctowego zawsze dadzą prawidłowych potomków. Jeśli chodzi o mutację to sytuacja jest bardzo podobna: w zależności od rodzaju reprezentacji można zastosować standardowe operatory mutacji, bądź jakieś bardziej wyrafinowane.

W przypadku reprezentacji 'naturalnej' najprostszym rodzajem mutacji jest wymiana ze sobą dwóch miast w rozwiązaniu. Np:

1-2-3-4-5 -> wymiana miast 2 i 4 -> 1-4-3-2-5

Można również zmieniać kolejność przechodzenia miast. Np:

1-2-3-4-5 -> Zmiana kolejności w obrębie miast 1 i 4 -> 4-3-2-1-5

Można również przesunąć jakieś miasto (lub grupę miast) w ramach rozwiązania. Np:

1-2-3-4-5 -> Wstawienie miasta 1 pomiędzy 4 i 5 -> 2-3-4-1-5

Dla drugiej reprezentacji taka zabawa jest niepotrzebna, ponieważ w tym przypadku mutacja sprowadza się do zamiany wartości z pozycji i losową wartością z przedziału od 1 do n-i+1 (n - liczba wszystkich miast).

-6-

Wyszukiwarka

Podobne podstrony:
skanuj0051 (47) 11.8. Zrównoważony rozwój innych dziedzin gospodarczych 669 downictwie i działalnośc
skanuj0005 (335) 1. Problem komiwojażera - przykład rozwiązania za pomocą AG httv://vanda. be. univ.
skanuj0230 230 Cyfrowe oświetlenie i rendering W przypadku telewizji podobny problem ma miejsce, gdy
13194 skanuj0006 (253) POLITECHNIKA WROCŁAWSKA ZAKŁAD BUDOWNICTWA OGÓLNEGOWykresy ugięcia dla składo
Dla Hugona od św. Wiktora, podobnie jak dla innych „wiktorynów”, najważniejszy jest powrót do Boga.
186 187 186 Zadanie transportowe i problem komiwojażera •    dla klienta C: x + A 23
•    Kiedy jestem światłem dla innych? My podobnie jak te robaczki świętojańskie mamy
skanuj0009 56    2. Epistemologiczne problemy związane z prowadzeniem wywiadów tradyc
skanuj0011 (253) ■    „. ^.:v^^y>:r.-,v;^^^ ^    / - ŹVŻ?£ ’ f

więcej podobnych podstron