資源描述：
《0_1規(guī)劃問題閉環(huán)dna算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、第31卷第4期系統(tǒng)工程與電子技術(shù)Vol.31No.42009年4月SystemsEngineeringandElectronicsApr.2009文章編號:10012506X(2009)0420947205021規(guī)劃問題的閉環(huán)DNA算法1,211,22周康,覃磊,同小軍,許進(1.武漢工業(yè)學(xué)院數(shù)理科學(xué)系,湖北武漢430023;2.華中科技大學(xué)控制科學(xué)與工程系,湖北武漢430074)摘要:提出了閉環(huán)DNA分子的結(jié)構(gòu)靈活性的兩個方面,即DNA分子鏈長的可控性和DNA分子之間的相互轉(zhuǎn)化。針對非負整數(shù)系數(shù)的0-1規(guī)劃問題,提出了閉環(huán)DNA算法。該算法首先對0-1變量按照0和1的取值、對應(yīng)的各項
2、系數(shù)和檢測標(biāo)記進行五組DNA編碼并形成所有可能解;再利用接入實驗、電泳實驗和刪除實驗篩選出可行解,進而得到所有最優(yōu)解;最后通過檢測實驗輸出實驗結(jié)果。給出了算法的正確性的證明并討論了算法復(fù)雜性,給出一個算例說明了算法的有效性。對算法進行了改進,改進后的算法適用于可以含有負數(shù)的實數(shù)系數(shù)0-1規(guī)劃問題。關(guān)鍵詞:閉環(huán)DNA計算模型;0-1規(guī)劃問題;接入實驗;刪除實驗中圖分類號:TP301.6文獻標(biāo)志碼: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年張鳳月等人通過設(shè)計合021規(guī)劃問題在傳統(tǒng)的和現(xiàn)代的優(yōu)化算法中一直沒有理的表面上DNA的排列方式解決了這個問題,而這兩種算[123]找到合適的多項式算法。DNA計算以其高度并行性和法還只能用DNA計算找到021規(guī)劃問題的可行解,最優(yōu)解[6]巨大的儲存容量有望解決
