资源描述：
《0_1规划问题闭环dna算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第31卷第4期系统工程与电子技术Vol.31No.42009年4月SystemsEngineeringandElectronicsApr.2009文章编号:10012506X(2009)0420947205021规划问题的闭环DNA算法1,211,22周康,覃磊,同小军,许进(1.武汉工业学院数理科学系,湖北武汉430023;2.华中科技大学控制科学与工程系,湖北武汉430074)摘要:提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项
2、系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。关键词:闭环DNA计算模型;0-1规划问题;接入实验;删除实验中图分类号:TP301.6文献标志码:AClosedcircleDNAalgorithmof021planningproblem1,211,22ZHOUKang,QINLei,TONGXiao2Jun,XUJin(1.Dept.of
3、MathematicsandPhysics,WuhanPolytechnicUniv.,Wuhan430023,China;2.Dept.ofControlScienceandEngineer,HuazhongUniv.ofScienceandTechnology,Wuhan430074,China)Abstract:AclosedcircleDNAcomputingmodelanditsbio2chemistryexperimentsareintroduced.TheflexibilityofaclosedcircleDNAmoleculestructureisbroughtforw
4、ard,whichincludesthecontrollabitityofDNAchainsinlengthandmutualconversionamongtheDNAmolecules.Forthe021planningproblemofnon2negativeintegercoefficients,aclosedcircleDNAalgorithmisputforward.IntheclosedcircleDNAalgorithm,firstthefivegroupsofDNAencodingareencodedaccordingtovariable’s0or1values,its
5、coefficientsanditsdetectingmark.Allpossiblesolutionsaresynthesized.Thenallfeasiblesolutionsarefilteredoutusingthein2sertexperiment,electrophoresisexperimentanddeleteexperiment.Alloptimizationsolutionsarefilteredoutu2singthesamemethod.Finallyalloptimizationsolutionsarefoundusingadetectexperiment.
6、Thecorrectnessofthealgorithmisproved,andthecomplexityofthealgorithmisdiscussed.AndthefeasibilityoftheDNAalgo2rithmisexplainedbyanexample.TheclosedcircleDNAalgorithmisimprovedsoastosolvethe021planningproblemoftherealcoefficientincludingnegativenumbers.Keywords:closedcircleDNAcomputingmodel;021pla
7、nningproblem;insertexperiment;deleteexperi2ment的亮度来判断是否满足约束条件。由于对亮度(而不是亮0引言[5]点)的判断有误差,于是2004年张凤月等人通过设计合021规划问题在传统的和现代的优化算法中一直没有理的表面上DNA的排列方式解决了这个问题,而这两种算[123]找到合适的多项式算法。DNA计算以其高度并行性和法还只能用DNA计算找到021规划问题的可行解,最优解[6]巨大的储存容量有望解决
