Pytanie szczegółowe przy stosowaniu algorytmu genetycznego do podróżującego sprzedawcy

Question

Przeczytałem różne rzeczy na ten temat i zrozumiałem zasadę i koncepcje, jednak żaden z artykułów nie wspomina o szczegółach dotyczących sposobu obliczania sprawności chromosomu (który reprezentuje trasę) z udziałem sąsiednich miast (w chromosomie), które nie są połączone bezpośrednio krawędzią (na wykresie).

Na przykład, biorąc pod uwagę chromosom 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, w którym każdy gen reprezentuje indeks miasta na wykresie/mapie, w jaki sposób obliczamy jego sprawność (np. całkowita suma pokonanych odległości), jeśli, powiedzmy, nie ma bezpośredniej krawędzi/połączenia między miastami 2 i 8. Czy stosujemy jakiś chciwy algorytm do wyznaczania trasy między 2 a 8, i dodajemy odległość tej trasy do suma?

Ten problem wydaje się dość powszechny podczas stosowania GA do TSP. Każdy, kto już to zrobił, podziel się swoim doświadczeniem. Dzięki.

Answer 1

Jeśli na wykresie nie ma powiązania między 2 a 8, to każdy chromosom z 2 | 8 lub 8 | 2 jest nieprawidłowy dla klasycznego problemu z handlowcem podróżującym. Jeśli znajdziesz inną trasę między 2 a 8, prawdopodobnie naruszysz wymaganie "odwiedź każdą lokalizację raz".

Jednym z naprawdę podejrzanych, ale pragmatycznych rozwiązań jest dodanie krawędzi pomiędzy tymi węzłami o niesamowicie dużych odległościach, a nawet + INF, jeśli twój język je obsługuje. W ten sposób Twoja standardowa funkcja minimalizacji funkcji fitness w naturalny sposób przycina je.

Myślę, że oryginalne sformułowanie problemu zawiera krawędzie między wszystkimi węzłami, więc nie jest to problem.

Answer 2

Jest to dokładny rodzaj problemu, wyspecjalizowane metody Crossover i mutation zostały zastosowane do rozwiązań opartych na GA do problemów TSP. Zobacz to question.

Answer 3

jeśli chromoson nie jest prawidłowym rozwiązaniem, wówczas całkowicie nie nadaje się do rozwiązania problemu. W zależności od tego, w jaki sposób zamówić fitness. tzn. jeśli niższa liczba oznacza większą sprawność (prawdopodobnie dobry pomysł, gdy kondycja reprezentuje całkowity koszt), to przydzielisz mu maksymalną wartość i przerwiesz dalsze obliczenia sprawności na tym chromosonie, gdy dojdziesz do sekwencji genów, która jest nieważna.

(lub vice versa, przypisać mu sprawność wynosiła zero, jeśli wyższa siłownia oznacza chromosone jest bardziej zdolny do pracy)

jednak jak inni zwrócili uwagę mogłoby być lepiej, aby upewnić się, że nieprawidłowe chromosones nie występują . Jeśli jednak jest to proces nadmiernie skomplikowany, to dopuszczenie do nich i zapewnienie, że złamane chromosony nie będą w stanie przetrwać kolejnych pokoleń, może stanowić akceptowalne podejście.