Doktoraty Wydziału IET

mgr inż. Mateusz Godzik

Promotor: prof. dr hab. inż. Aleksander Byrski (AGH)
Promotor Pomocniczy: dr inż. Jacek Dajda (AGH)
Dyscyplina: Informatyka techniczna i telekomunikacja

Teza rozprawy:
Hybrydyzacja ewolucyjnego systemu wieloagentowego (EMAS) polegająca na wprowadzeniu heterogenicznych agentów, podejmujących przez pewien czas przeszukiwanie przestrzeni rozwiązań przy pomocy innych metod globalnej optymalizacji (np. inteligencji roju) pozwoli na poprawę skuteczności i efektywności w porównaniu do referencyjnych metod niehybrydowych.

Abstract:
Despite the fact that faster and more efficient computers are being developed, researchers working in the field of computational science still have to deal with a group of problems resisting the effective use of the deterministic method. When solving hard problems, it turns out that e.g. using exact methods, after crossing a seemingly inconspicuous boundary (for TSP it is a dozen cities) it is impossible to achieve an optimal solution in a reasonable time regardless of the quality of the used equipment. Perhaps in the future the situation will change thanks to the use of, for example, quantum computing, but so far it is necessary to continue searching and developing innovative algorithms, very often assigned to the so-called metaheuristics group. One of the proven, universal metaheuristics is the Evolutionary Multi Agent System (EMAS). It consists of a group of agents, subject to evolutionary rules, whose capabilities and actions are limited by the resources associated with the quality of the solution to the problem. The algorithm was proposed in 1996 by Krzysztof Cetnarowicz and has been developed ever since. This dissertation focuses on the proposal of a new agent metaheuristics, created as a hybrid of EMAS with other metaheuristics. EMAS agents, based on a set of predefined rules, decide from time to time to search the solution space using other global optimization methods. The transition to the hybrid step and the return are fully compatible with EMAS, which involves the realization of appropriate adaptation of transferred resources (energy). The main original elements in the work are the proposal of a new metaheuristic algorithm, embedding it in the EMAS environment (along with the necessary energy redistribution methods), preparation and testing of a number of agent control rules, and the use of the developed hybrids to solve a number of multidimensional benchmark problems and problems encountered at competitions held at the well-known international evolutionary conference CEC. The analysis of the obtained experimental results showed that the introduced changes made it possible to improve the efficiency and effectiveness of the thus developed HEMAS in comparison with the reference algorithms, thus proving the truth of the thesis made at the beginning of the dissertation. The dissertation begins with a motivation and thesis statement, followed by a review of the current state of the art on various optimization methods, with a particular focus on the algorithms used in the hybrid system. The next section is devoted to describing the concept of hybrid metaheuristics using the EMAS-derived concept of autonomous agents, while giving agents the ability to run other metaheuristics. The dissertation is concluded with a presentation and discussion of experimental results of various versions of HEMAS. The presented results can serve to expand knowledge in the area of evolutionary agent systems and provide a starting point for using the presented systems to solve computational problems posed by readers.

Streszczenie
Pomimo tego, iż opracowuje się coraz szybsze i wydajniejsze komputery, badacze działający w obszarze nauk obliczeniowych ciągle muszą się mierzyć z grupą problemów opierającą się efektywnemu zastosowaniu metod deterministycznych. Rozwiązując trudne problemy obliczeniowe okazuje się, że znalezienie rozwiązania optymalnego nie jest możliwe, przykładowo stosując pełen przegląd po przekroczeniu na pierwszy rzut oka niepozornej granicy (dla TSP jest to kilkanaście miast) nie ma możliwości doczekania się rozwiązania w rozsądnym czasie, niezależnie od jakości stosowanego sprzętu. Być może w przyszłości sytuacja zmieni się dzięki zastosowaniu choćby obliczeń kwantowych, ale póki co konieczne jest dalsze poszukiwanie i rozwijanie nowatorskich algorytmów, bardzo często przypisywanych do tzw. grupy metaheurystyk. Jedną ze sprawdzonych, uniwersalnych metaheurystyk jest agentowy model obliczeń ewolucyjnych (EMAS - ang. Evolutionary Multi Agent System). Składa się on z grupy agentów, podlegających zasadom ewolucji, których możliwości i akcje ograniczone są poprzez zasoby związane z jakością posiadanego rozwiązania problemu. Algorytm ten został zaproponowany w 1996 roku przez Krzysztofa Cetnarowicza i jest od tego czasu rozwijany. Niniejsza dysertacja skupia się na propozycji nowej metaheurystyki agentowej, powstałej jako hybryda EMAS z innymi metaheurystykami. Agenty działające w EMAS, bazując na szeregu wcześniej zdefiniowanych reguł, podejmują co pewien czas decyzję o przeszukiwaniu przestrzeni rozwiązań przy pomocy innych metod globalnej optymalizacji. Przejście do kroku hybrydowego oraz powrót są w pełni kompatybilne z EMAS, co wiąże się z realizacją odpowiedniej adaptacji przekazywanych zasobów (energii). Głównymi oryginalnymi elementami w pracy jest propozycja nowego algorytmu metaheurystycznego, osadzenie go w środowisku EMAS (wraz z niezbędnymi metodami redystrybucji energii), przygotowanie i przetestowanie szeregu reguł sterujących agentami oraz zastosowanie opracowanych hybryd do rozwiązania szeregu wielowymiarowych problemów benchmarkowych oraz problemów spotykanych na konkursach organizowanych w ramach znanej, międzynarodowej konferencji ewolucyjnej CEC. Analiza otrzymanych wyników eksperymentów wykazała, że wprowadzone zmiany umożliwiły poprawę efektywności i skuteczności opracowanego w ten sposób HEMAS w porównaniu do algorytmów referencyjnych, wykazując tym samym prawdziwość tezy postawionej na początku rozprawy. Rozprawa rozpoczyna się od podania motywacji i postawienia tezy, a następnie zamieszczono przegląd aktualnego stanu wiedzy dotyczący różnych metod optymalizacyjnych, ze szczególnym uwzględnieniem algorytmów używanych w systemie hybrydowym. Kolejna sekcja poświęcona jest opisie koncepcji hybrydowej metaheurystyki wykorzystującej pochodzącą z EMAS koncepcję autonomicznych agentów, równocześnie dając możliwość agentom uruchamiania innych metaheurystyk. Dysertacja podsumowana zostaje prezentacją i omówieniem wyników eksperymentalnych różnych wersji HEMAS. Zaprezentowane wyniki mogą służyć do poszerzenia wiedzy z obszaru ewolucyjnych systemów agentowych oraz stanowić punkt wyjścia do wykorzystania zaprezentowanych systemów w celu rozwiązania problemów obliczeniowych stawianych przez czytelników.

Ważniejsze publikacje doktoranta:

• M. Godzik, J. Dajda, M. Kisiel-Dorohinicki, A. Byrski, L. Rutkowski, P. Orzechowski, J. Wagenaar, J. H. Moore: Applying autonomous hybrid agent-based computing to difficult optimization problems. W: Journal of Computational Science, 64, 2022.
• M. Godzik: Energy Redistribution in Autonomous Hybridization of Agent-based Computing. W: Computer Science, 22(3), 2021.
• M. Godzik, M. Idzik, K. Piętak, A. Byrski, M. Kisiel-Dorohinicki: Autonomous hybridization of agent-based computing. W: Computational collective intelligence: 12th International Conference, ICCCI 2020, Da Nang, Wietnam, 30 Listopad - 3 Grudzień 2020: eds. Ngoc Thanh Nguyen, [et al.]. — Cham : Springer Nature Switzerland AG, cop. 2020. — (Lecture Notes in Artificial Intelligence), s. 139–151.
• M. Godzik, B. Grochal, J. Piekarz, M. Sieniawski, A. Byrski, M. Kisiel-Dorohinicki: Differential evolution in agent-based computing. W: Intelligent information and database systems : 11^th Asian conference, ACIIDS 2019 : Yogyakarta, Indonezja, 8–11 Kwiecień 2019: eds. Ngoc Thanh Nguyen, [et al.]. — Switzerland : Springer Nature Switzerland AG, cop. 2019. — (Lecture Notes in Computer Science), s. 228–241.

Nagrody i wyróżnienia doktoranta:

• Nomination for Best Student Paper Award na 11^th Asian Conference on Intelligent Information and Database Systems, 2019.
• Best Student Paper Award na 12^th International Conference on Computational Collective Intelligence, 2020.