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

Imię i Nazwisko: Studia:

Specjalność:

Nr albumu:

Promotor:

Rok akademicki 2005/2006

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]:

1954: 49 punktów

1962: 33 punktów

1977: 120 punktów

1987: 532 punktów

1987: 666 punktów

1987: 2392 punktów

1994: 7397 punktów

1998: 13509 punktów

2001: 15112 punktów

2004: 24978 punktów

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*10⁶¹

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

100!= 9,3326215443944152681699238856267*10¹⁵⁷

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

Heurystyka

To metoda znajdowania rozwiązań, dla której nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt kosztowny. Wśród algorytmów heurystycznych dużą role odgrywają algorytmy sukcesywnego dołączania węzłów. Algorytmy takie polegają na przedłużaniu trasy częściowej, przebiegającej przez zbiór miast będących podzbiorem zbioru wszystkich n miast. W każdym kroku do trasy dodawane jest nowe miasto, proces ten trwa do chwili aż trasa złożona będzie ze wszystkich miast. Istnieje wiele możliwych strategii dołączania miast np: dołączanie najdalszego miasta, dołączanie najbliższego miasta itp. Dołączenie miasta polega na wstawieniu go do trasy w taki sposób, aby wzrost długości ścieżki wynikający z dodania miasta był jak najmniejszy. Zaletą takiego postępowania jest jego niska złożoność obliczeniowa.

Algorytm dołączania najdalszego miasta od cyklu

O dołączeniu kolejnego miasta do ścieżki decyduje tu jego odległość od najbliższego miasta w cyklu. Dołączamy to miasto, dla którego ta odległość jest największa. Raz dołączone do ścieżki częściowej miasto pozostaje w niej w kolejnych iteracjach aż do końca postępowania. Rozwiązanie uzyskane za pomocą tej metody jest zbliżone do optymalnego.

Najbliższe miasto

Jest to algorytm dołączający do ścieżki kolejne miasta, wybierając za każdym razem to, które znajduje się najbliżej dodanego ostatnio. Algorytm charakteryzuje duża szybkość i prostota. Algorytm przegląda listę miast, oblicza odległości do każdego z nich i dołącza do ścieżki to leżące najbliżej. W każdym kolejnym kroku liczba miast, które można dołączyć do ścieżki maleje o 1. Dla n miast algorytm musi, więc wykonać n przebiegów, za każdym razem wybierając jedno z n-1, n-2, n-3 itd. miast. Można z tego wywnioskować, że taki algorytm będzie miał złożoność O(n log n). Pomimo tego daje on jednak przeważnie słabe rezultaty.

Metoda podziału i ograniczeń

Pokaże przykład, jaki udało mi się znaleźć:

Tworzymy macierz kosztów:

Odejmujemy „stałą” od wierszy i kolumn, aby każdy wiersz (kolumna) zawierał, co najmniej jedno zero.

„stała” - najmniejsza wartość elementów w wierszu (kolumnie).

Po redukcji wierszy macierz ma postać:

Po redukcji kolumn macierz ma postać:

Macierz została zredukowana poprzez odjęcie: 3,3,4,16,7,25 (dla wierszy) oraz 15 i 8 (dla kolumn).

Razem: 81

LB = 81 stanowi dolne ograniczenie macierzy (lower bound)

Zredukowaną macierz dzielimy na dwa podzbiory.

Wybieramy takie połączenie, dla którego wartość elementu macierzy wynosi 0, a którego zablokowanie spowoduje największy przyrost dolnego ograniczenia.

Wybrano połączenie 6-3

z (6,3)

Rozwijamy tę gałąź, która ma mniejsze dolne ograniczenie z (6,3) LB=81

Wybieramy połączenie (4,6), ponieważ jego zablokowanie spowoduje największy przyrost dolnego ograniczenia.

Możliwe połączenia (2,1) lub (3,5)

Usuwamy z macierzy 2-gi wiersz i 1-wszą kolumnę, oraz blokujemy 1-2

Wybieramy połączenie (1,4)

Macierz po usunięciu 1 -go wiersza i 4-tej kolumny

Macierz po redukcji

Połączenia (5,2) i (3,5)

Ostatecznie: (6,3) i (4,6) i (2,1) i (1,4) i (5,2) i (3,5) LB=84+20=104

ROZWIĄ ZANIE: 1-4-6-3-5-2-1 KOSZT =104

Algorytm podziału i ograniczeń pozwala pomijać pewne podzbiory rozwiązań, a zatem oszczędzać czas obliczeń na niepotrzebnym badaniu poszczególnych przypadków.

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

Mamy dany zbiór punktów na płaszczyźnie, o współrzędnych będących liczbami naturalnymi. Należy znaleźć taki cykl prosty obejmujący wszystkie punkty, że wielokąt zdefiniowany przez ten cykl jest prosty i posiada minimalną możliwą powierzchnię.

Wielokąt jest prosty, jeżeli nie przecina sam siebie. Cykl jest prosty, jeśli nie odwiedza żadnego wierzchołka więcej niż raz. Dopuszcza się zastosowanie pewnego przybliżenia przy obliczaniu powierzchni wielokąta.

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

Mamy dany zbiór wielokątów prostych na płaszczyźnie (nazywanych sąsiedztwami), o współrzędnych będących liczbami naturalnymi. Należy znaleźć najkrótszy cykl prosty odwiedzający, co najmniej jeden punkt (o współrzędnych będących liczbami naturalnymi) z obszaru każdego sąsiedztwa.

Wykorzystanie algorytmów genetycznych[1]

Czym są „algorytmy genetyczne”?...

Najprościej rzecz ujmując jest to próba zasymulowania w pamięci komputera populacji jakiegoś gatunku. Na taką populację składają się dziesiątki, setki, tysiące pojedynczych osobników. Osobniki te między sobą mogą się krzyżować, mogą również następować jakieś samoistne zmiany w strukturze pojedynczego osobnika, (tzw. mutacja). W wyniku krzyżowania i mutacji powstają nowe osobniki. Ze względu na fakt, że populacja ma swój z góry narzucony maksymalny rozmiar część osobników należy z niej usunąć (ten krok nazywany jest selekcją). Oczywiście usuwane są te najmniej przystosowane. Cały ten proces (krzyżowanie, mutacja, selekcja) powtarzany jest w nieskończoność.

Powyższy opis dotyczył komputerowych algorytmów, ale na pierwszy rzut oka widać ogromną analogię do matki natury (krzyżowania chyba nie muszę tłumaczyć, mutacja może być spowodowana, np. Czarnobylem, a selekcji może dokonywać wilk, który szybciej dogoni słabszą sarenkę). I to chyba ona była wzorem dla twórców algorytmów genetycznych.

Cóż z algorytmów genetycznych jest dobrego dla kodera, a tym bardziej dla sztucznej inteligencji?...

Przyjmijmy, że mamy do rozwiązania nasz „problem komiwojażera”. W przypadku małej ilości miast problem wydaje się być łatwy. Wystarczy zestawić wszystkie permutacje miast, obliczyć otrzymane w ten sposób odległości i wybrać najkrótszą. Jednak problem komiwojażera jest NP-trudny (oznacza to, że przy wzroście rozmiaru instancji (liczby miast) czas potrzeby na obliczenia rośnie wykładniczo (w przypadku problemu komiwojażera dodanie jednego miasta powoduje dwukrotne zwiększenie czasu obliczeń), dlatego ten sposób rozwiązania na dłuższą metę jest niefajny...

Zaprzęgnijmy, więc do roboty algorytmy genetyczne. Jako „gatunek” możemy przyjąć trasę komiwojażera. Każdy osobnik będzie pamiętał jedną trasę. Takich osobników może być dowolna ilość (im więcej tym bardziej zróżnicowana populacja jednak kosztem dłuższych obliczeń). Na początku do każdego osobnika wpisujemy trasę zupełnie losową. I rozpoczynamy algorytm genetyczny. Krzyżowanie polega na wymianie pomiędzy dwoma osobnikami pewnych elementów tras, (czyli pod tras), natomiast mutacja może oznaczać wymianę w pojedynczym osobniku dwóch miast między sobą. Jeśli dodamy do tego krok selekcji, czyli wybór do następnej populacji osobników najlepiej przystosowanych (to znaczy takich, które reprezentują trasy o najmniejszym koszcie) otrzymamy algorytm, który po pewnej liczbie kroków znajdzie nam całkiem niezłą trasę przez wszystkie miasta.

Niestety algorytmy genetyczne są tylko heurystyką. Oznacza to, że otrzymane rozwiązania nie zawsze będą najlepszymi możliwymi. W zamian za to otrzymujemy rozwiązania bardzo dobre w rozsądnym czasie.

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

Szczegółowy opis elementów algorytmu genetycznego powinniśmy rozpocząć od opisu najmniejszego elementu algorytmu, czyli od opisu pojedynczego osobnika. W zasadzie jest to jedyny element w algorytmie, który jest różny w przypadku różnego wykorzystania algorytmów. Dlatego projektowanie osobnika jest chyba najważniejszą częścią projektowania całego algorytmu genetycznego. Ze względu na niepowtarzalność gatunku trudno jest zdefiniować „złotą zasadę” projektowania osobnika. W tym miejscu mogę podać jedynie kilka cech, które tworzony przez nas gatunek powinien spełniać. Przede wszystkim należy pamiętać, że w algorytmie genetycznym bierze udział bardzo wiele osobników (kilkadziesiąt/set/tysięcy), dlatego ważną cechą osobnika jest długość jego reprezentacji. Wiadomo, że liczba osobników jest sztywno ograniczana liczbą dostępnej pamięci (komputera), dlatego im mniejsza będzie reprezentacja gatunku tym więcej osobników będzie mogło brać udział w ewolucji (a co za tym idzie większe będą szanse znalezienia globalnego optimum). Poza tym inne elementy algorytmu (krzyżowanie, mutacja...) będą działać dużo szybciej gdy poszczególne osobniki będą miały mniejszą wielkość. I od razu mały przykładzik. Przyjmijmy, że naszym gatunkiem jest homo sapiens charakteryzujący się następującymi cechami:

- Płeć (kobieta / mężczyzna)

- Kolor oczu (mamy do wyboru: niebieskie, piwne, brązowe i czarne)

- Wzrost (poniżej 140, 140-150, 150-160, 160-170, 170-180, 180-190, 190-200, powyżej 200)

- Narodowość (mamy do wyboru: Polak, Niemiec, Czech, Rosjanin)
Najprostszą reprezentacją homo sapiens wydaje się być struktura, w której będą zapamiętywane wartości poszczególnych atrybutów. Jeśli na każdy atrybut przeznaczymy zmienną typu char* (string) to otrzymamy całkiem pokaźny rozmiar osobnika. Dodatkową wadą takiej reprezentacji jest dosyć duża niewygoda krzyżowania i mutacji, (o której będzie mowa za chwilę). Niewątpliwą zaletą tej reprezentacji jest „bezpośredniość”, wszystkie pola struktury pamiętają konkretną wartość atrybutu. Celem zmniejszenia rozmiaru struktury można przyjąć, że dla przechowywania wartości atrybutów wykorzystane zostaną zmienne liczbowe (int, byte...), wtedy rozmiar naszej struktury opisującej człowieka zmniejszy się do 4 bajtów. W tym wypadku nie będziemy mieli w strukturze natychmiastowej informacji o wartościach atrybutów i w związku z tym należy stosować pewne oznaczenia. Np: dla płci 0 oznacza kobietę, 1 oznacza mężczyznę, dla koloru oczu 0 oznacza niebieskie, 1 oznacza piwne, 2 oznacza brązowe, 3 oznacza czarne. Reprezentacja ta jest już niewielka i całkiem wygodna w późniejszej obsłudze. Można się jednak w opisie homo sapiens posunąć trochę dalej i wykorzystać reprezentację bitową. Proszę zauważyć, że do reprezentacji płci wystarczy jeden bit (wartość zero-kobieta, jeden-mężczyzna), do reprezentacji koloru oczu dwa bity (00-niebieskie, 01-piwne, 10-zielone, 11-czarne), do reprezentacji wzrostu też trzy bity, a do reprezentacji narodowości dwa bity. I w przypadku takiego kodowania wartości wszystkich atrybutów mieszczą się w 9 bitach. Te 9 bitów tworzą całkowity obraz pojedynczego osobnika. Przy tej reprezentacji należy na początku przyjąć, w jakiej kolejności poszczególne atrybuty będą występowały w reprezentacji osobnika. W naszym przypadku przyjmijmy, że pierwszy bit będzie informował o płci następne o kolorze oczu, wzroście i narodowości. Dla przykładu chromosom: 00000000 reprezentuje niebieskooką Polkę o wzroście nieprzekraczającym 140cm, a chromosom 11011001 reprezentuje wysokiego (190-200) Niemca o brązowych oczach.

I jeszcze jeden przykładzik pokazujący jak można stworzyć binarną reprezentację liczb naturalnych. Przyjmijmy, że mamy do rozwiązania problem znalezienia takiego x'a dla którego funkcja postaci y=f(x) ma minimum (maksimum). Szukamy po prostu ekstremów funkcji. W tym przypadku pojedyncze rozwiązanie ma reprezentować pojedynczą wartości x'a. Można do tego celu użyć zmiennej typu float (real), jednak wtedy trudno jest wymyślić jakiś rozsądny sposób krzyżowania takich osobników. Innym wygodniejszym sposobem kodowania x'ów jest zastosowanie reprezentacji bitowej. W tym wypadku tracimy jednak na maksymalnej rozdzielczości. Dla przykładu, jeśli badamy funkcję w przedziale 1-3 i reprezentujemy x'y na 4 bitach to otrzymujemy maksymalną rozdzielczość: (max_x-min_x)/(2^{(liczba_bitów)}-1)=(3-1)/(2⁴-1)=2/15=0.1333 Oznacza to, że najmniejsza możliwa różnica pomiędzy analizowanymi x'ami jest równa 0,13333. Następujące wartości bitów odpowiadają następującym wartościami x'a:

0000-1.0

0001-1.1333

0010-1.2666

0011-1.4 itd.

Jeśli mamy już zaprojektowany chromosom (krótki i wygodny w obsłudze) możemy zająć się samym algorytmem. W uproszczeniu wygląda on następująco:

1. Losowanie populacji

2. Ocena osobników

3. Selekcja

4. Krzyżowanie

5. Mutacja

6. Powrót do punktu 2

Poniżej opis poszczególnych jego elementów:

Losowanie populacji

W tym miejscu należy ustalić jak wielka będzie tworzona populacja. Jeśli populacja będzie zawierała zbyt mało osobników to algorytm może zatrzymać się w jakimś minimum lokalnym, (gdy jakieś niezłe, (ale nienajlepsze) rozwiązanie zdominuje całą populację). Z drugiej strony zbyt duża liczebność populacji zmniejsza szybkość działania algorytmu. Po ustaleniu wielkości populacji należy stworzyć wszystkie osobniki. Ze względu na fakt, że początkowa populacja powinna być jak najbardziej różnorodna każdy osobnik powinien być tworzony całkowicie losowo. W tym miejscu widać przewagę reprezentacji bitowej gdzie bez względu na rodzaj problemu nowo tworzony osobnik zawiera n losowo wygenerowanych bitów. W przypadku reprezentacji osobnika w strukturze należy każde jej pole wypełnić osobno. Na tym kroku należy pamiętać, aby tworzone osobniki były poprawne to znaczy reprezentowały obiekty należące do dziedziny problemu. Np przy tworzeniu x'ów (problem znajdowania ekstremum) w przedziale 1-3 wygenerowany chromosom nie może reprezentować x'a o wartości np. 5. W przypadku reprezentacji bitowej ten problem pojawia się wtedy, gdy do reprezentowania jakiegoś atrybutu nie są wykorzystywane wszystkie kombinacje bitów. Wracając do poprzedniego przykładu chromosomu opisującego homo sapiens, jeśli nie uwzględnialibyśmy Rosjan to chromosom 000000011 nie byłby poprawny.

Ocena osobników

W tym kroku badana jest „dobroć” poszczególnych osobników. W zależności od rodzaju problemu różne są funkcje sprawdzające przystosowanie osobników. W przypadku ekstremum funkcji „dobrocią” jest po prostu wartość funkcji w zadanym x'ie. W przypadku rozwiązywania problemu komiwojażera jest to długość trasy, jaka jest reprezentowana przez danego osobnika. W tym miejscu można wprowadzić tzw. funkcję kary za niedopuszczalne rozwiązanie. Wcześniej wspomniałem, że o poprawne osobniki należy zadbać podczas tworzenia populacji (niepoprawne osobniki mogą też powstawać w krokach krzyżowania i mutacji). Czasami jest to jednak trudne do wykonania, dlatego przy losowaniu można te osobniki zaakceptować a w tym kroku dodać funkcję kary. Spowoduje ona dużo mniejsze prawdopodobieństwo przejścia przez danego osobnika kroku selekcji. W zależności od tego czy funkcję dopasowania („dobroć”) minimalizujemy czy maksymalizujemy wartość funkcji błędu należy do niej dodać bądź odjąć.

Selekcja

Krok ten jest esencją całej genetyki. W tym miejscu tworzona jest nowa populacja na podstawie już istniejącej. W zależności od wartości funkcji oceny (obliczanej w poprzednim kroku) dany osobnik ma większe, (gdy jest „dobry”) lub mniejsze, (gdy jest „słaby”) szanse na znalezienie się w kolejnym pokoleniu. Istnieje kilka sposobów obliczania „szansy” poszczególnych osobników:

Koło ruletki - Polega na n krotnym losowaniu, (n - liczba osobników w populacji) ze starej populacji osobników, które zostaną przepisane do nowej populacji. Oczywiście wszystkie osobniki mają różne prawdopodobieństwa wylosowania. Prawdopodobieństwo to jest liczone z następującego wzoru: Wartość przystosowania danego osobnika/suma wartości przystosowania wszystkich osobników Powyższy wzór jest poprawny tylko wtedy, gdy maksymalizujemy funkcję oceny. Gdybyśmy ją minimalizowali można zastosować następujący wzór: (Wartość najgorszego osobnika-Wartość danego osobnika+1)/(suma wartości wszystkich osobników+1). Wzór ten odwraca minimalizację na maksymalizację. I od razu mały przykład (przyjmijmy maksymalizację funkcji przystosowania). Mamy trzy osobniki o następujących wartościach przystosowania: 5,1,2. Odpowiadające im wartości prawdopodobieństwa są, zatem równe:

• Pierwszy osobnik: 5/8, czyli 62,5%

• Drugi osobnik: 1/8, czyli 12,5%

• Trzeci osobnik: 2/8, czyli 25%

Ranking liniowy - Selekcja tą metodą jest bardzo podobna do selekcji metodą koła ruletki. Modyfikacja polega jedynie na zmianie funkcji określającej prawdopodobieństwo wyboru danego osobnika. Przed przystąpieniem do tej selekcji należy nadać każdemu z osobników pewną wartość (przystosowanie) zależną od jego położenia na liście posortowanej względem wartości funkcji oceny. Jeśli chcemy maksymalizować to wartości powinny być posortowane rosnąco, w przypadku minimalizacji wartości powinny być posortowane malejąco. Aby obliczyć prawdopodobieństwo wybrania każdego osobnika można skorzystać ze wzoru: Prawdopodobieństwo = Przystosowanie/Suma przystosowania wszystkich osobników Dla powyższego przykładu wartości prawdopodobieństw wyglądałyby następująco:

• Pierwszy osobnik: 3/6, czyli 50%

• Drugi osobnik: 1/6, czyli 16,7%

• Trzeci osobnik: 2/6, czyli 33,3%

Ten sposób wyliczania prawdopodobieństw zmniejsza przewagę, jaką mają najlepsze rozwiązania, gdy ich przewaga jest bardzo duża i zwiększa przewagę, gdy jest ona bardzo mała.

Turniej - Metoda jest zupełnie różna od powyższych i polega na losowym wyborze z całej populacji kilku osobników (jest to, tzw. grupa turniejowa), a później z tej grupy wybierany jest osobnik najlepiej przystosowany i on przepisywany jest do nowo tworzonej populacji. Losowanie grup turniejowych oraz wybieranie z nich najlepszego osobnika należy powtórzyć aż do utworzenia całej nowej populacji. Selekcja metodą turniejową jest pozbawiona niedogodności metody koła ruletki, gdzie wymagana jest maksymalizacja funkcji oceny, w turnieju ważna jest jedynie informacja o „lepszości” jednego rozwiązania nad innym.

Krzyżowanie

Zadaniem kroku krzyżowania jest wymiana „materiału genetycznego” pomiędzy dwoma rozwiązaniami w populacji. W wyniku krzyżowania na podstawie dwóch rozwiązań (rodzice) tworzone są dwa nowe osobniki (dzieci). Po wykonaniu krzyżowania dzieci zastępują w populacji rodziców. Oczywiście w tym kroku nie wszystkie rozwiązania muszą się ze sobą krzyżować. Liczbę krzyżowań określa tzw. współczynnik krzyżowania (o wartości od, 0 do 1), który pokazuje, jaka liczba osobników powinna być w jednej iteracji skrzyżowana, bądź określa prawdopodobieństwo, z jakim każde rozwiązanie może wziąć udział w krzyżowaniu. W przypadku binarnej reprezentacji chromosomu najprostsze krzyżowanie polega na podziale dwóch chromosomów (rodzice) na dwie części (niekoniecznie równe) i z nich tworzone są dzieci: pierwsze dziecko składa się z początkowej części pierwszego rodzica i końcówki drugiego natomiast drugie dziecko odwrotnie - początek drugiego rodzica i koniec pierwszego. Na przykładzie homo sapiens może to wyglądać następująco:

Pierwszy rodzic: 00000000 - niebieskooka Polka o wzroście do 140cm

Drugi rodzic: 11011001 - wysoki (190-200) Niemiec o brązowych oczach.

Jeśli punkt podziału ustalimy pomiędzy czwartym a piątym bitem to dzieci będą wyglądać następująco:

00001001 - Niemka o niebieskich oczach i wzroście 150-160cm

11010000 - Polak o brązowych oczach i wzroście 160-170cm

Rozszerzeniem tego krzyżowania jest krzyżowanie wielopunktowe, gdzie chromosomy rodziców dzieli się na kilka części a później dzieci tworzy się na podstawie przeplatanych wycinków rodziców. W przypadku niebinarnej reprezentacji gatunku należy wymyślić krzyżowanie stosowne do zastosowanej reprezentacji. Gdy np. dane trzymane są w strukturze to możne podmieniać pomiędzy rodzicami zawartości poszczególnych pól struktur. W tym wypadku jednak dzieci będą zawsze zawierały wartości występujące przynajmniej u jednego z rodziców. W powyższym przykładzie krzyżowania jednopunktowego wzrost dzieci jest różny od wzrostu rodziców. Stało się tak, dlatego, że punkt podziału trafił w środku bitów odpowiedzialnych za wzrost. W przypadku kodowania niebinarnego takie coś byłoby niemożliwe.

Mutacja

Mutacja podobnie jak krzyżowanie zapewnia dodawanie do populacji nowych osobników. Jednak w odróżnieniu od krzyżowania w przypadku mutacji modyfikowany jest jeden a nie dwa osobniki. Podobnie jak w przypadku krzyżowania istnieje tzw. współczynnik mutacji, który określa ile osobników będzie w jednej iteracji ulegało mutacji. W przypadku reprezentacji binarnej sprawa mutacji jest bardzo prosta wystarczy np. zanegować jeden bit w rozwiązaniu, aby otrzymać zupełnie nowego osobnika. W przypadku homo sapiens negacja pierwszego bitu powoduje zamianę kobiety na mężczyznę lub odwrotnie. Oczywiście mutacja może być bardziej urozmaicona (negacja losowej liczby bitów, odwracanie kolejności losowej liczby bitów, przesunięcie losowej liczby bitów i inne.). Należy jednak pamiętać, że operować ona może tylko na jednym rozwiązaniu. W przypadku niebinarnej reprezentacji rozwiązania mutacja może polegać np. na wpisaniu do losowego pola struktury losowej wartości (oczywiście przewidzianej przez gatunek).

Powrót do oceny osobników

W zasadzie algorytm genetyczny powinien działać w nieskończoność jednak dobrze jest zapewnić jakieś rozsądne wyjście z pętli. Może to być np. pewna liczba iteracji, wartość osiągniętego najlepszego rozwiązania, czas, brak poprawy wyniku przez pewną ilość iteracji lub inne w zależności od rodzaju zadania.

Powyżej zostały opisane podstawowe elementy algorytmu genetycznego, które w zupełności wystarczają do napisania programu rozwiązującego taki czy inny problem. Oczywiście istnieją jeszcze pewne inne techniki.

Porównanie kilku metod - testy [5]

Na początek musimy założyć, że nie interesuje nas czas, w jakim wykonujemy poszukiwania. Prawdopodobnie zmieniając czas wyniki mogłyby wyglądać nieco inaczej. Porównujemy jedynie długość trasy. A oto wyniki testów działania i efektywności powyższych algorytmów przeprowadzone dla 3 różnych konfiguracji miast.

Rysunek 2 Al.(heurystyczny) dł:1611

Rysunek 3 Al. (najbliższe miasto) dł:2078

Rysunek 4 Al. (genetyczny) dł:1611

Na tym prostym przykładzie widać, że algorytm dołączający najbliższe miasto jest raczej mało efektywny. Nawet „na oko” widać, że rozwiązanie odbiega od optimum. Natomiast pozostałe 2 algorytmy dały takie same rezultaty, co utwierdza nas w przekonaniu, że udało nam się znaleźć rozwiązanie optymalne.

Rysunek 5 Al.(heurystyczny) dł:1733

Rysunek 6 Al. (najbliższe miasto) dł:1487

Rysunek 7 Al. (genetyczny) dł:3023

Dla tego specyficznego przypadku najlepszy wynik dał algorytm dołączający najbliższe miasto. Miasta jednak w tym przypadku były ułożone w bardzo charakterystyczny sposób. Nieco gorzej poradził sobie z tym zadaniem algorytm heurystyczny. Zawiódł natomiast algorytm genetyczny, pomimo ustawienia ilości pokoleń na 10000. Być może dobranie innych parametrów dla mutacji i krzyżowania dałoby lepszy efekt...

Rysunek 8 Al.(heurystyczny) dł:1248

Rysunek 9 Al. (najbliższe miasto) dł:1377

Rysunek 10 Al. (genetyczny) dł:1268

W tym wypadku najlepszy rezultat dał algorytm heurystyczny, a niewiele gorszy - genetyczny. Po raz kolejny zawiódł algorytm dołączający najbliższe miasto...

W przypadku wszystkich problemów NP-zupełnych jesteśmy skazani na algorytmy generujące rozwiązania przybliżone. W wielu przypadkach algorytmy przybliżone dają na tyle satysfakcjonujące rezultaty, że można z powodzeniem wykorzystywać je do rozwiązywania rzeczywistych problemów.

Część praktyczna

Strona WWW

Strona www napisana w języku php wraz z clasami appletu znajduje się na serwerze 60free.ovh.org pod adresem http://www.kubal.ovh.org/.

Rysunek 11 Strona php z appletem w Javie

Wybrałem serwer 60free, dlatego że jest polski, darmowy, ma łatwy dostęp przez ftp i ma możliwość utworzenia bazy w MySql. Chciałem zrobić bazę miast w MySql, ale nie udało mi się połączyć z bazą na poziomie appletu. Wymagane jest do tego utworzenie mostka ODBC, czyli zainstalowanie po stronie klienta sterownika, który pośredniczy w przekazywaniu danych pomiędzy bazą a appletem. Należy także utworzyć zmienną środowiskową. Uznałem, że są to zbyt skomplikowane czynności przy uruchamianiu zwykłej strony internetowej i zrezygnowałem z bazy MySql.

Wymagania sprzętowe

Do prawidłowego działania strony potrzebny jest komputer PC z Przeglądarką Internet Explorer i dostęp do Internetu. Preferowana rozdzielczość ekranu to 1024 na 758 pikseli. Przy innej konfiguracji mogą nie zadziałać wszystkie funkcje appletu. Należy także zainstalować platformę Javy, do której jest link na stronie.

Rysunek 12 Moment ładowania platformy Javy

Możliwości i obsługa

Program służy do poszukiwania najkrótszej drogi pomiędzy kilkoma punktami. Mamy możliwość wybrać maksymalnie 100 punktów. Kiedy to zrobimy wybieramy jeden z dwóch dostępnych algorytmów.

Rysunek 13 Wybór algorytmu poszukiwań

Pierwszy wyznacza wszystkie możliwe trasy i wybiera tą najkrótszą, ale z uwagi na ilość możliwości i czas działania ilość punktów w tym algorytmie ograniczyłem do 12.

Rysunek 14 Okno dialogowe

Drugi to algorytm genetyczny, zasadę działania przedstawię w kolejnych rozdziałach. Możemy wybrać wielkość populacji dla większej liczby miast możemy zwiększyć, co jednocześnie zwiększy szanse znalezienia najkrótszej trasy lub zmniejszyć, co pozwoli skrócić czas poszukiwań. Następnie z uwagi na to, że algorytm może działać bez końca mamy możliwość ustawienia ilości powtórzeń, czyli czas graniczny, po którym zostaną wyświetlone wyniki.

Rysunek 15 Panel do ustawiania parametrów

Po skonfigurowaniu tych parametrów możemy przejść do uruchomienia algorytmu i tu mamy dwie możliwości. Krok po kroku śledzić postępy w poszukiwaniach lub od razu nacisnąć start. Po zadanym wyżej czasie program zakończy działanie i wyświetli wyniki. Jeżeli to, co pokazał nas nie zadowala możemy Np wydłużyć czas graniczny lub zwiększyć populację, ale wtedy wszystko zacznie się od nowa. A oto przykład rozwiązania problemu komiwojażera dla 20 punktów.

Rysunek 16 Jeden z efektów działania programu

Jedynką został zaznaczony punkt startowy. Długość trasy wyszła w zaokrągleniu 4897km. Algorytm działał: 22922ms czyli 23s. Nie jest to może najkrótsza trasa ale na pewno w tak krótkim czasie jest to bardzo zadowalający wynik. Do tej pory punkty były losowo wybierane, ale w programie mamy możliwość wybrać stałe punkty, dzięki czemu możemy tą samą trasę poszukiwać na różnych komputerach i porównywać wyniki. Dla ułatwienia punkty dostały nazwy miast. Żeby to zrobić zmieniamy zakładkę w górnym lewym rogu na wybrane miasta.

Rysunek 17 Zakładki

Wybieramy minimum 3 miasta. Zakładka losowe punkty zmieni się na mapa, wchodząc na nią możemy wrócić do poprzedniego widoku z zaznaczonymi miastami. W każdej chwili możemy dodać lub odznaczyć dowolne miasto z listy.

Rysunek 18 Wybór miast

Możemy dodać do listy swoje miasto. Niestety Java nie pozwala zapisywać danych do pliku na serwerze, musi to dla nas zrobić formularz w php i skrypty Java script. Naciskamy Dodaj nowe miasto i przechodzimy do formularza.

Rysunek 19 Dodawanie nowego miasta

Jeżeli wpiszemy miasto polskie nie używając polskich liter naciskając szukaj wyświetli się strona, na której znajdziemy współrzędne miasta. Jeżeli jednak chcemy używać polskich znaków po naciśnięciu szukaj jeszcze raz musimy wpisać nazwę miasta. Możemy także dodać miasto z poza granic Polski, ale wtedy sami musimy znaleźć współrzędne np. w google. Po wpisaniu miasta i jego położenia naciskamy zapisz, wracając do naszej listy miast. I znów ograniczenia Javy nie pozwalają na szybką reakcję i dodanie miasta, ponieważ Java pobierając dane z serwera tworzy strumień, czyli nic innego jak podobny plik na twoim komputerze i odświeży go dopiero po ok. 24h. Można to przyśpieszyć usuwając pliki tymczasowe w menu narzędzia i opcje internetowe.

Dlaczego wybrałem algorytm genetyczny?

Powodów jest wiele. Po pierwsze algorytm genetyczny daje dość dobre wyniki w krótkim czasie. Program zajmuje dość mało miejsca a w moim przypadku musimy go za każdym razem pobierać z serwera. I w końcu sam algorytm genetyczny jest bardzo elastyczny, możemy dobierać wiele parametrów. Możemy dobierać wielkość populacji oraz metodę jej generacji. Możemy na wiele sposobów krzyżować. Jest wiele metod mutacji osobników. Również funkcję oceny możemy dowolnie ustawić tak, aby nasz algorytm był jak najlepszy.

Algorytm

Populacja

Zaczynamy od ponumerowania wszystkich miast. Następnie tworzymy chromosom o długości takiej jak liczba miast. W kolejnych genach zapisujemy kolejne miasta na drodze. Czyli, jeśli w genie numer 1 siedzi miasto X a w genie numer 2 miasto Y to oznacza to, że idziemy z miasta X do Y. W ten sposób geny w chromosomie układają się dokładnie tak, jak miasta w cyklu. Dla przykładowych sześciu miast połączonych drogą przykładowy chromosom odwzorowujący cykl może wyglądać tak:

[1 4 6 2 3 5]

Do prawidłowego działania tworzymy minimum 8 początkowych chromosomów.

Fragment kodu Javy odpowiedzialny za utworzenie populacji:

//tworzenie populacji

for (int i=1; i<100; i++)

for (int j = 1; j <101; j++)

populacja[i][j] = 0;

if (jScrollBar1.getValue()>1)

{

for(int i=1;i<=jScrollBar2.getValue();i++)

{

populacja[i][1]=1;

for(int j=2;j<=jScrollBar1.getValue();j++)

{

double x=randomGenerator.nextDouble()*jScrollBar1.getValue();

int k=(int)x+1;

while (populacja[i][k]!=0)

{

k++;

if (k > jScrollBar1.getValue())

k = 2;

}

populacja[i][k]=j;

}

}

}

Funkcja oceny (kosztu)

Funkcją oceny jest po prostu droga, czyli długość całego cyklu w grafie. Im mniejsza, tym lepiej. Wykorzystujemy wzór na odległość Euklidesową pomiędzy dwoma punktami. Na płaszczyźnie jest to pierwiastek z sumy kwadratów różnic odległości dla poszczególnych współrzędnych:

Obliczenie drogi w Javie:

dlugosc=0;

for (int i=1; i<101 ; i++)

{

if(kolejnosc[i+1]==0)

{

dlugosc+=Math.sqrt(Math.pow((rndx[kolejnosc[i]]-rndx[kolejnosc[1]]),2)+Math.pow((rndy[kolejnosc[i]]-rndy[kolejnosc[1]]),2));

break;

}

dlugosc+=Math.sqrt(Math.pow((rndx[kolejnosc[i]]-rndx[kolejnosc[i+1]]),2)+Math.pow((rndy[kolejnosc[i]]-rndy[kolejnosc[i+1]]),2));

}

Selekcja

Sortujemy osobniki zaczynając od najlepszych (najkrótszych) i usuwamy połowę najgorszych (najdłuższych).

5.29

5.8

5.8

6.51 _

7.51

8.21

7.75

7.7

Sortujemy do połowy, reszta i tak zostanie zastąpiona potomstwem.

Funkcja sortowania

private void sortuj()

{

for (int s=1;s<=jScrollBar2.getValue()/2;s++);

{

for (int i=jScrollBar2.getValue();i>1;i--)

{

double dlugosc1=0;

for (int k=1; k<101 ; k++)

{

if(populacja[i][k+1]==0)

{

dlugosc1+=Math.sqrt(Math.pow((rndx[populacja[i][k]]-rndx[populacja[i][1]]),2)+Math.pow((rndy[populacja[i][k]]-rndy[populacja[i][1]]),2));

break;

}

dlugosc1+=Math.sqrt(Math.pow((rndx[populacja[i][k]]-rndx[populacja[i][k+1]]),2)+Math.pow((rndy[populacja[i][k]]-rndy[populacja[i][k+1]]),2));

}

double dlugosc2=0;

for (int k=1; k<101 ; k++)

{

if(populacja[i-1][k+1]==0)

{

dlugosc2+=Math.sqrt(Math.pow((rndx[populacja[i-1][k]]-rndx[populacja[i-1][1]]),2)+Math.pow((rndy[populacja[i-1][k]]-rndy[populacja[i-1][1]]),2));

break;

}

dlugosc2+=Math.sqrt(Math.pow((rndx[populacja[i-1][k]]-rndx[populacja[i-1][k+1]]),2)+Math.pow((rndy[populacja[i-1][k]]-rndy[populacja[i-1][k+1]]),2));

}

if (dlugosc2>dlugosc1)

{

kolejnosc = populacja[i];

populacja[i] = populacja[i-1];

populacja[i-1]=kolejnosc;

}

}

}

}

Krzyżowanie

Osobniki łączymy kolejno w pary:

5.29 5.8

5.8 6.51

Krzyżowanie genów przy reprodukcji (krzyżowanie cykliczne):

Każdy osobnik: permutacja

Rodzic 1: [3 4 6 2 1 5]

Rodzic 2: [4 1 5 3 2 6]

Losujemy pierwszy gen do wymiany: wylosowaliśmy pierwszy

Rodzic 1: [4 4 6 2 1 5]

Rodzic 2: [3 1 5 3 2 6]

Rodzic 1 ma dwie 4. Wymieniamy starą.

Rodzic 1: [4 1 6 2 1 5]

Rodzic 2: [3 4 5 3 2 6]

Rodzic 1 ma dwie 1. Wymieniamy starą.

Rodzic 1: [4 1 6 2 2 5]

Rodzic 2: [3 4 5 3 1 6]

Rodzic 1 ma dwie 2. Wymieniamy starą.

Rodzic 1: [4 1 6 3 2 5]

Rodzic 2: [3 4 5 2 1 6]

Brak powtórzeń: wymiana zakończona, zapisujemy geny potomstwa.

W potomstwie mogą pojawić się duplikaty już istniejących osobników. Duplikaty nie wnoszą nic do bazy genów wszystkie zostają poddane przymusowej mutacji.

Procedura krzyżowania

private void krzyzuj()

// krzyzowanie cykliczne

{

java.util.Random randomGenerator = new Random();

for (int s=jScrollBar2.getValue()/2+1;s<=jScrollBar2.getValue()-2;s++)

{

double x=randomGenerator.nextDouble()*(jScrollBar1.getValue()-1);

int k=(int)x+2;

for(int i=1;i<101;i++)

{

populacja[s][i] = populacja[s-jScrollBar2.getValue()/2+2][i];

populacja[s+1][i]=populacja[s-jScrollBar2.getValue()/2+3][i];

}

boolean ok=false;

while (ok!=true)

{

int z = populacja[s + 1][k];

populacja[s + 1][k] = populacja[s][k];

populacja[s][k] = z;

for (int i = 2; i <= jScrollBar1.getValue(); i++)

{

if ((populacja[s][i] == z) && (i != k))

{

k = i;

ok = false;

break;

}

else

ok=true;

}

}

s++;

}

}

Mutacja

Po wydaniu na świat potomstwa, ok. 50% generacji ulega mutacjom. Mutacji unika najlepiej przystosowany organizm, bo go szkoda.

Permutacja: przestawienie losowo wybranej pary:

Rysunek 20 Mutacja

Metoda odpowiedzialna za Mutację:

private void mutuj(int i)

{

java.util.Random randomGenerator = new Random();

double y=randomGenerator.nextDouble()*(jScrollBar1.getValue()-1);

int y1=(int)y+2;

double z=randomGenerator.nextDouble()*(jScrollBar1.getValue()-1);

int z1=(int)z+2;

int p=populacja[i][y1];

populacja[i][y1]=populacja[i][z1];

populacja[i][z1]=p;

}

Opis ważniejszych metod w applecie

Pobranie ścieżki dostępu do pliku i otwarcie strony na serwerze.

private void strona() {

try

{

AppletContext ac = getAppletContext();

URL ur = new URL(this.getDocumentBase(), "dodaj.php");

ac.showDocument(ur,"miasta");

}

catch(MalformedURLException e)

{

showStatus("URL not found");

}

}

Metoda tworzy strumień (połączenie z serwerem) i pobiera dane o miastach z pliku do tablicy.

private void pobierz()

{

try

{

URL url = new URL(this.getDocumentBase(), "plik.txt");

URLConnection urlConnection = url.openConnection();

dataInputStream = new DataInputStream(new BufferedInputStream( url.openStream() ));

}

catch (MalformedURLException e)

{

e.printStackTrace();

}

catch (IOException e)

{

e.printStackTrace();

}

int i=0;

try

{

String line = null;

while ((line = dataInputStream.readLine()) != null)

{

if ((i>jScrollBar4.getValue()-1)&&(i<jScrollBar4.getValue()+10))miasta[i-jScrollBar4.getValue()]=line;

i++;

}

jScrollBar4.setMaximum(i);

dataInputStream.close();

}

catch (IOException e)

{

e.printStackTrace();

}

jCheckBox1.setText(miasta[0]);

jCheckBox2.setText(miasta[1]);

jCheckBox3.setText(miasta[2]);

jCheckBox4.setText(miasta[3]);

jCheckBox5.setText(miasta[4]);

jCheckBox6.setText(miasta[5]);

jCheckBox7.setText(miasta[6]);

jCheckBox8.setText(miasta[7]);

jCheckBox9.setText(miasta[8]);

jCheckBox10.setText(miasta[9]);

}

Losowanie punktów z określonego zakresu

java.util.Random randomGenerator = new Random();

rndx[1] = randomGenerator.nextDouble();

rndx[1] *= 495;

rndy[1] = randomGenerator.nextDouble();

rndy[1] *= 295;

Przeliczanie współrzędnych

Zakładamy, że Ziemia jest kulą o promieniu 6371km i obwodzie 40000 km. Dane te są „trochę sprzeczne”, bo 2ၰ razy 6371 to 40030,1736.... Jeden stopień na równiku lub południku to 111 km. Możemy sprawdzić: 40000/360 to z dobrym przybliżeniem właśnie 111. Polska leży pomiędzy równoleżnikiem 49⁰ a 54⁰. Wystarczy, że weźmiemy pośredni równoleżnik 52⁰ i policzymy długość: d₅₂ = 2ၰ R cos ၦ, gdzie ၦ = 52⁰, a R jest promieniem Ziemi, R = 6371 km. Zatem d₅₂ = 24645 km, więc jeden stopień na tej szerokości to 68,5 km. Wiemy również, że 1⁰ = 60`. Położenie geograficzne miast jest podawane względem południka 0 w kierunku na wschód i równika z tym, że zarówno idąc na północ jak i na południe stopnie są dodatnie. Teraz wystarczy, że odpowiednio przeskalujemy i przesuniemy dane, aby były widoczne na naszej mapie.

rndx[i]=(Integer.parseInt(jCheckBox1.getText().substring(jCheckBox1.getText().length()-7,jCheckBox1.getText().length()-5))*60+Integer.parseInt(jCheckBox1.getText().substring(jCheckBox1.getText().length()-4,jCheckBox1.getText().length()-2)))*0.39-180;

rndy[i]=2020-(Integer.parseInt(jCheckBox1.getText().substring(jCheckBox1.getText().length()-15,jCheckBox1.getText().length()-13))*60+Integer.parseInt(jCheckBox1.getText().substring(jCheckBox1.getText().length()-12,jCheckBox1.getText().length()-10)))*0.6;

Obliczanie czasu trwania operacji

Początek : long startmil = System.currentTimeMillis();

.

.

Koniec: long stopmil = System.currentTimeMillis();

Wyliczenie: czas+=stopmil-startmil;

Podsumowanie

Na podsumowanie dodam, że nie ma jak na razie złotej reguły na rozwiązanie problemu komiwojażera a wybór jednej czy drugiej metody zależy od wielu czynników. Jednym z nich może być chociażby ilość lub rozmieszczenie punktów. Wiadomo, że jeżeli punkty będą rozmieszczone bardzo blisko siebie po okręgu to wybierzemy algorytm zachłanny on najszybciej znajdzie nam drogę i będzie to po prostu okrąg. Innym czynnikiem może być czas, jaki mamy dany do rozwiązania nie możemy przecież szukać drogi komiwojażerowi kilka lat. Następnym czynnikiem może być chociażby cena takiego wyliczenia. Nie będziemy przecież kupować super szybkich komputerów tylko po to, aby zrobić jak najszybciej zakupy w różnych sklepach. Również dużo do myślenia daje przestrzeń, w jakiej rozmieszczone są punkty. Najłatwiej, kiedy jest to płaszczyzna wówczas wyliczamy odległość Euklidesową, a co gdy jest to walec lub kula tu musimy wyliczać odległość sferyczną. Podobnie komplikuje się położenie punktów w przestrzeni trójwymiarowej wówczas, aby określić położenie musimy podać 3 współrzędne wówczas odległość
. A co z czasoprzestrzenią?

Jeśli chodzi o część praktyczną uważam, że udało mi się na tyle polepszyć algorytm, aby działał on w rozsądnym czasie na tak wolnej maszynie, jaką jest Java. Pewne przyśpieszenie uzyskuję poprzez rezygnację z wyliczania średniej (oceny), poniżej której należy usunąć osobniki oraz znajdowania najlepszego. Uzyskuję to wszystko poprzez sortowanie ustawiając w kolejności od najlepszego rozwiązania. Dodatkowo sortownie to odbywa się tylko do połowy! Gdyż wszystkie słabsze rozwiązania zostaną zastąpione nowym pokoleniem. Nie poszukuję także najlepszego rozwiązania, ponieważ w moim przypadku zawsze będzie na początku posortowanej tabeli. Kolejnym przyśpieszeniem jest rezygnacja ze skomplikowanych algorytmów poszukiwania i łączenia najlepszych rodziców w pary w celu późniejszego ich krzyżowania. W moim algorytmie rodzice są brani kolejno z wcześniej posortowanej tablicy. Z uwagi na to ze niestety nie każdy w domu ma megowe łącze z Internetem nie mogę rozbudowywać programu w nieskończoność i dodawać masy algorytmów, ale obiecuję dodać w przyszłości kilka niespodzianek. W pracy pokazałem kilka najbardziej znanych metod rozwiązywania jednak, co roku ukazuje się na ten temat ponad l00 poważnych publikacji i jeszcze długo problem komiwojażera będzie przedmiotem naukowych badań.

Wykaz załączników

Spis ilustracji

Bibliografia

1. Http://www.alife.pl/

2. Http://tomicki.net/

3. http://www.tsp.gatech.edu/

4. http://www.algorytm.org/

5. http://www.informatyka-pk.piwko.pl/

6. „JBuilder X. Efektywne programowanie w Javie” Autor: Jacek Matulewski

Data wydania: 05/2004

7. „JBuilder. Vademecum profesjonalisty” Autorzy: Michael Landy, Saleem Siddiqui, Jeff Swisher

Tytuł oryginału: “JBuilder Developers Guide” Tłumaczenie: Adam Majczak (rozdział 1 - 9, 30, 31), Tomasz Miszkiel (rozdział 17, 19, 20 - 24), Paweł Rośczak (rozdział 25, 28, 29), Marcin Samodulski (rozdział 10 - 16), Krzysztof Wołowski (rozdział 18, 26, 27)

Data wydania: 01/2004

8. „The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization” Autorzy: E. L. Lawler, Jan Karel Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys

Data wydania: 1985

2

Jakub Łuczak

Informatyka

12632

Prof. Dr hab. Volodymyr Hrytsyk

Definicja problemu, kodowanie zmiennych

Populacja początkowa

Selekcja „naturalna” Osobniki najgorzej przystosowane

(o największym koszcie) wymierają

Osobniki przystosowane na tyle dobrze by żyć -łączą się w pary

Wydają na świat potomstwo o genach odziedziczonych po rodzicach

Pewna liczba osobników poddana jest przypadkowej mutacji

Każdy osobnik z populacji niesie pewien kod genetyczny = zbiór zmiennych funkcji kosztu

Wymiana genów całkiem losowa. Korzystne cechy rodziców będą wzmacniane a słabsze eliminowane przez selekcję naturalną.

Mutacje mają wprowadzać cechy, których nie mają rodzice.

Krzyżowanie genów i mutacje oparte są o generator liczb losowych sterowane selekcją naturalną.

Z macierzy usuwamy wiersz 6-ty i 3-cią kolumnę, oraz blokujemy połączenie 3-6

Blokujemy w macierzy połączenie 6-3

Macierz po usunięciu wiersza 6-go i 3-ciej kolumny, oraz blokowaniu połączenia 3-6

Macierz po redukcji

Macierz po usunięciu wiersza 6-go i 3-ciej kolumny, oraz blokowaniu połączenia 3-6

Macierz po usunięciu 4go wiersza i 6-tej kolumny.

Macierz po zablokowaniu połączenia 4-6.

.

Macierz po usunięciu 4go wiersza i 6-tej kolumny.

Macierz po zablokowaniu połączenia 4-6, oraz redukcji.

Macierz po usunięciu z macierzy 2-giego wiersza i 1-wszej kolumny,

Redukujemy macierz (pierwszy wiersz redukujemy o 2 i pierwszą kolumnę o 1)

Redukujemy macierz: pierwszą kolumnę o 3, i drugi wiersz o 17

---