Artificial Evolution of Arbitrary Self-Replicating Cellular Automata

Simple item page
dc.contributor.advisorReggia, Jamesen_US
dc.contributor.authorPan, Zhijianen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2007-09-28T15:03:29Z
dc.date.available2007-09-28T15:03:29Z
dc.date.issued2007-08-22en_US
dc.description.abstractSince John von Neumann's seminal work on developing cellular automata models of self-replication, there have been numerous computational studies that have sought to create self-replicating structures or "machines". Cellular automata (CA) has been the most widely used method in these studies, with manual designs yielding a number of specific self-replicating structures. However, it has been found to be very difficult, in general, to design local state-transition rules that, when they operate concurrently in each cell of the cellular space, produce a desired global behavior such as self-replication. This has greatly limited the number of different self-replicating structures designed and studied to date. In this dissertation, I explore the feasibility of overcoming this difficulty by using genetic programming (GP) to evolve novel CA self-replication models. I first formulate an approach to representing structures and rules in cellular automata spaces that is amenable to manipulation by the genetic operations used in GP. Then, using this representation, I demonstrate that it is possible to create a "replicator factory" that provides an unprecedented ability to automatically generate a whole class of new self-replicating structures and that allows one to systematically investigate the properties of replicating structures as one varies the initial configuration, its size, shape, symmetry, and allowable states. This approach is then extended to incorporate multi-objective fitness criteria, resulting in production of diversified replicators. For example, this allows generation of target structures whose complexity greatly exceeds that of the seed structure itself. Finally, the extended multi-objective replicator factory is further generalized into a structure/rule co-evolution model, such that replicators with unspecified seed structures can also be concurrently evolved, resulting in different structure/rule combinations and having the capability of not only replicating but also carrying out a secondary pre-specified task with different strategies. I conclude that GP provides a powerful method for creating CA models of self-replication.en_US
dc.format.extent15350583 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/7404
dc.language.isoen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledSelf-Replicationen_US
dc.subject.pquncontrolledCellular Automataen_US
dc.subject.pquncontrolledEvolutionary Computationen_US
dc.subject.pquncontrolledArtificial Lifeen_US
dc.subject.pquncontrolledGenetic Programmingen_US
dc.subject.pquncontrolledArtificial Intelligenceen_US
dc.titleArtificial Evolution of Arbitrary Self-Replicating Cellular Automataen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
umi-umd-4824.pdf
Size:
14.64 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations