Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (4): 947-951.

• 软件、算法与仿真 • 上一篇    下一篇

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

周康1,2, 覃磊1, 同小军1,2, 许进2   

  1. 1. 武汉工业学院数理科学系, 湖北, 武汉, 430023;
    2. 华中科技大学控制科学与工程系, 湖北, 武汉, 430074
  • 收稿日期:2008-02-20 修回日期:2008-09-05 出版日期:2009-04-20 发布日期:2010-01-03
  • 作者简介:周康(1965- ),男,副教授,博士研究生,主要研究方向为DNA计算,运筹学,系统稳定性.E-mail:zhoukang65@tom.com
  • 基金资助:
    国家自然科学基金(60574041,60403002);湖北省自然科学基金(2007ABA407)资助课题

Closed circle DNA algorithm of 0-1 planning problem

ZHOU Kang1,2, QIN Lei1, TONG Xiao-Jun1,2, XU Jin2   

  1. 1. Dept. of Mathematics and Physics, Wuhan Polytechnic Univ., Wuhan 430023, China;
    2. Dept. of Control Science and Engineer, Huazhong Univ. of Science and Technology, Wuhan 430074, China
  • Received:2008-02-20 Revised:2008-09-05 Online:2009-04-20 Published:2010-01-03

摘要: 提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。

Abstract: A closed circle DNA computing model and its bio-chemistry 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.

中图分类号: