Temat Pracy Magisterskiej:

„Komputerowy system do badań efektywności meta-heurystyki „System Mrówek” w zakresie optymalizacji dyskretnej.”

Promotor:

Spis treści.

Spis treści.

1. Wprowadzenie

Wiek XX to gwałtowny rozwój nauk związanych z technikami obliczeniowymi. Rozwiązano wiele problemów, które ze względu na złożoność obliczeniową wydawały się nierozwiązywalne. Powstała nowa nauka nazwana „badaniami operacyjnymi”. Jej początki związane są z drugą wojną światową, kiedy w siłach zbrojnych USA i Wielkiej Brytanii zostały utworzone specjalne grupy naukowców w celu przygotowywania różnych wariantów rozwiązań dotyczących organizacji i zabezpieczenia środków dla działań bojowych. Po zakończeniu wojny metody działania badań operacyjnych zostają przeniesione do innych działań ludzkiej działalności. W dniu dzisiejszym metody badań operacyjnych wykorzystuje się w przemyśle, gospodarce rolnej, handlu, transporcie, organizacji służby zdrowia itp.

Ten gwałtowny rozwój badań operacyjnych w bardzo dużym stopniu związany jest z pojawieniem się maszyny nazwanej z biegiem czasu komputerem. Komputer ze względu na swoją moc obliczeniową pozwolił rozwiązywać problemy dużych rozmiarów, potrzebujące dużych ilości rachunków. Niemniej zostało jeszcze wiele problemów, dla których nie znaleziono rozwiązania lub znalezione rozwiązanie jest niezadowalające. Przykładem może być tzw. problem komiwojażera, którego istota przedstawiona będzie w dalszej części pracy. Nauka w dalszym ciągu poszukuje algorytmy, które pozwolą rozwiązywać to zadania w rozsądnym czasie, nawet gdy wielkość zadania jest duża. Praca ta ma na celu sprawdzenia, czy algorytm zwany „System mrówek” może znaleźć zastosowania właśnie do tego problemu.

Jako zagadnienie optymalizacji dyskretnej wybrano asymetryczne zagadnienie komiwojażera z uwagi na:

• Asymetryczne zagadnienie komiwojażera jest szczególnie trudnym zagadnieniem optymalizacji dyskretnej

• W bibliotece zadań testowych TSPLIB znajduje się znaczna liczba testów tego zagadnienia umożliwiająca porównanie otrzymanych rozwiązań za pomocą zaprojektowanych algorytmów z innymi algorytmami.

• Asymetryczne zagadnienie komiwojażera modeluje znaczną liczbę ważnych praktycznych problemów.

2. Podstawowe definicje

Ponieważ praca opiera się głównie na materiałach z konferencji naukowych uznałem za stosowne wyjaśnienie pewnych pojęć, które mogą być pomocne w odpowiednim zrozumieniu dalszej części pracy.

2.1 Graf

Graf G definiujemy jako parę G = (V, E), gdzie V jest zbiorem skończonym, zaś E jest relacją binarną w V. Zbiór V nazywamy zbiorem wierzchołków G, a jego elementy nazywane są wierzchołkami. Relacja binarna E jest nazywana zbiorem krawędzi G, a jej elementy krawędziami.

Rozróżniamy dwa podstawowe rodzaje grafów:

1. 
   Graf nieskierowany, zbiór krawędzi E to zbiór nieuporządkowanych par wierzchołków. Oznacza to, że krawędź jest zbiorem {u, v}, gdzie u, v należą do zbioru V. Jeżeli ponadto u ≠v, tj. graf nie posiada pętli oraz wielokrotnych krawędzi to nazywany jest grafem prostym.

Rys. 1

Na rysunku 1 przedstawiony jest przykład przedstawienia graficznego grafu nieskierowanego. Wierzchołki przedstawiane są jako kółka, krawędzie jako linie.

2. Graf skierowany, to graf gdzie zbiór krawędzi E to zbiór uporządkowanych par wierzchołków. Różnice z grafem opisywanym wcześniej są następujące:

• W tego typu grafie zapisy (u, v) i (v, u) oznaczają dwie różne krawędzie często nazywane łukami.

• W grafach skierowanych mogą pojawić się pętle.

Rys. 2

Na rysunku 2 przedstawiony jest obraz grafu skierowanego. Jak można zauważyć, różnica z rysunkiem 1 kryje się w przedstawieniu krawędzi. W grafie skierowanym przedstawiają je strzałki nie krawędzie.

Dla jasnego przeprowadzenia dalszych rozważań należy wyjaśnić dalsze dwa pojęcia związane z grafem:

• Ścieżka (droga) długości k z wierzchołka u do wierzchołka u' w grafie G=(V, E) jest ciągiem wierzchołków <v₀, v₁, v₂, ..., v_k> takich, że u=v₀, u'=v_k i (v_i-1, v_i) należy do zbioru E dla i=1, 2, ..., k. Długość ścieżki jest liczbą krawędzi ścieżki.

• Graf nieskierowany nazywamy spójnym, jeżeli każda para wierzchołków jest połączona ścieżką.

2.2 Cykl „Hamiltona”

Pojęcie cyklu „Hamiltona”, zwanego marszrutą, rozpatrywano już od przeszło stu lat. Związane jest ono z pojęciem grafu. Formalnie rzecz biorąc, cykl Hamiltona w grafie nieskierowanym G = (V, E) to cykl prosty zawierający wszystkie wierzchołki zbioru V. Graf, który ma cykl Hamiltona, nazywamy hamiltonowskim; w przeciwnym razie niehamiltonowskim.

2.3 Heurystyka

Pojęcie heurystyka jest mało znane, choć popularne są jego różne szczegółowe techniki i metody (a najbardziej intuicyjnie stosowane wskazówki heurystyczne). Trudno jest odnaleźć w literaturze definicje tego słowa. Nie ma go przykładowo w takich dużych opracowaniach encyklopedycznych jak: 30-tomowa Encyclopedia Americana, 29-tomowa Encyclopedia Britannica, 3-tomowa The Canadian Encyclopedia czy też w mniejszych pracach specjalistycznych: Słownik pojęć filozoficznych W. Krajewskiego, Słownik encyklopedyczny. Filozofia - G. Vesey, P. Foulkes.

• Heurystyka: nauka o metodach i regułach rządzących dokonywaniem odkryć i tworzeniem wynalazków.

• Heurystyka: metodologia twórczego rozwiązywania zadań.

• Heurystyka: umiejętność (sztuka) wykrywania nowych faktów i związków między nimi oraz formułowania hipotez (lub tworzenia modeli pełniących rolę hipotez). Jest przeciwieństwem do logiki, która uczy je udowadniać.

• Heurystyka: podejście mające na celu twórcze rozwiązanie problemu, zarówno logicznego, kierowniczego jak i matematycznego (np. rozwiązanie zadania, zbudowanie definicji) szczególnie przez eksperyment, często przy pomocy metody prób i błędów, odwoływania się do analogii, uogólnień.

• Heurystyka: metoda nauczania ułatwiająca i zachęcająca ucznia do odkrywania przez niego wiedzy w sposób aktywny i samodzielny.

• Heurystyka: program wszechstronnego i elastycznego uprawiania filozofii, traktującego na równi wiele idei heurystycznych właściwych dla różnych nurtów filozofii, w których zakłada się, że aby trafnie mówić o świecie należy znać i wykorzystywać znajomość zasad, którymi kieruje się myślenie filozoficzne i postęp wiedzy.

• Heurystyka: zbiór efektywnych reguł postępowania oraz wskazówek rozwijających twórcze zdolności jednostek oraz zespołów ludzkich.

• Heurystyka: proces poszukiwania i badania nowych form nauczania i szkolenia, w szczególności uwzględniających zdobywanie wiedzy w sposób uznawany za naukowy oraz poprzez intuicję.

• Heurystyka: umiejętność wyszukiwania informacji o literaturze i źródłach historycznych oraz jest to zbiór reguł wskazujących, jak zbierać i systematyzować materiały badawcze w historii.

• Heurystyka: zbiór odkrywczych technik pozwalających na szybkie i skuteczne odnalezienie rozwiązań problemów dających się sformułować w sposób ilościowy, wykorzystujących przeważnie metody samouczenia się maszyn (np. poprzez sprzężenie zwrotne) w celu poprawy wyników.

W Badaniach Operacyjnych bardzo często wykorzystywane jest pojęcie algorytmu heurystycznego. Odnosi się ono do algorytmów wykorzystujących metody pozwalające odkrywać rozwiązania złożonych problemów w oparciu o próby zrozumienia i odtworzenia niektórych czynności umysłu ludzkiego.

U podstaw tego typu algorytmów, leży założenie, że dla zadań, w których mamy do czynienia z dużymi przestrzeniami rozwiązań, ważne jest wczesne odrzucenie nieobiecujących kierunków przeszukiwania. Zapewnia to ogromne oszczędności na kosztach obliczeniowych, a w rezultacie przyspiesza znalezienie rozwiązania. Większa skuteczności tych metod polega na dostosowaniu kierunków poszukiwania do potrzeb rozwiązywanego problemu. W tym celu wykorzystuje się pewne informacje o zadaniu. Heurystyka to wszelkie metody pozwalające algorytmowi poszukującemu rozwiązania pójść "na skróty". Skuteczności kroków heurystycznych nie można w pełni udowodnić teoretycznie, można jedynie pokazać doświadczalnie ich trafność.

Algorytmy tego typu odegrały bardzo ważną role w rozwoju nauk związanych z obliczeniami komputerowymi. W obecnym czasie zastępowane są innymi grupami algorytmów, np. rozważanymi w tej pracy mata-heurystykami.

2.4 Meta-heurystyka

Dla wielu problemów NP-zupełnych nauka nie znalazła jeszcze algorytmu pozwalającego na znalezienie optymalnego rozwiązania w czasie umożliwiającym zastosowanie algorytmu w życiu codziennym. Dla wielu problemów zaproponowano zdroworozsądkowe algorytmy dostarczające w krótkim czasie możliwe do przyjęcia rozwiązanie, które nie zawsze jest rozwiązaniem optymalnym. Algorytmy takie wykorzystują wiedzę o specyfice problemu i na tej podstawie znajdują rozwiązanie, które może być wykorzystane do danego zastosowania.

W obecnym czasie, główna uwaga naukowców zajmujących się Badaniami Operacyjnym skoncentrowana jest na innej, nowej klasie algorytmów znanej meta-heurystyką. Meta-heurystyka to raczej swoistego rodzaju szkielet algorytmu, który może być modyfikowany i używany do konkretnych zastosowań. Przykładem meta-heurystyk są algorytmy:

• symulowane wyżarzanie,

• algorytmy genetyczne

• algorytm tabu-serch.

Meta-heurystyki bardzo często inspirowane są obserwacją przyrody. Wymienione wcześniej algorytmy zainspirowane były kolejno: analizą fizycznego procesu wyżarzania, Darwinowską teorią ewolucji i sprytnym zarządzaniem pamięci. Algorytm „system mrówek”, któremu poświęcona jest ta praca także należy do klasy algorytmów meta-heurystycznych.

2.5 Złożoność obliczeniowa algorytmów

Klasyfikując różne problemy, możemy na podstawie teorii matematycznych podzielić je na rozwiązywalne i nierozwiązywalne. Jednak to, co jest teoretycznie rozwiązywalnym zadaniem, w praktyce może okazać się nie do rozwiązania w realnym czasie (może to zająć miliony lat nawet najszybszym superkomputerom). Dlatego z praktycznego punktu widzenia zadania zostały podzielone na klasy:

• KLASA P (ang. polynomial class ) - klasa problemów rozwiązywalnych za pomocą deterministycznej maszyny Turinga w czasie wielomianowym. Oznacza to, że rozwiązanie zadania należącego do tej klasy zależy od pewnej wielkości N w sposób potęgowy, czyli N do którejś potęgi (N symbolizuje tu rozmiar zadania).

• KLASA NP (ang. nondeterministic polynomial class ) - klasa problemów rozwiązywalnych za pomocą niedeterministycznej maszyny Turinga w czasie wielomianowym. W tej klasie rozwiązanie zależy od N w sposób wykładniczy, czyli jakaś liczba do potęgi N. Wśród tej grupy problemów wyróżnia się te najtrudniejsze, nazywane NP-zupełnymi.

Trudność rozwiązywania problemów NP-zupełnych polega na tym, że liczba obliczeń, jakie trzeba wykonać, by znaleźć rozwiązanie, gwałtownie rośnie wraz z rozmiarem problemu. I tak, jeśli pewien mały problem tej klasy daje się rozwiązać w ciągu kilku minut, to już ten sam problem dwukrotnie większy można rozwiązywać kilkaset lat.

Omówiona w ten sposób złożoność obliczeniowa nazywana jest czasową złożonością algorytmów (ang. Time Complexitity of an Algorithm). Jej definicje można przedstawić jako funkcję złożoności czasowej, przyporządkowującą każdej wartości rozmiaru instancji I maksymalną liczbą elementarnych kroków (lub jednostek czasu) maszyny cyfrowej potrzebnych do rozwiązania za pomocą algorytmu A instancji o tym rozmiarze, to znaczy funkcję:

f_A(n) = max { t : (t jest liczbą elementarnych kroków maszyny cyfrowej niezbędną dla rozwiązania instancji I należącej do D_n)^(n = N(I))},

gdzie D_n jest zbiorem instancji problemu decyzyjnego a n jest rozmiarem każdej instancji.

Zwykle funkcje czasowej złożoności obliczeniowej algorytmu f_A(n) ocenia się z dokładnością do rzędu.

Drugim rodzajem złożoności obliczeniowej jest tzw. pamięciowa złożoność obliczeniowa algorytmu (ang. Space Complexitity of an Algorithm) rozumiana jako jest to rozmiar pamięci urządzenia liczącego niezbędny do wykonania algorytmu, wyrażony w funkcji rozmiaru problemu. Tego typu złożoność nie jest jednak przedmiotem rozważań w tej pracy i nie będzie rozpatrywana w dalszej jej części.

3. Opis rozważanego problemu

Jak zostało wspomniane we wstępie, w tej pracy zostanie przeprowadzone rozważanie na temat możliwości zastosowania algorytmu zwanego „System mrówek” dla znalezienia rozwiązania problemu zwanego „Problemem komiwojażera”. W tym rozdziale przedstawiony zostanie opis tego zagadnienia.

3.1 Problem komiwojażera

Komiwojażer, czyli obwoźny sprzedawca towarów ustawicznie boryka się z problemem, jak w najkrótszym czasie i w najtańszy sposób odwiedzić wszystkich znajdujących się w różnych miastach klientów i znaleźć się w końcu w punkcie wyjścia. Oczywistym jest fakt, że dwukrotna wizyta u jednego klienta w ciągu danego cyklu jest zbyteczna, a przede wszystkim nieekonomiczna i dlatego należy ja wykluczyć.

Problem komiwojażera można przedstawić za pomocą grafu. Graf przedstawiający problem zawiera zbiór V (N=|V|) wierzchołków, reprezentujących odwiedzane przez sprzedawcę miasta, oraz zbiór łuków E łączące wszystkie wierzchołki N, reprezentujące drogi między miastami. Jeżeli przez d_ij oznaczymy miarę oznaczającą długość łuku (i,j) należącego do zbioru E, będzie on reprezentował odległość miedzy miastami i oraz j. Rozwiązanie Problemu Komiwojażera polega na znalezieniu minimalnej wartości cyklu Hamiltona dla grafu G = (V, E). Cykl ten jest zamknięty, znajduje się w nim każdy wierzchołek oraz każdy wierzchołek znajduję się w nim tylko jeden raz.

Wyróżniamy jeszcze „Asymetryczny Problem Komiwojażera”, charakteryzujący się tym, że d_ij ≠ d_ji. Graf reprezentujący ten problem jest grafem skierowanym.

W opracowaniach naukowych „Problem komiwojażera” oznaczany jest symbole TSP. Skrót ten wzięty jest z angielskiej nazwy problemu, tzn. Traveling Salesman Problem. „Asymetryczny Problem Komiwojażera” reprezentowany jest symbelem ATSP (Asymmetric Traveling Salesman Problem).

Podsumowując opis „Problemu Komiwojażera”, jego definicję można przedstawić następująco:

TSP Niech: V = {a, ..., z } zbiór wierzchołków grafu odpowiadających miastom, które ma odwiedzić podróżujący sprzedawca E = { (r, s): r, s ∈ V } zbiór krawędzi grafu, odpowiadających drogom pomiędzy miastami d(r, s) = d(s, r) , (r, s) ∈ A miara odpowiadająca odległością pomiędzy poszczególnymi miastami Rozwiązanie problemu TSP polega na znalezieniu minimalnego pełnego cyklu zamkniętego, w którym każde miasto odwiedzane jest tylko raz. Jeżeli każde miasto r ∈ V podane jest poprzez jego współrzędne {xr, yr} oraz miara d(s, r) jest miarą Euklidesową pomiędzy miastami r i s, mówimy wtedy, że rozpatrujemy „Euklidesowy Problem Komiwojażera”. ATSP Jeżeli spotykamy się z problemem różniącym się od opisywane powyżej tylko tym, że d(r, s) ≠ d(s, r) wtedy problem oznaczany symbolem TSP staje się Asymetrycznym Problemem Komiwojażera (ATSP).

Definicja 1

Z punktu widzenia procesu optymalizacji dyskretnej zagadnienie ATSP jest znacznie trudniejszym problemem niż symetryczne zagadnienie TSP.

3.2 Zastosowanie praktyczne

W tym paragrafie podane zostaną przykłady zastosowania problemu komiwojażera w życiu codziennym. Przykłady te zaczerpnięte są z książki profesora Bogusława Filipowicza „Badania Operacyjne”. Trzeba jednak zauważyć, iż nie są to jednak jedyne przykłady zastosowań tego problemu.

3.2.1 Optymalizacja drogi w transporcie

Spotykanym w życiu codziennym problem optymalizacji drogi formalizowanym w postaci problemu komiwojażera jest dobór trasy dla ciężarówki zaopatrującej sklepy danego regionu w produkty pobrane w magazynie. Najbardziej reprezentacyjnym przypadkiem jest tu działalność firm kurierskich. Zasada działania tych firm opiera się na bardzo sprawnie działającej sieci kurierów obsługujących przydzielone im regiony. Optymalizacja drogi w rezultacie może dać nie tylko zmniejszenie kosztów własnych lecz również zredukować liczbę kurierów potrzebnych do realizacji zamówień firmy. Zauważamy, że optymalizować można bezpośrednio koszty transportu przeliczane np. na odległość według liniowej funkcji lub też minimalizować czas trwania przejazdów i tą drogą osiągnąć zwiększenie efektywności przedsiębiorstwa.

Kurier i dostawca muszą po skończeniu działania wrócić do bazy, aby podjąć się kolejnych prac i nie jest w ich interesie pojawienie się w tym samym punkcie dwa razy podczas jednego cyklu. Punkty do odwiedzenia to w interpretacji grafowej wierzchołki grafu, odcinki (etapy trasy) łączące poszczególne punkty to krawędzie grafu. Każdej krawędzi przyporządkowuje koszt przemieszczenia się między punktami będącymi wierzchołkami grafu. Ponieważ dążymy do minimalizacji kosztów, krawędziom reprezentującym niemożliwe do realizacji lub nie istniejące w rzeczywistości połączenia, przyporządkowuje się koszt nieskończenie wielki.

Problem ten staje się coraz bardziej aktualny w dobie rozwoju e-commers. Planowane jest powstanie wielu firm, których działalność polegała będzie na dostarczaniu do klienta towarów zamawianych przez Internet. Problem opisywany w tym paragrafie będzie dla nich jakże aktualny.

3.2.2 Optymalizacja drogi w elektronice i mechanice

Bardzo ważnym zastosowaniem metod optymalizacji drogi jest wykonanie otworów montażowych i lutowanie podzespołów elektronicznych. Elementy wykonawcze tzn. wiertła i lutownice przemieszczające się za pomocą specjalnego układu napędowego. Ponieważ są to układy mechaniczne ich prędkość działania jest ograniczona zarówno przez koszty wykonania automatu jak i wytrzymałość elementów, z których są wykonane. Istotnym czynnikiem w produkcji wieloseryjnej jest czas obróbki jednego detalu.

Sposób postępowania przy opisie tego problemu jako zagadnienia komiwojażera jest analogiczny jak dla przypadku dostawcy, tzn.:

• numerujemy kolejne punkty obróbki,

• określamy odległości lub czasy przemieszczenia narzędzie pomiędzy wszystkimi punktami

• konstruujemy macierz odległości

W masowej produkcji zysk z optymalizacji ma swoje źródło w skończonym czasie wykonania detalu, ograniczeniu energochłonności oraz zmniejszeniu zużycia mechanicznego automatu.

3.2.3 Optymalizacja drogi w systemach produkcyjnych

W elastycznych systemach produkcyjnych, jednym z elementów składowych jest system transportu detali pomiędzy stanowiskami roboczymi. Jak wiadomo, spotyka się na ogół trzy rodzaje sieci transportowych: sieć drabinkowa, mieszana oraz zamknięta w postaci pętli. Funkcjonowanie tej ostatniej może być zoptymalizowane za pomocą zagadnienia komiwojażera.

3.2.4 Optymalizacja drogi w systemach telekomunikacyjnych

Ostatni z przykładów zastosowania problemu komiwojażera dotyczy systemów telekomunikacyjnych. W sieci komputerowej typu „token ring” wymagane jest spełnienie warunku zamknięcia pętli łączącego wszystkie komputery. Koszty położenia jednego metra kabla i jego konserwacja mogą być zależne liniowo i odczytywane bezpośrednio z macierzy odległości. W przypadku zróżnicowania kosztów jednego metra instalacji macierz kosztów uzyskuje się na podstawie odpowiedniej wyceny odcinków między stacjami roboczymi i serwerami. Cena połączenia w obie strony, podobnie jak odległość jest zazwyczaj taka sama.

Rozwiązując problem komiwojażera obok zysku finansowego można poprawić również możliwości techniczne sieci. Wynika to z faktu, że prędkość propagacji sygnału w przewodach jest skończona, co nakłada ograniczenia na prędkość pracy takiej sieci oraz jej zasięg. Wyznaczenie najkrótszego połączenia pozwala na poprawę obu tych parametrów.

3.3 Metody rozwiązywania problemu komiwojażera

Ponieważ problem komiwojażera należy do problemów NP.-zupełnych, nie jest łatwo znaleźć algorytm rozwiązujący przy dużych rozmiarach problemu. Jednak ze względu na pojawianie się z życiu codziennym zadań łatwo sprowadzalnych do tego problemu, naukowcy zostali zmuszeni do prób opracowania metody rozwiązania problemu. Przykładem takich prób są metody:

• Metoda Estemana bazująca na algorytmie węgierskim

• Metoda Little'a bazująca na algorytmie podziału i ograniczeń

• Metoda kompozycji łacińskiej

Także autorzy meta-heurystyk przeprowadzali dyskusje nad możliwością zastosowania ich pomysłu do rozwiązywania tego problemu. W dalszej części tej pracy przedstawiona zostanie meta-heurystyka Dorigo „System mrówek” oraz moja próba realizacji tej meta-heurystyki właśnie do realizacji problemu komiwojażera.

4. Algorytm „System mrówek”

Za twórcę algorytmu zwanego „System Mrówek” uważany jest M. Dorigo. Zaproponował on nowe wielo-czynnikowe podejście do trudnych problemów optymalizacji kombinatorycznej. Algorytm ten wzorowany jest, jak większość metaheurystyk, na podstawie obserwacji przyrody. Dorigo przez długi okres czasu przyglądał się strukturze mrowiska.

Mrówki są owadami żyjącymi w koloniach, w których każdy osobnik ma dokładnie wyznaczone miejsce i pozycje. Ich zachowanie skierowane jest bardziej w kierunku przeżycia całej kolonii niż jako indywidualnej jednostki. Insekty przyciągnęły uwagę wielu naukowców ze względu na osiągnięcie wysokiego poziomu strukturalnego koloni, zwłaszcza w porównaniu ze względną prostotą jednostek indywidualnych.

Szczególną uwagę Dorigo zwróciły pracę biologów opisujących osobniki zajmujące się transportem pożywienia do mrowiska. Można znaleźć w nich stwierdzenie, że droga którą się udają do mrowiska jest najkrótszą jaką można dostać się z miejsca gdzie znajduje się pożywienia do mrowiska. Realizowane jest to dzięki temu, że w czasie przemierzanie drogi między źródłem pożywienia a gniazdem, mrówki składają na ziemi substancje zwana feromonem. Insekty te mają zdolność wyczuwania feromonu i w chwili wybierania drogi wybierają te, która oznaczona jest silnym stężeniem feromonu.

Ślad feromonu pozwala mrówkom na odnalezienie drogi z gniazda do źródła pożywienia i odwrotnie. Ponadto ten ślad może być używany przez inne mrówki do odnalezienia miejsca przechowywania żywności odnalezionej przez inne mrówki. W materiałach biologów opisany jest eksperyment wykazujący, że to zachowanie związane ze śladem feromonu jest przyczyną pojawienia się najkrótszych ścieżek. To znaczy gdy więcej ścieżek jest dostępnych z gniazda do źródła jedzenia , kolonia mrówek jest w stanie eksploatować ślady feromonu pozostawione przez inne mrówki w celu odkrywania najkrótszej drogi prowadzącej od gniazda do źródła jedzenia i z powrotem.

Ilustracją obserwacji biologów są umieszczone poniżej rysunki.

Rys. 3

Rysunek 3 przedstawia przemieszczającą się kolonię mrówek miedzy mrowiskiem a miejscem gdzie znalezione zostało pożywienie. Linia znajdująca się na rysunku ma obrazować pozostawiany przez owady feromon. Widzimy, że przemieszczające się mrówki, poruszają się wzdłuż linii, utworzonej z substancji chemicznej.

Rys. 4

Na rysunku 4 uwidocznione jest umieszczenie na linii feromonu przeszkody. Przeszkoda to uniemożliwia owadom dalsze poruszanie się po najkrótszej drodze miedzy dwoma punktami. W tym momencie rozpoczyna się poszukiwanie najkrótszej drogi do obejścia przeszkody.

Rys. 5

Na rysunku 5 widzimy początkowy losowy wybór drogi przejścia łańcucha mrówek. Pozostawiają one z dwóch stron fenemon, który będzie wykorzystany przez następne osobniki do wyznaczenia krótszej drogi.

Rys. 6

Stan końcowy przedstawiony jest na rysunku 6, gdzie droga pokazana na rysunku, jako droga nad przeszkodą, okazała się krótsza, feromon pozostawiony na tej ścieżce wolniej „parował”. Ślad pozostawianej substancji chemicznej okazywał się silniejszy właśnie na tej drodze, ponieważ jest ona krótsza. Powodowało to, że mrówki poruszające się później chętniej wybierały właśnie tę ścieżkę. Ślad feromonu stawał się coraz mocniejszy, aż wszystkie mrówki poruszały się tędy.

Należy też zauważyć, że ścieżka zostaje wybrana, nawet gdy alternatywna droga jest tej samej długości. Te prawidłowość zaobserwowano podczas następnego doświadczenia.

Rys. 7

Jak widać na rysunku 7, kolonia mrówek i źródło jedzenia zostały odgrodzone czymś co można określić jako binarny most. Każda z gałęzi tego mostu była tej samej długości. Mrówki pozostawiono tak, aby mogły swobodnie poruszać się między źródłem pożywienia a gniazdem i obserwowano ilość mrówek wybierających jedną z dwóch gałęzi.

Wykres 1

Wyniki doświadczenia widoczne są na wykresie 1. Widać tam, że po okresie przejściowym, w którym miały miejsce pewne wahania, mrówki zaczęły gromadzić się na tej samej (górnej) ścieżce.

Powodem takiego zachowania mrówek jest to, że początkowo nie ma feromonu na żadnej z gałęzi, które wybierane są z tym samym prawdopodobieństwem. Wahania w okresie przejściowym powodują, że kilka mrówek wybiera górną gałąź. Powoduje to zwiększenie ilości feromonu na tej gałęzi co z kolei stymuluje inne mrówki do jej wybrania itd. Należy jednak zauważyć, że przy powtórzeniu eksperymentu od początku, tak samo prawdopodobnym jest wybranie przez mrówki drugiej gałęzi.

Wydaje się być interesującym fakt że pomimo, iż każda z mrówek ma zdolność rozwiązywania problemów, tj. odnajdywanie ścieżki pomiędzy pojemnikiem jedzenia a gniazdem to dopiero kolonia mrówek charakteryzuje się zdolnością „odnalezienia najkrótszej drogi”. Również warto zaznaczyć, że mrówki zachowują się tak specyficznie, używając prostej formy pośredniej komunikacji za pośrednictwem składowania feromonu, zwanej stigmergy. Nazwa ta zaczerpnięta została z pracy pana Grass'e „La reconstruction ...”, która traktuje o innej społeczności owadów, tzn. termitów. W swojej pracy, Grass'e zdefiniował stigmery jako „stymulowanie robotników poprzez przedstawianie tego co osiągnęli”. W rzeczywistości Grass'e zaobserwował, że termity są w stanie zareagować na tzw. „ważne bodźce”, które uaktywniają genetycznie zakodowaną reakcje. W przypadku insektów stadnych, których zarówno mrówki jak i termity są najlepszym przykładem, skutki takich reakcji mogą być kolejnym ważnym bodźcem dla insektów, które je wyprodukowały jak i dla całej koloni. Takie wytworzenie nowego bodźca może być określone jako forma koordynacji działań i interpretowane jako forma komunikacji pośredniej. Na tej podstawie Grass'e zdefiniował stigmery jako środki komunikacji, które różnią się od innych dwoma aspektami:

1. Fizyczny charakter informacji składanej przez komunikujące się insekty

2. Miejscowy charakter składanej informacji, która może być udostępniona insektom, które odwiedzają miejsce, z którego informacja wyszła (lub sąsiedztwo tego miejsca).

Tak przedstawiona definicja dokładnie pasuje do sposobu komunikacji mrówek poprzez feromon składany przez nie na ziemi podczas przemieszczania się.

Opisane powyżej zachowanie zostało zaobserwowane eksperymentalnie, jednakże eksperymenty te zostały przeprowadzone w bardzo ograniczonych warunkach. Wysunięta na podstawie wyników teoria jest bardzo spójna, brakuje jednak formalnego dowodu na to, iż odnajdywanie najkrótszej drogi uzyskiwane jest przez feromon. Pojawiły się publikacje inaczej interpretujące wyniki opisywanych wcześniej doświadczeń i przypisujące odnajdywanie najkrótszej drogi przez mrówki wskazówkami wizualnymi.

Dorigo przychylił się jednak do opinii większości i na podstawie obserwacji biologów oraz swoich przemyśleń, zaproponował sposób znajdowania rozwiązania problemów NP-zupełnych wykorzystujący system agentów, zwanych właśnie mrówkami. Idea algorytmu polega na wykorzystaniu kolonii mrówek, z których każda pozostawia ślad na danej krawędzi grafu w postaci substancji chemicznej. Jej ilość, podobnie jak w biologicznej koloni tych owadów, zależy od wartości rozwiązania znalezionego przez mrówkę. Istotne jest to, że ów ślad na danej krawędzi sumuje się od każdej mrówki i ulega parowaniu w czasie dyskretnym. Widać więc, że algorytm ten jest wzorowany na opisywanych wcześniej obserwacjach.

4.1 Opis matematyczny algorytmu

W chwili t=0 wszystkie mrówki znajdują się w bazie, a wszystkie krawędzie (i,j) mają przypisane niewielkie, początkowe wartości (dobrane eksperymentalnie) śladu feromonu τ_ij(0) równe c.

W chwili t każda mrówka wybiera losowo węzeł grafu, do którego udaje się w chwili następnej t+1. W trakcie pojedynczej iteracji algorytmu wyznaczone są przemieszczenia wszystkich m mrówek w czasie przedziału czasu (t, t+1). Jeden cykl pracy algorytmu składa się z n takich iteracji. Na końcu cyklu każda mrówka znajduje rozwiązanie problemu. Wówczas wielkość śladu na krawędziach jest modyfikowana zgodnie z formułą:

τ( t+1 ) = ρ ∗ τ_ij( t ) + Δτ( t ), (1)

gdzie ρ, 0<ρ<1, jest współczynnikiem takim, że (1-ρ) określa stopień „zanikania” śladu w przedziale czasu (t, t+1), zaś:

(2)

jest wzorem określającym przyrosty śladu, a Δ τ_ij^r (t) jest wielkością kładzionego na krawędzi (i, j) przez mrówkę r w przedziale czasu (t, t+1).

Wartość ta jest obliczana zgodnie z formułą:

(3)

Wartość górna uzyskiwana jest w przypadku, gdy mrówka r poruszała się po krawędzi (i, j) w przedziale czasu (t, t+1) gdzie Q jest stałą, a L(r) jest kosztem rozwiązania znalezionego przez mrówkę r. W przeciwnym przypadku uzyskiwana jest wartość dolna.

Można więc zauważyć, że mrówki, które znalazły rozwiązanie o wyższym koszcie, układają mniejszą „ilość” śladu na krawędziach, po których przechodzą. W rezultacie krawędzie te są nie faworyzowane przy kolejnych etapach obliczeniowych.

Podczas poszukiwania rozwiązania, mogą pojawić się dodatkowe ograniczenia, np. mrówka r nie może odwiedzić żadnego wierzchołku grafu więcej niż jeden raz. Aby spełnić taki wymogi, wprowadza się listy tabu(r) oraz listy allowed(r). Pierwsza lista zawiera węzły odwiedzone przez mrówkę r w chwili czasu t, druga zawiera pozostałe dostępne węzły. Przy wyborze węzła, do którego ma przejść w chwili t+1, brane są pod uwagę węzły znajdujące się jedynie na liście allowed(r) danej mrówki. Na końcu każdego cyklu listy tabu(r) są wykorzystywane do pobrania rozwiązań znalezionych przez mrówki. List te są zerowane przed rozpoczęciem każdego cyklu.

Prawdopodobieństwo przejścia mrówki r znajdującej się w węźle i do węzła j w chwili czasu t+1 jest podane wzorem:

(4)

gdzie:

τ(i,j) - ilość feromonu na drodze od miasta i do miasta j

η(i,j) - definiowana dowolnie funkcja, w której argumentem jest odległość pomiędzy miastami i oraz j. W opisywanym w późniejszych rozdziałach zaprojektowanym systemie komputerowym zastosowano funkcję f(x) = 1/x, czyli proporcjonalność odwrotną.

J_k(r) - lista dozwolonych przejść dla mrówki r w chwili czasu t+1.

Wzór ten jest jednak modyfikowany w zależności od rozwiązywanego problemu. Pojawiające się w nim parametry α i β pozwalają kontrolować relatywny wpływ wielkości śladu i innych wartości przy wyborze docelowego węzła przemieszczenia.

Pseudo-kod rozpatrywanego algorytmu jest następujący:

: ustaw pozycje startowe algorytmu : ustaw początkową wartość śladu dla wszystkich krawędzi τ(i,j) := C dla (i, j) ∈ E for iteracje := 1 do IT for r := 1 do m for krok := 1 do n if ograniczenia nie przekroczone : określ prawdopodobieństwo P(i,j) wylosowania krawędzi (i,j) : losuj następną krawędź dla mrówki r wg rozkładu P : modyfikuj listę tabu(r) dla krawędzi end end end : policz wartość funkcji celu dla rozwiązania określonego przez drogę każdej mrówki w oparciu o listę tabu( r ) : określ najlepsze rozwiązanie w populacji : policz przyrost śladu dla Δτ^kij( t ) dla każdej krawędzi ( i, j ) od każdej mrówki k : oblicz parowanie śladu i dodaj aktualne przyrosty : wyczyść listy tabu (r) : ustaw mrówki na pozycjach startowych : zapisz najlepsze rozwiązanie i zapis symboliczny jego grafu w tablicy best_graf end

Definicja 2

Algorytm może zawierać także pewne zmienne odpowiedzialne za wizualizacje otrzymanych wyników. Nie jest to jednak część meta-heurystyki tylko już konkretnej realizacji algorytmu.

4.2 Złożoność obliczeniowa algorytmu „System mrówek”

Oszacowanie złożoności obliczeniowej algorytmu, jest problemem stosunkowo łatwym. Załóżmy, że ilość iteracji oznaczona w definicji 2 przez IT jest równa l. Złożoność obliczeniowa jednej iteracji zdeterminowana jest pętlami FOR. Pojedyncza mrówka porusza się w czasie O (n² m), więc złożoność całego algorytmu jest równa T(n) = l*n²* m.

gdzie

• l - ilość iteracji

• n - wielkość problemu

• m - ilość mrówek.

4.3 Porównanie dwóch rodzajów mrówek

W meta-heurystycznej optymalizacji kolonii mrówek, kolonia sztucznych mrówek współpracuje w celu osiągnięcia rozwiązania problemu trudnej optymalizacji dyskretnej. Współpraca ta jest kluczowym czynnikiem algorytmu. Właściwe rozwiązanie problemu może być wyłonione tylko na drodze poprawnej interakcji i współpracy między agentami.

Sztuczne mrówki mają podwójny charakter. Z jednej strony wzorowane są na zachowaniu kolonii prawdziwych mrówek w odnalezieniu najlepszego rozwiązania. Z drugiej zaś wzbogacone zostały pewnymi umiejętnościami, których nie zaobserwujemy w ich naturalnych odpowiedników. Podejście takie wydaje się rozsądne ponieważ sprawia, że są bardziej skuteczne i sprawne w rozwiązywaniu problemów.

Postaram się teraz pokazać podobieństwa i różnice pomiędzy sztucznymi a prawdziwymi mrówkami. Do podobieństw należy zaliczyć:

• Wykorzystanie kolonii współpracujących jednostek - podobnie jak kolonie prawdziwych mrówek, algorytmy mrówkowe wykorzystują populacje zgodnych jednostek współpracujących wspólnie w celu odnalezienia rozwiązania określonego zadania. Pomimo, że każda mrówka jest w stanie znaleźć rozwiązanie indywidualnie (jak prawdziwa mrówka może znaleźć ścieżkę pomiędzy mrowiskiem a jedzeniem), rozwiązanie wysokiej jakości jest wynikiem współpracy pomiędzy każdą z jednostek.

• Szlak feromonu dla miejscowej komunikacji - sztuczne mrówki modyfikują pewne aspekty swojego środowiska tak samo jak robią to prawdziwe mrówki. Podczas gdy prawdziwe mrówki składają w odwiedzanym miejscu substancje chemiczną zwaną feromonem, sztuczne mrówki zmieniają informacje numeryczną lokalnie gromadzoną w miejscu, które odwiedzają. Ta informacja bierze pod uwagę bieżącą historię (dokonania mrówki) i może być odczytana przez każdą inną mrówkę mającą dostęp do tego miejsca. Zwykle w algorytmach mrówek występuje także mechanizm wyparowywania, zbliżony do wyparowywania prawdziwego feromonu. Pozwala to kolonii mrówek na powolne zapominanie historii tak, aby mogły skierować swoje poszukiwania w nowym kierunku bez obciążania rozumowania przeszłymi decyzjami.

• Szereg miejscowych ruchów w celu odnalezienia najkrótszej drogi - zarówno sztuczne jak i prawdziwe mrówki mają wspólne zadanie: odnalezienie najkrótszej (przy minimalnym koszcie) drogi łączącej gniazdo z miejscem gdzie znajduje się jedzenie. Prawdziwe mrówki nie skaczą, tylko przechodzą przez sąsiadujące części ziemi. Tak samo czynią sztuczne mrówki przemieszczając się krok po kroku przez „ sąsiadujące tereny” problemu. Oczywiście dokładne definicje miejsc i sąsiedztwa są specyficzne dla problemu.

• Zasada stochastycznej decyzji korzystającej z miejscowej informacji i brak przewidywania - sztuczne mrówki , tak jak i prawdziwe stosują zasadę prawdopodobieństwa do podjęcia decyzji o wybraniu miejsca następnego ruchu. Zasady, według których wybierają drogę wykorzystują tylko miejscową informacje i nie przewidują przyszłego położenia, są to więc zasady wyłącznie lokalne zarówno w czasie jak i w przestrzeni. Są one zarówno funkcją głównej informacji reprezentowanej przez specyfikę problemu (struktura ziemi dla prawdziwych mrówek) jak i miejscowych modyfikacji w środowisku ( szlak feromonu) wywołanych przez wcześniejsze mrówki.

Oprócz wymienionych powyżej podobieństw istnieją także czynniki różniące prawdziwe mrówki od sztucznych. Zaliczamy do nich:

• Sztuczne mrówki żyją w świecie dyskretnym a na ich ruchy składają się przemieszczenia z miejsc dyskretnych w miejsca dyskretne.

• Sztuczne mrówki posiadają pamięć poprzednich dokonań mrówek

• Sztuczne mrówki składają feromon, którego ilość jest funkcją zależną od jakości znalezionego rozwiązania

• Określenie czasu w składowaniu feromonu jest zależne od problemu i często nie odzwierciedla zachowania prawdziwych mrówek, np. w wielu przypadkach sztuczne mrówki uaktualniają szlak feromonu dopiero po odnalezieniu rozwiązania.

• W celu poprawy efektywności całego systemu kolonia mrówek, algorytm może być wzmocniony dodatkowymi mechanizmami takimi jak: przewidywania, optymalizacja lokalna, powrót szlakiem itd., których nie posiadają prawdziwe mrówki.

4.4 Optymalizacja badanego algorytmu

Po okresie wstępnego zafascynowania możliwościami algorytmu mrówkowego stwierdzono, że algorytm „System Mrówek” może być raczej stosowany tylko jako wstępne poszukiwanie rozwiązania. badanego problemu. Gdy potrzebna jest duża efektywność przy rozwiązywaniu problemów kombinatorycznej optymalizacji NP- zupełnej algorytm ten jest raczej marny w porównaniu z innymi podejściami. Zaproponowane zastały pewne rozszerzenia i ulepszenia, mające na celu poprawy efektywności działania algorytmu. W tym punkcie zostaną przedstawione przykładowe rozszerzenia.

4.4.1 System Koloni Mrówek (ang. Ant Colony System - ACS)

Modyfikacja ta, zastała zaproponowana przez samych twórców algorytmu. Sami autorzy stwierdzili, że „System Koloni Mrówek” jest w pewnym sensie algorytmem prostszym i z biegiem czasu stał się przez nich preferowanym. Różni się on od algorytmu opisywanego wcześniej trzema głównymi aspektami:

• Korzysta z bardziej agresywnej zasady wyboru

• Feromon dodawany jest do łuków należących do globalnego rozwiązania

• Gdy mrówka korzysta z łuku (i, j) do przemieszczenie się, usuwa z łuku trochę feromonu.

Poniżej przedstawiamy bardziej szczegółowo te modyfikacje.

Konstrukcja trasy:

W opisywanej modyfikacji, mrówki wybierają kolejne wierzchołki grafu wykorzystując zasadę pseudo-przypadkowo-proporcjonalnego wyboru (ang. pseudo-random-proportional action choice rule). Polega ona na tym, że gdy mrówka k znajduje się w wierzchołku i musi losowo wybrać jedna z dwóch możliwości:

• Przejście z prawdopodobieństwem q₀ do miasta l, dla którego

τ_il(t) * [η_il]^β (5)

jest maksymalne, tzn. z prawdopodobieństwem q₀ zostaje wykonany najlepszy ruch wskazany przez tory feromonu i heurystyczną informację (wykorzystanie wyuczonej wiedzy)

• Z prawdopodobieństwem 1-q₀ wykorzystuje do wyboru miasta wzór oznaczony symbolem (4).

Lokalna aktualizacja feromonu

W opisywanej modyfikacji mrówki korzystają dodatkowo z zasady lokalnej aktualizacji feromonu, którą stosują zaraz po przejściu łuku w czasie konstrukcji trasy. Opisuje ją wzór:

τ_ij = (1 - ξ)*τ_ij + τ₀*ξ (6)

gdzie: ξ, 0 < ξ < 1 i τ₀ są dwoma parametrami.

Zasada lokalnej aktualizacji ma za zadanie sprawić, aby wybrany łuk stał się mniej pożądany dla kolejnej mrówki. Tym samym prawdopodobieństwo eksploatacji jeszcze nie odwiedzanych łuków wzrasta.

4.4.2 Max-Min System Mrówek (ang. Max-Min Ant System - MMAS)

Rozwiązanie w tej modyfikacji uzyskiwane jest tak samo jak w przypadku bez modyfikacji. Wykorzystywana jest także pseudo-przypadkowo-proporcjonalna zasada wyboru, opisywana w Systemie Koloni Mrówek. Główne dodatkowe modyfikacje są następujące:

• W celu znalezienia najlepszego rozwiązania tylko jedna mrówka w każdej iteracji ma prawo dodać feromon

• W celu uniknięcia stagnacji stosujemy zasadę mocy szlaku feromonu

• Szlaki feromonu są inicjalizowane od wyższej wartości, co powoduje zwiększone przeszukiwanie na początku algorytmu.

Aktualizacja szlaku feromonu

Po znalezieniu rozwiązania przez wszystkie mrówki, szlaki feromonu aktualizowane są według wzoru:

τ_ij(t + 1) = (1 - ξ) * τ_ij(t) + ξ * Δτ_ij^best (7)

gdzie: Δτ_ij^best = 1/L^best.

Mrówka, która złoży feromon, może znaleźć rozwiązanie najlepsze w danej iteracji (ang. iteration-best solution T^ib) lub globalnie najlepsze (ang. global-best solution T^gb). Zatem, jeżeli konkretne łuki są często wykorzystywane w najlepszych rozwiązaniach, otrzymują one największą dawkę feromonu. Wyniki eksperymentów przeprowadzonych przez twórców tej modyfikacji pokazały, że najlepsze wyniki uzyskiwane są poprzez stopniowy wzrost częstotliwości wyboru T^gb dla aktualizacji szlaku.

Ograniczenia szlaku

W przypadku MIN-MAX narzucone są dolne i górne ograniczenie na możliwe nasycenie feromonu w celu uniknięcia stagnacji poszukiwań. Szczególnie narzucone ograniczenia odnoszą skutek w pośrednim ograniczeniu prawdopodobieństwa p_ij wyboru wierzchołka j kiedy mrówka jest w wierzchołku i do przedziału [p_min, p_max] gdzie 0 < p_min < p_ij < p_max < 1. Tylko w przypadku, gdy mrówka ma jedną możliwość wyboru następnego wierzchołka p_min = p_max. Wyniki eksperymentalne sugerują, że dolne ograniczenia prawdopodobieństwa wyboru szlaku wykorzystywane w MIN-MAX są istotniejszymi, ponieważ maksymalna moc szlaku na łukach jest na dłuższą metę ograniczona z powodu ulatniania się feromonu.

Inicjalizacja szlaku

Szlaki feromonu w MIN-MAX są inicjalizowane od wyższych wartości. Dzięki temu poszukiwania najlepszego rozwiązania na początku działania algorytmu wzrasta, ponieważ różnice względne pomiędzy mocami szlaku feromonu są mniej wyraźne.

4.4.3 System Mrówek wykorzystujący rangi (ang. Rank-Based Version of Ant System - AS_rank)

Kolejnym udoskonaleniem algorytmu „System Mrówek” jest wersja oparta na rangach (AS_rank). W tej modyfikacji korzystamy zawsze z globalnie najlepszego rozwiązania w celu aktualizacji śladów feromonu. Dodatkowo tylko ograniczona liczba mrówek każdej iteracji może dodać feromon. W tym celu mrówki są sortowane według znalezionych rozwiązań (L¹(t)<L²(t)<...<L^m(t)), a ilość mrówek, które mogą złożyć feromon jest odmierzana według rangi r mrówki. Tylko (w - 1) najlepszych mrówek każdego powtórzenia może złożyć feromon. Najlepsze globalnie rozwiązanie, dające najsilniejsze sprzężenie zwrotne osiąga wagę w. Najlepsza mrówka r obecnej iteracji przyczynia się do aktualizacji feromonu z wagą nadaną przez wzór:

max {0, r-w} (8)

Zatem zmieniona zasada aktualizacji feromonu wyglada następująco:

(9)

gdzie:

i

Twórcy tej modyfikacji porównywali swój algorytm z algorytmami genetycznymi oraz z algorytmem symulowanego wyżarzania Okazało się, że algorytm oparty na systemie rang dawały dla większych problemów lepsze wyniki.

4.4.4 Podsumowanie

Wszystkie proponowane opcje algorytmów mrówkowych mają wiele cech wspólnych. Algorytm w pierwszej formie używany jest głównie jako pierwsze podejście do problemu NP-zupełnego i rozwiązanie znalezione przez niego jest raczej marne w porównaniu z innymi podejściami. Zaproponowano zatem kilka modyfikacji algorytmów dla poprawy jego działania.

Główną cechą proponowanych udoskonaleń jest to, że wykorzystują one do dalszych poszukiwań najlepsze rozwiązania znalezione podczas wcześniejszych poszukiwań. Osiąga się to, poprzez nadanie większe wagi lepszym rozwiązaniom przy aktualizacji feromonu i często dopuszcza się do tworzenia dodatkowego śladu feromonu na łukach globalnie najlepszego rozwiązania.

Naturalnie poprzez silniejsze wykorzystywanie najlepszych rozwiązań, łuki znajdujące się na najlepszych trasach otrzymują dodatkowe, silne sprzężenie zwrotne, a zatem są wybierane z większym prawdopodobieństwem w kolejnych iteracjach algorytmu. Powstaje jednak problem, że wraz z silniejszą eksploatacją najlepszych rozwiązań, doprowadzimy do stagnacji algorytmu, tzn. takiej sytuacji, w której wszystkie mrówki podążają jedną trasą. Zatem niektóre modyfikacje, w szczególności ACS i MMAS, wprowadzają dodatkowe cechy w celu uniknięcia stagnacji.

Wszystkie opisane modyfikacje algorytmu wykazują znacznie lepsze działanie przy rozwiązywaniu problemów optymalizacji kombinatorycznej i wykazują silniejszą eksploatacje najlepszych rozwiązań znalezionych przez mrówki. Rozsądnym będzie więc stwierdzenie, że koncentracja poszukiwań wokół najlepszych rozwiązań znalezionych w czasie poszukiwań jest kluczem do udoskonalenia działania algorytmu.

4.5 Zastosowanie algorytmów mrówkowych dla rozwiązania problemu komiwojażera

W przypadku problemu komiwojażera, każda pojedyncza mrówka konstruuje rozwiązanie podróżując między poszczególnymi miastami. W czasie inicjalizacji umieszczamy wszystkie mrówki w mieście będącym miastem startowym algorytmu, następnie modyfikujemy algorytm w ten sposób, aby mrówki po przejściu wszystkich miast, odwiedziły każde miasto tylko jeden raz a następnie powróciły do punktu startowego algorytmu.

W trakcie implementacji algorytmu należy zwrócić uwagę na poprawną obsługę list tabu(r) oraz allowed(r). Są one niezbędne dla spełnienia warunku pobytu komiwojażera w każdym mieście tylko jeden raz.

5. Opis systemu komputerowego

5.1 Dane techniczne

System komputerowy to aplikacja mogąca pracować pod kontrolą systemów Windows 95/98/NT/2000. Minimalne parametry komputera na którym może pracować system to:

• Procesor 486 SX lub Pentium

• 8 MB pamięci operacyjnej

• 30 MB wolnej przestrzeni dyskowej

• Karta Graficzna SVGA

• Napęd CD-ROM

• Zainstalowany jeden z wcześniej wymienionych systemów operacyjnych.

5.2 Dane wejściowe

Pierwszym krokiem niezbędnym do rozpoczęcia pracy aplikacji testowej jest wprowadzenie danych wejściowych zawierających macierz odległości pomiędzy poszczególnymi miastami. Można to zrobić na dwa sposoby:

5.2.1 Wczytywanie danych z pliku

Plik z danymi jest plikiem tekstowym o rozszerzeniu ATS. Składa się on z dwóch części:

• Nagłówka - znajduje się w nim nazwa pliki, rodzaj i wielkość problemu. Przykładowy nagłówek, skopiowany z jednego z plików zamieszczony jest poniżej.

NAME: ftv33

TYPE: ATSP

COMMENT: Asymmetric TSP (Fischetti)

DIMENSION: 34

EDGE_WEIGHT_TYPE: EXPLICIT

EDGE_WEIGHT_FORMAT: FULL_MATRIX

• Z macierzy danych. Zawiera ona liczby, które odpowiadają odległością pomiędzy poszczególnymi miastami.

Plik z danymi można odczytać za pomocą opcji „Open” dostępnej w pasku narzędzi lub rozwijalnym menu aplikacji. Po aktywacji tej opcji pojawia się standardowy dla wszystkich wersji dedykowanego systemu operacyjnego okienko dialogowe pozwalające na wybranie pliku (zobacz rys. 8).

Rys. 8

Wybrany plik zostaje wczytany do pamięci operacyjnej komputera. W wyniku tego aktywne stają się opcję aplikacji służące do inicjalizacji obliczeń, opisane w dalszej części rozdziału.

Do wersji instalacyjnej systemu dostarczone są pliki zawierające przykładowe zagadnienia ATSP zaczerpnięte z biblioteki TSPLIB. Są to zagadnienia ATSP, dla których znane jest rozwiązanie optymalne. Dziki temu, podczas testowania systemu, można porównać znalezione przez aplikacje rozwiązanie z rozwiązaniem optymalnym.

5.2.2 Tworzenie nowego problemu.

System komputerowy pozwala także na stworzenie nowego problemu poprzez generacje macierzy odległości pomiędzy miastami. Możliwe jest poprzez opcje „New” dostępną w pasku narzędzi lub rozwijalnym menu aplikacji. Po aktywacji tej opcji pojawia się następujące okienko dialogowe:

Rys. 9

Pozwala ono na wybranie sposobu wprowadzania danych, tzn.:

• Poprzez losowanie wartości odległości przez komputer. Definiujemy wtedy rozmiar problemu (ilości miast) oraz minimalną oraz maksymalną wartość odległości.

• Poprzez ręczne wprowadzanie wszystkich wartości wszystkich odległości. Przy wybraniu tej opcji niezbędne jest zdefiniowanie tylko rozmiaru problemu (ilości miast).

Po wybraniu każdego rodzaju wprowadzania danych pojawia się okienko dialogowe, służące do weryfikacji lub edytowania dych:

Rys. 10

Okienko dialogowe widoczne na rysunku 10 pozwala w łatwy sposób dokonywać zmian w macierzy opisującej odległości pomiędzy miastami. Weryfikacja taka może odbywać się nie tylko podczas tworzenia problemu, lecz także w czasie pracy aplikacji, gdy macierz danych wejściowych znajduje się w pamięci operacyjnej komputera. Można to uzyskać poprzez opcję „Data Review” dostępnej w pasku narzędzi oraz rozwijalnym menu aplikacji.

5.2.3 Zapis danych do pliku

Nowowprowadzone lub zmodyfikowane dane wejściowe mogą być zapisane do pliku. W przypadku modyfikacji danych, zapis danych do istniejącego już pliku uzyskujemy poprzez opcje „Save” dostępną w pasku narzędzi oraz w rozwijalnym menu aplikacji. Aktywacja tej opcji powoduje nadpisanie pliku ze zmodyfikowaną macierzą odległości.

Zapis danych do nowego pliku uzyskujemy poprzez opcje „Save as...” dostępną w rozwijalnym menu aplikacji. Po aktywacji tej opcji pojawia się standardowy dla wszystkich wersji dedykowanego systemu operacyjnego okienko dialogowe pozwalające na wprowadzenia nazwy pliku , pod którą mają zapisane być dane (zobacz rys. 11).

Rys. 11

Zapis danych do pliku nie powoduje ich kasacji z pamięci operacyjnej komputera, w dalszym ciągu możliwa jest praca aplikacji na zapisanych wcześniej danych.

5.3 Ustawienie parametrów procesu obliczeń

System komputerowy posiada implementacje algorytmu „System Mrówek” oraz jego modyfikacji zaproponowanej przez Dorigo, tzn. „System Koloni Mrówek”. Przed rozpoczęciem procesu obliczeń należy wybrać interesującą nas opcję algorytmu oraz wprowadzić wartości parametrów występujących we wzorach matematycznych, na których bazują algorytmy. Służy do tego celu okienko dialogowe dostępne poprzez opcję „Settings” dostępną w pasku narzędzi oraz rozwijalnym menu aplikacji.

Rys. 12

Oprócz opcji algorytmu, która będzie wykonywana w procesie obliczeń w okienku dialogowym pokazanym na rysunku oznaczonym numerem 12 możemy określić następujące wartości:

• „Ants Number” - ilość mrówek występujących podczas każdej iteracji

• „Series Number” - ilość iteracji algorytmu

• „Begin Trace Value” - wartość początkowa feromunu, znajdująca się na wszystkich krawędziach na początku procesu obliczeń

• „Alfa Parameter” - parametr α użyty we wzorze oznaczonym literą 4

• „Beta Parameter” - paramert β użyty we wzorze oznaczonym literą 4

• „q Parameter” - parametr q użyty we wzorze oznaczonym literą 1

• „Q Parameter” - paramert Q użyty we wzorze oznaczonym literą 3

• „Ksi Parameter” - parametr ξ użyty we wzorze oznaczonym literą 6

• „Q-Zero Parameter” - parametr q₀ określającym prawdopodobieństwo wyboru miasta w zasadzie pseudo-przypadkowo-proporcjonalnego wyboru

• „Tau-Zero Parameter” - parametr τ₀ użytym we wzorze oznaczonym literą 6

Wszystkie wymienione wcześniej wartości mają znaczący wpływ na znalezione przez system rozwiązanie, należy wiec dobierać je dla każdego rozpatrywanego problemu. Złe wartości parametrów mogą powodować niepoprawną pracę algorytmu.

5.4 Proces obliczeń

Proces obliczeń aktywowany jest poprzez opcje „Run” dostępną w pasku narzędzi oraz w rozwijalnym menu aplikacji. Aktywacja tej opcji powoduje zablokowanie innych opcji, których użycie podczas procesu obliczeń mogłoby być krytyczne dla poprawnej pracy algorytmu.

Długość procesu obliczeń jest zależna od następujących czynników

• Wielkości rozpatrywanego problemu

• Ilości iteracji algorytmu

• Ilości mrówek poszukujących rozwiązania w każdej iteracji

Widać więc, że może być on względnie długi, dla różnych ustawień aplikacji i danych wejściowych. Dla ilustracji postępów pracy algorytmu, oraz czasu jaki pozostał do zakończenia pracy, w głównym oknie aplikacji umieszczone zastały dwa paski postępu (zobacz rysunek 13)

Rys. 13

Opisywane wcześniej paski postępu widoczne są w prawym rogu głównego okna aplikacji. Pierwszy nazwany „Iteration Progress” informuje o ilości wykonanych przez algorytm iteracji, drugi nazwany „Ant Progress” informuje o ilości mrówek, które poszukiwały już rozwiązania podczas każdej iteracji.

5.5 Wyniki obliczeń

Po zakończeniu procesu obliczeń samoczynnie wyświetlane jest okienko dialogowe pokazujące szczegółowo najlepsze znalezione rozwiązanie. Okienko to jest dostępne także w opcji „Result” dostępnej w pasku narzędzi oraz w rozwijalnym menu aplikacji.

Rys. 14

W opisywanym okienku dialogowym możemy zobaczyć wartość najlepszego rozwiązania znalezionego przez aplikacje w procesie obliczeń oraz dokładny opis drogi.

Wyniki obliczeń widoczne są także w głównym oknie aplikacji. Znajdują się tam dwa wykresy wizualizujące:

• „Iterationts Best Solution” - wykres najlepszych rozwiązań znajdywanych w poszczególnych iteracjach

• „Global Best Solution” - wykres ukazujący postępy w poszukiwaniu globalnie najlepszego rozwiązania.

Wykresy te pojawiają się także na zakończenie procesu obliczeń.

5.6 Pliki pomocy

Zaimplementowany system komputerowy posiada także rozwinięty system plików pomocy. Zaopatrzony jest w pomoc kontekstową mogącą być pomocną podczas pracy z aplikacją przez użytkowników nie zapoznanych z treścią części pisemnej pracy. Pomoc kontekstowa uaktywniana jest za pomocą klawiatury komputerowej przyciskiem F1.

5.7 Opis implementacji systemu.

System komputerowy został zaimplementowany przy użyciu środowiska programistycznego Visual C++, z wykorzystaniem biblioteki MFC (Microsoft Foundation Class ). Jest to system dwu-wątkowy, w którym wszystkie obliczenia odbywają się w oddzielnym wątku, dla uniknięcia blokady całego systemu podczas procesu obliczeń.

Klasy zaimplementowane podczas realizacji systemu można podzielić na następujące grupy:

5.7.1 Główne klasy aplikacji

5.7.1.1 Klasa CAntApp

Nazwa klasy	CAntApp
Klasa bazowa	CWinApp
Krótki opis	Implementacja obiektu aplikacji. Zawiera wszystkie obiekty i zmienne globalne, do których jest dostęp we wszystkich wątkach systemu.
Uwagi	Wartości zmiennych, które zawierają wartości parametrów obliczeń zapisywane są w rejestrze systemowym i odczytywane przy ponownym uruchomieniu aplikacji.

Tabela 1

Diagram dziedziczenia dla klasy CAntApp.

Diagram współpracy dla klasy CAntApp

Spis metod oraz zmiennych klasy

1. Metody Publiczne

• CAntApp ()

• ~CAntApp ()

• virtual BOOL InitInstance ()

• virtual int ExitInstance ()

• virtual void WinHelp (DWORD dwData, UINT nCmd = HELP_CONTEXT)

• afx_msg void OnAppAbout ()

2. Atrybuty Publiczne

• double** m_matrix

• CString m_strProblemName

• CString m_strType

• CString m_strComment

• CString m_strFileName

• long m_nSize

• long* m_pResultTable

• double m_nResultSize

• unsigned long m_nSeriesNumber

• unsigned long m_nAntNumber

• unsigned long m_nAntOperation

• unsigned long m_nQZero

• double m_dbBeginTrace

• double m_dbAlfa

• double m_dbBeta

• double m_dbQ

• double m_dbTauZero

• double m_dbKsi

• double m_db_q_Param

5.7.1.2 Klasa CAntDoc

Nazwa klasy	CAntDoc
Klasa bazowa	CDocument
Krótki opis	Implementacja obiektu dokumentu, niezbędnego do realizacji architektury Widok-Dokument, preferowanej w MFC.
Uwagi	Brak

Tabela 2

Diagram dziedziczenia dla CAntDoc

Diagram współpracy dla CAntDoc:

Spis metod klasy

1. Metody Publiczne

• virtual BOOL OnNewDocument ()

• virtual void Serialize (CArchive& ar)

• virtual ~CAntDoc ()

2. Metody Chronione

• CAntDoc ()

5.7.1.3 Klasa CAntView

Nazwa klasy	CantView
Klasa bazowa	CformView
Krótki opis	Implementacja obiektu widoku, niezbędnego do realizacji architektury Widok-Dokument, preferowanej w MFC.
Uwagi	Brak

Tabela 3

Diagram dziedziczenia dla klasy CAntView

Diagram współpracy dla klasy CAntView:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntDoc* GetDocument ()

• virtual BOOL PreCreateWindow (CREATESTRUCT& cs)

• int UpdateAllControl (bool bUpdate)

• virtual ~CAntView ()

2. Atrybuty Publiczne

• CProgressCtrl m_ctrIterationProgress

• CProgressCtrl m_ctrAntProgress

• CString m_strProblemDescription

• CString m_strProblemName

• long m_nProblemSize

• CAntChart m_leftAntChart

• CAntChart m_rightAntChart

3. Metody Chronione

• CAntView ()

• virtual void DoDataExchange (CDataExchange* pDX)

• virtual void OnInitialUpdate ()

• afx_msg void OnEditCut ()

• afx_msg void OnEditCopy ()

• afx_msg void OnEditPaste ()

• afx_msg void OnEditUndo ()

• afx_msg void OnEditDelete ()

• afx_msg void OnEditSelectAll ()

• afx_msg void OnUpdateEditCopy (CCmdUI* pCmdUI)

• afx_msg void OnUpdateEditCut (CCmdUI* pCmdUI)

• afx_msg void OnUpdateEditDelete (CCmdUI* pCmdUI)

• afx_msg void OnUpdateEditPaste (CCmdUI* pCmdUI)

• afx_msg void OnUpdateEditSelectAll (CCmdUI* pCmdUI)

• afx_msg void OnUpdateEditUndo (CCmdUI* pCmdUI)

• afx_msg BOOL OnHelpInfo (HELPINFO* pHelpInfo)

4. Metody Prywatne

• void ProgressInitialUpdate ()

5.7.1.4 Klasa CAntFrame

Nazwa klasy	CAntFrame
Klasa bazowa	CFrameWnd
Krótki opis	Implementacja obiektu szkieletu okna, występującego w aplikacji typu SDI (Single document interface).Zawiera obsługę wszystkich wiadomości przekazywanych przez wątek roboczy do głównego wątku aplikacji..
Uwagi	Brak

Tabela 4

Diagram dziedziczenia dla klasy CAntFrame

Diagram współpracy dla klasy CAntFrame:

Spis metod i zmiennych klasy

1. Metody Publiczne

• virtual BOOL PreCreateWindow (CREATESTRUCT& cs)

• virtual ~CAntFrame ()

2. Atrybuty Publiczne

• CAntThread* m_pWorkingThread

3. Metody Chronione

• CAntFrame ()

• afx_msg int OnCreate (LPCREATESTRUCT lpCreateStruct)

• afx_msg void OnFileNewAnt ()

• afx_msg void OnFileOpenAnt ()

• afx_msg void OnFileSaveAnt ()

• afx_msg void OnFileSaveAsAnt ()

• afx_msg void OnAntRun ()

• afx_msg void OnUpdateFileNewAnt (CCmdUI* pCmdUI)

• afx_msg void OnUpdateFileOpenAnt (CCmdUI* pCmdUI)

• afx_msg void OnUpdateFileSaveAnt (CCmdUI* pCmdUI)

• afx_msg void OnUpdateFileSaveAsAnt (CCmdUI* pCmdUI)

• afx_msg void OnResult ()

• afx_msg void OnDataReview ()

• afx_msg void OnSettings ()

• afx_msg void OnClose ()

• afx_msg void OnTbAntsMenu ()

• afx_msg void OnTbEditMenu ()

• afx_msg void OnTbFileMenu ()

• afx_msg void OnTbHelpMenu ()

• afx_msg void OnUpdateTbAntsMenu (CCmdUI* pCmdUI)

• afx_msg void OnUpdateTbEditMenu (CCmdUI* pCmdUI)

• afx_msg void OnUpdateTbFileMenu (CCmdUI* pCmdUI)

• afx_msg void OnUpdateTbHelpMenu (CCmdUI* pCmdUI)

• afx_msg void OnUpdateAntRun (CCmdUI* pCmdUI)

• afx_msg void OnUpdateDataReview (CCmdUI* pCmdUI)

• afx_msg void OnHelpToc ()

• afx_msg BOOL OnHelpInfo (HELPINFO* pHelpInfo)

• afx_msg LRESULT OnThreadStop (WPARAM, LPARAM)

• afx_msg LRESULT OnInitialWorkThread (WPARAM, LPARAM)

• afx_msg LRESULT OnAntStep (WPARAM, LPARAM)

• afx_msg LRESULT OnIterationStep (WPARAM, LPARAM)

• afx_msg LRESULT OnResultShow (WPARAM, LPARAM)

• afx_msg void OnToolsCustomize ()

4. Atrybuty Chronione

• CStatusBar m_wndStatusBar

• BOOL m_bThreadRun

• BOOL m_bFileOpen

5.7.1.4 Klasa CAntThread

Nazwa klasy	CAntThread
Klasa bazowa	CWinThread
Krótki opis	Implementacja wątku roboczego aplikacji. Posiada zaimplementowane dwa algorytmy obliczeniowe, tzn. „Ants System” oraz „Ants Colony System”.
Uwagi	Praca aplikacji nie może być zakończona podczas pracy obiektu tej klasy. Grozi to pozostawieniem przez aplikację nie zwolnionej pamięci operacyjnej.

Tabela 5

Diagram dziedziczenia dla klasy CAntThread

Diagram współpracy dla klasy CAntThread:

Spis metod i zmiennych klasy

1. Metody Publiczne

• virtual void SetOwner (HWND hWnd)

• void SetBeginTraceValue (double dbTraceValue)

• virtual BOOL InitInstance ()

• virtual int ExitInstance ()

2. Metody Chronione

• CAntThread ()

• virtual ~CAntThread ()

• int PostMessageToOwner (UINT iMessage, WPARAM w , LPARAM l )

• int SendMessageToOwner (UINT iMessage, WPARAM w , LPARAM l )

• int RunOneAnt (int* pEdgeNumber, unsigned int nSeed = 0)

• void UpdateTraceValue (int** pEdge, double* pResult, int nWidth, int nHeight)

• double FindMinResult (double* pResult, int nSizeint, int &nBestNumber)

• void CalculateAntResult (int** pTable, int nWidth, int nHeight, double* pResult)

• void CalculateGrowth (double** pTable, int** pEdge, double* pResult, int nWidth, int nHeight)

• BOOL AntSystem ()

• BOOL AntColonySystem ()

• int RunACSAnt (int* pEdgeNumber)

3. Atrybuty Chronione

• HWND m_hOwnerWnd

4. Atrybuty Prywatne

• double m_dbBeginValueTrace

• double** m_pMatrix

• double** m_pTraceMatrix

• double* m_pBestResults

• long m_nSize

• unsigned long* m_pAntAllowed

• unsigned long m_nSeriesNumber

• unsigned long m_nAntNumber

• unsigned long m_nQZero

• CAntRandom* m_pRnd

• double m_qParam

• double m_Q_Param

• double m_db_Alfa

• double m_db_Beta

• double m_db_Tau_Zero

• double m_db_Ksi

5.7.2 Klasy implementacji okienek dialogowych

5.7.2.1 Klasa CAboutDlg

Nazwa klasy	CAboutDlg
Klasa bazowa	CDialog
Krótki opis	Implementacja dialogu zawierającego krótki opis aplikacji.
Uwagi	Brak

Tabela 6

Diagram dziedziczenia dla klasy CAboutDlg

Diagram współpracy dla klasy CAboutDlg:

Spis metod klasy

1. Metody Publiczne

• CAboutDlg ()

2. Metody Chronione

• virtual void DoDataExchange (CDataExchange* pDX)

5.7.2.2 Klasa CAntDataReviewDlg

Nazwa klasy	CAntDataReviewDlg
Klasa bazowa	CDialog
Krótki opis	Implementacja dialogu pozwalającego na weryfikacje macierzy odległości wprowadzonej jako dane wejściowe do aplikacji.
Uwagi	Brak

Tabela 7

Diagram dziedziczenia dla klasy CAntDataReviewDlg

Diagram współpracy dla klasy CAntDataReviewDlg:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntDataReviewDlg (CWnd* pParent = NULL)

2. Atrybuty Publiczne

• CAntGrid m_wndGrid

• long m_nSize

• bool m_bReadOnly

3. Metody Chronione

• virtual void DoDataExchange (CDataExchange* pDX)

• virtual BOOL OnInitDialog ()

• afx_msg BOOL OnHelpInfo (HELPINFO* pHelpInfo)

• afx_msg void OnContextMenu (CWnd* pWnd, CPoint point)

• virtual void OnOK ()

5.7.2.3 Klasa CAntGridDlg

Nazwa klasy	CAntGridDlg
Klasa bazowa	CDialog
Krótki opis	Implementacja dialogu pozwalającego wprowadzenie macierzy odległości podczas tworzenia nowego problemu.
Uwagi	Brak

Tabela 8

Diagram dziedziczenia dla klasy CAntGridDlg

Diagram współpracy dla klasy CAntGridDlg:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntGridDlg (CWnd* pParent = NULL)

2. Atrybuty Publiczne

• CAntGrid m_wndGrid

• BOOL m_bRandom

• int m_nMinRand

• int m_nMaxRand

• long m_nSize

3. Metody Chronione

• virtual void DoDataExchange (CDataExchange* pDX)

• virtual BOOL OnInitDialog ()

• virtual void OnOK ()

• afx_msg BOOL OnHelpInfo (HELPINFO* pHelpInfo)

• afx_msg void OnContextMenu (CWnd* pWnd, CPoint point)

5.7.2.3 Klasa CAntNewProblem

Nazwa klasy	CAntNewProblem
Klasa bazowa	CDialog
Krótki opis	Implementacja dialogu pozwalającego na wybranie rodzaju wprowadzania danych oraz rozmiaru nowego problemu.
Uwagi	Brak

Tabela 9

Diagram dziedziczenia dla klasy CAntNewProblem

Diagram współpracy dla klasy CAntNewProblem:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntNewProblem (CWnd* pParent = NULL)

2. Atrybuty Publiczne

• CEdit m_ctr_wl_Rodzaj

• CEdit m_ctr_wl_Min

• CEdit m_ctr_wl_Max

• CEdit m_ctr_ed_Rodzaj

• int m_nRadio

• long m_db_Max

• long m_db_MIN

• long m_l_wl_Rodzaj

• long m_l_ed_Rodzaj

3. Metody Chronione

• virtual void DoDataExchange (CDataExchange* pDX)

• virtual BOOL OnInitDialog ()

• virtual void OnOK ()

• virtual void OnCancel ()

• afx_msg void OnRadioLosowanie ()

• afx_msg void OnRadioEdycja ()

• afx_msg BOOL OnHelpInfo (HELPINFO* pHelpInfo)

• afx_msg void OnContextMenu (CWnd* pWnd, CPoint point)

4. Metody Prywatne

• void EnableLosowanie (bool bEnable)

• void EnableWprowadzanie (bool bEnable)

5.7.2.4 Klasa CAntResultDlg

Nazwa klasy	CAntResultDlg
Klasa bazowa	CDialog
Krótki opis	Implementacja dialogu pozwalającego na obejrzenie szczegółów dotyczących najlepszego rozwiązania znalezionego podczas procesu obliczeń.
Uwagi	Brak

Tabela 10

Diagram dziedziczenia dla klasy CAntResultDlg

Diagram współpracy dla klasy CAntResultDlg:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntResultDlg (CWnd* pParent = NULL)

2. Atrybuty Publiczne

• CListCtrl m_ctrList

• CString m_strResult

3. Metody Chronione

• virtual void DoDataExchange (CDataExchange* pDX)

• virtual BOOL OnInitDialog ()

• afx_msg BOOL OnHelpInfo (HELPINFO* pHelpInfo)

• afx_msg void OnContextMenu (CWnd* pWnd, CPoint point)

4. Metody Prywatne

• void AddListData ()

• void AddListHeaders ()

5.7.2.5 Klasa CAntSettingsDlg

Nazwa klasy	CAntSettingsDlg
Klasa bazowa	CDialog
Krótki opis	Implementacja dialogu pozwalającego na ustawienie parametrów obliczeń.
Uwagi	Brak

Tabela 11

Diagram dziedziczenia dla klasy CAntSettingsDlg

Diagram współpracy dla klasy CAntSettingsDlg:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntSettingsDlg (CWnd* pParent = NULL)

2. Atrybuty Publiczne

• CSpinButtonCtrl m_ctrQZeroSpin

• CSpinButtonCtrl m_ctrSmallQSpin

• CSpinButtonCtrl m_ctrSeriesNumberSpin

• CSpinButtonCtrl m_ctrKsiSpin

• CSpinButtonCtrl m_ctrAntsNumberSpin

• int m_nOperation

• UINT m_nAntsNumber

• UINT m_nSeriesNumber

• UINT m_nSmallQParam

• UINT m_nKsiParam

• UINT m_nQZero

• double m_dbAlfa

• double m_dbBeta

• double m_dbBeginTraceValue

• double m_dbBigQ

• double m_dbTauZero

3. Metody Chronione

• virtual void DoDataExchange (CDataExchange* pDX)

• virtual BOOL OnInitDialog ()

• virtual void OnOK ()

• afx_msg BOOL OnHelpInfo (HELPINFO* pHelpInfo)

• afx_msg void OnContextMenu (CWnd* pWnd, CPoint point)

5.7.3 Klasy pomocnicze

5.7.3.1 Klasa CAntChart

Nazwa klasy	CAntChart
Klasa bazowa	CStatic
Krótki opis	Implementacja klasy odpowiedzialnej za wykresy wyświetlane w głównym oknie aplikacji.
Uwagi	Brak

Tabela 12

Diagram dziedziczenia dla klasy CAntChart

Diagram współpracy dla klasy CAntChart:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntChart ()

• void RemoveAll ()

• int Add (double dbNewElement)

• void ShowChart (unsigned long nSeriesNumber)

• void InitialGraph (unsigned long nSeriesNumber)

• void SetGraghStyle (unsigned long nSeriesNumber)

• void SetAutoscale (BOOL)

• void ClearChart ()

• virtual void SetGraphData (int nIndex,int nGroup,double d)

• virtual ~CAntChart ()

• void SetIndexText (int nIndex, LPCSTR lpText)

2. Atrybuty Publiczne

• BOOL m_bIsAutoscale

• int m_nNumberOfPointsToShift

3. Metody Chronione

• afx_msg void OnPaint ()

• afx_msg BOOL OnEraseBkgnd (CDC* pDC)

4. Atrybuty Chronione

• BOOL m_bIsGraphShow

• CString m_strNoData

• SRGraph m_Graph

• SRGraph m_EmptyGraph

• SRGDecimalScale* m_pYDS

• SRGDecimalScale* m_pXDS

• SRGTickMarks* m_pXT

• SRGTickMarks* m_pYT

• SRGGridLines* m_pG

5. Atrybuty Prywatne

• double m_dbMaxValue

• double m_dbMinValue

• CObArray m_arData

5.7.3.2 Klasa CAntElement

Nazwa klasy	CAntElement
Klasa bazowa	CObject
Krótki opis	Klasa odpowiedzialna za przetrzymywanie wartości rozwiązań znalezionych w poszczególnych iteracjach.
Uwagi	Konieczność implementacji tej klasy wynikało z użycia klas kontenerów zaimplementowanych w MFC.

Tabela 13

Diagram dziedziczenia dla klasy CAntElement

Diagram współpracy dla klasy CAntElement:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntElement ()

• CAntElement (double dbElement)

• virtual ~CAntElement ()

• double GetElement ()

• void SetElement (double db)

2. Atrybuty Prywatne

• double m_db

5.7.3.3 Klasa CAntFileManager

Nazwa klasy	CAntFileManager
Klasa bazowa
Krótki opis	Klasa odpowiedzialna za operacje na plikach z danymi, tzn. zapis pliku na dysk i odczyt pliku z dysku.
Uwagi	Brak

Tabela 14

1. Metody Publiczne

• bool Initialize ()

• bool OpenFile (CString strFile)

• bool SaveFile (CString strFile, CString strProblemName, CString strType, CString strComment, long nSize)

• CAntFileManager ()

• virtual ~CAntFileManager ()

5.7.3.4 Klasa CAntGrid

Nazwa klasy	CAntGrid
Klasa bazowa	CWnd
Krótki opis	Klasa odpowiedzialna za obsługę siatki użytej do wprowadzania i weryfikacji danych wejściowych.
Uwagi	Brak

Tabela 15

Diagram dziedziczenia dla klasy CAntGrid

Diagram współpracy dla klasy CAntGrid:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntGrid ()

• virtual ~CAntGrid ()

• CString GetCellValue (ROWCOL nRow, ROWCOL nCol)

2. Metody Chronione

• virtual BOOL OnValidateCell (ROWCOL nRow, ROWCOL nCol)

5.7.3.5 Klasa CAntRandom

Nazwa klasy	CAntRandom
Klasa bazowa	CObject
Krótki opis	Implementacja generatora liczb pseudo-losowych. Obiekty tej klasy używane są podczas generacji nowych problemów oraz podczas wyboru drogi w czasie procesu obliczeń.
Uwagi	Ustawienie punktu startowego generatora odbywa się w konstruktorze, ale może być zmieniane podczas życia obiektu.

Tabela 16

Diagram dziedziczenia dla klasy CAntRandom

Diagram współpracy dla klasy CAntRandom:

Spis metod i zmiennych klasy

1. Metody Publiczne

• CAntRandom(unsigned int nSeed=0)

• BOOL InitWeights(unsigned int)

• BOOL AddWeight(unsigned int, unsigned int)

• unsigned int GetSeed()

• BOOL SetLBound(unsigned int)

• unsigned int GetLBound()

• unsigned int GetUBound()

• BOOL SetUBound(unsigned int)

• BOOL SetBounds(unsigned int, unsigned int)

• unsigned int GetRandom()

• unsigned int GetRandomWeighted()

• unsigned int GetRange()

• unsigned int GetRange(unsigned int nMin, unsigned int nMax)

• void SetMultiplier()

• virtual ~CAntRandom()

2. Atrybuty Chronione

• unsigned int m_nMin

• unsigned int m_nMax

• unsigned int m_nSeed

• double m_dMultiplier

• unsigned int m_nWeights

• unsigned int* m_pWeights

Wersja instalacyjna systemu komputerowego zawarta jest na krążku CD-R dołączonym do tekstu pracy. Znajduje się na nim plik wykonywalny o nazwie AntSetup.exe, uruchomienie którego powoduje rozpoczęcie procesu instalacji. Po pomyślnym zakończeniu procesu instalacji aplikacja gotowa jest do użytku.

6. Przykłady i wnioski

System komputerowy został wykonany zgodnie z projektem przedstawionym w poprzednim rozdziale, zaimplementowany w języku programowania C++, przy użyciu klas MFC. Testy systemy przeprowadzone zostały na komputerze z procesorem Pentium 166 MHz, 32 MB pamięci operacyjnej RAM pod kontrolą systemu operacyjnego Windows 98.

Testowanie systemu zostało ukierunkowane na porównanie wyników uzyskiwanych przez zaimplementowane algorytmy z optymalnymi rozwiązaniami znanych problemów. Wykorzystano do tego przykładowe zagadnienia ATSP zaczerpnięte z biblioteki TSPLIB. Wyniki tych testów przedstawione są w tabeli.

Nazwa problemu	AS	ACS	Najlepsze znane rozwiazanie
ft70	39831	38781	38673
kro124p	38361	36241	36230
p43	2840	2810	2810
ry48p	15343	14422	14422

Tabela 17

Na postawie danych zawartych w tabeli 17, można stwierdzić, że uzyskane podczas testów najlepsze rozwiązania są bardzo zbliżone do najlepszych znanych rozwiązań problemów, w niektórych przypadkach są nawet równe najlepszym rozwiązaniom.

Naturalnym wydaje się spostrzeżenie, że główny wpływ na wyniki obliczeń mają dwa czynniki, tzn.

• ilość mrówek

• ilość iteracji

Wpływ tych czynników na wartość znalezionego rozwiązania przedstawia wykres:

Wykres 2

Na podstawie wykresu wyraźnie widać, że wraz ze wzrostem wartości tych parametrów wzrasta efektywność tych parametrów. Niestety radykalnie wzrasta czas pracy algorytmu.

Wykres 3

Należy jednak podkreślić, że system operacyjny pod który dedykowana jest aplikacja nie pozwala na dokładne badanie zależności czasowych.

Innymi czynnikami mającymi wpływ na efektywność algorytmu są wartości parametrów, które można zmieniać za pomocą okienka dialogowego „Settings”. Nie potrafiłem jednak znaleźć ogólnych zasad, według których można ustalać najlepsze wartości tych parametrów. Podczas testowania aplikacji, dobierane one były eksperymentalnie w zależności od problemu. Według moich eksperymentów, najlepsze wyniki otrzymywane były z następującymi wartościami parametrów:

• α = 1

• β = 0.2

• τ = 0.7

• ξ = 0.1

• τ₀ = 0.01

• ρ = 0.9

Aplikacja pozwala na badanie wpływu tych czynników na wartości rozwiązań znajdywane przez algorytm. Jako przykład zamieszczamy wpływ parametru α.

Wykres 4

Pragnę jednak podkreślić, że w przypadku wybrania innego problemu, wykres ten mógłby wyglądać inaczej i że nie można jednoznacznie określić najlepszych wartości opisywanych parametrów.

Jednak na podstawie wszystkich eksperymentów, jestem w stanie stwierdzić, że efektywność metaheurystyki „Ant Colony System” jest duża, pozwalająca myśleć o zastosowaniu metaheurystyki w opracowaniu rozwiązań do problemów życia codziennego i należy ją propagować. Być może praca ta będzie miała czynny udział w propagowaniu tej metaheurystyki.

7. Literatura

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Wprowadzenie do algorytmów. Warszawa 1997, 1998.

2. Bogusław Filipowicz. Badania operacyjne. Wybrane metody obliczeniowe i algorytmy. Część 1. Kraków 1997

3. Antoni Kościeliski. Teoria obliczeń. Wykłady z metematycznych podstaw informatyki. Wydawnictwo Uniwersytetu Wrocławskiego 1997.

4. Aleksej Anisimow. Hipertekstowy słownik informatyczny. Praca magisterska napisana pod kierunkiem dr inż. Tomasza Bilskiego.

5. Paweł Martynowicz. Badania operacyjne - referat, AGH Kraków, Wydział EAIiE.

6. Mirosław Jabłoński. Zagadnienie podgrafu gęstego w grafie zwykłym. Projekt z przedmiotu Automatyzacja Procesów Dyskretnych pod przewodnictwem prof. dr hab. Inż. Konrada Wali, AGH Kraków, Wydział EAIiE.

7. Vittorio Maniezzo, Alberto Colornii. The Ant System Applied to the Quadratic Assignment Problem.

8. Zbigniew J. Czech, Ewa Marzec. Heuristic Algorythms for Solving the Set-partitioning Problem.

9. Urszula Boryczka, MARIUSZ Boryczka, Daniel Kuna. Generative Policies in the Job-shop Scheduling Problem.

10. Marco Dorigo, Vittorio Maniezzo, Alberto Colorni. The Ant System: Optimization by a colony of cooperating agents.

11. Marco Dorigo, Luca Maria Gambardella. Ant colonies for the traveling salesman problem.

12. Marco Dorigo, Luca Maria Gambardella. Ant-Q: A Reinforcement Learning approach tothe traveling salesman problem.

13. Marco Dorigo, Gianni Di Caro, Luca Maria Gambardella. Ant Algorithms for Discrete Optimization.

14. Luca Maria Gambardella, Marco Dorigo. Has-Sop: Hybrid Ant System for The Sequential Ordering Problem.

15. Luca Maria Gambardella, Marco Dorigo. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem

16. Luca Maria Gambardella, Marco Dorigo. Solving Symmetric and Asymmetric TSPs by Ant Colonies.

17. Thomas Stutzle, Marco Dorigo. ACO Algorithms for the Traveling Salesman Problem.

T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, „Wprowadzenie do algorytmów”, Warszawa 1997, 1998

A. Kościeliski, „Teoria obliczeń. Wybrane metody obliczeniowe i algorytmy”, Kraków 1997

A. Anisimow, „Hipertekstowy słownik informatyczny”, Praca magisterska napisana pod kierunkiem dr inż. T. Bileckiego.

B. Filipowicz, „Badania operacyjne. Wybrane metody obliczeniowe i algorytmy”, Kraków 1997.

P. Martynowicz, „Badania operacyjne- referat”, AGH Kraków.

M. Dorigo, V. Maniezzo, A. Colorni, „The Ant System: Optimization by a colony of cooperating agents”.

M. Jabłoński, „Zagadnienie podgrafu gęstego w grafie zwykłym”, projekt, AGH Kraków.

M. Dorgio, G. Di Carlo, L. M. Gambardella, „Ant Algorithms for Discrete Optimization”

M. Dorigo, V. Maniezzo, A. Colorni, „The Ant System: Optimization by a colony of cooperating agents”.

Informatyka w Sterowaniu i Zarządzaniu

3

Informatyka w Sterowaniu i Zarządzaniu

3

2

6

5

4

1

2

3

6

5

4

1

---