Algorytm podzialu - jak zdefiniować osobnika

0

Cześć,

Mam taki problem do rozwiażania algorytemem genetycznym. Najktórej mówiąc to problem komiwojażera z tą różnicą że komiwojażer-ów jest trzech. Czyli mamy X miast, drogi do pokonania pomiędzy dwoma każdymi miastatmi są znane. I jak zdefiniować osobnika aby rozwiązać ten problem ?

Jak na razie wymyśliłem takie rozwiązanie żę jeden osobnik to trzy wektory gdzie każdy wektor będzie lista miast jakie ma pokonać podróżnik. Problem w tym jest taki że krzyżwoanie i mutacja mogą być dość pogmatfane żeby nie duplikwoać miast.

Czy ktos ma inny pomysł na podejscie do zdefiniwoania osobnika ?

0

Osobnik musi jednoznacznie określać trasę, tutaj za wiele nie zdziałasz. Najprościej zrobić tutaj listę wierzchołków które odwiedzasz w danej kolejności.
Mutacja to losowa zamiana miejscami dwóch wierzchołków.
Krzyżowanie jest bardziej problematyczne, bo musisz zachować spójność rozwiązania. Ja bym wybrał podzbiór wierzchołków z jednego osobnika i w drugim osobniku zmienił kolejność tych wierzchołków tak żeby były spójne i takie coś uznał za nowego osobnika.

0

W tym waku: Algorytm podzialu zbioru na podzbiory znalazłem taka propozycje ale nie jak spróbować ją wykorzystać:

"
...
Możesz zastosować algorytm genetyczny o strukturze chromosomu takiej:
{nr-węzła}|{nr-podzbioru}

(powtórzone k razy dla wszystkich węzłów)
...
"

Może odnośnei tego jakiś pomysł ?

1 użytkowników online, w tym zalogowanych: 0, gości: 1