Doktoraty Wydziału IET

mgr inż. Wojciech Korczyński

Promotor: dr hab. inż. Aleksander Byrski (AGH)
Dyscyplina: Informatyka

Klasyczne stwierdzenie no-free-lunch stanowi jedną z głównych motywacji do rozwoju nowych metaheurystyk, tj. metod ogólnego przeznaczenia stosowanych w rozwiązywaniu problemów poszukiwawczych i optymalizacyjnych trudnych do rozwiązania przy pomocy powszechnych technik analitycznych. Problemy te zwane są często „problemami czarnej skrzynki” z racji nikłej wiedzy nt. ich dziedziny. Metaheurystyki, mimo że nie gwarantują znalezienia rozwiązania optymalnego, pozwalają na uzyskanie zadowalających wyników w krótkim czasie i z wykorzystaniem rozsądnych środków obliczeniowych.

Przez lata wyraźną popularność w dziedzinie obliczeń metaheurystycznych zdobyły metody populacyjne, a w szczególności algorytmy ewolucyjne inspirowane darwinowską teorią doboru naturalnego. W licznych badaniach dowiedziono ich skuteczności w rozwiązywaniu problemów trudnych. Ponadto, prace Michaela Vose'a pozwoliły na uznanie ich jako dobrze zdefiniowanych algorytmów globalnej optymalizacji. Jednakże, klasyczne algorytmy ewolucyjne posiadają pewne wady (np. wysoki nakład obliczeniowy, nieuwzględnienie niektórych ważnych cech ewolucji), które stały się bodźcem do tworzenia nowych metaheurystyk, stanowiących połączenie różnych technik i podejść.

Znaczący skok jakościowy w dziedzinie obliczeń ewolucyjnych przyniosło wprowadzenie koncepcji agentowości. Okazało się, że systemy agentowe są w stanie osiągać lepsze rozwiązania niż techniki klasyczne, wymagając przy tym mniejszego nakładu obliczeniowego. Jednocześnie, możliwa stała się symulacja takich istotnych cech ewolucji, jak dekompozycja populacji czy koewolucja gatunków. Jednym z przykładów skutecznego zastosowania systemu wieloagentowego w obszarze metaheurystyk ewolucyjnych jest system EMAS (Evolutionary Multi-Agent System).

Dalsze usprawnienia zostały zapewnione przez metody hybrydowe, takie jak algorytmy memetyczne, które łączą eksploatację lokalnego przeszukiwania ze zorientowanymi na eksplorację metaheurystykami ewolucyjnymi. Dodatkowo, wstępne badania wykazały możliwość efektywnej realizacji algorytmów memetycznych w środowisku agentowym.

Pomimo iż metaheurystyki populacyjne stanowią efektywne narzędzia, problemem pozostaje ich wydajność. W szczególności w tę kategorię wpisują się algorytmy memetyczne, z racji ogromnej liczby ewaluacji osobników. Dlatego niezbędne jest opracowywanie nowych, wydajnych metod memetycznych, gdyż zastosowanie dedykowanych operatorów przeszukiwania lokalnego umożliwi zwiększenie efektywności przeszukiwania przestrzeni rozwiązań w agentowych systemach obliczeniowych w porównaniu do ewolucyjnych systemów wieloagentowych oraz klasycznych algorytmów ewolucyjnych, umożliwiając jednocześnie osiągnięcie lepszych rozwiązań w krótszym czasie.

W celu poparcia powyższej tezy dokonano przeglądu metod poprawy wydajności metaheurystyk. Następnie, zaprezentowano technikę buforowania funkcji oceny przystosowania, umożliwiającą zmniejszenie złożoności obliczeń memetycznych i pozwalającą na uzyskanie lepszych wyników w krótszym czasie, niż w przypadku relewantnych metod ewolucyjnych i agentowych. Kolejno, przeprowadzono eksperymentalną weryfikację zaproponowanego podejścia przy wykorzystaniu trudnych, wielowymiarowych (5000 wymiarów) funkcji ciągłych. Również, przedyskutowano możliwości przyśpieszenia obliczeń poprzez delegację ich najkosztowniejszych części do urządzeń GPU i FPGA.

Wśród najważniejszych efektów niniejszej pracy zidentyfikować można:

• opisanie idei memetyzacji w trakcie życia agenta, jako alternatywy dla klasycznego podejścia, w którym proces lokalnego przeszukiwania odbywa się przy okazji reprodukcji,
• zaproponowanie i implementacja techniki buforowania funkcji oceny przystosowania, która to technika pozwala na redukcję złożoności ewaluacji jakości rozwiązań w ciągłej przestrzeni przeszukiwań,
• adaptacja platformy obliczeniowej PyAgE do obliczeń hybrydowych z wykorzystaniem urządzeń GPU i FPGA,
• zaprojektowanie komponentów delegujących kosztowne operacje metaheurystyczne do jednostek GPGPU i implementacja tychże na platformie PyAgE,
• zaprojektowanie komponentów delegujących kosztowne operacje metaheurystyczne do jednostek FPGA i implementacja tychże na platformie PyAgE,
• przeprowadzenie szeregu szczegółowych eksperymentów, popartych analizą statystyczną, porównujących skuteczność dyskutowanych algorytmów w procesie rozwiązywania wielowymiarowych trudnych problemów ciągłych,
• przeprowadzenie dogłębnej analizy wpływu poszczególnych parametrów memetycznych na jakość uzyskiwanych rozwiązań,
• zastosowanie dyskutowanych klasycznych i memetycznych algorytmów w praktycznym inżynieryjnym problemie optymalizacji kształtu rotującego dysku.

Recenzja - dr hab. inż. Bogdan Trawiński, prof. PWr

Recenzja - dr hab. Dariusz Barbucha, prof. AMG

1. W. Korczyński, A. Byrski, M. Kisiel-Dorohinicki: Buffered local search for efficient memetic agent-based continuous optimization, Journal of Computational Science, vol. 20, s. 112–117, Elsevier, 2017.
   IF=1.078, MNiSW=30
2. W. Korczyński, A. Byrski, R. Dębski, M. Kisiel-Dorohinicki: Classic and agent-based evolutionary heuristics for shape optimization of rotating discs, Computing and Informatics, vol. 36 (2), s. 331–352, Slovak Academy of Sciences, 2017.
   IF=0.504, MNiSW=15
3. W. Korczyński, M. Kisiel-Dorohinicki, A. Byrski: Lamarckian and lifelong memetic search in agent-based computing, Proceedings of EvoApplications 2017 - the 20th European Conference on Applications of Evolutionary Computation, 19-21 April, 2017, Amsterdam, The Netherlands, s. 253–265, Springer International Publishing, 2017.
   IF=0, MNiSW=0
4. W. Korczyński, A. Byrski, M. Kisiel-Dorohinicki: Efficient memetic continuous optimization in agent-based computing, Procedia Computer Science, vol. 80, s. 845-854, Elsevier, 2016.
   IF=0, MNiSW=0
5. M. Kaziród, W. Korczyński, A. Byrski: Agent-oriented computing platform in Python, Proceedings of IAT 2014 - the 2014 IEEE/WIC/ACM international conference on Intelligent Agent Technology, 11–14 August 2014, Warsaw, Poland, s. 365-372, IEEE, 2014.
   IF=0, MNiSW=10
6. A. Byrski, W. Korczyński, M. Kisiel-Dorohinicki: Memetic multi-agent computing in difficult continuous optimisation, Advanced Methods and Technologies for Agent and Multi-Agent Systems, vol. 252, Frontiers in Artificial Intelligence and Applications, s. 181-190, IOS Press, 2013.
   IF=0, MNiSW=10