Problem komiwojażera

Przykłady zastosowania algorytmów genetycznych on-line

Travelling Salesman Problem Genetic Algorithm by Michael LaLena
[on-line, off-line, .NET 2.0, kod źródłowy]

Program znajdujący rozwiązanie problemu komiwojażera, dla zadanego rozkładu miast. Miasta można wczytać z pliku (tylko wersja off-line) lub rozmieścić ręcznie.

Parametry algorytmu genetycznego w programie

  • Population Size – Rozmiar populacji – liczba losowych tras wygenerowanych na początku działania algorytmu. Wraz ze zwiększaniem liczebności populacji wydłuża się czas znalezienia rozwiązania. Zmniejszanie populacji zwiększa szanse na powtarzalność rozwiązań w kolejnych generacjach i może uniemożliwić znalezienie optymalnego rozwiązania.
  • Group Size – Rozmiar grupy – liczba tras wybieranych losowo z każdego pokolenia. Dwie najlepsze (najkrótsze) zostają rodzicami. Dwie najgorsze zamieniane są przez dzieci. Większe wartości pozwalają wybrać lepszych rodziców dla pokolenia, ale mogą spowodować, że porównywalnie dobre nigdy nie zostaną rodzicami (problem turnieju, rozwiązywany rozstawianiem dobrych zawodników). Większe wartości przyspieszają też działanie algorytmu, ale mogą spowodować pogorszenie jakości rozwiązania.
  • Mutation % – Prawdopodobieństwo mutacji – procent zmian w każdym dziecku wykonywany po krzyżowaniu. Mutacja polega na losowej zamianie miejscami dróg prowadzących do dwóch miast.
  • # Nearby Cities – Najbliższe miasta – parametr populacji startowej. Algorytm preferuje łączenie miast, które są blisko siebie. Parametr wskazuje, jak duża liczba miast jest uznawana za bliskie. Liczba musi być mniejsza od liczby miast i nie mniejsza niż trzy (zachowanie możliwości wyboru).
  • Nearby City Odds % – Kurs na bliskie miasto – prawdopodobieństwo wybrania miasta uważanego za bliskie (zgodnie z wypranymi wyższym parametrem) zamiast losowego. Zero oznacza wybór całkowicie losowy.
  • Maximum Generations – Liczba pokoleń – warunek zatrzymania algorytmu – tu, jeden z możliwych do zastosowania, niezależny od jakości osiągniętego rozwiązania, inne, to np. trend zmiany obserwowanego parametru.

Pozostałe opcje programu

(dostępne wyłącznie w wersji off-line)

  • Random Seed – Ziarno losowe – możliwość ustalenia ziarna startowego dla algorytmu pseudolosowości, w celu zapewnienia powtarzalności parametrów początkowych.
  • City List – Lista miast – możliwość wczytania listy miast z pliku xml. Po wskazaniu pliku należy wybrać Open City List.

Zasoby: