Doktoraty Wydziału IET

mgr inż. Mateusz Starzec

Promotor: prof. dr hab. inż. Aleksander Byrski (AGH) Promotor pomocniczy: dr inż. Kamil Piętak (AGH) Dyscyplina: Informatyka

Metaheurystyczne algorytmy optymalizacyjne stanowią punkt wyjściowy do efektywnego rozwiązywania problemów NP-trudnych. Uniwersalność tych metod pozwala dostosować je do różnorodnych przypadków użycia, jednak teoria no-free-lunch jest stałą motywacją do rozwoju istniejących i tworzenia nowych.

Algorytmy mrówkowe są jedną z popularnych i efektywnych metod optymalizacji, w szczególności problemów logistycznych i transportowych, które w bardzo intuicyjny sposób mogą być reprezentowane jako graf. Przez lata, wiele badań doprowadziło do powstania coraz bardziej wydajnych wariantów tej metaheurystyki, a także licznych jej specjalizacji dla węższych grup problemów. Podstawą działania algorytmu jest szeroka eksploracja przestrzeni rozwiązań, która na podstawie wiedzy zebranej w kolejnych iteracjach, zostaje ukierunkowana w sąsiedztwo najbardziej obiecujących możliwości, w celu jego eksploatacji.

Za eksplorację przestrzeni odpowiada grupa agentów, którzy w kolejnych iteracjach, niezależnie od siebie, tworzą nowe propozycje rozwiązań. Agentowy model algorytmu zachęca do zrównoleglenia obliczeń, aby lepiej wykorzystać nowoczesne klastry obliczeniowe lub środowiska HPC.

Pomimo dużego zainteresowania rozproszeniem algorytmu mrówkowego, tylko niewielka część opublikowanych prac skupia się na typowym podejściu master-slave z utrzymywaniem globalnej informacji w całym systemie. Zwykle skupiano się na podejściach dzielących zasoby obliczeniowe pomiędzy mniejsze kolonie z ograniczoną wymianą informacji pomiędzy nimi. Wynika to z rozmiaru współdzielonej wiedzy w postaci macierzy feromonów, której synchronizacja po każdej iteracji, w dużym klastrze, skutecznie ogranicza skalowalność algorytmu w klasycznej formie.

Praca prezentuje technikę rozproszenia i desynchronizacji dostępu do globalnej wiedzy w dużych klastrach obliczeniowych, która pozwala uruchomić obliczenia z dużymi grupami agentów w środowisku HPC przy zachowaniu wysokiej skalowalności algorytmu, a w efekcie poprawić jakość otrzymywanych rozwiązań w porównaniu do referencyjnych algorytmów sekwencyjnych.

W ramach pracy zaprojektowano oraz zaimplementowano zdesynchronizowaną wersję algorytmu mrówkowego. W serii eksperymentów wykazano wysoką skalowalność systemu oraz wyraźną poprawę jakości i szybkości zbiegania do optymalnych rozwiązań. Wykorzystanie klastra obliczeniowego pozwala na uruchomienie bardzo dużej liczby agentów działających jednocześnie, co przekłada się na zwiększenie eksploracji przestrzeni rozwiązań, a w efekcie na lepsze wyniki końcowe działania algorytmu. Zaproponowana metoda nie przyjmuje dodatkowych założeń dotyczących rozwiązywanego problemu w porównaniu do standardowego algorytmu mrówkowego, co zapewnia jej uniwersalność. Ponadto przedstawiono też możliwości przeniesienia mechanizmu desynchronizacji wiedzy globalnej do innych agentowych algorytmów optymalizacyjnych oraz symulacji.

Praca udostępniona publicznie: Ant Colony Optimization with Distributed Pheromones Matrix for Discrete Large-scale Optimization Problems

Recenzje: Recenzja prof. K. Kurowskiego | Recenzja prof. D. Barbuchy

Ważniejsze publikacje doktoranta:

1. Starzec, M., Starzec, G., Byrski, A., Turek, W., & Piętak, K. (2020). Desynchronization in distributed Ant Colony Optimization in HPC environment. Future Generation Computer Systems, 109, 125-133.
2. Starzec, M., Starzec, G., Byrski, A., & Turek, W. (2019). Distributed ant colony optimization based on actor model. Parallel Computing, 90, 102573.
3. Starzec, M., Starzec, G., Byrski, A., Turek, W., & Kisiel-Dorohinicki, M. (2019). Distributed ant system for difficult transport problems. Journal of Intelligent & Fuzzy Systems, 37(6), 7347-7356.
4. Starzec, M., Starzec, G., & Paciorek, M. (2020). Desynchronization of simulation and optimization algorithms in HPC Environment. Computer Science, 21(3).

—-