| Abstrakt: | 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. |