发布时间 : 星期三 文章DNA进化算法及其改进研究更新完毕开始阅读ee197a242f60ddccda38a04a
点13次，陷入局部最优点33次，除去偏差较大点4次，较大偏差点出现次数明显比基本型算法少，46次有效数据均值-0.9996，比基本型算法有所改进。
对Camel函数的50次实验结果中，5次找到理论最优点，陷入局部最优点40次，较大偏差出现5次，45次有效数据均值-0.9271，比基本型算法有所改进。
在对Shaffer函数的50次实验结果中，12次找到理论最优点，平均代数75,30次陷入局部最优，42次有效数据的均值0.9903。
从以上数据分析可以得知，自适应改进后的算法与基本型算法相比，效果有所改进，找到理论最优点次数增多，所用进化代数减少了，均值更加靠近理论值了。
4.3 采用与模拟退火算法结合的混合算法实验结果
在测试与模拟退火算法结合的混合算法实验中，进化操作概率同基本算法一致，DNA长度30，DNA汤规模20，进化代数为200代，模拟退火初始温度为100，马科夫链长度10000，温度衰减因子为0.95，搜索步长0.02，容差为1e-8。
表 4 DNA-SA算法实验结果
函数
找到最优点次数
陷入局部最优点次
数
F1函数 Camel函数 Shaffer函数
50 50 30
0 0 20
-1.000 -1.031628 0.9998
-1.000 -1.031628 1.000
均值
最优点值
采用与模拟退火算法结合的算法后，对于前两个函数，50次实验每次均找到了理论最优点值，没有出现陷入局部最优点的情况。每次运算结果均为理论最优点，对Shaffer函数的50次运算结果中，30次找到理论最优点，没有出现较大偏差的情况，50次实验的均值为0.9998，以及非常接近理论最大值了。
改进后算法的模拟退火操作在基本DNA进化算法之后，故本表中不再涉及进化代数的问题。
基于统计结果，我们可以看出与模拟退火算法结合的混合算法有着极优的寻优功能，这也证明了模拟退火算法有良好的局部寻优能力的结论，其唯一缺点是运算时间和结果两个方面存在矛盾，这是因为如果想要得到很好的结果的话，每一次退火操作之后，又要经过马科夫链长度那么多次迭代计算，而为了结果精确，马科夫链长度往往会选择较长。
4.4 典型测试函数运行效果图
运算结果如下列图示，由于算法运算每次都是随机的，故效果图只定性的
第21页 共27页
分析适应度随进化代数之间的关系。
0-0.1-0.2-0.3-0.4BestF-0.5-0.6-0.7-0.8-0.9-1020406080100Times120140160180200
图7 F1函数运行效果图
上图横坐标表示进化代数，纵坐标为每一代对应的最佳适应度值，从上图可以看出，算法在大概50代以后趋于收敛，求得适应度值接近-1。
1412108x 104BestF6420-2020406080100Times120140160180200
图8 camel函数运行效果图
同上，横坐标表示进化代数，纵坐标为每一代对应的最佳适应度值，从上
第22页 共27页
图可以看出，算法在大概50代以后趋于收敛，求得适应度值接近-1。
10.950.90.85BestF0.80.750.70.65020406080
100Times120140160180200
图9 shaffer函数运行效果图
从上图可以得知，算法运行过程中，30代以后趋于收敛，收敛前适应度值随进化代数增加而直接增大。
4.5 几种方法的比较
通过对表2、表3和表4的分析得知，基本算法在计算过程中，能够寻找到最优点，但是对于50次试验的统计规律看，寻优次数并不多，而且，偏离理论最优点幅度较大的次数较多。采用自适应算法后，寻优的速度较基本算法要快一些，这一点我们可以从找到最优点平均进化代数中读出来，找到最优点的机会也明显大了一些，因为找到最优点次数有所增加，另外，陷入局部最优值的次数也有所增加，说明偏离理论最优点较大的机会更少了，但是总体说来改进效果仍然不是非常理想。表4中数据位采用与模拟退火算法结合的算法，很明显的是寻优效果最好，且前两个函数的运行基本上能够达到每一次都能找到最优点，但因为算法是先让基本算法寻优，再对寻优找到的结果附近有模拟退火操作，所以计算时间偏长。
另外，对于不同的测试函数，同种方法达到的效果也不一样，比如在基本算法与模拟退火结合的混合算法中，shaffer函数存在收敛于局部最优点的情况，而改进后对于另外两个函数，效果很理想。
第23页 共27页
结 论
DNA计算是一个崭新的研究领域，DNA进化算法是基于生物DNA编码和进化机制的一类仿生优化算法，对解决复杂的组合优化问题非常有效，传统的遗传算法是一种在分子水平模拟生物进化过程并能够在电子计算机上实现求解复杂问题的有效算法，故可作为研究DNA进化算法的桥梁。
本研究在借鉴标准遗传算法的基础上，对于DNA链上的生物信息，也就是四个碱基A、T、C和G，分别赋以0、1、2、3，用四进制代替传统遗传算法的二进制对DNA链进行编码，同时，丰富了变异操作，增加了倒位操作，以期得到较遗传算法更好的效果。
在对典型测试函数的测试实验中可以表明，基本DNA算法虽然能够达到找到最优点的要求，但是主要问题在于实验50次，找到最优点的次数较少，更多的时候是陷入局部最优值或者偏离理论值过大，为此，本设计中引入了两种改进方法：对算法中的进化操作概率赋以自适应动态改变的自适应算法和与模拟退火算法结合的混合算法。
自适应算法在一定程度上改进了遗传性能，但不足之处在于，它们往往都是对适应度低的个体以恒定较高的概率进行交叉，而对于适应度高的个体以自适应变化的、但总体较低的概率进行交叉操作。这样对于保护种群中的优势个体不被破坏是有效的，但对于新的优势个体的产生反而是不利的，算法一旦陷入局部最优，很难跳出[8]。
模拟退火算法有着非常好的局部寻优能力，所有本设计设想能否先用DNA进化算法搜索出一个值，理论上这点与最优点不会相差太远，然后利用模拟退火算法的超强局部搜索能力，很高质量的找到最优点，实验结果证明这种设想是正确的。
DNA算法作为一个新兴的研究领域，目前学术界对其研究的论文数量远不如其他很成熟的算法那般多，相信经过学术界的进一步研究，DNA算法会越来越成熟，由于笔者水平有限，本研究中难免可能有一些不正确之处，请各位老师指正。
第24页 共27页