Logowanie do System sprawozdań KDM

Identyfikacja Automatów Komórkowych z wykorzystaniem Algorytmów Ewolucyjnych

Kierownik projektu: Witold Bołt

Instytut Badań Systemowych PAN w Warszawie

Warszawa

Streszczenie projektu

Opis projektu:

Celem projektu jest opracowanie algorytmów budujących reguły automatów komórkowych, na bazie obserwacji wyidealizowanego zjawiska. Zakłada się, że dostępne obserwacje są cząstkowe - tzn. brakuje w nich wartości dla części komórek oraz brakuje części kroków czasowych, tj. konfiguracji automatu w pewnych chwilach czasu. Rozważane strategie rozwiązania problemu identyfikacji, budowane są w oparciu o algorytmy ewolucyjne - głównie zmodyfikowany algorytm genetycznych.

Badania mają charakter teoretyczny - rozważane obserwacje, na obecnym etapie projektu - są wygenerowane przez program komputerowy. Nie mniej jednak, definicja problemu oraz rozważane metody rozwiązania pozwolą w przyszłości na rozwiązywanie problemu identyfikacyjnego w praktycznych zagadnieniach modelowania matematycznego.

Oczekiwane rezultaty naukowe to lepsze zrozumienie własności dynamicznych automatów komórkowych (badane są związki znanych metryk własności dynamicznych automatów oraz możliwości / wydajności identyfikacji) oraz budowa zestawu algorytmów rozwiązujących problem identyfikacji dla 1-wymiarowych, dwu-stanowych automatów komórkowych.

Uzasadnienie wykorzystania zasobów KDM TASK:

W ramach badań, planujemy przebadać wpływ braków w obserwacjach na wydajność identyfikacji - tj. czas jaki potrzebny jest na znalezienie rozwiązania przez algorytm ewolucyjny. Badaną przez nas klasą automatów są tzw. elementarne automaty komórkowe. Jest ich 256. Dla każdego z nich przeprowadzamy szereg eksperymentów - algorytm identyfikacyjny uruchamiany jest dla serii obserwacji o różnym stopniu ?cząstkowości? obserwacji (tj. różnej liczbie brakujących wartości w komórkach). W sumie daje to kilkanaście tysięcy przypadków do sprawdzenia. Ze względu na stochastyczną naturę algorytmów ewolucyjnych, każdy przypadek musi zostać rozważony wielokrotnie - aby możliwe było otrzymanie wyników istotnych z punktu widzenia statystyki.



Tak duży rozmiar eksperymentu wymaga zastosowania komputerów o dużej mocy obliczeniowej. Przeprowadzenie symulacji nie jest możliwe z wykorzystaniem zwykłych stacji roboczych czy komputerów ogólnie dostępnych.



Użyte metody obliczeniowe i narzędzia technologiczne:

Każdy konkretnych przypadek - tj. zestaw obserwacji danego systemu, realizowany jest oddzielnie jako program działający na jednej, wieloprocesorowej maszynie. Obliczenia zrównoleglone są z wykorzystaniem biblioteki OpenMP - wszystkie procesory biorą udział w wyliczaniu funkcji dopasowania osobników w populacji algorytmu ewolucyjnego. Zrównoleglenie na wielu maszynach uzyskuje się przez uruchomienie w tym samym czasie wielu przypadku (algorytmu dla wielu zbiorów obserwacji). Poszczególne wykonania są jednak w pełni niezależne, co daje dużą elastyczność i możliwość rozłożenia obliczeń w czasie - zależnie od dostępnych zasobów obliczeniowych. Nie istnieje potrzeba komunikacji między poszczególnymi maszynami realizującymi obliczenia w tym samym czasie (nie ma żadnej korzyści z wprowadzenia takiej komunikacji).



Oprogramowanie zaimplementowane jest w językach C/C++ z wykorzystaniem bibliotek OpenMP oraz GNU Scientific Library (GSL). Przetwarzanie danych wynikowych realizowane jest w języku Python oraz za pomocą skryptów shell.

Publikacje

  1. Witold Bołt, Jan Baetens, Bernard De Baets, Identification of Cellular Automata based on incomplete observations with bounded time gaps, Communications in Nonlinear Science and Numerical Simulation ?, (2016) ?

Centrum Informatyczne Trójmiejskiej Akademickiej Sieci Komputerowej
ul. G. Narutowicza 11/12, 80-233 Gdańsk   |   tel. 58-347-24-11
email: office@task.gda.pl   |   NIP: 584-020-35-93