发布时间 : 星期二 文章DNA进化算法及其改进研究更新完毕开始阅读ee197a242f60ddccda38a04a
经网络、信号处理等领域。
基本DNA算法和模拟退火算法各有优缺点，首先DNA进化算法类似于遗传算法，局部的搜索能力较弱，但是其对搜索整体过程方面的把握比较有优势，模拟退火算法则反之，它拥有较好的局部搜索能力，但是不容易使搜索过程进入很理想的区域，所以，将这两种算法结合起来，应该会出现比较好的结果。本设计的改进算法实现过程中，首先用基本型DNA进化算法找出一个解，当然，这个解可能不是最优解，由于DNA进化算法具有较为优异的全局寻优性能的特点，故可假设求出的解与理论最优点相距不远了，而由于模拟退火算法有着较强的局部搜索能力，所以在之前基本算法的计算基础上，一定范围内的精细的模拟退火搜索很快能够找到最优值。
本设计中，模拟退火算法程序基本框架如下：
·······················································
初始化(初始点为原算法求得点) While(1)
Tem=tem * 衰减因子(退火操作) For i=0:1:马科夫链长度 While(1)
在初始点附近随机选下一点 判断新产生点是否在搜索范围内 End
%判断新产生点是否比原来最佳点更优 If(新产生点由于原最佳点) 保存新点最为最佳点 End
%接受新产生的点为下一迭代的开始点 If(新产生点与原来更优) 将原来点赋值为新点的值 End End
%结束条件为根据上一个最优解与最新的一个最优解的
之差小于某个容差
End
························································
第17页 共27页
起始初始化实际问题的DNA链编码计算适应度控制退火参数执行退火操作产生新个体是得到解？否选择交叉评价当前种群个体变异否达到最优目标？是结束倒位图6 与模拟退火结合的混合算法流程图
4 研究结果
本设计对以下三个典型函数进行优化来测试算法的性能，三个函数具有不
第18页 共27页
同的性质，其中第一个和第三个函数是利用算法求解最小值，对第二个函数求解最大值，三个典型函数均为二元函数，在算法设计过程中，首先初始化生成一个20行30列的DNA汤，即每一代运算可运算出20个不同的适应度值(即为函数值)，每一列有30位编码，前15位为x1编码对应映射至某个数值，后15位为x2的编码对应映射另一数值，然后用这20对x1和x2运算出20个不同的适应度，对这20个适应度值进行按大小顺序的排列，排列完成后就可以按顺序找到最大或最小值了，这20个适应度值是在一代计算中完成的，也就是说每一代进化后都会产生20个适应度值，我们求解出的则是这20个适应度值中最大或最小的那个。
以下为试验中用到的三个函数： (1) F1函数
?(x1??)F(x,x)??cosx()?cosx()?e12 1122?(x2??)2 (12)
其中x1和x2的取值范围均为-100至100，函数最小值为-1.00，最优点为(3.1410,3.1416)。
(2) Shaffer函数
sin2x2?y2?0.5F（x,y）?0.5?,?100?x?10,0?100?y?100222(1?0.001)(x?y) (13)
此函数有无限个局部极大值, 它们的取值均为0.9903,其中只有一个为全局极大点( 0, 0), 极大值为1。 （3） Camel函数
1f(x,y)?4x2?2.1x4?x6?xy?4y2?4y4,?5?x?5,?5?y?53
(14)
函数有6个局部极小点,其中有两个(- 0.0898,0.7126)和( 0.0898, - 0.7126) 为全局最小点, 最小值为- 1.0316。
本设计使用Matlab7.12软件来实现，采用蒙特卡洛统计法，每种算法各运行50次,对50次运算结果取平均值，同时统计找到最优点次数和找到最优点平均代数，并将几个函数的测试结果分别进行比较。其中找到最优点次数次数是指50次运算下找到全局最优解的次数。
找到最优解的代数是搜索时找到全局最优解时所需的进化代数, 如果在到终止代数( 200代)还不能搜索到最优解的以200代计,在结果分析时，因为测试函数性质是已知的，故算法运算过程中，若与理论值偏差较大的点，本设计中将其排除(因为即使不知道测试函数的最大值或最小值，在多次计算过程中也可判断出测试函数最大或最小值的趋势，至少能够确定出与理论值非常接近的一
第19页 共27页
点)。
4.1 基本算法的实验结果
在测试基本算法的实验中，各参数设置为：选择概率pc=0.8，变异和倒位概率均为0.01，DNA链的长度为30，DNA汤规模为20，进化代数为200代。
表 2基本算法实验结果
函数
找到最优点次数
找到最优点平
均代数
陷入局部最优
点次数
均值
最优点值
F1函数 Camel函数 Shaffer函数
9 0 10
24 未找到 128
16 7 28
-0.9991 -0.8557 0.990284
-1.000 -1.031628 1.000
从上表中可以看出，基本DNA算法对F1函数的50次运算结果中，直接找
到理论最优点次数为9次，这9次运算的平均找到最优点代数为24代，陷入局部最优点次数16次，50次运算中挑选出数据25组，剩下25组认为偏差较大，不参与统计，均值为-0.9991，接近理论值。
对Camel函数的实验中，基本算法未能找到最优点，陷入局部最优解7次，均值-0.8557，大致接近理论最小值。
对Shaffer函数的实验结果中，找到10次最优点，平均代数128代，28次陷入局部最优，12次出现偏差较大值，略去，均值为0.990284，仍然接近理论最大值。
从以上的统计结果我们可以看出，该算法基本上能够对典型测试函数进行寻优，但是多次实验中不能每次找到最优点，更多情况下陷入局部最优解，另外有较大偏差值的产生。最后，针对不同的函数，情况也不一样。
4.2 采取自适应方法改进的DNA进化算法实验结果
在测试自适应改进后算法的实验中，交叉概率、变异概率和倒位概率均采用自适应的方法，故为动态概率，其他参数同基本算法一致。
表3自适应改进算法实验结果 函数
找到最优点次
数
找到最优点平
均代数
陷入局部最优
点次数
均值
最优点值
F1函数 Camel函数 Shaffer函数
13 5 12
38 46 75
33 40 30
-0.9996 -0.9271 0.9903
-1.000 -1.031628 1.000
上表中，改进后的DNA进化算法对F1函数的50次运算结果中，找到最优
第20页 共27页