分享,拿去。
孟晓春 两种智能优化算法及其应用遗传算法应用领域是应用研究的主要任务.
2 蚁群算法
蚁群算法(antcolonyalgorithm,ACA)是一种通用仿生并行算法,是20世纪90年代由意大利学者M.Dorigo[3,4]等人首先提出来的一种新型模拟进化算法,可用来求解传统方法难以解决的非凸、非线性非连续的优化问题.它通过模拟蚂蚁群的行为来求解问题,本质上是一种基于群体的多代理算法.蚁群算法与其他模拟进化算法一样,通过候选解组成的群体的进化过程来寻求最优解,包含两个基本阶段:适应阶段和协作阶段.在适应阶段,各候选解根据积累的信息不断调整自身结构;在协作阶段,候选解之间通过信息交流,以期望产生性能更好的解.
2.1 蚁群算法的基本原理
蚂蚁在走过的路上会释放一种特殊的分泌物—(),到并影响它们的行为,,从,.2.2 ,以求解非线形规划问题为例.考虑如下的非线性规划问题:minF(x1,x2,Λ,),,ai1x1+ai2x2+Λ+ainxn≥bi,i=1,2,Λ,r.这里F为任一非线形函数,约束条件构成Rn上的一个凸包.可以使用不等式变换的方法求得包含这个凸包的最小的n维立方体.设该立方体为li≤xi≤ui,i=1,2,Λ,n.
选取一定的长度length,设ki=ui-li/length,则可将该立方体在第i维上分成ki个子区间,其中j个子区间为[li+(j-1)3length,min(ui,li+j3length)].
设系统中有m只蚂蚁,我们将解的n个分量看成n个顶点,第i个顶点代表第i个分量,在第i个顶点到第i+1个顶点之间有ki条连线,代表第i个分量的取值可能在ki个不同的子区间.我们记其中第j条连线上在t时刻的信息量为τij(t).每只蚂蚁要从第1个顶点出发,按照一定的策略选择某一条连线到达第2个顶点,再从第2个顶点出发,……,在到达第n个顶点后,在kn条连线中选取某一条连线到达终点.每个蚂蚁所走过的路径代表一个解的初始方案,它指出解的每一个分量所在的子区间.用pijk(t)表示在t时刻蚂蚁k由城市i转移到城市j的概率,则式(1,2)
kpij(t)=
kpij(r∈allowedαβτ()η()j∈allowedkαβ∑τir(t)ηir(t)k(1)
(2) t)=0.
m只蚂蚁得到m个解后,要对它们进行评估,本人使用Lagrange函数作为评估解的优劣的适应度函数,否则要对每个解进行合法性检查并去除其中的不合法解.然后要根据适应度函数值更新各条边上的信息量.要根据下式对各路径上的信息量作更新:
ττ ir(t+1)=ρ3τir(t)+Δir,
kΔτ 其中τir=∑irk=1m(3)(4)
kΔτij表示蚂蚁k在本次循环中在城市i和j之间留下的信息量.
重复这样的迭代过程,直至满足停止条件.
候选组里的遗传操作:若候选组里的候选值的个数gi=0,即候选组里没有候选值,此时则产生一个[li+(j-1)×length,min(ui,li+j×length]间的随机数作为解分量的值wij,vij,跳过选择、交叉、变异等遗传操作.
若gi=1,即候选组里只有一个候选值wik,vik,则跳过交叉、选择等操作,直接对这个候选值wik,vik进行变异操作.
若gi=2,即候选组里有两个候选值,则跳过选择操作,直接对这两个候选值进行交叉、变异等操作.在所有蚂蚁都得到解以后,修改边条上的信息量按式(3)和式(4)相应地更新各子区间上的信息量.
95
