Change search
ReferencesLink to record
Permanent link

Direct link
Evolution of Cellular Automata using Lindenmayer Systems and Fourier Transforms
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Computer and Information Science.
2013 (English)MasteroppgaveStudent thesis
Abstract [en]

Cellular automata (CAs) are a class of highly parallel computing systems consisting of many simple computing elements called cells. The cells can only communicate with neighboring cells, meaning there is no global communication in the system. Programming such a system to solve complex problems can be a daunting task, and indirect methods are often applied to make it easier. In this thesis we use evolutionary algorithms (EAs) to evolve CAs. We also look at the possibility of employing L-systems to develop complex CAs while maintaining a relatively small genome. Input and output are handled by streaming them through the edge cells, and we look at the use of a discrete Fourier transform (DFT) as a way to interpret the output. Experiments show that it is possible to evolve uniform and semi-uniform CAs that solve various problems. On harder problems semi-uniform CAs outperform uniform CAs, and using an L-system further improves the performance. However, on simpler problems the extra complexity of semi-uniform CAs seem to only hinder evolution. The experiments also show that interpreting the output with a DFT works well, and outperforms a more direct approach.

Place, publisher, year, edition, pages
Institutt for datateknikk og informasjonsvitenskap , 2013. , 72 p.
URN: urn:nbn:no:ntnu:diva-23601Local ID: ntnudaim:9414OAI: diva2:676808
Available from: 2013-12-06 Created: 2013-12-06 Last updated: 2013-12-06Bibliographically approved

Open Access in DiVA

fulltext(616 kB)225 downloads
File information
File name FULLTEXT01.pdfFile size 616 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(216 kB)15 downloads
File information
File name COVER01.pdfFile size 216 kBChecksum SHA-512
Type coverMimetype application/pdf
attachment(87 kB)9 downloads
File information
File name ATTACHMENT01.zipFile size 87 kBChecksum SHA-512
Type attachmentMimetype application/zip

By organisation
Department of Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 225 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 35 hits
ReferencesLink to record
Permanent link

Direct link