Metody ewolucyjne w wielokryterialnym projektowaniu układów przetwarzania sygnałów
Nr projektu badawczego: 3 T11A 008 29
Politechnika Gdańska, Wydział Elektroniki, Telekomunikacji i Informatyki,
Katedra Systemów Decyzyjnych i Robotyki
Do podstawowych osiągnięć pracy można zaliczyć następujące aspekty przeprowadzonych badań: koncepcja rodzajnika genetycznego oparta na obserwacji przyrody; opracowanie metodologii oraz procedur związanych z rozpoznawaniem rodzajnika genetycznego osobników; zastosowanie operacji genetycznych do osobników o odmiennych wariantach genetycznych; systematyzację i opracowanie metod niszowania w wersji ciągłej i okresowej; wykorzystanie globalnego poziomu optymalności jako ostatecznego wskaźnika efektywności ewolucyjnych poszukiwań; praktyczne zastosowanie opracowanych algorytmów do projektowania układów sterowania oraz układów diagnostyki.
Klasyczny algorytm genetyczny pozbawiony mechanizmu niszowania może prowadzić do przedwczesnej zbieżności do rozwiązań sub-optymalnych. Dlatego procedura rangowania w sensie Pareto powinna być uzupełniona o mechanizm niszowania. Zastosowanie takich modyfikacji pozwala na bardziej efektywną eksplorację przestrzeni parametrów oraz jednocześnie zabezpiecza przed przedwczesną zbieżnością algorytmu ewolucyjnego i pozwala na utrzymanie różnorodności osobników w populacji. Przeprowadzone badania mechanizmów niszowania ujawniły pewną interpretację odpornościową, związaną z podtrzymywaniem egzystencji gęstych (i rzadkich) populacyjnie niszy (gatunków), wbrew mechanizmowi, który reprezentuje ‘ewolucyjną politykę równomiernej hodowli'.
Mechanizmy niszowania rang w porównaniu z niszowaniem przystosowania charakteryzują się ‘silniejszą' ingerencją, bezpośrednio związaną ze zmianą równocześnie rang i struktury dominacji pomiędzy osobnikami. Niszowanie przystosowania stanowi jedynie źródło pośredniej modyfikacji rang, jako że zmiana wektora przystosowania nie musi pociągać za sobą zmiany w strukturze dominacji osobników pomiędzy osobnikami. Zastosowane w algorytmach ewolucyjnych mechanizmy niszowania rang i przystosowania puli rodzicielskiej są zdolne do znalezienia rozwiązań, które są Pareto-optymalne. Wynik taki można wiązać z faktem, iż oba podejścia skutecznie wymuszają różnorodność ewoluujących pokoleń osobników.
Zastosowanie czasowo uruchamianego mechanizmu niszowania w trakcie genetycznych poszukiwań (okresowe niszowanie) nie wpływa znacząco na możliwość osiągnięcia najwyższego globalnego poziomu optymalności. Przeciwnie, na podstawie przeprowadzonych eksperymentów dotyczących ciągłego i okresowego niszowania zaobserwowano, że w każdym okresie działania mechanizmu niszowania obserwuje się systematyczne zwiększanie globalnego poziomu optymalności. Ponadto w przypadku kiedy rozważane kryteria nie są dostatecznie złożone, wówczas wprowadzenie mechanizmu niszowania może być po prostu nieefektywne.
Drugą istotną modyfikacją zaproponowaną w celu poprawienia skuteczności obliczeń ewolucyjnych jest metoda rodzajnikowa GGA rozwiązywania zadań wielokryterialnej optymalizacji, która realizuje ewolucyjne obliczenia z rozpoznawaniem indywidualnego rodzajnika genetycznego osobników. W opisywanym podejściu, na podstawie Pareto-suboptymalnego procesu rangowania, wydobywana jest informacja o stopniu przynależności do danego wariantu genetycznego (podzbioru, sub-populacji) analizowanych osobników. Owa informacja wykorzystywana jest w procesie łącznia i krzyżowania osobników o odmiennym wariancie (rodzajniku).
Wewnątrz każdego rodzajnikowego zbioru Pareto-optymalizacja jest wykorzystywana jako skuteczne narzędzie suboptymalnej oceny "wewnętrznie" jednorodzajnikowej rywalizacji w celu ich jednakowej klasyfikacji oraz selekcji (w większej liczbie) do sub-pul rodzicielskich w każdym kroku iteracji cyklu genetycznego. Metoda rodzajnikowa może być interpretowana jako nowy mechanizm preselekcji zarówno przejściowych, jak i ostatecznych osobników oraz wzajemnego międzyrodzajnikowego wsparcia w genetycznych poszukiwaniach.
Z zastosowania zaproponowanego podejścia z rodzajnikiem genetycznym (GGA) wynikają pewne praktyczne ulepszenia w wydajności obliczeń ewolucyjnych, które uzyskuje się względem klasycznego algorytmu genetycznego (GA), a polegające na: mniejszej wrażliwości na wybór początkowej populacji osobników (rozwiązań); znaczącym zmniejszeniu wpływu (‘przekleństwa') wielowymiarowości; charakterystycznych frontach Pareto, które występują w większej liczbie; naturalnym pielęgnowaniu różnorodności osobników w populacji; reprezentowaniu atrakcyjnej ‘mocy' genetycznych poszukiwań (polegającej na zarówno wewnętrznej, jak i zewnętrznej rywalizacji osobników); zapobieganiu przedwczesnej zbieżności (poprzez restrykcje w krzyżowaniu); uzyskiwaniu bardziej optymalnych rozwiązań; dostarczaniu jasnych przesłanek, co do wyboru ostatecznego rozwiązania.
Główny sukces podejścia rodzajnikowego może być przypisany faktowi uporania się z dużą liczbą kryteriów poprzez redukcję wymiarowości analizowanych przestrzeni kryterialnych. W porównaniu z innymi metodami zaproponowane podejście rodzajnikowe jest proste (zarówno pod względem koncepcji, jak i obliczeń), osadzone na podstawach metodologii GA, bardziej pomysłowo wykorzystuje przesłanki z natury, spełnia wymagania inżynierskiego projektowania, co do decyzji wyboru ostatecznego rozwiązania, oraz otwarte jest na inne nowelizacje i rozwinięcia proponowane w literaturze. Ponadto, w rodzajnikowym podejściu różnorodność podtrzymywana jest w sposób bardziej racjonalny niż dzieje się to w przypadku mechanizmów niszowania. Przy tym podejście GGA oferuje nowatorskie rozwiązanie zagadnienia ewolucyjnej optymalizacji w przestrzeniach wielowymiarowych odmienne od innych propozycji spotykanych w literaturze.