Doktoraty Wydziału IET

Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
                             

^   **PRZEWODNICZĄCY I RADA DYSCYPLINY**    \\    **INFORMATYKI TECHNICZNEJ I TELEKOMUNIKACJI**    \\    **AKADEMII GÓRNICZO-HUTNICZEJ im. ST. STASZICA W KRAKOWIE**   ^
|   zapraszają na    \\    publiczą dyskusję nad rozprawą doktorską    \\      \\   //mgr inż. Mateusza Starca//      \\                 |
|  **ANT COLONY OPTIMIZATION WITH DISTRIBUTED PHEROMONES MATRIX FOR DISCRETE LARGE-SCALE OPTIMIZATION PROBLEMS**  |
|  Dyskusja odbędzie się 22 czerwca 2021 roku o godz. 15:00 w formie on-line   \\  [[https://tinyurl.com/by49tvpc|Link do spotkania w systemie Microsoft Teams]]  |
|  **PROMOTOR:**  prof. dr hab. inż. Aleksander Byrski, Instytut Informatyki AGH  |
|  **PROMOTOR POMOCNICZY:**  dr inż. Kamil Piętak, Instytut Informatyki AGH  |
|  ** RECENZENCI:**  dr hab. Dariusz Barbucha, Katedra Systemów Informacyjnych UM w Gdyni  |
|  ** RECENZENCI:**  dr hab. inż. Krzysztof Kurowski, Instytut Chemii Bioorganicznej PAN  |
|  Z rozprawą doktorską i opiniami recenzentów można się zapoznać \\ w Czytelni   Biblioteki Głównej AGH, al. Mickiewicza 30  |

\\
\\
\\
----

\\


\\

==== Ant Colony Optimization with Distributed Pheromones Matrix for Discrete Large-scale Optimization Problems ====
     
\\

//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:**  {{ :2021:mstarzec:doktorat-5.pdf |Ant Colony Optimization with Distributed Pheromones Matrix for Discrete Large-scale Optimization Problems}}

 **Recenzje:**  
{{ :2021:mstarzec:recenzja_doktoratu_m._starca_-_k._kurowski.pdf |Recenzja prof. K. Kurowskiego}} | 
{{ :2021:mstarzec:starzec_mateusz_recenzja_prof._dariusz_barbucha.pdf |Recenzja prof. D. Barbuchy}}

\\

----

\\

 **Ważniejsze publikacje doktoranta**:

  - 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.
  - Starzec, M., Starzec, G., Byrski, A., & Turek, W. (2019). Distributed ant colony optimization based on actor model. Parallel Computing, 90, 102573.
  - 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.
  - Starzec, M., Starzec, G., & Paciorek, M. (2020). Desynchronization of simulation and optimization algorithms in HPC Environment. Computer Science, 21(3).
----
Doktoraty Wydziału IET

Narzędzia użytkownika

Narzędzia witryny

Narzędzia strony
