单变量边缘分布算法与蚁群算法的混合算法收敛性分析

单变量边缘分布算法与蚁群算法的混合算法收敛性分析摘要：智能混杂算法是当前智能优化算法的研究热点，可以融合多种优化算法的优势，提高算法的性能。

单变量边缘分布算法具有大范围快速全局搜索能力，但不能很好地利用系统中的反馈信息；蚁群算法是一种并行的分布式正反馈系统算法，但其初期信息素匮乏，求解速度慢。

将单变量边缘分布算法与蚁群算法相结合，可以优势互补。

基于上述思想，提出一种基于单变量边缘分布算法与蚁群算法混合的算法，并运用马尔科夫随机过程理论对该算法的收敛性进行了分析，结果表明了该算法的优化解满意值序列是单调不增的和收敛的。

关键词：单变量边缘分布算法；蚁群算法；收敛性；智能混杂算法1单变量边缘分布算法与蚁群算法混合的思路与方法1.1单变量边缘分布算法与其群算法混合的思路描述单变量边缘分布算法［1］具有大范围快速全局搜索能力，但当求解到一定范围时往往对系统中的反馈信息利用不够，求精确解效率低。

蚁群算法［2］主要通过蚁群之间的信息素的传递和更新达到最终收敛的最短路径上，其原理是一种正反馈机制，但初期信息素匮乏，求解速度比较慢。

单变量边缘分布算法与蚁群算法的结合(umdaaa)正是基于单变量边缘分布算法的快速全局搜索能力和蚂蚁算法的正反馈收敛机制，初期采用单变量边缘分布算法过程生成信息素分布，后期利用蚂蚁算法正反馈求精确解，优势互补。

1.2umdaaa中对蚁群算法模型的选择与改进umdaaa中对蚁群算法选择基于蚂蚁圈模型和mmas(max min ant system)算法［5］，在吸取其各自优点的基础上并进行改进。

信息素的初值设置：为了更加充分地进行寻优，mmas把各路径信息素初值设为最大值τmax，为了避免算法过早收敛非全局最优解，mmas 将各路经的信息素浓度限制在［τmin,τmax］之间，实验表明在防止算法过早停滞及有效性方面取得了很好的效果［6］。

这里通过单变量边缘分布算法得到了一定的路径信息素dsm，所以把信息素的初值设置为［7］τs=τc+τg，其中τc是一个根据具体求解问题规模给定的一个信息素常数，相当于mmas算法中的τmin,τg=dsm是umda算法求解结果转换的信息素值，那么本文中的信息素初值的设置为τij(t)=dsm+min τij(t)。

1.3单变量边缘分布算法与其群算法混合的模型描述(1) 随机产生m个个体作为初始群体dl，l=0；(2) 计算m个个体的适应值，如果符合开启条件，算法转向步骤(6)，否则继续进行；(3) 进行选择操作，选择n0,limn→∞ p{∪∞k=n(|xk(w)－x(w)|≥ε)}=0ε>0,p{∩∞n=1∪∞k=n(|xk(w)－x(w)|≥ε)}=0。

引理2［6］蚁群系统序列{τ(m),x(m),f*(m)}(m=1,2,…)是有限齐次马尔科夫链。

引理3［8］杰出者选择遗传算法种群序列{x(n);n≥0}是有限齐次马尔科夫链。

定理1umda算法种群序列{x(n);n≥0}是有限齐次马尔科夫链。

证明：由于s={0,1}l中有2l个个体，则种群空间sn中有2nl 个个体，sn为种群序列的状态空间，是有限的。

x(n+1)=t(x(n))=tsa·tm·ts(x(n))，其中tsa，tm，ts均与n 无关。

因此，x(n+1)仅与x(n)有关，根据马尔科夫链的性质，有{x(n);n≥0}是有限状态的齐次马尔科夫链。

定理2umdaaa算法的优化解序列{x(n);n≥0}是有限状态的齐次马尔科夫链。

证明：由定理1知umda算法中x(n+1)仅与x(n)有关，与迭代次数n无关。

由引理1知蚁群系统{τ(m+1),x(m+1),f*(m+1)}仅与{τ(m),x(m),f*(m)}有关，而与循环周期m无关。

同时，由蚂蚁圈模型知每一次信息素仅更新最优蚂蚁圈，因此，取：x(n+1)=(xi(n+1)=tig·tisa·tim·tis(x(n))；(i≤n－1);xn(n+1)=xi0(n))这里i0=argminj{f(xj(n))}表示使f(xj(n))取最小值的个体为xj(n)，且转移概率矩阵为：p{x,y}=p{x(n+1)=y|x(n)=x}=∏nk=1p{t(x(n))k=yk}，i0∈m(x),使yn=xi00,其他式中:m(x)={i;f(xi)=min{f(xj)}}则:t(x(n))=tig(tisa(tim(tis(x(n)))))=tig·tisa·tim·tis(x(n))上式表明，x(n+1)仅与x(n)有关，而与n无关。

umdaaa算法的优化解序列{x(n);n≥0}是有限状态的齐次马尔科夫链。

引理4［8］杰出者遗传算法的马尔科夫链序列的优化解满意值序列是单调不增的，即：f(x(n))≥f(x(n+1)),n≥0。

定理3umda算法的马尔科夫链序列的优化解满意值序列是单调不增的，即对于任意的n≥0，有f(x(n))≥f(x(n+1))。

证明xn(n+1)=xi0(n)，其中i0=argminj{f(xj(n))}。

则f(x(n))≥f(xn(n+1))≥f(x(n+1))。

定理4umdaaa算法的马尔科夫链序列的优化解满意值序列是单调不增的，即对于任意的n≥0，有f(x(n))≥f(x(n+1))。

证明：由定理3，i0=argminj{f(xj(n))}，则有xn(n+1)=xi0(n)，f(x(n))≥f(xn(n+1))≥f(x(n+1))。

又由于算法采用了蚂蚁圈的算法，i0=argminj{f(xj(n))}，同样有xn(m+1)=xi0(m)，f(x(m))≥f(xn(m+1))≥f(x(m+1))。

而蚂蚁圈算法是以umda算法的结果为初始分布，具有优值继承性，因此对于任意的n≥0，有f(x(n))≥f(x(n+1))。

即umdaaa算法的马尔科夫链序列的优化解满意值序列是单调不增的。

引理5［8］杰出者遗传算法种群马尔科夫链序列{x(n);n≥0}由概率1收敛到满意种群集m*的子集m*0定理5umda算法种群马尔科夫链序列{x(n);n≥0}由概率1收敛到满意种群集m*的子集m*0m*0={y=(y1,y2,…，yn);yn∈m}即：limn →∞ p{x(n)∈m*0|x(0)=x0}=1证明：对于任意x,y∈sn,有：p(n,n+1,x,yi)=∑y1,y2,zp{ts(x(n))=y1,y2)}p{tm(y1,y2)=z}p{tsa(z)=yi}式中：yi=(x1,…，xi－1,yi,xi+1,…,xn)。

而当y≠yi(i≤n)时p{n,n+1,x,y}=0,于是{x(n);n≥0}是非时齐的马尔科夫链，记为：p∞(x,y)=limn→∞ p{n,n+1,x,y}。

那么有：p∞(x,y)>0,x∈m*,y∈m*0,因此p(∞)=(p∞(x,y);x,y∈sn)具有惟一的不可约非周期常返类m*。

而sn|m*中的种群均为非常返状态。

于是{x(n);n≥0}是强遍历的，即有：limn→∞p{x(n)=y|x(0)}=π(y),(y∈m*)且∑y ∈mπ(y)=1,于是limn→∞p{x(n)∈m*|x(0)}=limn→∞∑y∈m*p{x(n)=y|x(0)}=∑y∈m*π(y)=1证毕。

定理6umdaaa算法的优化解马尔科夫链序列{x(n);n≥0}由概率1收敛到满意种群集b的子集b*0，即limn→∞p{x(n)∈b*0|b(0)=x0}=1。

证明：设x′是f(x)的惟一最小值解，由定理2和定理5知p(x,y)有性质：（1）当x,y∈b*0时，p{x,y}>0,p{y,x}>0，即x y;（2）当x∈b*0,y b*0 时，p{x,y}=0,即x→y。

因此，b*0为正常返的非周期的不可约闭集，sn|b*0为非常返的状态集：limn→∞ p{x(n)=y|x(0)=x0}=π(y),y∈b*00,y b*0于是 limn→∞ p{x(n)∈b*0|x(0)=x0}=1证毕。

推论对于umdaaa算法，若{x(n);n≥0}对于任意满意解集均收敛，则必收敛到全局最优解集。

因为对于ε>0有满意解集b(ε)={y;f(y)≤f(x*)+ε}，其中x*表示最优解，即x*∈m为全局最优解集。

m是所有满意解集之交集，m为最小满意解集。

3实验仿真及分析采用umdaaa算法对tsp30城市问题进行仿真实验，umdaaa算法中umda算法迭代次数为40次，蚁群算法中路径初始值τc的设置为60，轨迹更新为ρ=0.8，q=1 000。

其仿真结果如图1所示。

图1umdaaa一次随机求解tsp30城过程表1表示的是umdaaa算法优化解的数据逼近过程。

依次从随机优化解，选择算子，概率模型算子，抽样算子，蚁群算法更新优化值。

从其最大值，最小值，平均值来看，umdaaa算法是一个逐步收敛过程，与理论分析相一致。

表2是umdaaa算法随机求解的tsp30城市问题的优化解分布。

目前公认的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城问题的一次随机求解过程。

从图中可以看出，在蚁群算法求解的过程中，算法的收敛性非常的明显，而在选择算子，概率模型算子，抽样算子的作用过程中迭代的次数较多。

那是因为前面算子的行为是为了积累更多的信息素，为算法的最后收敛作准备。

从图1可以看出，算法经过40多代就已经收敛，而且是单调收敛的。

表2umdaaa随机求解的30个优化解的分布tsp30城优化解值的分布（α=1，β=2，ρ=0.8，q=1 000）440427433447432429 442437429440452430431439428425434441427430443432438436431 4434254374334284结语智能混杂算法是当前智能优化算法的研究热点，可以融合多种优化算法的优势，提高算法的性能。

而算法的收敛性是算法最重要的指标之一。

齐次有限马尔科夫链是进行优化算法分析的有力工具，本文提出将umda与aa结合的umdaaa算法，并运用齐次有限马尔科夫链对其收敛性进行了分析。