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.

Las metaheurísticas (MH) son procedimientos de Inteligencia Artificial que suelen basarse en la evolución que permiten obtener soluciones aproximadas de problemas difíciles, siendo procedimientos costosos desde el punto de vista computacional ya que exploran grandes espacios de soluciones. Este trabajo pretende sentar las bases de mapeos generales para implementar una HM utilizando construcciones de Biología Sintética en colonias celulares. Dos ventajas de este enfoque son: aprovechar la capacidad de paralelismo a gran escala de de las colonias celulares y el uso de procesos celulares existentes para implementar dinámicas básicas definidas en versiones computacionales. Proponemos un marco que mapea los elementos de MH a circuitos sintéticos en colonias celulares en crecimiento para replicar el comportamiento del MH en las colonias celulares. Los mecanismos de comunicación célula-célula como el quorum sensing (QS), la conjugación bacteriana y las señales del entorno se corresponden con los operadores de evolución de las técnicas de MH para adaptarse a las colonias en crecimiento. Como prueba de concepto implementamos Algoritmos Genéticos Simples codificados como circuitos sintéticos. Las pruebas de implementación muestran la utilidad del procedimiento y el hecho de que el paralelismo de las colonias celulares acelera la ejecución. Además, mostramos un ejemplo de cómo el procedimiento permite también simular un Autómata Celular.