Evolutionary Computation as a Paradigm for DNA-Based Computing

Evolutionary Computation focuses on probabilistic search and optimization methods gleaned from the model of organic evolution. Genetic algorithms, evolution strategies, and evolutionary programming are three independently developed representatives of this class of algorithms, with genetic programming and classifier systems as additional paradigms in the field.This paper focuses on the link between evolutionary computation and DNA-based computing by discussing the relevant aspects of evolutionary computation both from a practical and a theoretical point of view. In particular, theoretical results concerning the calculation of convergence velocities and the derivation of optimal schedules for mutation rates, respectively steps sizes, are presented.The potential for cross-fertilization between the fields of DNA-based computing and evolutionary computation is outlined both from a fundamental point of view and by means of an experimental investigation concerning the NP-hard maximum clique problem. A simple evolutionary approach to maximum clique is introduced and the hypothesis whether the increase in population size possible by realizing evolutionary computation with DNA yields the expected improvement in solution quality is tested. Results obtained for a limited range of population sizes up to 105 indicate that the hypothesis holds for about two-thirds of the investigated problem instances (which were taken from the DIMACS library).