Grant/Projek zakończony

Analiza czasoprzestrzenna automatów komórkowych z wykorzystaniem algorytmów genetycznych

Identyfikator grantu: PT00504

Kierownik projektu: Marcin Dembowski

Uniwersytet Gdański

Wydział Matematyki, Fizyki i Informatyki

Gdańsk

Data otwarcia: 2015-09-24

Data zakończenia: 2022-03-25

Streszczenie projektu

Opis projektu: Problem głosowania większościowego w automatach komórkowych ? jest zagadnieniem polegającym na wyszukiwaniu reguł dla automatów komórkowych poprawnie określających głosowanie większościowe, gdzie dla skończonej liczby iteracji zmienia się liczba komórek znajdujących się w stanie, który dominował na początku. Aktualnie trwają prace nad metodami wykorzystującymi do tego celu między innymi algorytmy genetyczne. Celem projektu jest znalezienie między innymi reguły bądź reguł pozwalających na poprawne sklasyfikowanie dowolnej konfiguracji jedno oraz dwuwymiarowego automatu komórkowego, a także znalezienie różnic oraz podobieństw pomiędzy różnymi automatami.

Uzasadnienie wykorzystania zasobów KDM TASK: Aby móc znaleźć regułę automatu komórkowego klasyfikującego inicjalną konfigurację wejściową należy zbadać jak największą liczbę kombinacji konfiguracji inicjalnych o stosunkowo dużej długości. Pojawia się tutaj jednak problem obliczeniowy, ponieważ przebadanie wszystkich możliwych konfiguracji dla binarnych wektorów o długości n jest praktycznie niemożliwe (przyjmując nawet, że takich unikalnych kombinacji jest 2do potęgi n /n). Wykonanie eksperymentu na dopasowanym, mniejszym podzbiorze pozwala skrócić czas oczekiwania na wyniki, jednak ze względu na stochastyczną naturę eksperymentów potrzebne jest wielokrotne wykonanie eksperymentów.
Użyte metody obliczeniowe i narzędzia: Aby przebadać jak największą liczbę możliwych kombinacji należy zrównoleglić operacje w taki sposób, aby pozwalały na przebadanie jak największej liczby potencjalnych reguł na największej liczbie różnych konfiguracji wejściowych. Do tego celu wykorzystuje się najprostsze operacje matematyczne oraz biblioteki pomocnicze takie jak GNU Scientific Library czy OpenMP. Zdecydowaną większość obliczeń da się jednak w bardzo prosty sposób zrównoleglić. Poszczególne uruchomienia eksperymentu mogą być wywoływane niezależnie na wieloprocesorowej maszynie, zależnie od dostępnych zasobów obliczeniowych. Nie istnieje potrzeba wymiany informacji pomiędzy poszczególnymi maszynami wykonującymi obliczenia.
Oprogramowanie zaimplementowane jest w językach C z wykorzystaniem bibliotek OpenMP oraz GNU Scientific Library (GSL). Przetwarzanie oraz generowanie danych realizowane jest w języku Python oraz za pomocą skyptów bash.

Publikacje

  1. Wolnik Barbara, Dembowski Marcin, Bołt Witold, Baetens Jan M., De Baets Bernard, The Density Classification Problem in the Context of Continuous Cellular Automata, Cellular Automata: 12th International Conference on Cellular Automata for Research and Industry, ACRI 2016, Fez, Morocco, September 5-8, 2016. Proceedings, Springer International Publishing 9863, (2016) 79--87
  2. Dembowski, M., Wolnik, B., Bołt, W., Baetens, J.M., De Baets, B., Affine continuous cellular automata solving the fixed-length density classification problem, Natural Computing 16, (2017) 1-11
  3. Wolnik, B., Dembowski, M., Bolt, W., Baetens, J.M., De Baets, B., Density-conserving affine continuous cellular automata solving the relaxed density classification problem, Journal of Physics A-Mathematical and Theoretical 34, (2017) 1-18
  4. M. Dembowski, B. Wolnik, W. Bołt, J. M. Baetens and B. De Baets, Solving the relaxed density classification problem by means of two-dimensional Affine Continuous Cellular Automata. In: Proceedings of the 23rd International Workshop on Cellular Automata and Discrete Complex Systems, In: Proceedings of the 23rd International Workshop on Cellular Automata and Discrete Complex Systems 23, (2017) 1-8
  5. M. Dembowski, B. Wolnik, J. M. Baetens, B. De Baets, An exploration of the dynamics of one-dimensional outer-totalistic continusous cellular automata, Proceedings of the International Workshop on Cellular Automata and Discrete Complex Systems 24, (2018) 77-84
  6. M. Dembowski, B. Wolnik, W. Bołt, J.M. Baetens, B. De Baets, Two-dimensional Affine Continuous Cellular Automata Solving the Relaxed Density Classification Problem, Journal OF Cellular Automata 14, (2019) 191 - 212


← Powrót do spisu projektów

CONTACT

Our consultants help future and novice users of specialized software installed on High Performance Computers (KDM) at the TASK IT Center.

Contact for High Performance Computers, software / licenses, computing grants, reports:

kdm@task.gda.pl

Administrators reply to e-mails on working days between 8:00 am – 3:00 pm.