Koewolucja

Koewolucja
Polecane artykuły


Koewolucja - wzajemna ewolucja dwóch, lub więcej, gatunków. W wyniku koewolucji każdy z gatunków nią dotknięty powoli dostosowuje się do reszty. Przykładowo występuje ona wśród drapieżników i ich ofiar lub zapylaczy i kwiatów (szczególnie storczyków). Korzystanie z mechanizmu koewolucyjnego jest istotnym elementem, przyczyniającym się do rozwiązywania różnych problemów. Termin ten, poza biologią, jest również stosowany analogicznie w takich dziedzinach jak socjologia, informatyka czy astronomia.
Współzależna ewolucja owadów i roślin została wspomniana w książce On the Origin of Species (1859) autorstwa Darwin’a C.

Algorytmy koewolucyjne

Biologiczne mechanizmy, będące oparte na darwinowskiej teorii ewolucji, mają różne zastosowanie. Istnieje, wykorzystująca je, heurystyczna metoda i służy do rozwiązywania problemów złożonych obliczeniowo. Algorytm koewolucyjny to pewnego rodzaju algorytm ewolucyjny, albo grupa algorytmów ewolucyjnych i jest dedykowany do określonych problemów. Góruję on nad algorytmem ewolucyjnym w konkretnych przypadkach. Korelacja jednego osobnika z innymi wpływa na jego wartość przystosowania do nich.

Algorytmy koewolucyjne dzielą się z kolei na[1]:

  1. "Algorytmy kooperacyjne
  2. Algorytmy konkurencyjne"

Jeżeli osobniki wykazują lepszą współpracę ze sobą są nagradzane w algorytmie kooperacyjnym, natomiast współzawodnictwo jest wywyższone w algorytmach konkurencyjnych. Algorytmy koewolucyjne działają na zasadzie opartej na “przetwarzaniu wielu populacji”, jak również ocenie osobników stosownie do ich przystosowania do środowiska oraz jak kooperują z osobnikami, będącymi z obcych populacji[2].

Wytyczne konieczne do zastosowania algorytmów koewolucyjncyh to podział problemu i przypisania każdego z członów do oddzielnej populacji, gdyż każda ewoluuje osobno oraz poszczególny osobnik jest tylko elementem domniemanego rozwiązania. Metoda koewolucyjna ma pozytywne zastosowanie w wielu problemach w obu jej wariantach. Są nimi na przykład określenie systemów nieliniowych lub uszkodzeń czy różne metody inteligentne[3].

Koewolucja konkurencyjna

Krawiec K., Jaskowski W. i Szubert M. w swojej publikacji, dotyczącej ewolucji graczy small-board go, opisują wykorzystanie koewolucyjnego nauczania (Coevolutionary Temporal Difference Learning - CTDL) by wdrażać strategie small-board Go. Z powodu ograniczonej liczby przeciwników spada tzw. obciążenie obliczeniowe ale uprzedza poszukiwania. Dlatego też, patrząc od strony nauki gry, najlepszym wyjściem jest koewolucja, gdyż sprawność jednego z graczy jest zależna od rezultatów interakcji z pozostałymi. Dana interakcja podczas grania pojedynczej gry zwiększa sprawność wygrywającego, a zmniejsza przegranego. Taki program oceny jest zwany koewolucją konkurencyjną[4].
Koewolucyjne nauczanie (Coevolutionary Learning - CEL) dotyczące strategii gry to podążanie za programem oceny konkurencyjności. Zaczyna się od wytypowania początkowej losowej liczby graczy. Na podstawie rozegranych przez nich gier i ich wyników określana jest sprawność. Wybiera się najlepsze strategie i poddaje się np. krzyżowaniu, dzięki czemu powstaje nowa strategia (wynik koewolucji). Koewolucyjne nauczanie jest wykorzystywane w innych dwuosobowych grach, np. NERO, warcaby czy Ant Wars[5].

Koewolucja kooperatywna

Koewolucja kooperatywna (cooperative coevolution) znajduje zastosowanie na przykład w dekompozycji zadań. Dany wariant obliczeń ewolucyjnych wykorzystuje wiele, zamiast jednej, populacji osobników. Ich ocena nie jest dokonywana niezależnie, ponieważ przedstawiają one tylko częściowe rozwiązania problemu. Konieczna tutaj jest agregacja osobników, które pochodzą z różnych populacji. W tej koewolucji pełne rozwiązania nie są formowane na stałe, tylko tymczasowo, aby móc wykorzystać je do przeprowadzenia oceny. Dobór odpowiednich reprezentantów ma tutaj wpływ na pomyślny przebieg przeprowadzanej procedury. Prostą metodą jest zastosowanie reprezentanta, będącego najlepszym osobnikiem wśród populacji z generacji poprzedniej. Celnie dobrany algorytm daje możliwość uzyskania “trafności rozpoznawania”, będące niemal podobnymi do najlepszych stworzonych algorytmów. Dodatkowo metodyka ta ma uniwersalne zastosowanie[6].

Koewolucyjny algorytm analizy portfelowej

W swoim artykule Kameduła M. i Gajda J. wykorzystują mechanizm koewolucji, dla otrzymania odpowiedniego zestawu portfeli z wykorzystaniem genetycznego algorytmu. Taki mechanizm polega na przeprowadzaniu obliczeń w jednakowym czasie dla pewnej grupy podpopulacji, odpowiednio od siebie oddalonych, a pomiędzy nimi zachodzi przepływ pewnych informacji charakteru genetycznego[7].
Autorzy, wykorzystując tę metodę oparli się na założeniu, iż koewolucja zagwarantuje zbliżenie się do optymalnego rozwiązania w szybszy sposób, niż gdyby posłużyli się “niezależnymi przebiegami algorytmu o rozdzielonych populacjach”. Po porównaniu wyników stwierdzono, iż faktycznie algorytmy koewolucyjne działają szybciej, co pozytywnie wpływa na przebieg całego algorytmu[8].

Bibliografia

Przypisy

  1. Kuczkowski Ł., Śmierzchalski R. (2015) Optymalizacja nieciągłych funkcji wielomodalnych z wykorzystaniem kooperacyjnego algorytmu koewolucyjnego, "Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej", Nr 47, s. 103-106
  2. Kuczkowski Ł., Śmierzchalski R. (2015) Optymalizacja nieciągłych funkcji wielomodalnych z wykorzystaniem kooperacyjnego algorytmu koewolucyjnego, "Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej", Nr 47, s. 103-106
  3. Kuczkowski Ł., Śmierzchalski R. (2015) Optymalizacja nieciągłych funkcji wielomodalnych z wykorzystaniem kooperacyjnego algorytmu koewolucyjnego, "Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej", Nr 47, s. 103-106
  4. Krawiec K., Jaśkowski W., Szubert M. (2011) Evolving small-board Go players using coevolutionary temporal difference learning with archives, "International Journal of Applied Mathematics and Computer Science", Vol. 21, no 4, s. 717-731
  5. Krawiec K., Jaśkowski W., Szubert M. (2011) Evolving small-board Go players using coevolutionary temporal difference learning with archives, "International Journal of Applied Mathematics and Computer Science", Vol. 21, no 4, s. 717-731
  6. Krawiec K. (2005) Koewolucja kooperatywna w dekompozycji zadań rozpoznawania obrazów, Wydawnictwo Uniwersytetu Śląskiego, Seria: Zarządzanie i technologie informacyjne, str. 333-358
  7. Kameduła M., Gajda J. (2015) Wpływ parametrów startowych na tempo zbieżności koewolucyjnego algorytmu genetycznego, "Studia Ekonomiczne", Tom 235, s. 100-112
  8. Kameduła M., Gajda J. (2015) Wpływ parametrów startowych na tempo zbieżności koewolucyjnego algorytmu genetycznego, "Studia Ekonomiczne", Tom 235, s. 100-112

Autor: Angelika Trólka