背包问题的闭环DNA算法  

Closed Circle DNA Algorithm of Knapsack Problem

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

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

出　　处：《系统仿真学报》2008年第17期4605-4608,共4页Journal of System Simulation

基　　金：国家自然科学基金(60403002);湖北省自然科学基金(2007ABA407;2004ABA031;2005ABA233);湖北省优秀中青年科技创新团队计划;浙江省自然科学基金(ZJNSF-Y105654).

摘　　要：提出了闭环DNA分子的结构多样性,即闭环DNA分子在同一个位置上具有不同的DNA序列。提出了双约束的整数规划背包问题闭环DNA算法,即对变量取值进行DNA编码并形成所有可能解;用批接入实验、电泳实验和批删除实验筛选出可行解,用批接入实验、电泳实验得到最优解;通过检测实验输出所有最优解。由一个算例说明算法的有效性。针对减少DNA编码和内切酶数量的问题改进了算法;对有特殊要求的背包问题提出了解决方法。Molecular configuration diversity of closed circle DNA was brought forward, namely, closed circle DNA＇s the same position has different DNA sequence. For twin-restriction integer-programming knapsack problem, closed circle DNA algorithm was put forward. In the closed circle DNA algorithm, DNA encoding for all values of any variable were encoded. And all possible solutions were synthesized. Then all feasible solutions, which satisfied weight and capacity＇s needs, were filtered out using group insert experiment, electrophoresis experiment and group delete experiment. And all optimization solutions were filtered out using group insert experiment, electrophoresis experiment. Finally all optimization solutions were found using detect experiment. And an example explains feasibility of the DNA algorithm. In order to decrease number of DNA encoding and inscribed enzyme, the closed circle DNA algorithm was improved. For especial need＇s knapsack problem, DNA algorithm was put forward.

关 键 词：闭环DNA计算模型 背包问题 批接入实验 批删除实验 

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