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ą:
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).
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.