DNA-Based Evolutionary Algorithm for Cable Trench Problem

摘要

An evolutionary DNA computing algorithm is proposed for solving a cable trench problem in this paper. The cable trench problem is a combination of the shortest path and minimum spanning tree problems, which makes it difficult to be solved by conventional computing method. DNA computing is applied to overcome the limitation, where fixed-length DNA strands are used in representing numerical values and the weights are varied by melting temperatures. Biochemical techniques in terms of DNA thermodynamic properties are used for effective local search of the optimal solution.