Biological Evolution and Genetic Algorithms: Exploring the Space of Abstract Tile Self-Assembly

Christian Schroeder de Witt

July, 2012

Abstract

A physically-motivated genetic algorithm (GA) and full enumeration for a tile-based model of self-assembly (JaTAM) is implemented using a graphics processing unit (GPU). We observe performance gains with respect to state-of-the-art implementations on CPU of factor {{< math >}} $7.7$ {{< /math >}} for the GA and {{< math >}} $2.9$ {{< /math >}} for JaTAM. The correctness of our GA implementation is demonstrated using a test-bed fitness function, and our JaTAM implementation is verified by classifying a well-known search space {{< math >}} $S_{2, 8}$ {{< /math >}} based on two tile types. The performance gains achieved allow for the classification of a larger search space {{< math >}}$S^{32}{3,8} $< / m a t h > b a s e d o n t h r e e t i l e t y p e s . T h e p r e v a l e n c e o f s t r u c t u r e s b a s e d o n t w o t i l e t y p e s d e m o n s t r a t e s t h a t s i m p l e o r g a n i s m s e m e r g e p r e f e r r a b l y e v e n i n c o m p l e x e c o s y s t e m s . T h e m o d u l a r i t y o f t h e l a r g e s t s t r u c t u r e s f o u n d m o t i v a t e s t h e a s s u m p t i o n t h a t t o f i r s t o r d e r, < m a t h >$ S{2,8} $< / m a t h > f o r m s t h e b u i l d i n g b l o c k s o f < m a t h >$ S_{3,8}${{< /math >}}. We conclude that GPUs may play an important role in future studies of evolutionary dynamics.

Type

Thesis

Publication

In Master’s thesis (MPhys), University of Oxford - Awarded University of Oxford Tessella Prize for Innovation in Software

Deep Multi-Agent Reinforcement Learning Cooperative AI

Biological Evolution and Genetic Algorithms: Exploring the Space of Abstract Tile Self-Assembly

Abstract

Christian Schroeder de Witt

AI & Security Research | Strategy