基于遗传算法和蚂蚁算法求解函数优化问题

基于遗传算法和蚂蚁算法求解函数优化问题

第!"卷第#期$%%&年#月

!"’()*+,-(./013,++361*738:+3+11*3+<31+<1245944;

工学版"浙!江!大!学!学!报!

=(->!"?(>#

@,*>$%%&

基于遗传算法和蚂蚁算法求解函数优化问题

杨剑峰

"浙江大学电气工程学院$浙江杭州##"%%$&

摘!要#针对遗传算法求解精度低以及蚂蚁算法求解速度慢的问题$提出一种基于遗传算法和蚂蚁算法的混合算法>该混合算法利用了遗传算法快速随机的全局搜索能力的优点$设计了编码与适应度函数$进行了种群生成与染色体的选择$并通过设定交叉算子和变异算子$生成了信息素分布>该混合算法利用了蚂蚁算法正反馈以及具有分布式并行全局搜索能力的优点$通过确定吸引强度的初始值$建立了强度更新的模型$从而求得精确解>并将该算法应用于求解函数优化问题>结果表明$该混合算法与遗传算法和蚂蚁算法相比$收敛速度快$寻优性能好>关键词#遗传算法&蚂蚁算法&函数优化

#中图分类号#JK"#!!!!!文献标识码#Q!!!!!文章编号#"%%PE&#R"$%%&%#%!$&%!

‘F0,*+"0"*+#+/(*+"0$)"5%&#5(-&9"01&0&*+,$

(%")+*2#(09(0*(%")+*2#11

SQ?‘’3,+G.1+4

"8(**’’(*’?$,%?.*/"%"’’,%"01’%.""%4’,#%$."71(&#"%%$&$81%".#+)/++$2+35$6+

%Q65-*)(,*3H1D,8801W*(I-1H7(.-(B7(-)83(+W*1<373(+I1+183<,-(*380H,+D7-(B*17(-63+11DI94447W9

,+8,-(*380H$,0I*3D,-(*380HI,71D(+41+183<,-(*380H,+D,+8,-(*380HB,7W*171+81D>J01H1*3849444(.,Y)3<[,+D*,+D(H4-(I,-71,*<03+3+41+183<,-(*380HB,7)71D3+8(801W*((71D0I*3D,-(*380H>44W94

$J01<(D3++D.38+177.)+<83(+B,7D173+1D,+DW()-,83(+W*(D)<3++D<0*(H(7(H171-1<83(+B1*14,4W4,$1*.(*H1D>J01D173+(.<*(77(61*(1*,8(*,+DH)8,83(+(1*,8(*B,7D181*H3+1D,+D801+W01*(H(+1W4WW

D378*3I)83(+B,7,<03161D>J01H1*387(.W(738361.11DI,<[3+,+8,-(*380H$801W,*,--1-W*(<1773++D44,-(I,-71,*<03+1*1)83-3C1D3+801W*((71D0I*3D,-(*380H$,+D8013+383,-6,-)1(.,88*,<83(+3+81+73844BW949

,+D801+8011V,<87(-)83(+B,7(I8,3+1D>J01B,7<(+.3*H1D>J01H(D1-(.3+81+738D,83+,7718)9)W4BW$,-(*380HB,7,-31D8(7(-61.)+<83(+(83H3C,83(+W*(I-1H7>J01*17)-8770(B80,8<(H,*1DB38041G4WWWW

+183<,-(*380H,+D,+8,-(*380H$801W*((71D,-(*380H<(+61*17.,781*,+D0,7I1881*71,*<03+44W444,I3-38>9

%7&")9-1+183<,-(*380H&,+8,-(*380H&.)+<83(+(83H3C,83(+444W8.控制’决策中普遍存!!函数优化问题是在工程’在的一类优化问题$其优化目标函数可能包含多个在一定范围内的连续变量$传统的优化手段对目标函数要求苛刻$如需要满足可导或者可微等>导致有些函数难以优化$容易陷入局部解而难以得到全局最优解$收敛速度较慢>近年来$人们从仿生学的机

收稿日期#$%%A""N>

理中受到启发$提出了许多用于求解函数优化问题的新方法$如模拟退火算法’遗传算法’蚁群算法等>然而对于函数优化问题的复杂性$每种算法都表现出各自的优势和缺陷>

遗传算法"是T1+183<,-(*380H$‘Q#(--,+D44

教授首先提出来的一类仿生型优化算法>在使用

浙江大学学报!工学版"网址#BBB>!()*+,-7>C)>1D)><+1+224

基金项目#高等学校博士点专项科研基金资助项目"#$%%#%##N%%$>

作者简介#杨剑峰"$男$江苏盐城人$博士生$从事蚁群算法方面的研究>%"E&&F#:GH,3-."E&&%!C)>1D)><+922

基于遗传算法和蚂蚁算法求解函数优化问题

!$P

浙!江!大!学!学!报!工学版""卷!!!!!!!!!!!!第!

‘Q算法求解函数优化问题时!

一般先将实际问题进行数学建模!将其抽象为一个数值函数的优化问题>‘Q提供了一种求解这种优化问题的通用框架>‘Q通过对群体所施加的迭代优化过程!

不断将当前群体中具有较高适应度的个体遗传到下一代群体中!并且不断地淘汰适应度低的个体!从而最终寻找出适应度最大的个体>其优点是""#具有大范围全局搜索的能力!与问题领域无关$$#搜索从群体出发!

具有潜在的并行性$可进行多值比较!鲁棒性强$搜索使用评价函数启发!过程简单$##使用概率机制进行迭代!

具有随机性$具有可扩展性!容易与其他算法结合>但是缺点是‘Q算法对于系统中的反馈信息利用不够!当求解到一定范围时往往做大量无为的冗余迭代!

求解效率低>蚂蚁算法%,+8,-4

(*380H!QQ#由意大利学者U(*34

(等人&"G$’

最早提出来!蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优>其优点是""#它的原理是一种正反馈机制!通过信息素的不断更新!最终收敛到最优路径上$$#分布式计算"蚂蚁算法是一种基于种群的进化算法!具有本质并行性!易于并行实现$##易与其他方法结合"蚂蚁算法很容易与多种启发式算法结合!

以改善算法的功能>但是其缺点是初期信息素匮乏!求解速度较慢&#’

>

因此本文算法吸取了‘Q和QQ的优点!采用‘Q生成信息素分布!

利用QQ求精确解!力求将两种算法优势互补!期望同时获得较好的优化性能和时间性能>

!蚂蚁算法的模型

>:!蚁周系统模型

蚁周系统模型是全局优化较好的蚂蚁算法!假如路径%%!2#在$时刻信息素轨迹强度为6%2!蚂蚁=在路径%%!2#上留下的单位长度轨迹信息素轨迹强度$6%2!=!轨迹的持久性(%%&(&"#!则轨迹强度的更新方程为

6%2%$L"#I((6%2%$#L0$6%2!

=%$#9%"#设0=为第=只蚂蚁在本次循环中所走的路径长度!则$6%2!

&=%$#]\)0=!其中\为一个常数#:!’

9

如果设%2为边路径%%!2#的能见度!一般取为")>%2!这里>%2为路径%%!2#的长度!路径能见度的相对重要性为&%&$%#!路径轨迹的相对重要性为!%!$%#!3为可行点集!蚂蚁=在$时刻的转移概率为C%2!

=%$#!则%2!

=%$#可定义&!’

如下"&%%$#’!&%’&$C%2!

=I0*"3&

6%*%$#’!&’%*’&2"3!%$#$2F39:?;!YY6A算法

最大最小蚂蚁系统%H,VGH3+,+879

781H!@@Q;#是比利时学者J0(H,7提出来的&N’

!它对基本蚂蚁算法进行了#点改进""#为了更加充分地进行寻优!各路径信息素轨迹强度初值设为最大值6H,V$

$#一圈中只有最短路径的蚂蚁才进行信息素修改增加!这与蚁周系统%,+879781H!Q;#模型调整方法相似$##为了避免算法过早收敛于非全局最优解!将各路径的信息素轨迹强度限制在&6H3+!6H,V’之间!超出这个范围的被强制设为6H3+或者6H,V!从实验结果看!@@Q;算法在防止算法过早停滞及有效性方面对Q;算法有较大的改进>

$!基于‘Q与QQ的混合算法的设计

;>:!函数优化问题的QQ模型

在函数优化问题中!由于最初的蚂蚁算法思想源于离散型的网络路径问题!因此必须对模型中的

实施细节加以修正&A’

>

本文主要研究的是一维函数的优化问题>

假定优化函数为H3+0])%;#9;"&.!A’!设-个蚂蚁!刚开始位于区间的-等分处!将式%$#中6%2改为62!称为蚂蚁2的邻域吸引强度!’

%2定义为)%F)2!即目标函数差异值!参数!!&"&"!N’!就可以得到蚂蚁的转移概率为

C%2I%&6!2’&’%2’&#)%0&6

=’!&’%=’&#9%#

#=

强度更新方程为

62%$L"#I((62%$#L0$62!

%!

#=

$62I\)T29

%N#式中"$62为第2只蚂蚁在本次循环中的领域吸引强度的增加!\为正常数!%#\#"%%%%!T2为本次循环中)%E#的变化量!定义为)%E_,#F)%E#

!%&(&"!于是函数优化就借助-个蚂蚁的不断移动来进行9当’%2$%时!蚂蚁%按概率C%2从其邻域%移至蚂蚁2的邻域$当’%2&%时!蚂蚁%做邻域搜索!搜索半径为,!即每个蚂蚁要么转移至其他蚂蚁处!要么进行邻域搜索9

可见一旦蚂蚁个数足够多!搜索半径足够小!这种搜寻方式相当于一群蚂蚁对区间%.!A#做穷尽的搜索!逐渐收敛到问题的全局最优解9

算法中的邻域设定可根据具体的问题来定!如

":’

C

基于遗传算法和蚂蚁算法求解函数优化问题

第#期

杨剑峰!等"基于遗传算法和蚂蚁算法求解函数优化问题

一维问题就是直线搜索!二维问题可以定义为圆等9搜索半径的大小主要和所要得到的解的精度有关!若问题的局部最优点密集!全局最优解不易得到时!就必须设置比较小的,!蚂蚁个数-则主要和搜索空间有关!搜索空间越大!所需的蚂蚁个数也越多9;>;!混合算法的设计思想

基于‘Q和QQ的混合算法!其基本思想"&#

是

汲取两种算法的优点!克服各自的缺陷!优势互补>

其基本思路"&#

是算法前过程采用‘Q!充分利用‘Q

的快速性$随机性$全局收敛性!其结果是产生有关问题的初始信息素轨迹强度分布%

算法后过程采用QQ!

在有一定初始信息素轨迹强度分布的情况下!充分利用QQ的并行性$正反馈机制以及求解效率高等特性!提高求解效率>

;><!混合算法中‘Q的构造原理

编码与适应值函数&结合解决的具体问题!采用十进制实数编码!适应值函数结合目标函数而定>在本文所要求解的函数优化问题中!以目标函数可行域中的点进行编码!适应度函数直接取为对应的目标函数值>

种群生成与染色体选择&利用Z,+D函数随机生成一定数量的十进制实数编码种群!根据适应度函数选择准备进行交配的一对染色体父串9

交叉算子&采用顺序交叉方法!具体操作如下&"’随机在父串上选择一个交配区域%例如两个父串选为

.]"$,#!NA,

&PE!A]EP,&AN!,

#$"9$

’将A的交配区域加到.之前!将.的交配区域加到A的前面&

.M]&AN!,

"$#!NA&PE!AM]#!NA,EP&AN!#$"9#’依次删除.M!AM中与交配区相同的数码!得到最终的两子串&

?]&AN!"$#PE!

>]#!NAEP&$"9

变异算子&采用逆转变异方法"##

!如染色体(":$:#:!:N:A’在区间$:#和区间N:A处发生断裂!断裂片段#9N又以反向顺序插入9于是逆转后的染色体变为(":$:N:!:#:A’9这里的进化!指逆转算子的单方向性!只有经过逆转后!适应值有提高的才被接受下来!否则逆转无效9

;>>!混合算法中的QQ设计

在混合算法中!蚂蚁算法采用本文"9$节所说的@@Q;算法!

这种算法在防止算法过早停滞以!$E

及有效性方面较蚁周系统有较大的改进>对于本文求解的函数优化问题!考虑到@@Q;与‘Q算法

的衔接问题!对$>"节用于函数优化的QQ模型中的邻域吸引强度的初始设置以及强度更新做以下处理>

吸引强度的初值设计&把各蚂蚁的邻域吸引强度初值设为最大值6H,V!这里通过‘Q得到了一定的蚂蚁邻域吸引强度!因此把吸引强度的初值设为67]6L_6‘9(A’式中&6L为一个根据具体求解问题给定的吸引强度常数!相当于@@Q;算法中的6H3+!6‘为‘Q求解结果转换的吸引强度9

强度更新模型&采用蚁周系统模型进行强度更新!即一周中只有目标函数值变化最小的蚂蚁才进行强度修改增加!而所有路径的轨迹更新方程均采用式(!’9

>=!算法步骤

根据本文算法的设计思想!其基本步骤如下&"

’输入问题!定义目标函数和适应值函数9随机生成一组实数编码9

$’根据适应值函数选择E$‘!对E$‘进行交叉计算9根据适应值函数进行逆转变异9进行递归迭代!直到生成若干组优化解9

#’初始化参数!根据优化解生成吸引强度初始分布9将-只蚂蚁置于各自的初始邻域!每只蚂蚁按概率C%2移动或做邻域搜索9

!’计算各蚂蚁的目标函数0=!

=]"!$!)!-!记录当前的最优解9按更新方程式(!’修正轨迹强度9N’$62修正!

=9=_"9若=小于预定的迭代次数!则转到步骤#’9

否则输出最优解9!仿真算例

为了验证本文算法的效果!本文选取了$个不同的一维连续性变量空间函数进行了算法的仿真实

验9求函数)"(

;’];#_#;$

FE;!;""FN!$#的最大值以及函数)$(

;’];73+("%,;’_$!;""F"!$#的最大值9&:!函数<:!

!"的计算结果由理论计算可以知道!该函数在解空间;""FN!$#中有一个最优解F#!相应的最优值为$&9"(

;’的优化函数较为简单!在解空间中仅有一个局部最优点9用本文提出的混合算法来进行求解!并

与‘Q算法"P#

$QQ算法"E#的求解进行了比较!

结果如表"所示9表"为"%次求解的平均值9本文算法

;#<)

基于遗传算法和蚂蚁算法求解函数优化问题

!#%

浙!江!大!学!学!报!工学版""卷!!!!!!!!!!!!第!

表:!函数<:!

!"的计算结果J,I>"!L(HW

)8,83(+*17)-87(..)+<83(+)!;"算法名称最优值最优解迭代次数‘Q

$A>E#""F$>EA"!

$PP

QQ$A>EEE$F$>EPPN!P本文算法

$&>%%%%

F#>%%%%

$P

的具体参数设置如下!‘Q迭代次数设定为$%代"

QQ中的各邻域强度初值#"%$

6L设置为#%"‘Q求解结果转换的强度值6‘]""蚂蚁数-]N"!]""&]""

]%9

&"\]"",]%9N9从表"可以看出"与‘Q和QQ算法相比"用本文算法求解)"%;&的最优值"迭代次数由$PP和!P"减少到$P"因此本文算法的求解速度较高9此外"用本文算法求得的最优值和最优解为$&9%%%%和F#9%%%%"与理论计算结果一致"因此本文算法的求解精度较好9

&;!函数<;!

!"的计算结果由理论计算可以知道"该函数在解空间;"#F""$$中有一个最优解"9PN"

相应的最优值为9PN9)$%;&的优化函数较为复杂"在解空间中分布有"&个局部最优点9

用本文提出的混合算法来进行求解"并与‘Q算法#P$

’QQ算法#E$的求解进行了比

较"结果如表$所示9表$为"%次求解的平均值9本文算法的具体参数设置如)"%

;&的参数设置9表;!函数<;!

!"的计算结果J,I>$!L(HW)8,83(+*17)-87(..)+<83(+)$!;"算法名称最优值最优解迭代次数‘Q

#>P#N!">P#&A

#NA

QQ#>P!!A">P!&PA%本文算法

!!从表$可以看出"

与‘Q和QQ算法相比"用本文算法求解)$%;&的最优值"迭代次数由#NA和%"减少到#$"

因此本文算法的求解速度较高>此外"用本文算法求得的最优值和最优解为#>PN%%和">PN%%"与理论计算结果一致"因此本文算法的求解精度较好>

!结!语

本文提出的混合算法汲取了‘Q和QQ两者的优点"同时克服了两种算法各自的缺点"在求解函数优化问题时"本文的算法在求精解效率和收敛速度上"都明显优于‘Q和QQ>此外"本文的算法对其他类型函数的优化问题也同样适用>

参考文献!D&3&)&0,&-"##"$UMZb‘M@"‘Q@OQZU:ccQc@>Q+8<(-(+317.(*

8018*,61-3+47,-17H,+W*(I-1H#’$>]+"-8-*&#-""EE&"!#%$&!&#P">

#$$UMZb‘M@"‘Q@OQZU:ccQc@>Q+8<(-(+979

7G81H!QL((W1*,8361-1,*+3+4,WW*(,<08(8018*,61-3+47,-1,H,+W*(I-1H#’$>LJJJ@)(0-(,*+"0"0J4"%F*+"0()8!"#$

*F*(*+"0""EE&""!N#AA?##$吴庆洪"张纪会"徐心和>具有变异特征的蚁群算法#’$>

计算机研究与发展""EEE"#A%"%&!"$!%"$!N>

\5d3+4G0(+4"/TQ?‘’3G0)3"R5R3+G01>Q+,+8<(-(+9,-4(*380HB380H)8,83(+.1,8)*17#’$>E"F)0(%"3,"#KBF*&)D&-&(),2P&4&%"$#&0*""EEE"#A%"%&!"$!%"$!N>

#!$UMZb‘M@"OMLQO:Q5:"JT:ZQMcQ‘>Q+8,-G

4(*380H,+D7834H1*49#’$>‘F*F)&Q&0&D(*+"0!"#$F*K&)A8

-*&#"$%%%""A!PN"P&">#N$JTM@Q;;J5//c:"TMc‘:ZTTMM;"18,->

@QRG@b?,+879781H#’$>‘F*F)&Q&0&)(*+"0!"#$F*&)A8

-*&#"$%%%""A%P&(PPEE"!?#A

$魏平"熊伟清>用于一般函数优化的蚁群算法>宁波大学学报"$%%"""!%!&!N$NN>

\:bK3+4"RbM?‘\13GY3+4>Q+8<(-(+9,-4(*380H.(*41+1*,-.)+<83(+W*(I-1H7#’$>E"F)0(%"3M+015"I0+K4&)-+*8

"$%%"""!%!&!N$NN?#&

$丁建立"陈增强"袁著址>遗传算法与蚂蚁算法的融合#’$>计算机研究与发展""EEE"#A%"%&!"$!%"$!N>Ub?‘’3+4G-3"LT:?/1+4GY3,+4"S5Q?/0)GC03>M+801<(HI3+,83(+(.41+183<,-4(*380H,+D,+8,-4(*380H#’$>E"F)0(%"3!"#$F*&)D&-&(),2(09P&4&%"$#&0*""EEE"#A%"%&!"$!%"$!N?

#P$张铃"张钹>遗传算法机理研究#’$>软件学报"$%%%"""

%&&!E!NEN$>

/TQ?‘c3+4"/TQ?‘O(>Z171,*<0(+801H1<0,G+37H(.41+183<,-4(*380H#’$>E"F)0(%"3A"3*.()&"$%%%"""%&&!E!NEN$?

#E$詹士昌>蚁群算法在连续空间优化问题中的应用#’$>

杭州师范学院学报"$%%!"#%N&!#EN#EE>

/TQ?;3G<0,+4>J01,WW-3<,83(+(.,+8<(-(+9,-4(G*380H3+801<(+83+)()77W,<1(W83H3C,83(+W*(I-1H7#’$>E"F)0(%"3W(01/2"F@&(,2&)-!"%%&1&"$%%!"#%N&!#EN#EE>

#"%$@QZL5;ZQ?UOQcc"Q?UZ:\c:\b;>QW,*,--1-3HW-1H1+GJ,83(+(.,+8<(-(+9(W83H3C,83(+#’$>E"F)0(%"3B()(%%&%(09P+-*)+5F*&9!"#$F*+01"$%%$"A$%E&!"!$""!#$?

(<#A!

本文来源：https://www.bwwdw.com/article/ryp4.html