MACEA

MCACEA ( Multiple Coordinated Agents Coevolution Evolutionary Algorithm ) to ogólna struktura, która wykorzystuje pojedynczy algorytm ewolucyjny (EA) na agenta, dzieląc się swoimi optymalnymi rozwiązaniami w celu koordynowania ewolucji populacji EA przy użyciu celów współpracy. Ramy te można wykorzystać do optymalizacji niektórych charakterystyk wielu współpracujących agentów w problemach optymalizacji matematycznej . Mówiąc dokładniej, ze względu na swój charakter, w którym optymalizuje się zarówno cele indywidualne, jak i cele współpracy, MACEA jest używany w wielocelowych problemach optymalizacji.

Opis i realizacja

MACEA wykorzystuje wiele EA (po jednym na każdego agenta), które ewoluują własne populacje, aby znaleźć najlepsze rozwiązanie dla powiązanego problemu zgodnie z ich indywidualnymi ograniczeniami i ograniczeniami współpracy oraz obiektywnymi wskaźnikami. Każdy EA to problem optymalizacyjny, który działa równolegle i który wymienia pewne informacje z innymi podczas etapu oceny. Ta informacja jest potrzebna, aby każdy EA mógł zmierzyć cele koordynacyjne rozwiązań zakodowanych we własnej populacji, biorąc pod uwagę możliwe optymalne rozwiązania pozostałych populacji innych EA. W tym celu każdy pojedynczy EA otrzymuje informacje dotyczące najlepszych rozwiązań pozostałych przed oceną wspólnych celów każdego możliwego rozwiązania własnej populacji.

Ponieważ wartości celu współpracy zależą od najlepszych rozwiązań innych populacji, a optymalność rozwiązania zależy zarówno od celów indywidualnych, jak i celów współpracy, tak naprawdę nie jest możliwe wybranie i przesłanie najlepszego rozwiązania każdego planisty do innych. Jednak MACEA dzieli etap oceny wewnątrz każdego EA na trzy części: W pierwszej części EA identyfikują najlepsze rozwiązanie, biorąc pod uwagę tylko jego indywidualne wartości obiektywne i wysyłają je do innych EA; w drugiej części obliczane są wartości celu współpracy wszystkich rozwiązań z uwzględnieniem otrzymanych informacji; aw trzeciej części EA obliczają przydatność rozwiązań, biorąc pod uwagę wszystkie wartości celów indywidualnych i współpracy.

Chociaż każda populacja może zaoferować tylko unikalne optymalne rozwiązanie, każda EA utrzymuje zbiór optymalnych rozwiązań Pareto i wybiera unikalne optymalne rozwiązanie na końcu, gdy ostatnia populacja została już uzyskana. Dlatego, aby móc określić unikalne optymalne rozwiązanie zgodnie z indywidualnymi celami w każdej generacji (a więc używając go z ramą MCACEA), krok odpowiedzialny za wybór ostatecznego optymalnego rozwiązania musi być również uwzględniony na etapie oceny każdy EA.

Faza oceny w MCACEA

Pełna faza oceny poszczególnych współpracujących EA jest podzielona na sześć etapów. Podczas poszukiwania rozwiązania pojedynczego EA wykorzystywane są tylko dwa pierwsze etapy tego nowego procesu oceny. MACEA rozszerza ten proces z tych dwóch kroków do kolejnych sześciu:

1. Ocena poszczególnych celów każdego rozwiązania.

2. Obliczenie przydatności każdego rozwiązania za pomocą pojedynczej funkcji oceny (zawierającej tylko poszczególne cele).

3. Znalezienie najlepszego rozwiązania populacji.

4. Wysyłanie (i otrzymywanie) najlepszego rozwiązania do innych pojedynczych EA.

5. Kalkulacja celów współpracy z uwzględnieniem otrzymanych informacji od innych EA.

6. Obliczenie przydatności każdego rozwiązania z pełną funkcją ewaluacji (zawierającą zarówno cele indywidualne, jak i cele współpracy), które uzyskano w krokach 1 i 5.

Podobne podejścia

Chociaż MACEA może wyglądać podobnie do zwykłej równoległości EA, w tym przypadku zamiast rozdzielać rozwiązania całego problemu między różne EA, które okresowo udostępniają swoje rozwiązania, algorytm dzieli problem na mniejsze problemy, które są rozwiązywane jednocześnie przez każde EA biorąc pod uwagę rozwiązania części problemów, które uzyskują inne EA.

Inną możliwością jest wysłanie najlepszych, całkowicie ocenionych rozwiązań poprzedniej generacji do innych EA zamiast naszego obecnego najlepszego, ocenianego indywidualnie celu. Niemniej jednak podejście to wprowadza uprzedzenia w kierunku przestarzałych, całkowicie ocenionych trajektorii, podczas gdy MCACEA robi to w kierunku obecnie dobrych, indywidualnie ocenianych trajektorii.

Aplikacje

MACEA została wykorzystana do wyszukiwania i optymalizacji trajektorii bezzałogowych statków powietrznych (UAV) podczas jednoczesnego lotu w tym samym scenariuszu.

Zobacz też

• Sztuczny rozwój
• Biologia rozwojowa
• Obliczenia ewolucyjne
• Robotyka ewolucyjna
• Sprawność fizyczna
• Krajobraz fitness
• Przybliżenie sprawności
• Operatory genetyczne
• Interaktywne obliczenia ewolucyjne
• MOEA Framework , otwarta platforma Java dla wieloobiektywnych algorytmów ewolucyjnych
• ECJ , zestaw narzędzi do implementacji algorytmów ewolucyjnych
• Paradiseo , ramy metaheurystyki

Bibliografia

L. de la Torre, JM de la Cruz i B. Andrés-Toro. Ewolucyjny planer trajektorii dla wielu UAV w realistycznych scenariuszach . Transakcje IEEE dotyczące robotyki, tom. 26, nie. 4, s. 619–634, sierpień 2010.