www.eprace.edu.pl » algorytmy-genetyczne » Wstęp » Zagadnienie Komiwojażera - Travelling Salesman Problem

Zagadnienie Komiwojażera - Travelling Salesman Problem

Jako zagadnienie testowe wybrano Symetryczne Zagadnienie Komiwojażera. Jest to najbardziej popularne zadanie optymalizacji dyskretnej. Należy do klasy problemów NP-trudnych, w związku z tym niemożliwy jest przegląd zupełny przestrzeni rozwiązań. Problem TSP jest często wybierany do weryfikacji nowych pomysłów w dziedzinie Algorytmów Genetycznych, dlatego badania na ten temat są dobrze udokumentowane. Zostało także dla niego opracowanych wiele efektywnych operatorów genetycznych.

Zagadnienie Komiwojażera polega na znalezieniu cyklu Hamiltona o najmniejszej sumie wag krawędzi. Mówiąc obrazowo, należy dobrać najkrótszą ścieżkę pomiędzy miastami, przy czym każde miasto powinno zostać odwiedzone raz oraz miasto początkowe powinno być zarazem miastem końcowym cyklu.

Model matematyczny

Dane są:

  •   Zbiór wierzchołków W = 1,..., n

  •   Macierz odległości n x n-wymiarowa A = [ai,k]

    Należy znaleźć permutację π = (π(1),..., π(n)) elementów zbioru W, która minimalizuje funkcję celu Φ(π):



    Istnieją ścisłe metody rozwiązania problemu TSP. Należą do nich programowanie dynamiczne, metoda podziału i ograniczeń oraz metoda płaszczyzn tnących. Dynamiczny postęp, jaki się dokonał w dziedzinie zagadnienia komiwojażera, najlepiej obrazuje następująca tabela (por. [2]). Zawarto w niej rok i rozmiar zagadnienia, dla którego wyznaczono rozwiązanie optymalne:

    Tablica 1.1: Największe rozwiązane metodami ścisłymi instancje problemu TSP.

    Liczba miast Rok Odkryte przez
    2,392 1987 Manfred Padberg
    3,038 1992 William Cook Group
    4,461 1993 William Cook Group
    7,397 1994 William Cook Group
    13,509 1998 William Cook Group
    15,113 2001 William Cook Group
    24,978 2004 William Cook Group
    33,810 2005 William Cook Group
    85,900 2006 William Cook Group

    W skład William Cook Group wchodzą William Cook, Vaśek Cłwatal, David Applegate oraz Robert Bixby. Utworzyli oni bardzo wydajny program o nazwie Concorde, który potrafi wyznaczać rozwiązania optymalne, jak również dolne ograniczenia.

    Ze względu na ogromną przestrzeń rozwiązań w zagadnieniu TSP oraz specyfikę zagadnienia, klasyczne metody genetyczne zostały wyparte przez specjalizowane operatory pseudogenetyczne. Obecnie najbardziej skutecznym programem rozwiązującym TSP metodami przybliżonymi jest oparty heurystyce Lin"a-Kernighan program LKH rozwijany przez Kelda Helsgaun"a. Do niego należy rekord najkrótszej trasy dla instancji o nazwie World-TSP, która obejmuje 1,904,711 miast. Rozwiązanie z 12 maja 2009 jest o 0.0487% większe od dolnego ograniczenia wyznaczonego przez Concorde [13]. Dla problemu składającego się z 2,392 miast LKH uzyskuje rozwiązanie optymalne w czasie 1 sekundy na standardowym komputerze osobistym.

    Celem pracy jest przeanalizowanie różnych aspektów modelu wyspowego, a nie uzyskanie algorytmu lepszego od najskuteczniejszych istniejących programów. Problem TSP jest tylko jednym z bardzo licznego zbioru problemów, które można rozwiązywać za pomocą wielopopulacyjnych algorytmów genetycznych. Dlatego, aby uzyskane wnioski można było stosować także do innych problemów, użyto klasycznych metod genetycznych (krzyżowanie, mutacja).



    komentarze

    Gdzie jest wyjaśnienie co to jest cykl Hamiltona, gdzie jest napisane co to są problemy NP-trudne. Winno być wytłumaczone przed użyciem w tekście. Kto tę pracę sprawdzał?

    skomentowano: 2009-07-21 22:15:53 przez: recenzent

    Cel pracy nie pokrywa się z podanym w poprzednim podrozdziale. Co nowego wnosi praca, bo badanie istniejących i poznanych algorytmów nie jest odkrywcze

    skomentowano: 2009-07-21 22:25:05 przez: recenzent

    To nie jest praca doktorska, ona nie musi być odkrywcza.

    skomentowano: 2009-11-25 14:52:09 przez: znawca

    skomentowano: 2016-06-12 11:28:29 przez: Aaaa

  • Copyright © 2008-2010 EPrace oraz autorzy prac.