Genetic algorithm in DNA computing:A solution to the maximal clique problem

Genetic algorithm is one of the possible ways to break the limit of brute-force method in DNA computing. Using the idea of Darwinian evolution, we introduce a genetic DNA computing algorithm to solve the maximal clique problem. All the operations in the algorithm are accessible with today's molecular biotechnology. Our computer simulations show that with this new computing algorithm, it is possible to get a solution from a very small initial data pool, avoiding enumerating all candidate solutions. For randomly generated problems, genetic algorithm can give correct solution within a few cycles at high probability. Although the current speed of a DNA computer is slow compared with silicon computers, our simulation indicates that the number of cycles needed in this genetic algorithm is approximately a linear function of the number of vertices in the network. This may make DNA computers more powerfully attacking some hard computational problems.

作 者： LI Yuan Fang CHEN OUYANG Qi   作者單位： Center for Theoretical Biology and Department of Physics, Peking University, Beijing 100871, China  刊 名： 科學(xué)通報(bào)(英文版)  SCI 英文刊名： CHINESE SCIENCE BULLETIN  年，卷(期)： 2004 49(9)  分類(lèi)號(hào)： Q5  關(guān)鍵詞： DNA computer   genetic algorithm   NP-complete problem  

【Genetic algorithm in DNA computing:A】相關(guān)文章：

Underground water quality model inversion of genetic algorithm04-28

Optimization and Sizing for Propulsion System of Liquid Rocket Using Genetic Algorithm04-30

An integrated decision method for prediction of tropical cyclone movement by using genetic algorithm04-29

THE EFFECTIVENESS OF GENETIC ALGORITHM IN CAPTURING CONDITIONAL NONLINEAR OPTIMAL PERTURBATION WITH PARAMETERIZATION ON-04-27

Cleaner production for continuous digester processes based on hybrid Pareto genetic algorithm04-28

Optimization of a Reduced Chemical Kinetic Model for HCCI Engine Simulations by Micro-Genetic Algorithm04-29

Geometric Optimization Design System Incorporating Hybrid GRECO-WM Scheme and Genetic Algorithm04-30

Improved NSGA-Ⅱ Multi-objective Genetic Algorithm Based on Hybridization-encouraged Mechanism04-28

BESⅢ track fitting algorithm04-28

DNA電腦04-26