DNA计算求解连续空间优化问题.pdf

《DNA计算求解连续空间优化问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1期魏平等：DNA计算求解连续空间优化问题·151·*!"#计算求解连续空间优化问题魏平，熊伟清，王小权（宁波大学计算机科学与技术研究所，浙江宁波315211）摘要：首先构造了二进制编码的网络空间，其两个节点连接权的四条边对应到DNA编码，设计了相应的算子起到DNA计算酶的作用，该算法设计使得DNA计算能够求解连续空间优化问题。通过测试函数表明该算法具有较好的收敛速度和稳定性，求解结果非常好。关键词：群体进化；DNA计算；连续空间优化；函数优化中图法分类号：TP301.6文献标识码：A文章编号：1001-3695（2006）01-0151-03DNAComputingfo

2、rContinuousSpaceOptimizationWEIPing，XIONGWei-ging，WANGXiao-guan（InstituteofComputerScience&Technology，NingboUniuersity，NingboZhejiang315211，China）Abstract：Abinarycodingnetworkspaceisconstructed，itsfouredgefortwonodejointweightcorrespondtotheDNAco-ding，acorrespondingoperatorisusedascomputin

3、genzymeforDNA，thedesignfortheaigorithmmakestheDNAcomputingtosoivethecontinuousspaceoptimization.Thetestfunctionsshowthattheaigorithmhasbetterconvergencespeedandstabiiity，thesoivingresuitisexceiient.Keywords：SwarmEvoiution；DNAComputing；ContinuousSpaceOptimization；FunctionOptimization于连续空间优化

4、的DNA进化计算，经多个典型的多维函数优1引言化测试检验，该算法表现出良好的性能。1994年，美国南加州大学的Adieman教授在Science上发2DNA计算的数学模型表了关于DNA计算的开创性文章，运用生化实验的方法，解决了一个七节点的~amiiton路径问题，标志产生了一种新的计Adieman实验即是利用生物学工具得出了一个数学问题［1，2］算模式即DNA计算。的解。从这个例子可以看出，生物数学的思路包含着两个过在自然界中，生物体表现出的形状多种多样，而每个物种程：又保持相似性，这一切都是由生物体的遗传物质脱氧核糖核酸（1）生物体所具有的复杂结构实际上是编码在DNA序

5、列决定的。DNA中有四种碱基1腺嘌呤（A）、鸟嘌呤（G）、胞嘧中的原始信息经过一些简单的处理后得到的，或者说，经过一啶（C）和胸腺嘧啶（T），各种碱基的不同组合就构成了异常丰系列DNA简单操作可得出一个复杂的结果；富的遗传信息。科学家们指出，DNA含有大量的遗传密码，通（2）求一个含变量W的可计算函数的值也可以通过求一［2］过生化反应传递遗传信息。系列含变量W的简单函数的复合处理来实现的，即通过对WDNA链主要是一个脱氧核苷酸上的5*-磷酸基与另一个脱运用简单的函数关系可获得对W的复杂函数（fW）的结果。氧核苷酸核糖上的3*-羟基共价连接而成，反映了DNA链接从DNA计算的

6、原理和一些生物操作工具来看，与数学操是有向的。DNA由两条极长的核苷酸键组成，这两条核苷酸作非常类似，单股DNA可看作由四种不同符号A，T，C和G组键利用碱基之间的氢键结合在一起，形成一条双股的螺旋结成的串，就像计算机中编码“0”和“1”一样，可表示成四字母的构，且一股中的碱基序列与另一股中的碱基序列互补。A和T集合2｛A，G，C，T｝来译码信息。DNA串可作为译码信息，在配对，C和G配对。每个染色体是一段双股螺旋的DNA，A，T，DNA序列上可执行一些简单操作，这些操作是通过大量能处C，G在核苷酸中排列序列的多样性构成了丰富的遗传信息。理一些基本任务的酶来完成的。也就是说

7、，酶可看作模拟在［3］~oiiand的复杂自适应系统理论认为：诸如人脑、免疫系DNA序列上简单的计算。不同的酶用于不同的算子，如限制统、生命系统、细胞、蚂蚁群以及人类社会中的政党、组织等都内核核酸酶可作为分离算子，能够识别特定的DNA短序列，即是并行相互作用的Agent组成的网络。限制位。任何一个在其序列中包含限制位的双链DNA，在限本文首先构造了一个二进制编码的有向图，结果发现制位处被酶切断。DNA连接酶可作为绑结算子，将一条DNADNA编码实际上就是分子间的连接信息，于是我们提出了用链的末端连接到另一条DNA链