论文研究-求解多目标最小生成树的改进多目标蚁群算法.pdf

所需积分/C币:16 2019-07-22 21:18:14 316KB .PDF
47
收藏 收藏
举报

多目标最小生成树问题是典型的NP问题。针对此问题,提出一种改进的多目标蚁群算法。为获得更好的非劣前端,通过合理选取多个信息素扩散源与扩散策略来避免其早熟收敛,并引入非支配排序算子,提高种群多样性并避免算法过早陷入局部最优解。对比实验结果表明:对于多目标最小生成树问题,该算法是有效的,不但在求解效率和解的质量方面优于相关算法,而且随着问题规模的扩大,算法仍保持较好的性能。
476 计算机应用研究 elei(q<p)then如果p被q文配 法的表现还是很不错.可以看出本文算法更加适合于求解复杂 1n,加1 多维问题 [(I=0)then F1←F1U{pp是第一等级中的解 由以上实验与分析可以得出,本文算法的有效解体现了较 明显的优势,在多目标最小生成数中取得了很好的效果,性能 hile F/=2 改进显著 H← for each p∈F对于F中的每个解 5结束语 for each o∈S,更改sn中每个成员的n。减1 n← 网络优化、道路设计等许多问题都需要计算最小生成 in4=0 then H+-HUgl如果n为0,将q并人H 树,在实际应用中优化的目标往往相互冲突,这就是多日标 F←H将H中的解赋给F 优化问题。本文提出一种改进的多目标蚁群算法,为获得更 3)算法基本流程 好的非劣前端,通过合理选取多个信息素扩散源与扩散策略 本文改进算法( RMACA)的基本流程如下: 来避免其早熟收敛,并引人非支配排序算子,提高种群多样 RMACA 性并避免算法过早陷人局部最优解。对比实验结果表明:对 于多目标最小生成树问题,该算法是有效的,不但在求解效 =0; 种群p(t)初始化及参数初始化 率和解的质量方面都优于相关算法,而且随着问题规模的扩 选择产生m个信息素扩散源中心点,并初始化所有大,算法仍保持较好的性能。该算法能够求出问题的许多 个体的信息素; Pareto最优解集,为决策者提供了多个可供选择的解,因而是 实用的 whie(不满足结束条件) t:=t+1 参考文献 a)依据信息素与适应值,从父种群p(t-1)选择个体,执行交叉 [1]陈囯龙,郭文忠,涂雪珠,等.求解多目标晸小生成树问题的改进 变异操作产生种群p(t); 算法[J].软件学报,2006,17(3):364-37 h)从p(t-1)中的信息素扩散源中心点和p(t)中选新的m个信 [2]郭文忠,陈国龙。一种解多日标最∴生成树问题的有效离散粒 怠素扩散源中心点,并根据信息素产生公式,更新源中心点的信息素 子群优化算法「J].模式识別与人工智能,2009,22(4):597-604 c)根据信息素扩散公式,更新种群中求属于各信息素扩散源的个[3] ZHOU Gen-gui,CENM. Genetic algorithm approach on multi-crite 体的信息素; ria minimum spanning tree problem J]. European Journal of end of while Operational Research, 1999, 114(1): 141-152 [4]余荣祖,王唯良,冰。求解多目标最小生成树的一种新的遗传 算法[J].计算机工程与应用,2009,45(16):48-49,65 4实验结果与分析 [5]李密青,郑金华,罗彪.一种基于最小生成树的多月标进化算法 [J].计算机研究与发展,2009,46(5):803-813 在不文的数值实验屮,采用随机生成的顶点数分别为20 L6」段海滨,王道波,于秀芬,蚁群算法的研究进展评述J」.然杂 30、50的三个完全图分别作为实验问题的网络,网络中每条边 忐,2006,28(2):102-105 有两个权重。权重随机产生,分别在[0,50]和[0,1001]上服[7]谢涛,陈火旺,康立山,多目标优化的演化算法[J.计算机学 从均匀分布。实验环境如下:CPU为P41.7GH;内存大小为 报,2003,26(8):997-1003 256MB;操作系统为 Windows XP;编程语言为C;编码方式为[8] ZoU Xiu-fen, YU Chen, LIU Ming-zhong,eta. A new evolutionary 实数编码。算法的参数取值为:种群规模N=200,交叉概率为 algorithm for solving many-cbjective optimization problems J. IEEE 0.98,变异概率为0.05。图1和2为规模是20与50的运行 Trans on Systems, Man and Cybernetics, Part B, 2008, 38(5) 100代后非支配解的分布情况。 1402-1412 [9]公茂果,焦李成,杨咚咚,等,进化多目标优化箕法研究[J].软 1.89 件学报,2009,20(2):271-289 1.88 「10张勇德,黄莎白.多目标优化问题的蚁群算法研究「J,控制与决 :170-173,17 1.85 1.84 11]益君,陈德钊,用于多日标优化的蚁群算法的构建及其应用[冂] 高技人通讯,2006,16(12):12 1.8 751.771.791.81.83.85 2.542.582.622.662.7 [12]池元成,蔡囯飙.基于蚁群算法的多日标优化[J.计算机工程 图1进化100代时的 Pareto 图2进化100代时的 Pareto 2009,35(15):168-169,172 最优解集(规模是20个顶点) 最优解集(规模是50个顶点 [13]李密青,郑金华,伍军.一种新的分布性保持方法[J].控创理论 图1、2给出了三种算法分别运行100代后非支配解的分 与应用,2009,26(8):843-849 布情况。从图中可以看出, RMACA比QMEA和NA-1的搜141李窗青,全华,肖柱霞,一种多目标进化算法的分布度评价方法 索空间更广阔找到的解质量更好,这表明采用改进的多目标 [冂].模式识别与人工智能,208,21(5):695-703. 蚁群优化算法是有发展前景的;同时也证明本文采用的信息素 [15 DORIGO M. Optimization, learning and natural algorithms[D]. Ita- 策略是成功的,在避免算法陷入局部最优、防止早熟上是有效 ly: Department of Electronics, Politecnico di Milano, 1992 [16 DORIGO M, MANIEZZO V, COLOMI A. The anl syslem: uplinizi 的。本文算法将仝局搜索与局部搜索很好地进行结合,仝局搜 tion by a colony of cooperating agents J. IEEE Trans on Sys 索则有助于进化方向朝着 Pareto最优前端进行,局部搜索能够 tems, Man, and Cybernetics, Part B, 1996, 26(1): 29-4 趔测到未知区域中更多的可行解,从而维持解的多样性,使得171朱庆保蚁群优化算法的收敛性分析「J.控制与决策,2006,21 算法快速有效地收敛。同时,随着问题复杂度的增加,本文算 (7):763-766

...展开详情
试读 3P 论文研究-求解多目标最小生成树的改进多目标蚁群算法.pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-求解多目标最小生成树的改进多目标蚁群算法.pdf 16积分/C币 立即下载
1/3
论文研究-求解多目标最小生成树的改进多目标蚁群算法.pdf第1页

试读结束, 可继续阅读

16积分/C币 立即下载