Piszę algorytm genetyczny mający za zadanie podzielić graf pomiędzy m (znane - parametr alg.) komiwojażerów w taki sposób zeby koszt przebycia każdego z wydzielonych fragmentów był jak najmniejszy. Ale nie wiem jaka stworzyć funkcje oceny osobników.
Macie jakieś pomysły?
koszt przebycia każdego z wydzielonych fragmentów był jak najmniejszy
Chociaż Ty potrzebujesz algorytmu dla wielu komiwojażerów, to może przykładowy kod algorytmu genetycznego dla problemu komiwojażera Ci pomoże ;) - http://pyevolve.sourceforge.net/examples.html#example-12-the-travelling-salesman-problem-tsp
Tak Shalom ale codzilo mi bardziej jak taką funkcje skonstruować czy potraktować to jak zadanie klasyfikacji i liczyc odleglosc od srodka klastra, czy może jakoś inaczej.
Napisalem co prawda najprostszą wersje czyli policz trasę (po kolei) przez wszystkie punkty dla każdej grupy i zsumuj wynik, ale rozwiazanie w postaci
Salesperson_1: n-2 miast;
Salesperson_2: 1 miasto;
Salesperson_3: 1 miasto
wydaje mi sie dziwne(chyba i nie do konca prawidlowe :( )
Ponawiam pytanie jak skonstruować taką funkcję? Na czym sie oprzeć?
Ale szukasz rozwiązania gdzie suma przebycia wszystkich wydzielonych części była jak najmniejsza czy ogólnie żeby przebycie poszczególnych fragmentów było najkrótsze?
Jeżeli to drugie, to musiałbyś sprecyzować co to dokładnie znaczy, bo nie wiadomo jaka może być różnica między nimi, czy preferowane jest więcej mniejszych, czy więcej równych.
To zadanie wyglądałoby dużo lepiej jeżeli byłoby trzeba policzyć wspomnianą na początku mojego postu sumę.
To dokladnie w ten sposób działa licze koszt dla każdej cześci a nastepnie sumuje te koszty. I daje mi rozwiazania podobne do tych opisanych wczesniej. Na podstawie grafu wnioskuje ze te rozwiązania nie lezaly nawet kolo optymalnego, bo to jedno miasto jest polozone dość "daleko" od punktu statowego.
Jeżeli jest dość daleko to może i dobrze, bo możliwe, że nie opłaca się do(z) niego iść z(do) reszty grafu.
Twoja funkcja wydaje się ok, bo właśnie o to chodzi - zsumowanie kosztów przejścia części grafu przez każdego z komiwojażerów.
Druga sprawa to odpowiednie krzyżowanie i mutacje, które doprowadzą do jak najlepszego wyniku i tutaj może być problem (o ile wyniki są dalekie od optymalnych).