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
- PDF / 988,405 Bytes
- 26 Pages / 439 x 666 pts Page_size
- 26 Downloads / 256 Views
Abstract. 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 DNAbased 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).
1
Introduction
The goal of this paper is to bring together some of the main concepts from the areas of evolutionary computation and DNA-based (or, more general, molecular) computing. We argue that this is beneficial for both areas. For evolutionary computation, we outline how the massive parallelism of DNA-based computing can be exploited, and for DNA-based computing an evolutionary approach would offer the possibility of scaling the method to problems of increasing dimensionality by substituting the usual filtering approach with an evolutionary one. Therefore, we outline the main ideas, notions, and trends of evolutionary computation to the extent we feel is needed for creating a solid bridge to the area of DNA-based computing. In particular, Sect. 2 presents an introduction to evolutionary computation that focuses on a general view of evolutionary algorithms, with genetic algorithms and evolution strategies as two rather different instances of the general algorithm. Especially, the theoretical results about evolution strategies and the transfer of this kind of theory to genetic algorithms provide the main topic of the theoretical overview given in this section. Section 3 gives
L. F. Landweber et al. (eds.), Evolution as Computation © Springer-Verlag Berlin Heidelberg 2002
16
Thomas Back, ¨ Joost N. Kok, and Grzegorz Rozenberg
a brief overview of the basic aspects of DNA-based computing, and Sect. 4 explains the relationship we see between the two areas. In Sect. 5, we propose an application example for evolutionary DNAbased computing, namely the maximum clique problem, which h
Data Loading...
