一类特殊整数规划问题的DNA计算

DNA Computation for a Category of Special Integer Planning Problem

基于生化反应原理的DNA计算由于在解决一类困难问题,特别是完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义.提出了约束方程组的”秩”以及约束方程的3种“约束补链”概念,并基于这些概念,利用在基于表面的DNA计算中采用荧光标记的策略,给出了一类特殊整数规划问题最优解的一种基于DNA计算的求解算法.新算法利用荧光猝灭技术来排除非解,从而得到满足约束条件的所有可行解,最后再通过比较所有可行解的目标函数值来求得问题的所有最优解.算法分析表明,新算法具有解读、编码简单和错误率低的特点.

DNA computation based on the theory of biochemical reactions has better performance in solving a class of intractable computational problems, especially the NP-complete problems, than traditional computing methods based on the current silicon computers, so it is of great importance to study the DNA computation. The new concepts such as rank of constraint equation group and three kinds of constraint complement links of constraint equation group are proposed, and according to those concepts and on the basis of the method of fluorescence-labeling in the surface-based approach to DNA computation, a novel algorithm based on DNA computation is designed, which solves the problem of optimal solutions to a category of special integer planning. By using the fluorescence-quenching technique to eliminate false solutions from all the possible solutions to the given integer-planning problem, the new algorithm can identify all of the feasible solutons, and then, can obtain all the optimal solutions to the given integer-planning problem by comparing the target-function＇s value of those feasible solutions. Analyses show that, the new algorithm has some good characteristics such as simple encoding, low cost and short operating time, etc.