W Y Ż S Z A              S Z K O Ł A              I N F O R M A T Y K I

W Y D Z I A Ł              I N F O R M A T Y K I

P R A C A              D Y P L O M O W A

M A G I S T E R S K A

Tytuł pracy  PROBLEM KOMIWOJAŻERA

2

Jakub Łuczak

Informatyka

12632

Prof. Dr hab. Volodymyr Hrytsyk

Imię i Nazwisko: Studia:

Specjalność:

Nr albumu:

Promotor:

Rok akademicki 2005/2006

Wstęp              3

Rys historyczny [2]              4

Opis problemu [4]              6

Przykłady zastosowań              9

Metody rozwiązania problemu              10

Heurystyka              10

Algorytm dołączania najdalszego miasta od cyklu              10

Najbliższe miasto              11

Metoda podziału i ograniczeń              11

Min-area TSP (problem komiwojażera z minimalizacją obszaru)              19

TSP with neighborhoods (problem komiwojażera ze zdefiniowanymi sąsiedztwami)              19

Wykorzystanie algorytmów genetycznych[1]              19

Rozłóżmy algorytmy genetyczne na elementy pierwsze...[1]              21

Losowanie populacji              24

Ocena osobników              25

Selekcja              26

Krzyżowanie              28

Mutacja              29

Powrót do oceny osobników              30

Porównanie kilku metod – testy [5]              30

Część praktyczna              35

Strona WWW              35

Wymagania sprzętowe              36

Możliwości i obsługa              36

Dlaczego wybrałem algorytm genetyczny?              41

Algorytm              42

Populacja              43

Funkcja oceny (kosztu)              44

Selekcja              45

Krzyżowanie              47

Mutacja              50

Opis ważniejszych metod w applecie              51

Podsumowanie              55

Wykaz załączników              57

Spis ilustracji              57

Bibliografia              57

Wstęp

              Praca dotyczy problemu komiwojażera w skrócie TSP (travelling salesman problem). Niektórzy, którym mówiłem o problemie mówili z uśmiechem, „co za problem połączyć kreską kilka punktów? ” – Mam nadzieję, że po przeczytaniu mojej pracy już będą wiedzieli. W pracy umieściłem krótką historię, opis, kilka różnych metod poszukiwań i przykładów. Jak każda praca magisterska ta też zawiera część praktyczną. Program napisany w Javie i obecny cały czas w Internecie, czyli najbardziej rozpowszechnionym, ale niestety i najwolniejszym środowisku programistycznym. Proponuję samemu sprawdzić jak to działa. Adres strony i instrukcja obsługi znajduje się w następnych rozdziałach. Dla tych, którzy zaczną krytykować pracę lub sposób pisania w Javie powiem tylko, że jest to mój pierwszy program i na pewno nie jest on typu „Hello Word”. Do ułatwienia pisania użyłem Borland JBuilder 9 Enterprise Trial. Podobnie jak w poprzednich moich pracach w tej też pokazałem najciekawsze rozwiązania programistyczne niektórych problemów. Praca powstała w oparciu o literaturę i pisma fachowe, a przede wszystkim źródła zawarte w sieci (witryny internetowe). Kończy się wnioskami, jakie nasunęły mi się w związku z opracowaniem zebranych materiałów.

Rys historyczny [2]

Zadanie komiwojażera jest koncepcyjnie bardzo proste: komiwojażer musi odwiedzić każde miasto na swoim terytorium dokładnie raz i wrócić do punktu startowego. Przestrzeń rozwiązań w zadaniu komiwojażera jest zbiorem permutacji n miast. Każda permutacja n miast jest rozwiązaniem, (które jest pełnym objazdem n miast). Optymalnym rozwiązaniem jest permutacja, dla której koszt objazdu jest najmniejszy. Rozmiar przestrzeni rozwiązań wynosi n.

Zadanie komiwojażera sformułowano dosyć dawno. Było ono zapisane już, w 1759 r. przez Eulera, (chociaż nie pod tą nazwą), który zajmował się rozwiązywaniem zadania ruchu konika po szachownicy. Prawidłowe rozwiązanie wymagało, aby konik odwiedził każde z 64 pól na szachownicy dokładnie raz w czasie całego ruchu.

Termin „komiwojażer” był po raz pierwszy użyty w 1932 r. w książce niemieckiej Komiwojażer, jak i co powinien on robić, aby wykonać zlecenia i mieć powodzenie w interesach, napisanej przez byłego komiwojażera. Chociaż nie było to głównym tematem książki, zadanie komiwojażera i szeregowanie są omawiane w ostatnim jej rozdziale.

Zadanie komiwojażera w obecnym sformułowaniu wprowadziła RAND Corporation w 1948 r. Jej reputacja pomogła w tym, że stało się ono zadaniem znanym i popularnym. Zadanie komiwojażera także stało się popularne w tym czasie z powodu opracowania nowej metody programowania liniowego i prób rozwiązywania zadań kombinatorycznych.

Ponadto 5 godzin liczenia na komputerze za wiele milionów dolarów, aby znaleźć optymalne rozwiązanie, może nie być najlepsze pod względem kosztu, jeżeli można uzyskać gorsze od niego o kilka procent w sekundy na PC. Z tego powodu wynika potrzeba metod heurystycznych.

W ciągu ostatnich kilku dziesięcioleci powstało kilka algorytmów wyznaczania rozwiązania bliskiego optymalnemu: algorytm najbliższego sąsiada, algorytm zachłanny, algorytm najbliższego wstawiania, najdalszego wstawiania, podwajanego najkrótszego drzewa rozpinającego, oddzielania powłoki wypukłej, krzywej wypełniającej przestrzeń, algorytmy Karpa, Litkego, Christofidesa itp. (w niektórych z tych algorytmów zakłada się, że miasta odpowiadają punktom na płaszczyźnie przy pewnej standardowej metryce). Dana grupa algorytmów (2-opt, 3-opt, Lina-Kernighana) szuka lokalnych minimów - poprawy trasy przez lokalne przestawienia.

Zadanie komiwojażera stało się także celem do rozwiązania w dziedzinie algorytmów genetycznych. Mają one na celu wyszukanie rozwiązania bliskiego optymalnemu za pomocą populacji potencjalnych rozwiązań, które, podlegają pewnym jednoargumentowym i binarnym przekształceniom („mutacjom” i „krzyżowaniom”) za pomocą schematów selekcji biorących pod uwagę dopasowanie osobników.

Kolejne zarejestrowane rekordy [3]:

Opis problemu [4]

Problem komiwojażera jest ściśle związany z cyklem Hamiltona w grafie, tzn. takim cyklem, który zawiera każdy z wierzchołków danego grafu dokładnie 1 raz. Problem komiwojażera przedstawia się następująco: komiwojażer musi odwiedzić n miast w taki sposób, by wrócił do miasta, z którego wyruszył pokonując jak najmniejszą drogę, musi wyznaczyć sobie taką trasę między miastami, aby całkowity koszt jego podróży był najmniejszy. Problem ten można przestawić za pomocą grafu pełnego, tzn. grafu o stuprocentowym nasyceniu krawędziowym, co oznacza, że każda para wierzchołków jest połączona krawędzią.

Rysunek 1 Graf dla 5 polskich miast

Miasta, które musi odwiedzić komiwojażer są wierzchołkami, a drogi łączące te miasta to krawędzie z wagami, symbolizującymi koszt podróży daną drogą. Należy wyznaczyć cykl Hamiltona o najmniejszej sumie wag krawędzi należących do tego cyklu. Klasyczny sposób rozwiązania tego problemu polegający na sprawdzaniu długości każdego cyklu Hamiltona wymaga sprawdzenia wszystkich permutacji wierzchołków, co w konsekwencji prowadzi do złożoności wykładniczej (n!). Praktyczne zastosowanie takiego algorytmu już dla kilkunastu miast jest więc niemożliwe. Nawet przy zastosowaniu powracania, gdy w każdym kroku aktualny koszt porównywany jest z najkrótszym wyznaczonym do tej pory cyklem, nie zmniejszy tej złożoności, choć może skrócić czas wykonania algorytmu w średnim przypadku, gdy najkrótsza trasa zostanie wyznaczona w pierwszych krokach. Jednak złożoność nadal będzie wykładnicza. Alternatywą dla przeglądu wyczerpującego jest zastosowanie strategii zachłannej w algorytmie aproksymacyjnym, dającym wprawdzie rozwiązanie przybliżone, lecz w czasie O(n2). Dzieje się tak przy założeniu, że funkcja kosztu podróży spełnia warunek trójkąta, to znaczy, że koszt podróży z miasta u do miasta v jest na pewno mniejszy niż suma kosztów podróży z miasta u do w i z w do v, czyli: c(u,v) < c(u,w) + c(v,w). W przypadku problemu komiwojażera nierówność ta jest spełniona, gdyż koszt podróży z miasta u do v jest po porostu odległością euklidesową między tymi miastami. Można wykazać, że odległość przybliżona jest, co najwyżej dwa razy większa od odległości optymalnej. Aproksymacyjny algorytm wyznaczania najkrótszego cyklu Hamiltona w grafie polega na zastosowaniu algorytmu wyznaczającego minimalne drzewo rozpinające (metodą Kruskala lub Prima). Po zbudowaniu minimalnego drzewa rozpinającego należy przejść je metodą preorder (tzn. odwiedzać ojców przed synami) i zapisywać wierzchołki na liście tylko, gdy są odwiedzane po raz pierwszy. Przechodząc drzewo należy równocześnie sumować koszt przebycia krawędzi między dwoma kolejnymi wierzchołkami a na końcu dodać jeszcze koszt przebycia krawędzi między pierwszym i ostatnim wierzchołkiem na liście, ponieważ, zgodnie z założeniami problemu, komiwojażer musi powrócić do miasta, z którego wyruszył.

Dla zobrazowania problemu sprawdzenia wszystkich możliwych permutacji wierzchołków (możliwych tras) podam kilka obliczeń:

Dla 2 miast jest 1 możliwość

Dla 3 miast są 2 możliwości

Dla 4 miast jest 6 możliwości

Dla 5 miast 24 trasy

Dla 6 już 120 tras

Dla 7 miast 720

Dla 9 miast mamy 40320 dróg

Dla 11 mamy 3628800 i to jak na razie dla domowego PC jest granica, aby w rozsądnym czasie zakończyć działanie.

20!=2432902008176640000

Dla 31 miast- 265252859812191058636308480000000 dróg

Dla 46!-5502622159812088949850305428800254892961651752960000000000

Dla 49 miast mamy 48! około 1,241391559*1061

Przy założeniu, że jesteśmy w stanie liczyć miliard kombinacji na sekundę, czyli 6*1010 na min, licząc dalej 3,6*1012 na h. Przez jeden dzień 8,64*1013, przez rok byli byśmy w stanie sprawdzić 3,1536*1016 operacji. Nasz Wszechświat istnieje około 13-14 miliardów lat, w tym czasie wykonamy około 4*1026 obliczeń, czyli program działałby 2*1034 razy tyle, co wiek naszego Wszechświata.

100!= 9,3326215443944152681699238856267*10157

Tego już nikt nie jest w stanie sobie wyobrazić a to dopiero 101 miast.

Ogólnie mamy (n–1)! możliwych przypadków do przeanalizowania. Połowę możemy odrzucić, ponieważ są to te same drogi, ale w drugą stronę, czyli           (n-1)!/2

Jak widać, trudno je wszystkie sprawdzić niezależnie od dostępnej komukolwiek mocy obliczeniowej.

Np. zmiana z 50 do 51 miast skutkuje 50-krotnym wzrostem czasu obliczeń (zamiast 1 godziny – 2 dni)

Przykłady zastosowań

Rozwiązania problemu komiwojażera mają wiele praktycznych zastosowań:.

- w transporcie

- przemyśle, (np: jeżeli maszyna wiertnicza ma zrobić kilka otworów w materiale, komputer powinien wymyślić taką drogę, żeby trasa przejścia wiertła między punktami była jak najkrótsza),

- ramię automatycznej maszyny nitującej, rozmieszczającej nity na skrzydle samolotu, porusza się z punktu do punktu i po umocowaniu n nitów w n różnych miejscach wraca do punktu wyjścia (optymalna droga poruszania się ramienia jest rozwiązaniem odpowiedniego problemu komiwojażera).

- zestaw maszyn ma być użyty do wyprodukowania n elementów. Zmiana obrabianego elementu na inny jest związana ze zmianą oprzyrządowania maszyny i koszty tej dodatkowej czynności są znane (optymalna kolejność wyprodukowania n elementów jest rozwiązaniem problemu komiwojażera).

- także w poznawaniu struktury kryształów (promień rentgenowski musi przejść w krysztale przez kilka tysięcy punktów!)

Metody rozwiązania problemu

...