文档介绍：单变量边缘分布算法与蚁群算法的混合算法收敛性分析
摘要:智能混杂算法是当前智能优化算法的研究热点,可以融合多种优化算法的优势,提高算法的性能。单变量边缘分布算法具有大范围快速全局搜索能力,但不能很好地利用系统中的反馈信息;蚁群算法是一种并行的分布式正反馈系统算法,但其初期信息素匮乏,求解速度慢。将单变量边缘分布算法与蚁群算法相结合,可以优势互补。基于上述思想,提出一种基于单变量边缘分布算法与蚁群算法混合的算法,并运用马尔科夫随机过程理论对该算法的收敛性进行了分析,结果表明了该算法的优化解满意值序列是单调不增的和收敛的。
关键词:单变量边缘分布算法; 蚁群算法; 收敛性; 智能混杂算法
1单变量边缘分布算法与蚁群算法混合的思路与方法
单变量边缘分布算法[1]具有大范围快速全局搜索能力,但当求解到一定范围时往往对系统中的反馈信息利用不够,求精确解效率低。蚁群算法[2]主要通过蚁群之间的信息素的传递和更新达到最终收敛的最短路径上,其原理是一种正反馈机制,但初期信息素匮乏,求解速度比较慢。单变量边缘分布算法与蚁群算法的结合(umdaaa)正是基于单变量边缘分布算法的快速全局搜索能力和蚂蚁算法的正反馈收敛机制,初期采用单变量边缘分布算法过程生成信息素分布,后期利用蚂蚁算法正反馈求精确解,优势互补。
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) 随机产生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)