Skip navigation

Please use this identifier to cite or link to this item: http://hdl.handle.net/20.500.12128/5576
Title: Wielokryterialne, mrowiskowe algorytmy optymalizacji w nawigacji samochodowej
Authors: Bura, Wojciech
Advisor: Boryczka, Mariusz
Keywords: optymalizacja mrowiskowa; algorytmy; nawigacja samochodowa
Issue Date: 2014
Publisher: Katowice : Uniwersytet Śląski
Abstract: Rozwiązywanie złożonych problemów optymalizacji dyskretnej znajduje zastosowania praktyczne w wielu dziedzinach aktywności człowieka. Przykładem możne być wyszukiwanie optymalnej drogi między dwoma punktami na mapie drogowej w nawigacji samochodowej z zastosowaniem wielu kryteriów oceny. Problem jest znany w literaturze jako bardziej ogólny, wielokryterialny problem najkrótszej drogi w grafie (ang. multi-objective shortest path problem – MOSP). Na początku rozprawy zostały omówione różne, klasyczne podejścia do rozwiązywania problemów optymalizacji wielokryterialnej, ze szczególnym uwzględnieniem podejścia zaproponowanego przez włoskiego ekonomistę Vilfredo Pareto. W metodzie tej zakłada się, że w procesie optymalizacji wielokryterialnej bardzo rzadko możliwe jest wyznaczenie jednego rozwiązania, które jest optymalne z punktu widzenia każdego kryterium oceny równocześnie. W związku z tym wynikiem optymalizacji wielokryterialnej metoda Pareto jest najczęściej zbiór rozwiązań niezdominowanych. Każde rozwiązanie, które należy do tego zbioru charakteryzuje się tym, że nie da się już polepszyć żadnego z kryterium oceny bez pogorszenia pozostałych. W rozprawie zdefiniowano wielokryterialny problem wyszukiwania najkrótszej drogi w grafie oraz dokonano przeglądu różnych metod rozwiązywania tego problemu. Charakteryzują się one dużą złożonością obliczeniową, co zachęca do stosowania algorytmów wyznaczających rozwiązania przybliżone. Są wśród nich algorytmy optymalizacji mrowiskowej, które są skuteczną metodą rozwiązywania złożonych problemów optymalizacji dyskretnej. Optymalizacja mrowiskowa (ang. ant colony optimization – ACO) jest paradygmatem związanym z tworzeniem algorytmów heurystycznych dla rozwiązywania problemów optymalizacji dyskretnej, które należą do licznego grona algorytmów inspirowanych przez naturę. Jest on oparty na kolonii sztucznych mrówek, które współpracują i komunikują się za pośrednictwem sztucznych śladów feromonowych. Pierwszym algorytmem w tej klasie był system mrówkowy, który wywodzi się z badań w dziedzinie systemów naśladujących rzeczywiste zachowania mrówek i został zaproponowany w 1991 r. przez M. Dorigo, V. Maniezzo i A. Colorniego jako algorytm rozwiązujący problem komiwojażera. Mrówki podróżują w przestrzeni rozwiązań, która zwykle ma strukturę grafową. Następny punkt swojej drogi mrówki wybierają z prawdopodobieństwem zależącym od dwóch rodzajów informacji związanych z krawędzią: statycznej informacji heurystycznej, np. odległości między węzłami oraz śladu feromonowego, który zmienia się w trakcie obliczeń i jest środkiem „porozumiewania się” mrówek. Algorytmy mrowiskowe stały się podstawą zaproponowanych w rozprawie oryginalnych wielokryterialnych algorytmów optymalizacji w nawigacji samochodowej. Na podstawie algorytmu AVN, znanego z literatury, zaprezentowano nowe, udoskonalone algorytmy NAVN i MultiNAVN będące głównymi efektami prac nad niniejszą rozprawa. Zaproponowano dwie wersje algorytmu MultiNAVN: z kryterium zastępczym (MultiNAVNZ) oraz losowym wyborem kryterium (MultiNAVN-L), które zostały poddane eksperymentom na danych rzeczywistych. Wykorzystano cztery kryteria oceny rozwiązań: długość drogi, szerokość drogi, liczba skrzyżowań oraz bezpieczeństwo. Dane dotyczące trzech pierwszych kryteriów pozyskano z bazy danych systemu OpenStreetMap, a jako kryterium bezpieczeństwa wykorzystano informacje o wypadkach i kolizjach z systemu Policji o nazwie SEWiK. Oba algorytmy wyznaczają przybliżone zbiory rozwiązań niezdominowanych, których jakość może być mierzona odległością tych zbiorów (np. metryka Hausdorffa) od pełnych zbiorów rozwiązań wyznaczonych algorytmem deterministycznym. Za pomocą wielu eksperymentów wykazano, że zaproponowane algorytmy z powodzeniem wyznaczają drogi dla rzeczywistych map drogowych, przy czym wyniki są porównywalne, a nierzadko lepsze od rezultatów uzyskiwanych za pomocą innych algorytmów.
URI: http://hdl.handle.net/20.500.12128/5576
Appears in Collections:Rozprawy doktorskie (WNŚiT)

Files in This Item:
File Description SizeFormat 
Bura_Wielokryterialne_mrowiskowe_algorytmy.pdf3,29 MBAdobe PDFView/Open
Show full item record


Items in RE-BUŚ are protected by copyright, with all rights reserved, unless otherwise indicated.