基于人工鱼群遗传算法的DNA编码优化

胡娟 李冬 张丽丽

摘要：针对DNA计算中的编码序列设计问题，分析DNA编码序列设计的目标和需要满足的约束条件，从中选择适当的约束条件，给出评估公式，提出人工鱼群遗传算法生成有效的DNA编码序列。经实验结果表明，所述算法比遗传算法及遗传粒子群算法产生的DNA编码序列质量更加稳定可靠。

关键词：DNA计算；DNA编码；组合优化；人工鱼群遗传算法

中图分类号：TP3015 文献标志码：A

文章编号：1672-1098（2014）01-0056-05

1994年，当文献[1]用DNA计算成功地解决了有向Hamilton路问题，人类已经进入了借助DNA分子通过生化反应来进行计算的崭新时代。从此越来越多的学者用DNA计算模型解决了许多NP完全问题，然而早期DNA计算中所用的序列都需要在设定编码长度的基础上随机产生，这就会导致生物化学反应不可控制性。因此寻找高质量DNA序列及合适的DNA序列库变得尤为重要。通常为了满足DNA序列可靠性的要求，就会利用约束条件来筛选序列，决定序列编码的约束条件主要有Gibb自由能增量约束、解链温度约束Tm、H-measure约束、生物酶和DNA分子的生物特异性等，要想找到好的编码就需要充分考虑这些约束条件。

遗传算法（Genetic Algorithm，GA）是20世纪70年代初文献[2]16首先提出来的。它常用来处理很复杂的非线性问题，具有非常好的鲁棒性。但它最大的缺点就是进化过程盲目性，常会陷入局部极值。尤其在编码问题中，当约束条件较多时，它有可能会搜索不到符合要求的编码。而全局人工鱼群算法是模仿鱼群觅食的一种算法，算法简单，又有避免陷入局部极值的良好能力。

本文在深入研究传统遗传算法的基础上，为了克服其盲目搜索的缺点，提高进化效率，给出了一种基于遗传算法和全局人工鱼群算法的混合优化算法（GAFSA/GA），用于DNA的编码问题，经实验结果表明，所述算法比遗传算法产生的DNA编码序列质量更加稳定可靠。

1DNA编码序列设计及约束项分析

11DNA编码问题

DNA计算中的编码问题一般都描述为：设由四个字母组成的集合∑={A，T，C，G}，若DNA分子长度为n，其编码集合为S，很明显有|S|=4n，求CS使xi，xj∈C ，τ（xi，xj）≥k，其中τ为评价标准，k∈Z+。然而τ越严格，可供选择的编码数|C|就会越小。编码问题，主要是编码质量和数量问题。因为编码质量越高，可靠性就会越好；而编码数量越大，就会扩大应用范围。然而，在现实中，他们是相互矛盾的。这就希望在保证质量的前提下能最大限度的得到编码集合。

12约束项及评价函数

影响DNA计算的因素[3-7]有很多，结合众多约束条件，给出本文的DNA编码的约束条件。

1） H-measure约束。H-measure是一种通过移位比较两个DNA序列汉明距离的最小值而获得的有效约束，移位后的互补碱基对的数目可以有效防止杂交，定义公式如下：

2人工鱼群遗传算法

21基本遗传算法

遗传算法是模拟生物进化过程中适者生存规则，并将其与种群内部染色体的随机信息进行交换，是一种很好的局部优化搜索方法[2]141。它的主要思想是：随机生成DNA序列；计算DNA序列的适应度函数值，满足约束条件；利用遗传算子生成满足约束条件的新的DNA序列，从而获得 DNA序列的集合（见图1）。

图1算法流程图

22人工鱼群算法（GAFSA）

人工鱼群算法就是模拟鱼群的觅食，聚首及追尾行为而生成的全局优化算法。通过观察鱼觅食会发现在一片水域中，鱼最多的地方就是食物最多的地方，鱼有自行或尾随其他鱼找到食物最多的地方特点。人工鱼群算法就是根据鱼群的这一特点，来构造人工鱼群来模仿鱼群行为，从而实现寻优。

1） 确定鱼群规模N，随机产生N 个人工鱼个体，组成初始群体，同时设置相关参数；

2） 计算初始鱼群的个体适应函数值，并将最优人工鱼状态记录到公告板；

3） 个体通过觅食行为，聚首行为，追尾行为[8]生成新的鱼群；

4） 选最优个体与公告板进行比较，若比公告板优，则以自身状态更新公告板；

5） 根据文献[8]对视野和步长进行调整；

6） 判断是否满足终止条件，若满足，则输出公告板记录，算法终止；若不满足，则执行步骤3。

23人工鱼群遗传算法（GAFSA/GA）

该算法是以基本遗传算法为基础，将人工鱼群算法作为遗传算法的一个重要算子，具体步骤如下：

1） 设定相关参数，并产生初始种群；

2） 计算个体的适应度函数值，按照适应度函数值进行排序；

3） 判断是否满足目标，若满足，输出结果，结束进程； 否则进行下一步；

4） 更新个体种群，根据适应度函数值的确定一部分个体直接进入下一代种群，剩余个体通过GAFSA算法优化过后进入下一代种群；

5） 对下代种群执行遗传算法的复制、交叉和变异等操作，转步骤2。

流程图如图2所示。

图2算法流程图

3算法仿真结果及分析

31与遗传算法的实验比较

用全局人工鱼群遗传算法产生的DNA序列与文献[9]的遗传算法的编码序列进行了比较，并给出了好的有向哈密尔顿路问题的DNA 序列。比较结果如表1和图3所示。

从图3可以看出，GAFSA/GA 算法生成的DNA编码序列在Hairpin、GC含量方面比GA 算法生成的DNA编码序列更优，并且可以看出GAFSA/GA生成的序列解链温度变化更小，这意味着GAFSA/GA算法具有较低的不完全匹配双链产生的概率。同时GAFSA/GA算法大大降低了计算的难度，在解决DNA编码问题方面效果很好，而且依靠群体人工鱼并行计算，其收敛速度较快，如（见图4）横轴为进化代数；竖轴为每代群体经排序后最差个体的适应度值。从图4中可以看出，算法具有较好的收敛性。

进化代数

图4GAFSA/GA算法的进化收敛图

32与遗传粒子群算法的实验比较

虽然文献[10]遗传粒子群算法（GA/PSO）与GAFSA/GA选择的约束条件不同，但鉴于实验结果的比对应建立在相同约束条件的基础上进行，采用GAFSA/GA的评价方法进行实验比对。比较结果如表2和图5所示。

从表2和图5可以看出，GAFSA/GA算法生成的DNA编码序列在解链温度、发夹结构等约束方面优于遗传粒子群算法生成的DNA编码序列。

4结论

从DNA 编码的多个约束条件选取合适的约束，提出了GAFSA/GA 算法对DNA 计算中的编码序列实现了优化，产生了很好的DNA 序列，验证了该算法的可行性和有效性。

参考文献：

[1]ADLEMAN L M.Molecular computation of solution to combinatorial problems[J]. Science， 1994， 66（11）： 1 021-1 024.

[2]HOLLAND J H.Adaptation in natural and artificial systems [M].AnnArbor：University of Michigan Press，1975：1-153.

[3]DEATON R，GARZON M.The Rmodynamic Constraints on DNA-based Computing[C]// Computing with Bio Molecues：Theory and Expirements.ed.G.Paun，Springer-Verlag：Singapore，1998：138-152.

[4]DEATON R，FRANCESCHETI D R，GARZON M，et al. Information transfer through hybridyzation reaction in DNA based computing[C]//Proceedings of the Second Annual Conference，1997，July 13-16，Stanford University，.Morgan Kaufmann，San Francisco：463-471.

[5]DEATON R. A DNA Based Implementation of an Evolutionary Computation[C]// Proceedings IEEE Conference on Evolutionary Computation. Indianapolis，1997：267-271.

[6]MARATHE A.On combinatorial DNA word design[J].DIMACS Series in Discrete Mathematics and Theoretical Computer Science，1999，44：75-88.

[7]ROSE J A. The Fidelity of DNA computation[D].Ph.D thesis，The University of Memphis，1999：11.

[8]付媛媛，张大方，向旭宇.基于人工鱼群的DNA编码序列组合优化算法研究[J].湖南城市学院学报：自然科学版，2011，20（2）：55-56.

[9]ARITA M，NISHIKAWA A，HAGIVA M，et al. Improving sequencedesign for DNA computing[C]// In Proceedings of the Genetic andEvolutionary Computation Conference（GECCO-2000），2000：875-882.

[10]CUI G Z，NIU Y Y，WANG Y F，et al. A new approach based onPSO algorithm to findgood computational encoding sequences[J].Progress in Natural Science，2007，17（6）：712-716.

[11]Feldkamp U，Raube H，Banzhaf W.Software tools for DNA sequence design[J].Genetic Programming and Evolvable Machines，2003，4（2）：153-171.

[12]张凯，肖建华.基于汉明距离的DNA编码约束研究[J].计算机工程与应用，2008，44（14）：24-26.

[13]XIAO J H，JIN X，CHEN Z H，et al. A hybrid quantum chaotic swarm evolutionary algorithm or DNA encoding[J]. Computers& Mathematics with Applications，2009，57（11/12）： 1 949-1 958.

[14]CUI GUANGZHAO，LI XIAO GUANG，ZHANG XUN CAI，et al. The Optimization of DNA Encodings Based on Modif ied PSO/GA Algorithm[J].CHINESE JOU RNAL OF OMPUT ERSVol， 2010，33（2）：312-313.

（责任编辑：何学华，吴晓红）

进化代数

图4GAFSA/GA算法的进化收敛图

32与遗传粒子群算法的实验比较

虽然文献[10]遗传粒子群算法（GA/PSO）与GAFSA/GA选择的约束条件不同，但鉴于实验结果的比对应建立在相同约束条件的基础上进行，采用GAFSA/GA的评价方法进行实验比对。比较结果如表2和图5所示。

从表2和图5可以看出，GAFSA/GA算法生成的DNA编码序列在解链温度、发夹结构等约束方面优于遗传粒子群算法生成的DNA编码序列。

4结论

从DNA 编码的多个约束条件选取合适的约束，提出了GAFSA/GA 算法对DNA 计算中的编码序列实现了优化，产生了很好的DNA 序列，验证了该算法的可行性和有效性。

参考文献：

[1]ADLEMAN L M.Molecular computation of solution to combinatorial problems[J]. Science， 1994， 66（11）： 1 021-1 024.

[2]HOLLAND J H.Adaptation in natural and artificial systems [M].AnnArbor：University of Michigan Press，1975：1-153.

[3]DEATON R，GARZON M.The Rmodynamic Constraints on DNA-based Computing[C]// Computing with Bio Molecues：Theory and Expirements.ed.G.Paun，Springer-Verlag：Singapore，1998：138-152.

[4]DEATON R，FRANCESCHETI D R，GARZON M，et al. Information transfer through hybridyzation reaction in DNA based computing[C]//Proceedings of the Second Annual Conference，1997，July 13-16，Stanford University，.Morgan Kaufmann，San Francisco：463-471.

[5]DEATON R. A DNA Based Implementation of an Evolutionary Computation[C]// Proceedings IEEE Conference on Evolutionary Computation. Indianapolis，1997：267-271.

[6]MARATHE A.On combinatorial DNA word design[J].DIMACS Series in Discrete Mathematics and Theoretical Computer Science，1999，44：75-88.

[7]ROSE J A. The Fidelity of DNA computation[D].Ph.D thesis，The University of Memphis，1999：11.

[8]付媛媛，张大方，向旭宇.基于人工鱼群的DNA编码序列组合优化算法研究[J].湖南城市学院学报：自然科学版，2011，20（2）：55-56.

[9]ARITA M，NISHIKAWA A，HAGIVA M，et al. Improving sequencedesign for DNA computing[C]// In Proceedings of the Genetic andEvolutionary Computation Conference（GECCO-2000），2000：875-882.

[10]CUI G Z，NIU Y Y，WANG Y F，et al. A new approach based onPSO algorithm to findgood computational encoding sequences[J].Progress in Natural Science，2007，17（6）：712-716.

[11]Feldkamp U，Raube H，Banzhaf W.Software tools for DNA sequence design[J].Genetic Programming and Evolvable Machines，2003，4（2）：153-171.

[12]张凯，肖建华.基于汉明距离的DNA编码约束研究[J].计算机工程与应用，2008，44（14）：24-26.

[13]XIAO J H，JIN X，CHEN Z H，et al. A hybrid quantum chaotic swarm evolutionary algorithm or DNA encoding[J]. Computers& Mathematics with Applications，2009，57（11/12）： 1 949-1 958.

[14]CUI GUANGZHAO，LI XIAO GUANG，ZHANG XUN CAI，et al. The Optimization of DNA Encodings Based on Modif ied PSO/GA Algorithm[J].CHINESE JOU RNAL OF OMPUT ERSVol， 2010，33（2）：312-313.

（责任编辑：何学华，吴晓红）

进化代数

图4GAFSA/GA算法的进化收敛图

32与遗传粒子群算法的实验比较

虽然文献[10]遗传粒子群算法（GA/PSO）与GAFSA/GA选择的约束条件不同，但鉴于实验结果的比对应建立在相同约束条件的基础上进行，采用GAFSA/GA的评价方法进行实验比对。比较结果如表2和图5所示。

从表2和图5可以看出，GAFSA/GA算法生成的DNA编码序列在解链温度、发夹结构等约束方面优于遗传粒子群算法生成的DNA编码序列。

4结论

从DNA 编码的多个约束条件选取合适的约束，提出了GAFSA/GA 算法对DNA 计算中的编码序列实现了优化，产生了很好的DNA 序列，验证了该算法的可行性和有效性。

参考文献：

[1]ADLEMAN L M.Molecular computation of solution to combinatorial problems[J]. Science， 1994， 66（11）： 1 021-1 024.

[2]HOLLAND J H.Adaptation in natural and artificial systems [M].AnnArbor：University of Michigan Press，1975：1-153.

[3]DEATON R，GARZON M.The Rmodynamic Constraints on DNA-based Computing[C]// Computing with Bio Molecues：Theory and Expirements.ed.G.Paun，Springer-Verlag：Singapore，1998：138-152.

[4]DEATON R，FRANCESCHETI D R，GARZON M，et al. Information transfer through hybridyzation reaction in DNA based computing[C]//Proceedings of the Second Annual Conference，1997，July 13-16，Stanford University，.Morgan Kaufmann，San Francisco：463-471.

[5]DEATON R. A DNA Based Implementation of an Evolutionary Computation[C]// Proceedings IEEE Conference on Evolutionary Computation. Indianapolis，1997：267-271.

[6]MARATHE A.On combinatorial DNA word design[J].DIMACS Series in Discrete Mathematics and Theoretical Computer Science，1999，44：75-88.

[7]ROSE J A. The Fidelity of DNA computation[D].Ph.D thesis，The University of Memphis，1999：11.

[8]付媛媛，张大方，向旭宇.基于人工鱼群的DNA编码序列组合优化算法研究[J].湖南城市学院学报：自然科学版，2011，20（2）：55-56.

[9]ARITA M，NISHIKAWA A，HAGIVA M，et al. Improving sequencedesign for DNA computing[C]// In Proceedings of the Genetic andEvolutionary Computation Conference（GECCO-2000），2000：875-882.

[10]CUI G Z，NIU Y Y，WANG Y F，et al. A new approach based onPSO algorithm to findgood computational encoding sequences[J].Progress in Natural Science，2007，17（6）：712-716.

[11]Feldkamp U，Raube H，Banzhaf W.Software tools for DNA sequence design[J].Genetic Programming and Evolvable Machines，2003，4（2）：153-171.

[12]张凯，肖建华.基于汉明距离的DNA编码约束研究[J].计算机工程与应用，2008，44（14）：24-26.

[13]XIAO J H，JIN X，CHEN Z H，et al. A hybrid quantum chaotic swarm evolutionary algorithm or DNA encoding[J]. Computers& Mathematics with Applications，2009，57（11/12）： 1 949-1 958.

[14]CUI GUANGZHAO，LI XIAO GUANG，ZHANG XUN CAI，et al. The Optimization of DNA Encodings Based on Modif ied PSO/GA Algorithm[J].CHINESE JOU RNAL OF OMPUT ERSVol， 2010，33（2）：312-313.

（责任编辑：何学华，吴晓红）