0-1规划问题的闭环DNA算法  

Closed circle DNA algorithm of 0-1 planning problem

作　　者：周康[1,2] 覃磊[1] 同小军[1,2] 许进[2] 

机构地区：[1]武汉工业学院数理科学系,湖北武汉430023 [2]华中科技大学控制科学与工程系,湖北武汉430074

出　　处：《系统工程与电子技术》2009年第4期947-951,共5页Systems Engineering and Electronics

基　　金：国家自然科学基金(60574041,60403002);湖北省自然科学基金(2007ABA407)资助课题

摘　　要：提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。A closed circle DNA computing model and its bio-cbemistry experiments are introduced. The flexibility of a closed circle DNA molecule structure is brought forward, which includes the controllabitity of DNA chains in length and mutual conversion among the DNA molecules. For the 0-1 planning problem of nonnegative integer coefficients, a closed circle DNA algorithm is put forward. In the closed circle DNA algorithm, first the five groups of DNA encoding are encoded according to variable＇s 0 or 1 values, its coefficients and its detecting mark. All possible solutions are synthesized. Then all feasible solutions are filtered out using the insert experiment, electrophoresis experiment and delete experiment. All optimization solutions are filtered out using the same method. Finally all optimization solutions are found using a detect experiment. The correctness of the algorithm is proved, and the complexity of the algorithm is discussed. And the feasibility of the DNA algorithm is explained by an example. The closed circle DNA algorithm is improved so as to solve the 0-1 planning problem of the real coefficient including negative numbers.

关 键 词：闭环DNA计算模型 0-1规划问题 接入实验 删除实验 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]