DNA computing for Traveling Salesman problem
In this paper, Genetic algorithms is applied to traveling salesman problem whose solution requires encoding of real values in DNA strands. Encode weights in DNA computing is an important but challenging problem because many practical applications in the real world involve weights. In order to efficiently encode weights in DNA strands, we firstly proposed two definitions, the order number of weight and the relative length graph. And then, by means of the two definitions, we have devised a new method of encoding weights in DNA strands for a weighted graph. DNA algorithm solving the traveling salesman problem is given. The effectiveness of the proposed method is verified by simulation. The method was applied to solve the traveling salesman problem, and it can be expanded to solve other numerical optimization problems.
DNA computing Genetic algorithms Graph Traveling salesman problem
Liu Xikui Li Yan
College of Information and Engineering Shandong University of Science and Technology Qingdao 266510,China
国际会议
北京
英文
1-4
2009-06-11（万方平台首次上网日期，不代表论文的发表时间）