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

第#期

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

一维问题就是直线搜索!二维问题可以定义为圆等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本文算法

;#<)