Implementation of cell clustering in cellular automata

Adams, Roxane (2011-03)

Thesis (MSc (Mathematical Sciences)) University of Stellenbosch, 2011.

Thesis

ENGLISH ABSTRACT: Cellular Automata (CA) have become a popular vehicle to study complex dynamical behaviour of systems. CA can be used to model a wide variety of physical, biological, chemical and other systems. Such systems typically consist of subparts that change their state independently, based on the state of their immediate surroundings and some generally shared laws of change. When the CA approach was used to solve the LEGO construction problem, the best solution was found when using a variant of CA allowing for the clustering of cells. The LEGO construction problem concerns the optimal layout of a set of LEGO bricks. The advantages found for using the CA method with clustering in this case are the ease of implementation, the significantly smaller memory usage to previously implemented methods, and its trivial extension to construct multicoloured LEGO sculptures which were previously too complex to construct. In our research we propose to explore the definitions of clustering in CA and investigate the implementation and application of this method. We look at the ant sorting method described by Lumer and Faieta, and compare the implementation of this algorithm using regular CA as well as the clustering variation. The ant sorting model is a simple model, in which ants move randomly in space and pick up and deposit objects on the basis of local information.

AFRIKAANSE OPSOMMING: Sellulêre Outomate (SO) het ’n populêre metode geword om die komplekse dinamiese gedrag van sisteme bestudeer. SO kan gebruik word om ’n groot verskeidenheid fisiese, biologiese, chemiese en ander tipe sisteme te modelleer. Sulke sisteme bestaan tipies uit subafdelings wat, gebaseer op die status van hulle omgewing en ’n paar algemene gedeelde reëls van verandering, hulle status onafhanklik verander. Met die gebruik van die SO benadering om the LEGO konstruksieprobleem op te los, is die beste oplossing bereik deur gebruik te maak van ’n variant van SO, waar selle saamgroepeer kan word. Die LEGO konstruksieprobleem behels die optimale uitleg van ’n stel LEGO blokkies. In hierdie geval is die voordele van die SO met sel groepering die maklike implementasie, ’n beduidende kleiner geheuegebruik teenoor voorheen geïmplementeerde metodes, en die triviale uitbreiding daarvan om gekleurde LEGO beelde wat voorheen te kompleks was, te kan bou. In ons ondersoek verken ons die definisies van selgroepering in SO en ondersoek die implementasie en toepassing van die metode. Ons kyk na die miersorteringsmetode beskryf deur Lumer en Faieta, en vergelyk die implementasie van hierdie algoritme deur gewone SO asook die groeperingsvariasie te gebruik. Die miersorteringsmodel is ’n eenvoudige model waarin miere lukraak in ’n omgewing beweeg en voorwerpe optel of neersit volgens plaaslike inligting.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/6674
This item appears in the following collections: