DNA Genetic Algorithm And Its Application To The Assignment Problem

DNA(Deoxyribonucleic acid) computation is a new methods of simulating bimolecular structure and conducted by means of molecular biological techniques. DNA computation is currently still in its infancy, there are many theoretical and practical issues to be resolved. Genetic algorithm is a computation model, which simulates the natural selection and the genetic mechanism of the biological evolution. It has a unique advantage in the search of the optimal solution. Both of them have a definite link and they can learn from each other. For the limitations of the DNA computation, genetic algorithm can be used as a bridge of solving complex optimization problems by DNA computation. From the view of DNA computation, genetic algorithm is the most suitable way achieved by DNA in all methods based on evolutionary mechanism. Genetic algorithm based on DNA computation further simulates the biological genetic and gene regulation mechanisms, improves DNA computation and genetic algorithm and will have better prospects.This paper combined DNA computation ideas and genetic algorithm and researched DNA genetic algorithm focusing on the implementation of DNA computation, the improving of the search efficiency and local search capabilities and the overcoming the premature convergence. A DNA genetic algorithm based on the thought of excellent gene was proposed, extracting the excellent gene and inheriting it to future generations can speed up the convergence. The structure of DNA genetic algorithm was given and its specific operations including select, crossover and mutation operator were discussed.Finally, the improved DNA genetic algorithm mentioned above was applied to the optimal solution of assignment problem and its specific code and detailed steps were given. A simulation experiment to a concrete example was conducted, which proved that the improved DNA genetic algorithm has fast convergence and good global search capability. The effectiveness and practicality of the algorithm were verified initially.