Strona główna

Heurystyczne rozwiązania problemu komiwojażera


Pobieranie 25.7 Kb.
Data19.06.2016
Rozmiar25.7 Kb.
Heurystyczne rozwiązania

problemu komiwojażera.
Kamil Dębski i Michał Przyłuski



  1. Opis problemu

Problem komiwojażera jest klasycznym problem w informatyce, mimo to warto przypomnieć jego treść. Mając miasta do odwiedzenia oraz sieć dróg między nimi należy znaleźć najtańszą ścieżkę, która pozwoli odwiedzić wszystkie miasta i powrócić do miasta początkowego. Koszt ścieżki najczęściej jest równoznaczny z odległością między miastami, może jednak przyjąć bardziej skomplikowaną formę (np. koszt paliwa + koszt ewentualnych opłat drogowych). Odpowiednikiem problemu komiwojażera w teorii grafów jest problem znalezienia cyklu Hamiltona w grafie pełnym ważonym, gdzie wierzchołkami są miasta, a wagami odległości między miastami.


Problem komiwojażera, jeśli chcieć sprawdzić wszystkie możliwości charakteryzuje się złożonością . Jest to liczba wszystkich cykli Hamiltona w grafie pełnym.


  1. Przygotowanie danych

Dane w naszym programie, rozumiane jako wierzchołki, przez które ma przejść cykl są losowane z mapy Warszawy. Użyta mapa została ściągnięta ze strony www.ump.waw.pl. Użytkownik podaje liczbę wierzchołków, które mają znaleźć się w zbiorze danych wejściowych dla algorytmu. Następnie należy wybrać opcję „Oblicz macierz”, która powoduje wyliczenie macierzy grafu pełnego zawierającego te wierzchołki. Program wypełnia odległości między wierzchołkami na podstawie danych z mapy, przy czym założyliśmy, że problem jest symetryczny i wszystkie ulice są dwukierunkowe. W przypadku, gdy znajdziemy punkt, który nie jest połączony z główną siecią dróg, jest on usuwany z macierzy. W związku z tym, może zmniejszyć się liczba wierzchołków w macierzy.




  1. Interfejs programu

Program został wyposażony w interfejs graficzny umożliwiający wizualizację wylosowanych punktów, oraz cyklu wyliczonego za pomocą jednego z wybranych algorytmów.


Zostały również udostępnione opcje wczytywania i zapisywania obliczonej macierzy odległości między wierzchołkami. Okazało się to, konieczne z dwóch powodów - obliczanie takiej macierzy dla znacznej liczby wierzchołków jest samo w sobie procesem czasochłonnym. Drugi powód to umożliwienie łatwego porównania działania algorytmów na tym samym zestawie wierzchołków.



Rysunek 1. Główne okno programu



  1. Rozwiązanie dokładne problemu

Problem komiwojażera może zostać rozwiązany za pomocą programowania dynamicznego – wtedy jego złożoność wynosi co mimo charakterystyki wykładniczej jest lepsze niż złożoność rosnąca w funkcji silni.

Programowanie dynamiczne dla problemu komiwojażera jest dość intuicyjne, jednakże jego efektywna implementacja jest bardzo trudna. Problemem jest generacja zbiorów wierzchołków (tras częściowych, pośrednich) a następnie przypisywanie im pewnej wartości. Nie jest możliwe bowiem szybkie indeksowanie jakiejkolwiek struktury zbiorem numerów wierzchołków. Rozważane było też wykorzystanie masek bitowych do oznaczania przynależności do zbioru, jednakże takie rozwiązanie, aby było wydajne, ograniczone jest do 64-bitowej zmiennej całkowitej, a zatem jedynie dla 64 wierzchołków. Tworzenie wielopoziomowych indeksów nie byłoby już tak szybkie.

Z tego względu algorytmu programowania dynamicznego nie zaimplementowano. W przypadku małych grafów algorytmy local search dają bardzo dobre - referencyjne - rezultaty, a dla dużych grafów czas wykonania byłby zbyt znaczny.




  1. Metoda zachłanna – najbliższy sąsiad (NN)

W tej metodzie jako następne miasto wybierane jest najbliższe nieodwiedzone jeszcze miasto. Jest to bardzo prosty algorytm, lecz dosyć szybko znajduje dosyć efektywną ścieżkę. Pokazano, że ta metoda zawsze zwraca ścieżkę, o długości <= 0.5*(log(n)+1), gdzie n jest liczbą miast w rozważanym problemie.

Niestety, dla każdego n>1 istnieje nieskończenie wiele grafów, dla których algorytm ten daje najdłuższą ścieżkę ze wszystkich. Wynika to z jego zachłannej natury. Można jednakże ocenić, w przybliżeniu, jakość znalezionej ścieżki; jeśli ostatnie kilka kroków ma zbliżoną długość do pierwszych kilku kroków, oznacza to, że znaleziona ścieżka jest "dość" dobra. Jeśli ostanie kroki, natomiast, są bardzo długie, należy przypuszczać, iż istnieją znacznie lepsze ścieżki.
Na pytanie jak algorytm sprawuje się w praktyce, w sytuacji wykorzystania losowych punktów z mapy Warszawy. W przypadku, gdy algorytmy local search startowały z losowego grafu to dla dużych grafów (powyżej 200 wierzchołków) dawały one wyniki porównywalne lub gorsze niż algorytm najbliższego sąsiada. Dla mniejszych grafów algorytm NN dawał gorsze wyniki niż uzyskany z najlepszego algorytmu. Mimo to najlepszy algorytm zwykle podawał drogę równą nie mniej niż 70% długości uzyskanej algorytmem NN, widać, więc, że wynik tego najprostszego algorytmu jest całkiem dobry.
W przypadku, gdy algorytmy local search startowały ze ścieżki otrzymanej poprzez algorytm najbliższego sąsiada. Zawsze uzyskiwały poprawę dochodzącą do około 77% procent początkowej długości ścieżki.
Jest to algorytm bezkonkurencyjnie najszybszy.


  1. Algorytmy local search

Zostały zaimplementowane 4 algorytmy lokalnego poszukiwania. Wymiany 2,3 i 4 krawędzi oraz algorytm Lin-Kernighan ze zmienną liczbą wymienianych krawędzi zależną od poprawy całkowitej ściezki.


Algorytm 2-opt jest algorytmem najprostszym, są losowane dwie krawędzi i jeśli długość cyklu po wymianie jest mniejsza, krawędzie są zamieniane. W przypadku 3-opt losowane są 3 krawędzie i jest wybierana taka ich konfiguracja, która daje minimalną długość cyklu. Analogicznie jest dla 4-opt – rozłączane są 4 losowe krawędzie i łączone w sposób zapewniający najmniejszą całkowitą długość cyklu. W przypadku algorytmu Lin-Kernighan, jest tworzony łańcuch kolejnych wymian, który kończy się, gdy nie można znaleźć kolejnej wymiany poprawiającej długość cyklu. W każdej iteracji następuje próba utworzenia kolejnego łańcucha o co najmniej 2 elementach, jeśli to się nie powiedzie algorytm kończy działanie.
Każdy algorytm zaczyna od pewnego ustawienia początkowego wierzchołków i potem poprawia długość cyklu. Zostały przeprowadzone obliczenia dla dwóch przypadków – pierwsza kolejność przechodzenia wierzchołków była raz losowana, a za drugim razem jako początkową kolejność została podawana kolejność uzyskana algorytmem NN.
W przypadku losowego początku, algorytmy sprawdzają się lepiej od algorytmu NN dla grafów małych. Natomiast dla grafów powyżej 200 wierzchołków najlepsze wyniki były uzyskiwane za pomocą algorytmu NN. Można tłumaczyć to dużą gęstością grafów, jest duże prawdopodobieństwo, że w pobliżu jest jeszcze nieodwiedzony wierzchołek.. Natomiast algorytmy k-opt miały problem, gdy wierzchołki były gęsto, a ułożenie startowe było zupełnie losowe.
W przypadku, gdy jako początkowe ułożenie wierzchołków był używany wynik działania algorytmu NN zniknął problem tego, że algorytmu local search otrzymywały gorszy wynik niż algorytm NN. Zwykle algorytmy radziły sobie z poprawą drogi wyznaczonej przez algorytm NN, ale znowu tym lepiej im mniej wierzchołków było w grafie.
Odpowiedź na pytanie, który algorytm zachowywał się najlepiej jest trudna. Na pewno czas obliczeń dla 2-opt był najkrótszy, drugi zwykle był 3-opt dla 4-opt natomiast czas ten był najdłuższy. Algorytm LK znalazł się między 3-opt i 4 –opt.
Jeśli chodzi o wyniki to najlepsze wyniki uzyskiwały algorytmy 4-opt i LK z małą przewagą dla LK. Przy startowej kolejności wygenerowanej algorytmem NN, widać znacznie wyraźniej przewagę LK oraz 4-opt. Przy czym znowu jest niewielka korzyść na rzecz algorytmu LK. Natomiast, jeśli chodzi o kategorię „ECONO”, gdzie liczy się i czas i otrzymany wynik to wygrywa LK – w miarę dobry czas i w miarę dobry wynik.
7. Algorytmy probabilistyczne - metaheurystyka mrówek
Zupełnie odmiennym algorytmem jest metaheurystyka mrówek. W zarysie, algorytmy z tej rodziny symulują zachowanie grupy mrówek w poszukiwaniu najlepszej drogi do celu. Algorytm składa się z dwóch zasadniczych kroków, wykonywanych w wielu iteracjach.
Krok pierwszy: losowo rozmieszczone w węzłach mrówki, w oparciu o pewną tablicę feromonów, wybierają losowe ścieżki, aby przejść cały graf.

Krok drugi: każda mrówka zmienia "wiedzę społeczną"- uaktualniając tablicę feromonów.
Idea ta jest piękna, jednakże wszystko tkwi w szczegółach. Do celów implementacyjnych przyjęto kilka założeń. Iteracja to przebieg wszystkich mrówek przy stałej tablicy feromonów. Mrówki uaktualniają pewną tymczasową tablicę, która następnie jest scalana z poprzednią wersją.
W programie przyjęto, że mamy rój 100 mrówek, oraz 1000 iteracji. Te dwa arbitralne wskaźniki liczbowe mają kluczowe znaczenie dla wydajności oraz czasu działania algorytmu. Prawdopodobnie powinny one zależeć od liczby wierzchołków w grafie, jednakże nie udało się ustalić zależności, która by gwarantowała zauważalnie lepsze rezultaty niż przyjęte powyżej wartości.
Kolejnym punktem wymagającym trudnych decyzji projektowych była waga regulująca jak dobra ścieżka zmienia feromon. Tutaj, bez posiadania informacji o dolnym ograniczeniu na długość ścieżki mamy do czynienia ze zgadywaniem. Przyjęto, że waga danej ścieżki zależy od długości jak ((10000 * liczba_wierzcholkow) / długość_cyklu). W czasie rozwoju algorytmu były testowane również inne podejścia. Między innymi, stała pomniejszona o pierwiastek z długości trasy - zależność dobrze się sprawdzała dla małych grafów, jednakże (jak wiemy z rozwiązań innymi algorytmami) w przypadku grafu o 100 lub większej liczbie wierzchołków, długość cyklu jest znacznie większa niż dla 10-20 wierzchołkowych grafów. Z tego względu włączono liczbę wierzchołków do wskaźnika jakości.
Kolejnym założeniem koniecznym w tym modelu modelu powinna być funkcja odpowiedzialna za ulatnianie się feromonu. Niestety próby z różnymi funkcjami zakończyły się niepowodzeniem. Z tego względu feromon nie ulatnia się, zawsze jest tylko dodawany. Nie powinno to mieć krytycznego znaczenia dla algorytmu, gdyż zawsze przybywa nowy, który - w przypadku krótkiej ścieżki - ma wysoki wskaźnik jakości.
Poważnym problemem, który dotyczy wszystkich mrówkowych rozwiązań jest ich losowy charakter. Mrówki mają tendencję do testowania ogromnej liczby bardzo słabych rozwiązań. Daje się to szczególnie we znaki przy dużych i gęstych grafach. Dla 10-20 wierzchołków i 100 mrówek, możemy przypuszczać, że wszystkie wierzchołki są podobnie daleko, i wiele rozwiązań zostanie sprawdzonych. Dla 100 wierzchołków w rzeczywistości (na mapie Warszawy) jest już dość "gęsto". Niestety, mrówki o tym nie mają pojęcia (i jest to jedno z podstawowych założeń modelu), i losują dowolny wierzchołek. Najczęściej jednak w bliskim otoczeniu obecnego węzła jest jakiś nieodwiedzony wierzchołek, a niewykorzystanie tej informacji kosztuje potem dość dużo.
Kolejnym aspektem algorytmu jest jego wydajność. W naszej sytuacji mamy ustaloną liczbę 100000 przebiegów pętli wewnętrznej (1000 iteracji po 100 mrówek). Nie jest to duża liczba, jednakże czasochłonna jest operacja losowania wierzchołka, który nie był odwiedzony, z uwzględnieniem wag. Przy przyjętym systemie losowania, i sprawdzania czy dany wierzchołek był wcześniej odwiedzony powoduje to, że na wylosowanie ostatnich kilku kroków czeka się względnie długo w niekorzystnej sytuacji.
Z drugiej strony, dla dużych grafów należałoby stosować zmienną liczbę iteracji. Minusem tego rozwiązania byłoby znaczne wydłużenie czasu obliczeń, który i tak był dość pokaźny.
Dla małych grafów zaobserwowano ogromną zmienność w uzyskiwanych rozwiązaniach. Jest to zgodne z oczekiwaniami i rodzi pozytywne nadzieje, że odpowiedni dobór parametrów modelu może jeszcze poprawić rezultaty.
W przypadku dużych grafów algorytm bardzo łatwo grzęznął w pewnym - losowym - rozwiązaniu, które po pierwszej iteracji uzyskiwało pewną wagę w tablicy feromonów. Potem algorytm nie był w stanie się z niego uwolnić, i zwracał rozwiązania niskiej jakości.
Podsumowując, wydaje się, iż algorytmy oparte o rój mrówek są warte uwagi i może w nich leżeć wiele ciekawych wyników, jednakże szczegóły modelu, oraz ich losowy charakter powodują, że trudno jest uzyskać stabilne wyniki. Zarys idei im przyświecającej charakteryzuje się przejrzystością i szybkością, lecz detale wymagające sprecyzowania w trakcie implementacji pozostawiają ogromne pole do modyfikacji ich parametrów.
Algorytm ten ma jednakże jedną, ogromną zaletę ponad innymi algorytmami prezentowanymi tutaj. Można go w łatwy i intuicyjny sposób zrównoleglić. Wynika to z faktu, że każda ze 100 mrówek w ustalonej iteracji korzysta tylko ze swoich lokalnych danych. Z tego względu możliwe byłoby uruchomienie tego na klastrze o 100 jednostkach obliczeniowych, a jedynym momentem interakcji między węzłami byłoby podsumowanie wyników po każdej iteracji i załadowanie nowej tablicy feromonów.
Największy wachlarz możliwości poprawy tego algorytmu daje połączenie go z NN. Wydaje nam się, że wyposażenie mrówek w "wielkiego brata", który odpowiednio kierowałby nimi jest rozsądne - szczególnie w sytuacji bardzo gęstych grafów Warszawy. Chociażby, aby faworyzować wierzchołki położone w promieniu kilometra od aktualnego.


©snauka.pl 2016
wyślij wiadomość