The Research Of Molecular Optimization Algorithm And Its Applied Models

An overlap between life sciences and engineering is vivid characteristic of development of modern science and technology. With the fast development of computer and biotechnology, DNA computing, as a novel cross subject, develops very quickly in theory these years.DNA computing is a new calculation method that used biological molecule DNA as calculation medium and biochemical reaction as calculation tool. The advantages are the massive parallelism, high-density storage and energy efficiency. Generally considering, although the ability of the classical digital computer is unassailable when it executes serial task, DNA computing shows natural advantage compared with the classical digital computer in solving the problems that all possible solution should be verified which exist everywhere. When used to solve the parallel processing in large-size computing, it is of tremendous advantages.Initially, this paper introduced the biological background of DNA computing, and the present development condition, the mathematical theory and the biological foundations. Introduced some essential operation of DNA molecule, the overview of study in recent years. At the same time as a biotechnology, DNA computing and genetic algorithm have some common features. After explored the connection between evolutionary algorithm and DNA computing, proposed the thought and implement of the link of DNA computing and genetic algorithm. Then introduced the structure of the DNA-GA, the genetic operators and the implement steps on solve optimization problems. At last, two application examples based on DNA-GA are been established.A DNA-GA model to tackle M-person traveling salesman problem (M-TSP): the model has a wide practical application background, and has been proved as a NP problem. In the past, the study was mainly used to approximation algorithm, genetic algorithm, ant colony algorithm, and some achievements have been obtained. Based on former research, we gave the DNA-GA model. The experimental results show that the algorithm is effective for M-TSP problem, has better performance and can run in real time.The DNA-GA to solve path planning of robot in three-dimensional space is proposed. In the algorithm, the space between the source where robot located and the destination where the robot should arrive is divided into a three-dimensional grid, at the same time a valid path is defined between the source and the destination. The simulated experiment shows that the algorithm is not only effective but also with a great convergence rate. In the algorithm, precise of the algorithm is decided by the density of the grid, namely, the denser the grid is, the higher precise the algorithm is, but longer computing time is needed, and vice versa.Finally, the work of this dissertation is summarized and the prospective of future research is discussed on theory and application.