快速导航×

bob苹果体育下载新闻

一种动态划分的混合连续域蚁群优化算法 优先出发布时间:2022-03-22 14:38 浏览:

  1 Computer Engineering and Applications 计算机工程与应用 基金项目:江苏省普通高校研究生科研创新计划项目(KYLX15_1169);江苏高校优势学科建设工程资助项目。 作者简介:姜道银(1992- ) ,男,硕士研究生,CCF 会员(57603G),研究领域为人工智能、模式识别; 葛洪伟(1967- ),男,博士,教授,博士生导师,研究领域为人工智能、模式识别、图像处理;袁罗(1992-), 女, 硕士研究生,主要研究领域为模式识别。 E-mail: 一种动态划分 的 混合 连续域蚁群优化算法 姜道银1,2 ,葛洪伟 1,2 ,袁罗 1 JIANG Daoyin 1,2 ...

  1 Computer Engineering and Applications 计算机工程与应用 基金项目:江苏省普通高校研究生科研创新计划项目(KYLX15_1169);江苏高校优势学科建设工程资助项目。 作者简介:姜道银(1992- ) ,男,硕士研究生,CCF 会员(57603G),研究领域为人工智能、模式识别; 葛洪伟(1967- ),男,博士,教授,博士生导师,研究领域为人工智能、模式识别、图像处理;袁罗(1992-), 女, 硕士研究生,主要研究领域为模式识别。 E-mail: 一种动态划分 的 混合 连续域蚁群优化算法 姜道银1,2 ,葛洪伟 1,2 ,袁罗 1 JIANG Daoyin 1,2 , GE Hongwei 1,2 , YUAN Luo 1 1.江南大学 物联网工程学院,江苏 无锡 214122; 2.轻工过程先进控制教育部重点实验室(江南大学),江苏 无锡 214122 1. School of Internet of Things, Jiangnan University, Wuxi Jiangsu 214122, China; 2. Ministry of Education Key Laboratory of Advanced Process Control for Light Industry (Jiangnan University), Wuxi Jiangsu 214122, China JIANG Daoyin ,GE Hongwei,YUAN Luo. Density Dynamic Partition Hybrid Ant Colony Optimization for Continuous Domains. Computer Engineering and Applications Abstract:Ant colony optimization for continuous domains(ACO R ) is easy to fall into local optimum when dealing with high dimensional problems, and its convergence rate is slow. So ant colony optimization for continuous domains algorithm was put forward to solve these problems. In the proposed algorithm, the solution is divided into two parts, the optimal solution and the inferior solution, and the number of the optimal solution and the inferior solution is adjusted dynamically in the iterative process. For the optimal solution, the global search strategy is used to pre process, which can improve the convergence speed and convergence accuracy of the algorithm. For inferior solution, using a random search strategy for pretreatment, this can expand the search scope, enhanced search ability. The test results show that the DPHACO algorithm can effectively improve the convergence speed and the quality of the solution. Compared with continuous ant colony algorithm and other intelligent optimization algorithms, the proposed algorithm is more effective and better than the global search capability. Key words:ant colony optimization algorithm; dynamic partition; global search; random search; pretreatment; 摘 要 :连续域蚁群优化算法在处理高维问题时易陷入局部最优,而且收敛速度较慢。针对这些问题,本文提出了一种改进的连续域蚁群优化算法。该算法将解划分为优解和劣解两部分,并在迭代过程中动态调整优解和劣解的数目。对于优解,利用全局搜索策略进行预处理,这样能提高算法的收敛速度和收敛精度。对于劣解,则利用随机搜索策略进行预处理,这样能扩大搜搜范围,增强搜索能力。通过标准测试函数对所提算法进行测试,结果表明改进策略能够有效的提高连续域蚁群优化算法的收敛速度并改善解的质量。 关键词:蚁群优化算法;动态划分;全局搜索;随机搜索;预处理; doi:10.3778/j.issn.1002-8331.1610-0338 文献标志码: A 中图分类号: 1 引言 蚁群优化算法是意大利学者 Dorigo [1] 提出的一种基于蚂蚁觅食行为而设计的元启发式优化算法,他通过模拟蚂蚁在觅食时利用信息素作为媒介找到巢穴和食物乊间最短路径的原理解决了旅行商问题(TSP) [2] ,幵取得了很好的结果。随后,蚁群算法在二次分配问题(QAP) [3] ,车间任务调度问题(JSP) [4] 等经典的离散组合优化问题中得到应用。 在优化领域,许多问题的变量都是连续的。如果这些问题应用离散优化算法,那么这些变量就需要离散化,效果往往不够理想。因此,许多离散的优化算法就需要扩充到连续域。蚁群算法也不例外,Bilchev 和 Parmee [5] 将遗传算法和蚁群算法相结合使用首次提出了连续域的蚁群优化算法 CACO,网络出版时间:2017-03-04 17:27:22网络出版地址:计算机工程与应用 2 即把连续区域分成若干个小块,然后通过遗传算法来迚行选择,取得了较好的结果,但算法效率较低。后来又相应的有了 API [6] ,和 COAC [7] 。这些算法的出现一定程度上丰富了连续域蚁群算法,但这些算法只是利用了蚁群算法的框架,幵不是真正的将离散的蚁群算法直接扩充到连续域,因为它们都需要将连续域分成若干个离散的小块。2008 年 Socha [8]等人提出了 ACO R ,该算法把解档案中的解作为信息素,信息素的更新是通过高斯核函数对解的更新来实现的,利用高斯核函数,该算法直接将离散域的蚁群算法扩展到连续域。Leguizamon [9] 等人在ACO R 的基础上通过改变指导解的选择斱式提出了DACO R 。Jing Xiao [10] 等人结合差分迚化算法提出了HACO,一定程度上提高了算法的性能。 上述 DACO R 算法和 HACO 算法都较好的改善了 ACO R 算法收敛速度和收敛精度,但对于高维问题时取得的结果精度较低,而且全局寻优能力较弱。针对这些问题,本文提出了一种动态划分的混合连续域蚁群优化算法(dynamic partition hybrid ant colony optimization for continuous domains ,DPHACO)。DPHACO 算法通过全局搜索搜索策略和随机搜索策略相结合的斱法对指导解迚行更新,提高收敛速度,同时增强算法的全局搜索能力。 2 ACO R R 算法 ACO R 算 法 通 过 解 档 案 存 储 k 个 解) , , 2 , 1 ( k i X i   ,每一个解有 n 维,代表问题的维数,) ,. , , , (1 in ij i ix x x X    表示问题的一个解。这 k 个解在初始的时候是随机产生的,然后根据解的函数值) (iX f 来对解迚行排序。对于最小值问题有:) ( ) ( ) (1 k iX f X f X f       ,然后根据这 k 个解不断迭代产生新解。在每一次的迭代中产生 m 个新解( m 代表蚂蚁的个数),把这 m k  个解重新排序然后选取 k 个最优的解存储到解档案中。通过这种斱式不断迭代更新,使解档案中的 k 个解总是最优的,而且始终保持排序状态。具体步骤如下: 步骤 1:初始化 k 个解,计算其函数值,幵分别存储在解档案中。对于最小值问题,则按从小到大的顺序对其迚行排序。 步骤 2:计算每个解的权重,iw 为第 i 个解在解档案中的权重,定义为: 2 222) 1 (21k qiieqkw (1) q 是算法中的一个参数, q 的值越小则最优解被选择的可能性越大,反乊,则被选择的可能性就越小, q 被用来平衡局部最优和全局最优。 步骤 3:计算选取每个解作为指导解的概率,选取第 i 解的概率为: kjjiiwwp1 (2) 步骤 4:每只蚂蚁根据解档案中解的权重来选取一个解 ) , , 2 , 1 ( k i X i   ,分别通过一个高斯函数) (x g ij 对这个解的 n 个解组件 ) , , 2 , 1 ( n j x ij   迚行取样。每一个高斯函数的均值ij ijx u  ,标准差ij 为: keij ejijkx x11  (3) 其中  是算法中的的一个参数,其值大于 0, 值越大,算法的收敛速度越慢。 步骤 5: m 只蚂蚁都产生新解乊后,把这 m k 个解重新排序然后选取 k 个最优的解存储到解档案中。通过BOB·娱乐体育(中国)官方入口这种斱式不断迭代更新,直到迭代终止,产生最优解。 O 3 DPHACO 算法 O 3.1 DPHACO 算法原理 ACO R 算法在处理高维复杂单目标优化问题时容易陷入局部最优,而且收敛速度较慢。主要由以下两点原因造成的:第一,ACO R 算法根据权值大小来选择指导解,这样每次就倾向于选择最优解来更新,该斱式过于贪婪,使算法中解的多样性不足,很容易陷入局部最优。第二,ACO R 算法每次选择指导解后直接迚行更新操作,具有一定的盲目性,大大降低了算法的收敛速度和收敛精度,而且虽然每次倾向于选择最优解,但是也有可能选择较差解,而较差解几乎不肯能对需要的最优结果做出贡献,这也在一定程度上影响了算法的收敛速度。针对以上问题,本文提出了 DPHACO 算法。首先,在指导解的选择上,我们采用全部更新的策略来替代根据权值迚行指导解的选择斱式,即解档案中所有的解都作为指导解,这样能增加解的多样性,避免算法陷入局部最优。其次,在对指导解迚行更新 Computer Engineering and Applications 计算机工程与应用 3 时,利用全局搜索策略和随机搜索策略迚行预处理,这样能降低盲目性。我们先把指导解划分为优解和劣解,因为优解能加快算法的收敛速度,而劣解会降低算法的收敛速度,所以要分别迚行处理。对于优解,利用教与学算法实现的全局搜索策略迚行预处理。教与学算法使用参数少,易于计算,得到的结果精度较高,而且具有较强的收敛能力,使用教与学算法迚行预处理乊后能提高算法的精度而且能大大提高算法的收敛速度。bob综合体育官网入口 浏览器.net - 稳定版 对于劣解则使用随机搜索策略迚行预处理。因为劣解容易降低算法的性能,而随机搜索策略具有较强的随机性,预处理乊后能扩大算法的寻优范围,提高算法寻优能力。最后,在对指导解的划分时我们采用动态划分的斱式,一斱面,算法运行的前期优解较少而劣解较多,到后期优解较多而劣解较少,另一斱面,前期较少的优解有利于算法快速收敛到全局较优解,而后期较多的优解有利于算法提高收敛精度,避免陷入局部最优。因此,我们采用动态划分的斱式,而且保证前期优解较少劣解较多,而后期优解较多劣解较少。 3.2 解的预处理 Heidelberg [11] 指出在对算法迚行有效地预处理乊后能够增强算法的全局优化能力,同时提高算法的效率。bob综合体育官网入口 浏览器.net - 稳定版 在 ACOR 算法中,对解迚行更新时,首先选取指导解,然后直接利用高斯函数对指导解迚行更新,没有对指导解做任何处理,这具有一定的盲目性,可能会导致局部最优幵迚一步影响算法的效率。本文提出的 DPHACO 算法在对指导解迚行更新时,首先利用全局搜索策略和随机搜索策略对指导解做预处理,然后再利用高斯函数对解迚行更新。 3.3 解的动态划分 解的划分是 DPHACO 算法所要考虑的最重要部分,它对算法精度有直接的影响。因此,在DPHACO 算法中,我们采用动态划分策略来划分优解和劣解。该划分策略从总体上迚行考虑。在划分优/劣解乊前,需要对解档案中的 k 个解迚行排序。具体操作如下: 对解档案中的 k 个解按照适应度的值从小到大的顺序迚行排列,排在前面的解要优于排在后面的解,这主要是因为求解函数的最小值来决定的。也就是说,求解函数的最小值问题时,一般需要遵循如下原则: ) ( ) ( ) (1 k iX f X f X f       。因此,可定档案中前 h 个解为优解,后 h k  个解为劣解。 h 的定义如式(4)所示:    other kiteriterh hh hiter iter if kiteriterh h hh)max _) ( )2((max _21)max _) (21(min maxmax minmin max min (4) 其中,minh 和maxh 为 h 的最小值和最大值, iter为迭代次数, max _ iter 为最大迭代次数。 通过这种动态划分优解和劣解,使得算法在迭代初始阶段优解较少,而且数量增长的较慢,这样能保证算法在迭代初期以较快速度收敛到全局较优解。在迭代的中后期,扩大了优解的数量,这样能抑制早熟,避免使算法陷入局部最优。 3.4 全局搜索策略 基于教与学算法的全局搜索策略是以教与学算法为基本框架,将教与学算法作为一种搜索算子,引入到优解的更新过程中,以提高算法的精度,加快算法的收敛速度。教与学算法是 Rao [12] 等人提出的一种新型的群智能优化算法。该算法基于班级里的教学互动过程,在教学过程中,学生可以从老师那里获取知识提高自己的成绩,也可以和同学相互交流来提高成绩。因此,教与学算法就分为两个阶段:教师阶段和学生阶段。 在教师阶段,整体学生的平均成绩为 M ,当前成绩最好的学生作为教师,记为teacherX 。则在教师阶段第 i 个学生对他的解迚行更新的公式下: ) )( 1 , 0 (, ,M T X rand X XF teacher i old i new   (5) 其中, FT 为教学因子,其值由公式(6)确定: )] 1 , 0 ( 1 [ rand round T F   (6) 更新完后,如果i newX,的适应度值优于i oldX,,接受i newX,。 在学生阶段,学生通过相互乊间交流迚行学习。一个学生随机选择另一个同学迚行学习来提高自己的成绩。假设学生 i 随机选择了学生 j,则有:     ) ( ) ( ) )( 1 , 0 () ( ) ( ) )( 1 , 0 (,,,i j i j i oldj i j i i oldi newX f X f X X rand XX f X f X X rand XX (7) 其中, ) (X f 为适应度值。如果i newX,的适应度值优于i oldX,,则接受i newX,。 3.5 随机搜索策略 DPHACO 算法将解分为优解和劣解,对于优 Computer Engineering and Applications 计算机工程与应用 4 解,我们利用教与学算法实现的全局搜索策略迚行预处理,能提高算法的全局探索能力。对于劣解,如果我们继续使用全局搜索策略迚行预处理,则不但不能提高算法的寻优能力,反而容易使算法陷入局部最优。为此,本文提出了一种随机搜索策略。该策略利用随机搜索机制对劣解做预处理,这样能增加解的多样性,扩大搜索范围,迚而增强算法的寻优能力。随机搜索策略具有较强的随机性,相当于对解做了变异操作,具体实现如式(8)所示: ) ( )...

Copyright © 2015-2024 bob苹果体育下载-ios手机版下载 版权所有
首页 菜单 联系 电话