Hybrid DNA Genetic Algorithm And Its Application In The MTSP Problem

:Genetic algorithm is a random global search and optimization algorithm.It is developed by biological inheritance and evolutionary mechanism.It is first proposed by professor Holland of the university of Michigan in 1975 , after that the general framework of the genetic algorithm is established in the process of many scholars' research, the framework includes a few specific genetic operator-selection operators, crossover operator and mutation operator, It is a kind of practical and efficient, and robust optimization technology. DNA calculation is based on the molecular structure of DNA, and used modern biological lab technique, with the DNA and all kinds of enzyme as its main calculation tool, use biological means to solve practical problems, this technology is still in its initial stage,there are many problems remain to be solved.DNA computing and genetic algorithm is developed of biological genetic and evolutionary process,the two have natural affinities, this paper is proposed to combine DNA computing with genetic algorithm, and to solve the problems of optimization design, and it has very important practical significance.This paper use mixed DNA genetic algorithm for emergency goods distributing which is MTSP problem, and achieved good effect.This main research work in this paper are as follows:(1) By the effect that the process of the cross and mutation of the gene in chromosomes , in this paper,we improved the crossover operator, and proposed three crossover operator which are the replacement, inversion and transposed, through the crossover operation, it will get individual that has higher fitness.Function test results show that the new operators can effectively improve the population diversity, reduce the optimal algebra.(2) Inspired by the DNA and the process of genetic information expression, based on nucleotide coding , This paper presents two new mutation operator.One is inverse anticodon mutation operator which is designed by the process of the DNA translated into messenger RNA , and then mRNA translated into protein.The other is maximum-minimum mutation operator which is inspired by the process of rare bases instead of common bases.Testing function results show that the new mutation operator can greatly improve the convergence speed of DNA genetic algorithm , and enhance the algorithm's ability of overcoming deceptive problem.(3) This paper combines DNA genetic algorithm that has new operators with the traditional genetic algorithm , proposed and designed a new mixed DNA genetic algorithm, and used in emergency goods distributing which is MTSP problem, and also designed a new rule of chromosome encoding , sorting operator and crossover operator.The results show that the method has a good result to solve the emergency goods distributing which is MTSP problem.