Hybrydowy algorytm optymalizacji do rozwiązywania problemów planowania ścieżek oparty na algorytmie optymalizacji szarych wilków

Sprytniejsze trasy w zatłoczonych miastach

Codziennie kierowcy, dostawcze furgonetki i roboty stają przed tym samym wyzwaniem: jak dostać się z punktu A do B szybko, bezpiecznie i bez marnowania paliwa lub czasu? W artykule przedstawiono nową metodę komputerową, która planuje krótsze, płynniejsze trasy przez złożone sieci ulic pełne przeszkód i zatorów. Czerpiąc pomysły z zachowań stadnych szarych wilków podczas polowania oraz z metod poszukiwaczy złota, autorzy pokazują, jak skuteczniej kierować pojazdami i robotami w zatłoczonych środowiskach miejskich.

Dlaczego lepsze trasy są ważne

W miarę rozrastania się miast i zagęszczania ruchu nawet niewielkie usprawnienia w routingu mogą przekładać się na duże oszczędności czasu, energii i emisji. Tradycyjne metody wyszukiwania ścieżek sprawdzają się, gdy mapa jest prosta, ale często zwalniają lub utkwią, gdy środowisko zawiera wiele możliwych skrętów i przeszkód. Nowoczesne „inteligentne” metody wyszukiwania próbują naśladować naturę — na przykład stada ptaków czy kolonie mrówek — aby jednocześnie eksplorować wiele opcji i wybrać dobre rozwiązania. Jedna z takich metod, zwana algorytmem optymalizacji szarych wilków, zyskała popularność dzięki prostocie i elastyczności, lecz nadal boryka się z trzema głównymi problemami: może utknąć w rozwiązaniach drugorzędnych, zbyt wcześnie zbiegać, oraz nie zawsze przeszukiwać mapę wystarczająco dokładnie.

Mieszanka wilków, chaosu i poszukiwaczy złota

Aby przezwyciężyć te słabości, autorzy zaprojektowali ulepszoną wersję nazwaną CGGWO. Zachowuje ona podstawową ideę stada wirtualnych szarych wilków poszukujących najlepszej trasy, ale zmienia sposób, w jaki stado się rozprasza i uczy. Po pierwsze, zamiast losowego rozmieszczenia wilków, metoda wykorzystuje matematyczną sztuczkę zwaną mapowaniem chaotycznym, aby rozrzucić je bardziej równomiernie po obszarze poszukiwań. Zwiększa to szansę, że przynajmniej niektóre wilki odkryją obiecujące rejony mapy. Następnie metoda zapożycza regułę z innej techniki inspirowanej poszukiwaczami złota. Tutaj wiodący „alfa” wilk jest delikatnie popychany w stronę szczególnie bogatych obszarów przestrzeni poszukiwań, niczym górnicy stopniowo przesuwający się w rejony z większą ilością złota. Ten krok wprowadza kontrolowany element losowości i różnorodności, pomagając stadzie wydostać się z niekorzystnych, lokalnych rozwiązań.

Sprytne krzyżowanie i łagodne wstrząsy

CGGWO dodaje następnie dwa rodzaje ruchów „krzyżujących”, które mieszają informacje między wilkami. W ruchu poziomym dwie różne kandydatki na trasę wymieniają części swoich tras, zmniejszając martwe strefy i zachęcając do bardziej kompletnego przeszukania mapy. W ruchu pionowym różne segmenty w obrębie pojedynczej trasy mieszają się ze sobą, co może ożywić zastałe fragmenty rozwiązania i zapobiec zbyt wczesnemu zatrzymaniu się stada na błędnej drodze. Na koniec delikatna dawka mutacji gaussowskiej — małe, losowe pchnięcia zależne od jakości każdej wilczej trasy — utrzymuje eksplorację. Jeśli trasa wilka jest gorsza od średniej, otrzymuje silniejszy wstrząs, co pomaga całej grupie uniknąć utknięcia w jednym narożniku krajobrazu rozwiązań.

Próba nowej metody

Naukowcy najpierw przetestowali CGGWO na 23 standardowych matematycznych zadaniach powszechnie używanych do oceny algorytmów poszukiwawczych. Zadania te obejmują krajobrazy od gładkich z pojedynczą najlepszą doliną po chropowate tereny z wieloma lokalnymi minimami. W większości tych testów CGGWO znajduje lepsze rozwiązania, zbiega szybciej i wykazuje bardziej stabilne zachowanie niż kilka dobrze znanych konkurentów, w tym oryginalny algorytm szarych wilków, optymalizacja rojem cząstek i algorytmy genetyczne. Zespół następnie przystąpił do realistycznego problemu planowania ścieżek opartego na uproszczonej siatce ulic w pobliżu ruchliwej strefy handlowej w Lhasie. Przeszkody reprezentują zablokowane lub zakorkowane odcinki, a celem jest połączenie punktu startu i końca krótką, płynną trasą, która ich unika.

Krótsze, płynniejsze podróże

W teście stylizowanym na ruch drogowy CGGWO konsekwentnie generuje krótsze trasy z mniejszą liczbą ostrych skrętów niż inne metody, przy umiarkowanym zapotrzebowaniu na moc obliczeniową. W porównaniu z oryginalnym algorytmem szarych wilków i kilkoma konkurencyjnymi technikami jego zaplanowane trasy są bardziej proste i łatwiejsze do przebycia, zmniejszając odległość nawet o około jedną czwartą w niektórych zestawieniach. Dla czytelnika niebędącego specjalistą wniosek jest jasny: poprzez sprytne połączenie pomysłów z chaosu, polowań grupowych i poszukiwań złota nowa metoda przeszukuje mapy dokładniej i opiera się utknięciu na rozwiązaniach jedynie dostatecznych. To czyni ją obiecującym narzędziem dla przyszłych systemów nawigacyjnych, robotów dostawczych i innych inteligentnych maszyn, które muszą szybko znaleźć bezpieczne, efektywne trasy przez zatłoczone, zmienne labirynty współczesnych miast.

Cytowanie: Cheng, G., Liu, Y. Hybrid optimization algorithm for solving path planning problems based on grey wolf optimization algorithm. Sci Rep 16, 8479 (2026). https://doi.org/10.1038/s41598-026-35037-z

Słowa kluczowe: planowanie ścieżek, algorytm optymalizacyjny, inteligentny transport, inteligencja roju, nawigacja robotów