基于闭环DNA的指派问题算法.pdf

计算机科学2007V01．34No．12 基于闭环DNA的指派问题算法*) 周康1-2同小军1-2许进2 (武汉工业学院数理科学系 武汉430023)1(华中科技大学控制科学与工程系 武汉430074)2 摘要给出了闭环DNA计算模型及其生化实验。用闭环DNA计算模型设计出了指派问题的DNA算法。首先对 决策变量进行二维DNA编码来存放决策变量和效益值，然后通过有目的的终止技术和删除实验得到指派问题的全 部可行解，最后通过电泳实验和检测实验获得最优指派问题的最优解。举例说明了算法的可行性。最后，为减少 DNA编码数量和缩短DNA编码的码长，讨论了算法的两种改进方法。 关键词闭环DNA计算模型，指派问题，删除实验，有目的的终止技术 An of ProblemBasedonClosedCircleDNA AlgorithmAssignment ZHOU TONG XU Kan91-2 Yaao-Junl·2Jinz ofMathematicsand Polytechnic 430023)1 (Department Physics，WuhanUniversity，Wuhan ofControlScience ofScienceand 430074)2 (Department andEngineer。HuazhongUniversity Technology，Wuhan are for— AbstractInthis modelofclosedcircleDNA andits experimentsbrought paper，a computingbio-chemistry ward．An basedonclosedcircleDNAis for the algorithm designedassignmentproblem．Inalgorithm，firstplanar DNA each variableisencodedtO each variableandbenefitvalue． encodingfor decision-making depositdecision-making anddelete thenall Thenallfeasiblesolutionsare experiment．Andoptimiza— gained、^，ithpurposiveendingtechnology with anddetect ofthis isex- tionsolutionsareobtained experiment．Feasibility electrophoresisexperiment algorithm inordertOdecreasenumberof an twO methodsofthis arediscussed plainedby example．Finallyimproving algorit