《单变量边缘分布算法与蚁群算法的混合算法收敛性分析》由会员分享，可在线阅读，更多相关《单变量边缘分布算法与蚁群算法的混合算法收敛性分析（8页珍藏版）》请在金锄头文库上搜索。
1、 单变量边缘分布算法与蚁群算法的混合算法收敛性分析单变量边缘分布算法与蚁群算法的混合算法收敛性分析摘要：智能混杂算法是当前智能优化算法的研究热点，可以融合多种优化算法的优势，提高算法的性能。单变量边缘分布算法具有大范围快速全局搜索能力，但不能很好地利用系统中的反馈信息；蚁群算法是一种并行的分布式正反馈系统算法，但其初期信息素匮乏，求解速度慢。将单变量边缘分布算法与蚁群算法相结合，可以优势互补。基于上述思想，提出一种基于单变量边缘分布算法与蚁群算法混合的算法，并运用马尔科夫随机过程理论对该算法的收敛性进行了分析，结果表明了该算法的优化解满意值序列是单调不增的和收敛的。关键词：单变量边缘分布算法；
2、 蚁群算法； 收敛性； 智能混杂算法1 单变量边缘分布算法与蚁群算法混合的思路与方法1.1 单变量边缘分布算法与其群算法混合的思路描述单变量边缘分布算法1具有大范围快速全局搜索能力，但当求解到一定范围时往往对系统中的反馈信息利用不够，求精确解效率低。蚁群算法2主要通过蚁群之间的信息素的传递和更新达到最终收敛的最短路径上，其原理是一种正反馈机制，但初期信息素匮乏，求解速度比较慢。单变量边缘分布算法与蚁群算法的结合(umdaaa)正是基于单变量边缘分布算法的快速全局搜索能力和蚂蚁算法的正反馈收敛机制，初期采用单变量边缘分布算法过程生成信息素分布，后期利用蚂蚁算法正反馈求精确解，优势互补。1.2um
3、daaa 中对蚁群算法模型的选择与改进umdaaa 中对蚁群算法选择基于蚂蚁圈模型和 mmas(max min ant system)算法5 ，在吸取其各自优点的基础上并进行改进。信息素的初值设置：为了更加充分地进行寻优，mmas 把各路径信息素初值设为最大值 max，为了避免算法过早收敛非全局最优解，mmas 将各路经的信息素浓度限制在min,max之间，实验表明在防止算法过早停滞及有效性方面取得了很好的效果6 。这里通过单变量边缘分布算法得到了一定的路径信息素 dsm，所以把信息素的初值设置为7s=c+g，其中 c 是一个根据具体求解问题规模给定的一个信息素常数，相当于 mmas 算法中的
4、min,g=dsm 是 umda 算法求解结果转换的信息素值，那么本文中的信息素初值的设置为 ij(t)=dsm+min ij(t)。1.3 单变量边缘分布算法与其群算法混合的模型描述(1) 随机产生 m 个个体作为初始群体 dl，l=0；(2) 计算 m 个个体的适应值，如果符合开启条件，算法转向步骤(6)，否则继续进行；(3) 进行选择操作，选择 n0,limn pk=n(|xk(w)x(w)|)=0 对任一 0,pn=1k=n(|xk(w)x(w)|)=0。引理 26蚁群系统序列(m),x(m),f*(m)(m=1,2,)是有限齐次马尔科夫链。引理 38杰出者选择遗传算法种群序列x(n)
5、;n0是有限齐次马尔科夫链。定理 1umda 算法种群序列x(n);n0是有限齐次马尔科夫链。证明：由于 s=0,1l 中有 2l 个个体，则种群空间 sn 中有 2nl个个体，sn 为种群序列的状态空间，是有限的。x(n+1)=t(x(n)=tsatmts(x(n)，其中 tsa，tm，ts 均与n 无关。因此，x(n+1)仅与 x(n)有关，根据马尔科夫链的性质，有x(n);n0是有限状态的齐次马尔科夫链。定理 2umdaaa 算法的优化解序列x(n);n0是有限状态的齐次马尔科夫链。证明：由定理 1 知 umda 算法中 x(n+1)仅与 x(n)有关，与迭代次数 n 无关。由引理 1
6、知蚁群系统(m+1),x(m+1),f*(m+1)仅与(m),x(m),f*(m)有关，而与循环周期 m 无关。同时，由蚂蚁圈模型知每一次信息素仅更新最优蚂蚁圈，因此，取：x(n+1)=(xi(n+1)=tigtisatimtis(x(n)；(in1);xn(n+1)=xi0(n)这里 i0=argminjf(xj(n)表示使f(xj(n)取最小值的个体为 xj(n)，且转移概率矩阵为：px,y=px(n+1)=y|x(n)=x=nk=1pt(x(n)k=yk， i0m(x),使 yn=xi00,其他式中:m(x)=i;f(xi)=minf(xj)则:t(x(n)=tig(tisa(tim(t
7、is(x(n)=tigtisatimtis(x(n)上式表明，x(n+1)仅与 x(n)有关，而与 n 无关。umdaaa 算法的优化解序列x(n);n0是有限状态的齐次马尔科夫链。引理 48杰出者遗传算法的马尔科夫链序列的优化解满意值序列是单调不增的，即：f(x(n)f(x(n+1), n0。定理 3umda 算法的马尔科夫链序列的优化解满意值序列是单调不增的，即对于任意的 n0，有 f(x(n)f(x(n+1)。证明 xn(n+1)=xi0(n)，其中 i0=argminjf(xj(n)。则 f(x(n)f(xn(n+1)f(x(n+1)。定理 4umdaaa 算法的马尔科夫链序列的优化解
8、满意值序列是单调不增的，即对于任意的 n0，有 f(x(n)f(x(n+1)。证明：由定理 3，i0=argminjf(xj(n)，则有 xn(n+1)=xi0(n)，f(x(n)f(xn(n+1)f(x(n+1)。又由于算法采用了蚂蚁圈的算法，i0=argminjf(xj(n)，同样有 xn(m+1)=xi0(m)，f(x(m)f(xn(m+1)f(x(m+1)。而蚂蚁圈算法是以 umda 算法的结果为初始分布，具有优值继承性，因此对于任意的 n0，有 f(x(n)f(x(n+1)。即 umdaaa 算法的马尔科夫链序列的优化解满意值序列是单调不增的。引理 58杰出者遗传算法种群马尔科夫链序
9、列x(n);n0由概率 1 收敛到满意种群集 m*的子集 m*0定理 5umda 算法种群马尔科夫链序列x(n);n0由概率 1 收敛到满意种群集 m*的子集 m*0m*0=y=(y1,y2,，yn);ynm即：limn px(n)m*0|x(0)=x0=1 证明：对于任意 x,ysn,有：p(n,n+1,x,yi)=y1,y2,zpts(x(n)=y1,y2)ptm(y1,y2)=zptsa(z)=yi式中：yi=(x1,，xi1,yi,xi+1,xn)。而当 yyi(in)时 pn,n+1,x,y=0,于是x(n);n0是非时齐的马尔科夫链，记为：p(x,y)=limn pn,n+1,x,
10、y。那么有：p(x,y)0,xm*,ym*0,因此 p()=(p(x,y);x,ysn)具有惟一的不可约非周期常返类 m*。而 sn|m*中的种群均为非常返状态。于是x(n);n0是强遍历的，即有：limnpx(n)=y|x(0)=(y),(ym*)且ym(y)=1,于是 limnpx(n)m*|x(0)=limnym*px(n)=y|x(0)=ym*(y)=1 证毕。定理 6umdaaa 算法的优化解马尔科夫链序列x(n);n0由概率1 收敛到满意种群集 b 的子集 b*0，即 limnpx(n)b*0|b(0)=x0=1。证明：设 x是 f(x)的惟一最小值解，由定理 2 和定理 5 知p
11、(x,y)有性质：（1） 当 x,yb*0 时，px,y0,py,x0，即 x y;（2） 当 xb*0,y b*0 时，px,y=0,即 xy。因此，b*0 为正常返的非周期的不可约闭集，sn|b*0 为非常返的状态集：limn px(n)=y|x(0)=x0=(y),yb*00,y b*0 于是 limn px(n)b*0|x(0)=x0=1 证毕。推论对于 umdaaa 算法，若x(n);n0对于任意满意解集均收敛，则必收敛到全局最优解集。因为对于 0 有满意解集 b()=y;f(y)f(x*)+，其中 x*表示最优解，即 x*m 为全局最优解集。m 是所有满意解集之交集，m 为最小满意
12、解集。3 实验仿真及分析采用 umdaaa 算法对 tsp30 城市问题进行仿真实验，umdaaa 算法中 umda 算法迭代次数为 40 次，蚁群算法中路径初始值 c 的设置为 60，轨迹更新为 =0.8，q=1 000。其仿真结果如图 1 所示。图 1umdaaa 一次随机求解 tsp30 城过程表 1 表示的是 umdaaa 算法优化解的数据逼近过程。依次从随机优化解，选择算子，概率模型算子，抽样算子，蚁群算法更新优化值。从其最大值，最小值，平均值来看，umdaaa 算法是一个逐步收敛过程，与理论分析相一致。表 2 是 umdaaa 算法随机求解的 tsp30 城市问题的优化解分布。目前
13、公认的 tsp30 城最好解为 d=423.74，本文算法较好地逼近了这一最好解，有些值显得过大，原因在于 umda 算法的速度过快，导致种群的多样性缺失而造成的。表 1umdaaa 算法优化解数据逼近过程优化解的分布umdaaatsp30 优化解集最大值最小值平均值初始随机生成的优化值解 1 5001 2201 320.4 选择算子作用后的优化值解 1 2001 1071 142.5 概率模型算子作用后的优化值解 1 1121 0031 060.3 抽样算子作用后的优化值解 995805907.1 蚁群算法作用后的优化值解457424435.7图 1 是 umdaaa 算法对 tsp30 城
14、问题的一次随机求解过程。从图中可以看出，在蚁群算法求解的过程中，算法的收敛性非常的明显，而在选择算子，概率模型算子，抽样算子的作用过程中迭代的次数较多。那是因为前面算子的行为是为了积累更多的信息素，为算法的最后收敛作准备。从图 1 可以看出，算法经过 40 多代就已经收敛，而且是单调收敛的。表 2umdaaa 随机求解的 30 个优化解的分布tsp30 城优化解值的分布（=1，=2，=0.8，q=1 000）440427433447432429 4424374294404524304314394284254344414274304434324384364314434254374334284 结
15、语智能混杂算法是当前智能优化算法的研究热点，可以融合多种优化算法的优势，提高算法的性能。而算法的收敛性是算法最重要的指标之一。齐次有限马尔科夫链是进行优化算法分析的有力工具，本文提出将 umda 与 aa 结合的 umdaaa 算法，并运用齐次有限马尔科夫链对其收敛性进行了分析。结果表明，umdaaa 算法的满意解序列为一个单调不增的马尔科夫过程，并且一定能够收敛。参考文献1mehlenbein h. the equation for response to seletion and its use for prediction j. evolutionary computation, 1997, 5(3): 303 346.2miihlenbein h, paass g. from recombination of genes to the estimation of distributions m. berlin, germany: s.n.
