Original title:
Instrukcemi řízené celulární automaty
Translated title:
Instruction-Controlled Cellular Automata
Authors:
Bendl, Jaroslav ; Žaloudek, Luděk (referee) ; Bidlo, Michal (advisor) Document type: Master’s theses
Year:
2011
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato práce se zabývá návrhem nového konceptu řízení celulárního automatu založeného na tzv. instrukcích. Instrukci lze chápat jako určité pravidlo ověřující stavy předem definované skupiny buněk v sousedství vyšetřované buňky, přičemž při splnění stanovené podmínky kladené na danou skupinu je její stav změněn dle daného předpisu. Jelikož je možné v rámci jednoho výpočetního kroku uvažovat sekvenci složenou z více instrukcí, přičemž každá instrukce může změnit stav centrální buňky ihned po své aplikaci, lze jejich posloupnost pokládat za určitou formu krátkého programu. Tento koncept je zároveň možné rozšířit o jednoduché operace aplikované na buněčné okolí a prováděné během interpretace jednotlivých instrukcí - příkladem takové operace může být řádkový nebo sloupcový posun. Výhoda použití instrukcí tkví v redukci vyhledávacího prostoru, neboť oproti obvykle používané tabulkové metodě není nutné prohledávat množinu všech možných konfigurací buněk v okolí, nýbrž pouze několik oblastí vymezených předpisy instrukcí. Zatímco skupiny vyšetřovaných buněk v rámci instrukce jsou navrhovány ručně na základě analýzy řešené úlohy, posloupnost jejich umístění v chromozomu je optimalizována prostřednictvím genetického algoritmu. Úspěšnost navržené metody řízení celulárního automatu je zkoumána na vybraných benchmarkových úlohách - majoritě, synchronizace, samoorganizaci a návrhu kombinačních logických obvodů.
The thesis focuses on a new concept of cellular automata control based on instructions. The instruction can be understood as a rule that checks the states of cells in pre-defined areas in the cellular neighbourhood. If a given condition is satisfied, the state of the central cell is changed according to the definition of the instruction. Because it's possible to perform more instructions in one computational step, their sequence can be understood as a form of a short program. This concept can be extended with simple operations applied to the instruction's prescription during interpretation of the instructions - an example of such operation can be row shift or column shift. An advantage of the instruction-based approach lies in the search space reduction. In comparison with the table-based approach, it isn't necessary to search all the possible configurations of the cellular neighbouhood, but only several areas determined by the instructions. While the groups of the inspected cells in the cellular neighbourhood are designed manually on the basis of the analysis of the solved task, their sequence in the chromosome is optimized by genetic algorithm. The capability of the proposed method of cellular automata control is studied on these benchmark tasks - majority, synchronization, self-organization and the design of combinational circuits.
Keywords:
Cellular automata; evolutionary algorithm; genetic algorithm; majority task; self-organization task.; synchronization task; Celulární automat; evoluční algoritmus; genetický algoritmus; problém majority; problém samoorganizace.; problém synchronizace
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/54082