Algorytm genetyczny oparty na agentach — rozproszone przeszukiwanie ewolucyjne za pomocą autonomicznych agentów
- Autor metody
- Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
- Rok
- 1990s
- Typ
- Hybrid evolutionary-agent simulation
- Rodzina
- Simulation / optimization
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Algorytm genetyczny oparty na agentach (ABGA) dzieli populację algorytmu genetycznego na sieć autonomicznych agentów, z których każdy utrzymuje lokalną podpopulację i ewoluuje ją niezależnie.
Agenci okresowo wymieniają osobniki (migracja) w oparciu o zasady bliskości lub komunikacji, umożliwiając równoległą eksplorację przestrzeni poszukiwań, przy jednoczesnym zachowaniu różnorodności populacji i unikaniu przedwczesnej zbieżności.
Intuicja stojąca za metodą
Konwencjonalny algorytm genetyczny traktuje całą populację jako jeden zbiór, co może prowadzić do szybkiej zbieżności do lokalnych optimów, gdy dominuje jeden genotyp. Podejście oparte na agentach zamiast tego rozdziela podpopulacje między półautonomiczne agenty rozmieszczone w topologii sąsiedztwa. Każdy agent lokalnie wykonuje własną selekcję, krzyżowanie i mutację, a następnie okazjonalnie wymienia osobniki o wysokiej wartości funkcji celu z sąsiednimi agentami. Odzwierciedla to sposób, w jaki specjacja biologiczna zachodzi w populacjach geograficznie izolowanych, ale okazjonalnie połączonych, pozwalając różnym presjom ewolucyjnym działać równolegle i rekombinować rozwiązania w różnych niszach.
Historia
Rozproszone i równoległe algorytmy genetyczne pojawiły się na początku lat 90. XX wieku, gdy badacze starali się przezwyciężyć przedwczesną zbieżność i wykorzystać sprzęt równoległy. Adamidis i Petridis (1996) sformalizowali współpracujące populacje agentów o różnych zachowaniach ewolucyjnych. Ujęcie oparte na agentach zyskało na popularności pod koniec lat 90. i w latach 2000., wraz z rozprzestrzenianiem się modelowania opartego na agentach w naukach obliczeniowych, formalizując model interakcji autonomicznych, sterowanych topologią, który jest obecnie szeroko stosowany w optymalizacji złożonej.
Kiedy stosować
Użyj ABGA, gdy krajobraz funkcji celu jest nieregularny lub multimodalny, a standardowe GA konsekwentnie zbiegają przedwcześnie; gdy dostępny jest sprzęt równoległy lub rozproszony, który może obsługiwać współbieżne procesy agentów; lub gdy struktura problemu naturalnie mapuje się na półniezależne podproblemy (np. regionalne łańcuchy dostaw, polityka wielosektorowa). Nadaje się również do eksploracji zachowania algorytmu pod wpływem heterogenicznych presji ewolucyjnych. NIE używaj, gdy problem ma pojedynczy, unimodalny krajobraz (wystarczy prostszy GA), gdy narzut komunikacji między agentami dominuje nad obliczeniami, gdy rozmiary populacji są zbyt małe, aby można je było sensownie podzielić, lub gdy wymagana jest scentralizowana populacja dla dokładnej powtarzalności.
Ograniczenia i uwagi
- Dostrajanie polityki migracji (wskaźnik, topologia, częstotliwość) dodaje hiperparametry, które wymagają starannej kalibracji i są zależne od problemu.
- Narzut komunikacyjny między agentami może niwelować korzyści z równoległości w środowiskach obliczeniowych o dużych opóźnieniach lub luźno powiązanych.
- Teoretyczne gwarancje zbieżności są słabsze niż w przypadku standardowych GA; formalna analiza dynamiki ABGA pozostaje otwartym obszarem badań.
- Powtarzanie wyników wymaga ustalenia topologii agentów, harmonogramu migracji i losowych ziaren dla wszystkich agentów, co komplikuje replikację.
- Jeśli rozmiary podpopulacji są zbyt małe, poszczególni agenci są podatni na dryf genetyczny niezależnie od migracji.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Utrzymuje wyższą różnorodność populacji niż panmiktyczne GA, zmniejszając przedwczesną zbieżność na nieregularnych krajobrazach funkcji celu.
- Naturalnie wykorzystuje równoległą lub rozproszoną infrastrukturę obliczeniową do problemów optymalizacji na dużą skalę.
- Heterogeniczne ustawienia operatorów na agenta pozwalają na jednoczesną eksplorację i wykorzystanie różnych strategii.
- Migracja najlepiej przystosowanych osobników między agentami umożliwia rekombinację między niszami, która może odkryć nowe, wysokiej jakości rozwiązania.
- Modularna architektura ułatwia integrację specyficznych dla dziedziny heurystyk w pętlach ewolucyjnych poszczególnych agentów.
- Dobrze skaluje się z wymiarowością problemu, gdy podpopulacje można sensownie podzielić.
Zastosowania
- Planowanie i logistyka: rozproszone problemy typu job-shop lub vehicle routing, gdzie regionalne podproblemy naturalnie mapują się na agentów.
- Optymalizacja projektowania inżynierskiego: projektowanie konstrukcyjne lub aerodynamiczne z multimodalnymi przestrzeniami poszukiwań korzystającymi z równoległej eksploracji nisz.
- Symulacja polityki: optymalizacja parametrów polityki w modelach symulacji społecznych, gdzie agenci reprezentują aktorów regionalnych lub sektorowych.
- Wyszukiwanie hiperparametrów uczenia maszynowego: równoległe ewolucyjne dostrajanie konfiguracji modeli na rozproszonych klastrach obliczeniowych.
- Bioinformatyka: przewidywanie struktury białek i wnioskowanie o sieciach genowych na wysokowymiarowych, nieregularnych krajobrazach funkcji celu.
- Sztuczna inteligencja w grach i robotyka: ewolucja strategii zachowań agentów w środowiskach wieloagentowych z dynamiką koewolucyjną.
Jak to działa
Jak to działa
Zdefiniuj topologię agentów: określ liczbę agentów (podpopulacji), ich strukturę sąsiedztwa (pierścień, siatka, graf małego świata lub w pełni połączony) oraz protokół komunikacyjny regulujący, kiedy i jak agenci wymieniają osobniki. Każdy agent jest autonomiczną jednostką obliczeniową z własną pulą chromosomów.
Zainicjuj lokalną podpopulację każdego agenta losowo wygenerowanymi chromosomami (lub zainicjowanymi rozwiązaniami). Ustaw lokalny rozmiar populacji, operatory genetyczne (typ i wskaźnik krzyżowania, wskaźnik mutacji) oraz mechanizm selekcji (turniejowy, ruletkowy, oparty na randze) niezależnie dla każdego agenta lub jednolicie dla wszystkich agentów.
Każdy agent niezależnie wykonuje kilka generacji selekcji, krzyżowania i mutacji na swojej lokalnej podpopulacji. Działając równolegle (lub pseudo-równolegle w symulacji sekwencyjnej), agenci eksplorują różne regiony przestrzeni rozwiązań przy potencjalnie różnych konfiguracjach operatorów, zachowując różnorodność w całym systemie.
W zdefiniowanych interwałach migracji agenci wymieniają podzbiór swoich najlepiej przystosowanych osobników z sąsiednimi agentami zgodnie z polityką migracji (np. wysyłanie najlepszych, odbieranie i zastępowanie najgorszych). Wskaźnik migracji i topologia kształtują równowagę między lokalną eksploracją a globalną eksploracją; zbyt częsta migracja niszczy różnorodność, zbyt rzadka migracja marnuje rozproszoną architekturę.
Wszystkie zaimportowane i lokalnie wyewoluowane chromosomy są oceniane za pomocą wspólnej funkcji celu. Agenci mogą stosować lokalną presję selekcyjną po migracji, aby zintegrować odebrane osobniki ze swoją populacją, potencjalnie odrzucając mniej przystosowanych obecnych osobników. Ocena funkcji celu stanowi dominujący koszt obliczeniowy.
Zakończ, gdy zostanie spełnione globalne kryterium zatrzymania (maksymalna liczba generacji, zbieżność najlepszej funkcji celu między agentami lub upływ czasu). Zbierz najlepsze rozwiązanie znalezione spośród wszystkich agentów jako ostateczny wynik. Raportuj krzywe zbieżności dla każdego agenta, aby zdiagnozować różnorodność populacji i skuteczność migracji.
Częste pułapki
- Ustawienie zbyt wysokiego wskaźnika migracji powoduje zapaść różnorodności podpopulacji do de facto pojedynczego zbioru, eliminując główną zaletę architektury agentowej.
- Ignorowanie projektowania topologii sąsiedztwa: w pełni połączona topologia powoduje szybką zbieżność; pierścień z niską częstotliwością migracji może pozostawić agentów odizolowanych i w stagnacji.
- Ocena funkcji celu tylko lokalnie, bez wspólnej globalnej funkcji celu, prowadzi do tego, że agenci optymalizują niekompatybilne cele.
- Mylenie ABGA z algorytmem genetycznym wielokryterialnym: ABGA jest wariantem architektonicznym dla efektywności poszukiwań, nie jest z natury metodą wielokryterialną — wielokryterialne ABGA wymaga dodatkowej maszynerii Pareto.
- Zatrzymanie się na zbieżności indywidualnego agenta zamiast zbieżności globalnej może spowodować pominięcie lepszych rozwiązań wciąż ewoluujących u innych agentów.
Najczęściej zadawane pytania
Czym ABGA różni się od standardowego równoległego GA?
Standardowy równoległy GA zazwyczaj rozdziela ocenę funkcji celu pojedynczej, scentralizowanej populacji między procesory. ABGA daje każdemu agentowi autonomiczną podpopulację z własną pętlą ewolucyjną; interakcja odbywa się tylko poprzez jawną migrację, a nie poprzez wspólny zbiór. Ta różnica zachowuje niezależne presje selekcyjne na agenta.
Jaką topologię migracji wybrać?
Topologie pierścieniowa i siatkowa są standardowymi punktami wyjścia: ograniczają przepływ migracji i zachowują różnorodność. Topologie małego świata (kilka połączeń dalekiego zasięgu dodanych do pierścienia) przyspieszają propagację dobrych rozwiązań bez niszczenia różnorodności. Topologie w pełni połączone zazwyczaj należy unikać, chyba że chcesz uzyskać szybkie zachowanie zbieżności.
Ilu agentów i jaki rozmiar podpopulacji jest odpowiedni?
Częstą heurystyką jest 4-16 agentów z podpopulacjami po 20-50 osobników, co daje łączną populację porównywalną do tej, którą użyłby standardowy GA. Zbyt mała liczba agentów niweczy przewagę różnorodności architektury; zbyt wielu agentów z maleńkimi podpopulacjami cierpi na dryf. Konieczne jest empiryczne dostrajanie do konkretnego problemu.
Czy ABGA może być używany do optymalizacji wielokryterialnej?
Tak, ale należy dodać dodatkową maszynerię Pareto (taką jak rangowanie NSGA-II w każdym agencie). Architektura agentowa pomaga następnie utrzymać bardziej zróżnicowane przybliżenie frontu Pareto. Jest to podstawa wariantów ABGA wielokryterialnych.
Czy ABGA gwarantuje znalezienie globalnego optimum?
Nie. Podobnie jak wszystkie GA, ABGA są heurystyczne i nie zapewniają gwarancji globalnej optymalności. Lepsze zachowanie różnorodności zwiększa w praktyce prawdopodobieństwo uniknięcia lokalnych optimów, ale gwarancje zbieżności nie są silniejsze niż w przypadku standardowych GA i stanowią aktywny obszar badań teoretycznych.
Pokrewne metody
Źródła
Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.
Otwórz odnośnik do publikacjiSkopiowano.Genetic algorithm. Wikipedia.
Otwórz odnośnik do publikacjiSkopiowano.