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:
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.
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 <v0, v1, v2, ..., vk> takich, że u=v0, u'=vk i (vi-1, vi) 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ę:
fA(n) = max { t : (t jest liczbą elementarnych kroków maszyny cyfrowej niezbędną dla rozwiązania instancji I należącej do Dn)^(n = N(I))},
gdzie Dn jest zbiorem instancji problemu decyzyjnego a n jest rozmiarem każdej instancji.
Zwykle funkcje czasowej złożoności obliczeniowej algorytmu fA(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 dij 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 dij ≠ dji. 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:
Fizyczny charakter informacji składanej przez komunikujące się insekty
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 Δ τijr (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ą.
Jk(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 (n2 m), więc złożoność całego algorytmu jest równa T(n) = l*n2* 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 q0 do miasta l, dla którego
τil(t) * [ηil]β (5)
jest maksymalne, tzn. z prawdopodobieństwem q0 zostaje wykonany najlepszy ruch wskazany przez tory feromonu i heurystyczną informację (wykorzystanie wyuczonej wiedzy)
Z prawdopodobieństwem 1-q0 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 + τ0*ξ (6)
gdzie: ξ, 0 < ξ < 1 i τ0 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) + ξ * Δτijbest (7)
gdzie: Δτijbest = 1/Lbest.
Mrówka, która złoży feromon, może znaleźć rozwiązanie najlepsze w danej iteracji (ang. iteration-best solution Tib) lub globalnie najlepsze (ang. global-best solution Tgb). 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 Tgb 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 pij wyboru wierzchołka j kiedy mrówka jest w wierzchołku i do przedziału [pmin, pmax] gdzie 0 < pmin < pij < pmax < 1. Tylko w przypadku, gdy mrówka ma jedną możliwość wyboru następnego wierzchołka pmin = pmax. 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 - ASrank)
Kolejnym udoskonaleniem algorytmu „System Mrówek” jest wersja oparta na rangach (ASrank). 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ń (L1(t)<L2(t)<...<Lm(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 q0 określającym prawdopodobieństwo wyboru miasta w zasadzie pseudo-przypadkowo-proporcjonalnego wyboru
„Tau-Zero Parameter” - parametr τ0 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
Metody Publiczne
CAntApp ()
~CAntApp ()
virtual BOOL InitInstance ()
virtual int ExitInstance ()
virtual void WinHelp (DWORD dwData, UINT nCmd = HELP_CONTEXT)
afx_msg void OnAppAbout ()
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
Metody Publiczne
virtual BOOL OnNewDocument ()
virtual void Serialize (CArchive& ar)
virtual ~CAntDoc ()
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
Metody Publiczne
CAntDoc* GetDocument ()
virtual BOOL PreCreateWindow (CREATESTRUCT& cs)
int UpdateAllControl (bool bUpdate)
virtual ~CAntView ()
Atrybuty Publiczne
CProgressCtrl m_ctrIterationProgress
CProgressCtrl m_ctrAntProgress
CString m_strProblemDescription
CString m_strProblemName
long m_nProblemSize
CAntChart m_leftAntChart
CAntChart m_rightAntChart
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)
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
Metody Publiczne
virtual BOOL PreCreateWindow (CREATESTRUCT& cs)
virtual ~CAntFrame ()
Atrybuty Publiczne
CAntThread* m_pWorkingThread
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 ()
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
Metody Publiczne
virtual void SetOwner (HWND hWnd)
void SetBeginTraceValue (double dbTraceValue)
virtual BOOL InitInstance ()
virtual int ExitInstance ()
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)
Atrybuty Chronione
HWND m_hOwnerWnd
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
Metody Publiczne
CAboutDlg ()
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
Metody Publiczne
CAntDataReviewDlg (CWnd* pParent = NULL)
Atrybuty Publiczne
CAntGrid m_wndGrid
long m_nSize
bool m_bReadOnly
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
Metody Publiczne
CAntGridDlg (CWnd* pParent = NULL)
Atrybuty Publiczne
CAntGrid m_wndGrid
BOOL m_bRandom
int m_nMinRand
int m_nMaxRand
long m_nSize
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
Metody Publiczne
CAntNewProblem (CWnd* pParent = NULL)
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
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)
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
Metody Publiczne
CAntResultDlg (CWnd* pParent = NULL)
Atrybuty Publiczne
CListCtrl m_ctrList
CString m_strResult
Metody Chronione
virtual void DoDataExchange (CDataExchange* pDX)
virtual BOOL OnInitDialog ()
afx_msg BOOL OnHelpInfo (HELPINFO* pHelpInfo)
afx_msg void OnContextMenu (CWnd* pWnd, CPoint point)
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
Metody Publiczne
CAntSettingsDlg (CWnd* pParent = NULL)
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
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
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)
Atrybuty Publiczne
BOOL m_bIsAutoscale
int m_nNumberOfPointsToShift
Metody Chronione
afx_msg void OnPaint ()
afx_msg BOOL OnEraseBkgnd (CDC* pDC)
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
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
Metody Publiczne
CAntElement ()
CAntElement (double dbElement)
virtual ~CAntElement ()
double GetElement ()
void SetElement (double db)
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
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
Metody Publiczne
CAntGrid ()
virtual ~CAntGrid ()
CString GetCellValue (ROWCOL nRow, ROWCOL nCol)
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
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()
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 = 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
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Wprowadzenie do algorytmów. Warszawa 1997, 1998.
Bogusław Filipowicz. Badania operacyjne. Wybrane metody obliczeniowe i algorytmy. Część 1. Kraków 1997
Antoni Kościeliski. Teoria obliczeń. Wykłady z metematycznych podstaw informatyki. Wydawnictwo Uniwersytetu Wrocławskiego 1997.
Aleksej Anisimow. Hipertekstowy słownik informatyczny. Praca magisterska napisana pod kierunkiem dr inż. Tomasza Bilskiego.
Paweł Martynowicz. Badania operacyjne - referat, AGH Kraków, Wydział EAIiE.
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.
Vittorio Maniezzo, Alberto Colornii. The Ant System Applied to the Quadratic Assignment Problem.
Zbigniew J. Czech, Ewa Marzec. Heuristic Algorythms for Solving the Set-partitioning Problem.
Urszula Boryczka, MARIUSZ Boryczka, Daniel Kuna. Generative Policies in the Job-shop Scheduling Problem.
Marco Dorigo, Vittorio Maniezzo, Alberto Colorni. The Ant System: Optimization by a colony of cooperating agents.
Marco Dorigo, Luca Maria Gambardella. Ant colonies for the traveling salesman problem.
Marco Dorigo, Luca Maria Gambardella. Ant-Q: A Reinforcement Learning approach tothe traveling salesman problem.
Marco Dorigo, Gianni Di Caro, Luca Maria Gambardella. Ant Algorithms for Discrete Optimization.
Luca Maria Gambardella, Marco Dorigo. Has-Sop: Hybrid Ant System for The Sequential Ordering Problem.
Luca Maria Gambardella, Marco Dorigo. An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem
Luca Maria Gambardella, Marco Dorigo. Solving Symmetric and Asymmetric TSPs by Ant Colonies.
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
Wyszukiwarka
Podobne podstrony:
Komputerowy system do?dań?ektywności metaheurystyki ''System Mrówek'' w zakresie optymalizacj
Optymalizacja pracy Windows, Szkoła, Systemy Operacyjnie i sieci komputerowe, systemy, semestr II
Komputerowe systemy zarządzania produkcją
format[1], Szkoła, Systemy Operacyjnie i sieci komputerowe, systemy, semestr I
KOMPUTEROWE SYSTEMY STEROWANIA Nieznany
Program Laboratorium Komputerowe systemy pomiarowe Gawędzki KSP
Komputerowe systemy automatyki przemysłowej
ksa4, Edukacja, studia, Semestr VIII, Komputerowe Systemy Automatyki, KSA-lab
Dyski twarde-woluminy, Szkoła, Systemy Operacyjnie i sieci komputerowe, systemy, semestr II
raczynski 2, Edukacja, studia, Semestr VII, Komputerowe Systemy Automatyki
Komputerowy system rejestracji?nych pomiarowych PC Link Plus
EEG komputerowy system
Etapy uruchamiania komputera, systemu
INF II stopien Grafika komputerowa i systemy multimedialne
Normy prawne dotyczące rozpowszechniania programów komputerowych, 1.Systemy operacyjne i sieci kompu
Labolatorium komputerowych systemów automatyki, Systemy wizualizacji i sterowania, Politechnika Lube
Labolatorium komputerowych systemów automatyki, Systemy wizualizacji i sterowania, Politechnika Lube
Komputerowy system DAMB analizy dynamicznej budynków wysokich usztywnionych konstrukcjami ścianowymi
Architektura komputerów i systemy operacyjne
więcej podobnych podstron