单变量边缘分布算法与蚁群算法的混合算法收敛性分析
作者：黄情操余达祥
来源：《现代电子技术》2012年第06期
摘要：智能混杂算法是当前智能优化算法的研究热点，可以融合多种优化算法的优势，提高算法的性能。单变量边缘分布算法具有大范围快速全局搜索能力，但不能很好地利用系统中的反馈信息；蚁群算法是一种并行的分布式正反馈系统算法，但其初期信息素匮乏，求解速度慢。将单变量边缘分布算法与蚁群算法相结合，可以优势互补。基于上述思想，提出一种基于单变量边缘分布算法与蚁群算法混合的算法，并运用马尔科夫随机过程理论对该算法的收敛性进行了分析，结果表明了该算法的优化解满意值序列是单调不增的和收敛的。
关键词：单变量边缘分布算法；蚁群算法；收敛性；智能混杂算法
中图分类号：文献标识码：A文章编号：
convergence analysis of the hybrid algorithm with UMDA and AA
ng
(College of Information and Engineering, Nanchang Hangkong University, Nanchang 330063, China)
Abstract： The intelligent hybrid algorithm is a current research focus of intelligent optimization algorithms. It can fuse the advantages of many kinds of optimization algorithms to improve performance of the algorithm. The univariate edge distribution algorithm (UMDA) has widespread rapid global search capability, but can not use the feedback information in the systemquite well. The ant algorithm (AA) is a kind of parallel distributed positive feedback system algorithm, but its initial pheromone is lack and its solving speed is slow. The combination of UMDA and AA can complement each other′s advantages. Based on the idea mentioned above, a hyb rid algorithm based on UMDA and AA is proposed in this paper, and the convergence of the hybrid algorithm is analyzed with Markov random process theory. The result indicates that the optimal solution satisfaction value sequence is
onvergent.
Keywords： univariate marginal distribution algorithm; ant algorithm; convergence; intelligent hybrid algorithm
收稿日期：
基金项目：国家自然科学基金项目（60963002）单变量边缘分布算法由德国学者Miihlenbein在1996年提出［］，是一类基于概率模型的进化算法。与传统的进化计算算法不同，它不需要使用交叉和变异算子，而是根据当前种群的概率分布来产生下一代，并建立其概率分布模型，然后利用所建的分布模型产生新的个体，以形成下一代种群。如此迭代，直到满足终止条件为止。蚁群算法［2］最早是由Dorigo及其研究同伴所提出［］。是一种并行的分布式正反馈系统算法，但其初期信息素匮乏，求解速度慢。本文将两种算法结合，并运用马尔科夫链对其收敛性进行分析，分析结果表明新算法是一定收敛的。
1单变量边缘分布算法与蚁群算法混合的思路与方法
1.1单变量边缘分布算法与其群算法混合的思路描述
单变量边缘分布算法［1］具有大范围快速全局搜索能力，但当求解到一定范围时往往对系统中的反馈信息利用不够，求精确解效率低。蚁群算法［2］主要通过蚁群之间的信息素的传递和更新达到最终收敛的最短路径上，其原理是一种正反馈机制，但初期信息素匮乏，求解速度比较慢。单变量边缘分布算法与蚁群算法的结合(UMDAAA)正是基于单变量边缘分布算法的快速全局搜索能力和蚂蚁算法的正反馈收敛机制，初期采用单变量边缘分布算法过程生成信息素分布，后期利用蚂蚁算法正反馈求精确解，优势互补。
1.2UMDAAA中对蚁群算法模型的选择与改进
UMDAAA中对蚁群算法选择基于蚂蚁圈模型和算法［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) 进行选择操作，选择N
(4) 由优势群体DSl构建概率模型，估计联合概率分布:pl(x)=p(x|DSl)=∏ni=1pl(xi)=
∏ni=1∑Nj=1δj(Xi=xi|DSl)N式中：n为问题维数(变量个数)；δj(Xi=xi|DSl)=1,Xi=xi