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?