Komiwojażer algorytm ewolucyjny-genetyczny

komiwojażer:
mam n punktów muszę znaleźć najkrótsza trasę.

algorytm:
losuje n przypadkowych dróg (populacja początkowa)
obliczam ich długość (przystosowanie, w tym wypadku czym mniejsze tym lepsze)
zapamiętuję najlepsza
wybieram populacje nową wygenerowaną z pierwszej. O to chciałbym zapytać.

Otóż najlepszym, znanym mi, sposobem wyboru nowej populacji jest użycie dystrybuanty
(obliczam sumę dróg każda obliczoną drogę dzielę przez obliczona sumę)
Otrzymuje prawdopodobieństwo wylosowania danej drogi. "P"

Tworzę dystrybuantę
I element o wartości P1
II o wartości P1+P2
III P1+P2+P3
itd

losuje doubla z zakresu (0,1) wybierający określoną drogę, np wartość dystrybuanty elementu 5 jest = 0,3 a 6 = 0,35
po wylosowaniu liczby 0,33 wybieram element 6.

W takim przypadku większą szansę na wybraną mają drogi o wyższym prawdopodobieństwie (dłuższa trasa), czyli algorytm elegancki ale do wyznaczania najdłuższej trasy. Nie umiem poradzić sobie ze znalezieniem sposobu na przemianowanie wag moich dróg, tak aby krótsza droga miała większe prawdopodobieństwo.

Czy macie jakiś pomysł na przerobienie tego?

A w ogóle musisz to tak dziwnie robić? Tzn w sen sposób reprezentowac populację i w ogóle? Bo mnie to wygląda trochę jak totalny random ;] Chyba że przez "losuje n przykładowych dróg" rozumiesz "n przykładowych cykli hamiltona" w grafie.
Jeśli chodzi o ten wybór dróg to przeciez mógłbyś najdłuższą z dróg przez uzyskaną w danym przypadku i miałbyś wtedy relację najkrótsza droga = najwyższy wynik (bo byłby to stosunek najgorszej drogi w danym przypadku do aktualnej drogi) a potem mozesz to znormalizować do (0,1)

a = (max-długość - długość) / (max-długość - min-długość)
a = 0 dla maks długości
a = 1 dla minimalnej długości

b = 1 / (2 - a)
b = 1/2 dla maks. długości
b = 1 dla minimalnej długości

użyj b jako częściowego prawdopodobieństwa.