Informatyka w Sterowaniu i Zarządzaniu
Temat Pracy Magisterskiej:
„Komputerowy system do badań efektywności meta-heurystyki „System Mrówek” w zakresie optymalizacji dyskretnej.”
Promotor:
Spis treści. 2
1. Wprowadzenie 4
2. Podstawowe definicje 5
2.1 Graf 5
2.2 Cykl „Hamiltona” 6
2.3 Heurystyka 7
2.4 Meta-heurystyka 8
2.5 Złożoność obliczeniowa algorytmów 9
3. Opis rozważanego problemu 11
3.1 Problem komiwojażera 11
3.2 Zastosowanie praktyczne 12
3.2.1 Optymalizacja drogi w transporcie 12
3.2.2 Optymalizacja drogi w elektronice i mechanice 13
3.2.3 Optymalizacja drogi w systemach produkcyjnych 14
3.2.4 Optymalizacja drogi w systemach telekomunikacyjnych 14
3.3 Metody rozwiązywania problemu komiwojażera 14
4. Algorytm „System mrówek” 16
4.1 Opis matematyczny algorytmu 22
4.2 Złożoność obliczeniowa algorytmu „System mrówek” 25
4.3 Porównanie dwóch rodzajów mrówek 25
4.4 Optymalizacja badanego algorytmu 27
4.4.1 System Koloni Mrówek (ang. Ant Colony System - ACS) 27
4.4.2 Max-Min System Mrówek (ang. Max-Min Ant System - MMAS) 28
4.4.3 System Mrówek wykorzystujący rangi (ang. Rank-Based Version of Ant System - ASrank) 30
4.4.4 Podsumowanie 30
4.5 Zastosowanie algorytmów mrówkowych dla rozwiązania problemu komiwojażera 31
5. Opis systemu komputerowego 32
5.1 Dane techniczne 32
5.2 Dane wejściowe 32
5.2.1 Wczytywanie danych z pliku 32
5.2.2 Tworzenie nowego problemu. 34
5.2.3 Zapis danych do pliku 35
5.3 Ustawienie parametrów procesu obliczeń 37
5.4 Proces obliczeń 38
5.5 Wyniki obliczeń 40
5.6 Pliki pomocy 41
5.7 Opis implementacji systemu. 41
5.7.1 Główne klasy aplikacji 42
5.7.2 Klasy implementacji okienek dialogowych 51
5.7.3 Klasy pomocnicze 58
6. Przykłady i wnioski 64
7. Literatura 68
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.
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.
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:
a)
b) 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.
Na rysunku 1 przedstawiony jest przykład przedstawienia graficznego grafu nieskierowanego. Wierzchołki przedstawiane są jako kółka, krawędzie jako linie.
c) 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.
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ą[1].
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].
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.
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 pr...
stary_hipis