Logowanie do System sprawozdań KDM

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

Kierownik projektu: Marcin Dembowski

Uniwersytet Gdański

Wydział Matematyki, Fizyki i Informatyki

Gdańsk

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

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