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

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

!$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