A Framework for Implementing Metaheuristic Algorithms Using Intercellular Communication

Abstract

Metaheuristics (MH) are Artificial Intelligence procedures that frequently rely on evolution. MH approximate difficult problem solutions, but are computationally costly as they explore large solution spaces. This work pursues to lay the foundations of general mappings for implementing MH using Synthetic Biology constructs in cell colonies. Two advantages of this approach are: harnessing large scale parallelism capability of cell colonies and, using existing cell processes to implement basic dynamics defined in computational versions. We propose a framework that maps MH elements to synthetic circuits in growing cell colonies to replicate MH behavior in cell colonies. Cell-cell communication mechanisms such as quorum sensing (QS), bacterial conjugation, and environmental signals map to evolution operators in MH techniques to adapt to growing colonies. As a proof-of-concept, we implemented the workflow associated to the framework: automated MH simulation generators for the gro simulator and two classes of algorithms (Simple Genetic Algorithms and Simulated Annealing) encoded as synthetic circuits. Implementation tests show that synthetic counterparts mimicking MH are automatically produced, but also that cell colony parallelism speeds up the execution in terms of generations. Furthermore, we show an example of how our framework is extended by implementing a different computational model: The Cellular Automaton.