集合覆盖问题闭环DNA算法  

Closed circle DNA algorithm for set covering problems

作　　者：周康[1] 解智[1] 魏传佳[1] 易校尉[1] 

机构地区：[1]武汉工业学院数理科学系,湖北武汉430023

出　　处：《华中科技大学学报（自然科学版）》2010年第2期21-25,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60574041);湖北省自然科学基金资助项目(2007ABA407);湖北省教育厅科学技术研究重点项目(D20091805)

摘　　要：介绍了闭环DNA计算模型及其生化实验,分析了集合覆盖问题及其数学模型.根据任何一个元素至少属于一个集合构成可行集合覆盖的原理,设计了集合覆盖问题闭环DNA算法,该算法首先对集合的0-1决策变量按照0和1的取值、对应的价值系数进行两组DNA编码并形成所有可能解;再用接入实验和删除实验筛选出全部可行解;然后用接入实验得到这些可行解的目标函数值,并用电泳实验得到全部最优解;最后通过检测实验输出所有最优解.首次提出基于电泳技术检测实验以"接入-电泳-删除"为实验顺序,可以检测多种DNA编码.算例说明了算法的有效性.The computation model for closed circle DNA and its biochemistry experiments were introduced.Set covering and its mathematical model were analyzed.According to the principle that feasible set,covering is composed of these sets,of which an arbitrary element belongs to at least a set,closed circle DNA algorithm of set covering problem was designed.In the closed circle DNA algorithm,two groups of DNA encoding for every 0-1 decision variable of set were encoded according to taking values of variable and cost coefficients corresponding to variable;and all possible solutions were synthesized.All feasible solutions were filtered out by doing insert experiment and delete experiment,and the objective function values of these feasible solutions were obtained by doing insert experiment.And all optimization solutions were filtered out by doing electrophoresis experiment.Finally all optimization solutions were putout by doing detect experiment.An example explained feasibility of the DNA algorithm.Detection experiment based on electrophoresis technique is first put forward,which can detect various kinds of DNA encodings using the experiment order of ＂insert experiment-electrophoresis experiment-group separate experiment＂.

关 键 词：DNA算法 闭环DNA计算模型 集合覆盖问题 检测实验 电泳技术 

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