The Study On Coding And Some Optimization Models Of DNA Computing And Genetic Algorithms

The computer technique is considered as one of the three big revolutions of science in 20 centuries, and the computer is play great role for the development of society. But quantum physics successfully forecast the increase of micro-processing ability of chip cannot keep down for a long period. So, scientists are seeking other completely new computer structure. Such as artificial neural network computer, quantum computer, optical computer as well as DNA computer model. Among them, the DNA computer is paid much attention by scientists. Study on the DNA coding for DNA computing and Genetic Algorithms is implemented in this dissertation. The whole dissertation is divided into four parts: Introduction, Sequence Coding and Optimization Model of DNA Computing, Coding and Optimization Model of Genetic Algorithms, and Summary and Research Insights. This doctoral thesis mainly focuses on the following two subjects: the encoding problem and the volume efficient algorithm for combinatorial optimal problems.In DNA computing, the information is always represented by unique DNA sequences. Therefore, it is very important to select high quality ways to encode DNA sequences. In this thesis, we gives a novel graphical representation of DNA sequences by taking four special vectors in 2-D Cartesian coordinate system to represent the four nucleic acid bases in DNA sequences, so that a DNA sequence is denoted on a plane by a directed walk. A example to illustrate the efficiency of the method is given. It is shown that the new graphical representation of DNA sequences has lower or nondegeneracy.We develop support system for sequence design in DNA computing, which minimizes the evaluation function calculated as the linear sum of the plural evaluation terms. Our system not only searches for good sequences but also presents contribution ratio of each evaluation term to the evaluation function and can reduce the number of combination of evaluation terms by reduction of the evaluation function. It helps us to find a good criterion for sequence design in DNA computing. A new encoding scheme for real values that is biologically plausible and has a fixed code length is proposed. According to the character of the problem, a DNA algorithm solving the Minimum Spanning Tree Problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.Regarding the algorithm design, we mainly present efficient algorithms for the following problems. Firstly, We present a genetic algorithm for the incidence coloring on graphs and Steiner tree problem. The paper gives a simulating about a graph with incidence coloring number 6, and obtains the incidence coloring number of the graph. A edge coloring model for File Transmission Problems is given. An example to illustrate the convergence property and the convergence efficiency of the algorithm is given. Then, a new genetic algorithm for Steiner Tree Problem Based on Elmore Model is developed in this thesis. A new method constructing chromosome for solutions is presented. The complexity based on time and space is analyzed.