论文研究-多样性保持的和声搜索算法及其TSP求解.pdf

所需积分/C币:16 2019-07-22 23:42:08 526KB .PDF
14
收藏 收藏
举报

为了改善和声记忆库群体多样性, 提高算法的全局寻优能力, 在度量群体多样性指标的基础上, 从参数动态调整方法、和声记忆库更新策略两个方面对基本和声搜索算法进行了改进, 提出了多样性保持的和声搜索算法, 并将该算法应用于TSP的求解。结合TSP问题特点, 设计了基于交换和插入算子的和声微调方法。实例优化结果表明, 改进后的算法不容易陷入局部最优, 优化性能显著提高。
第12期 黄鉴,等:多样性保持的和声搜索算法及其TSP求解 3585 其中;x为解向量Ⅹ中第k个解分量,x∈[1,n-h+1];nIHS算法。 表示TP中的城市数目;f(x")为目标函数值 2)新和声的生成 4结束语 根据和声记忆保留穊率,按照如下公式产生新解X 为了克服基本HS算法容易陷入局部最优的不足,提出了 DMHS算法。该算法通过改进参数动态调整方法、和声记忆库 HIS] random(0, 1)<HR 更新策略,提高和声记忆库群体的多样性,从而増强算法的全 x, c rand[l,n-i+1]否则 局寻优能力;通过对典型组合优化问题—TSP的求解,验证了 般情况下,S算法中的音调微调扰动方法按照如下公DMIS算法的优越性。下阶段还可以考虑将DMIS算法与其 式进行 他智能优化算法结合起来,设计更加高效的混合优化算法。 x,t rnd x bw random(0, 1)<PR 参考文献 否则 [1 GEEM Z W, KIM JH, LOGANATHAN G V. A new heuristic opti 其中:nd为均匀分布的随机整数,bw为音调调整带宽。 nization algorithm: harmony search[ J]. Simulation, 2001, 76(2) 对于IS优化问题,一般的音词微调方法不利于邻域解 的搜索。为了克服该问题,设计基于交换和插入算子的和声微[2]韩红燕,浴全科,染静改进的和声搜索算法在函数优化中的应用 调方法。具体方法如下: 「J1.计算机工程,2010,36(13):245-247 对于解向量ⅹ,设其解码后的向量为B"=(b,b2,…,[3】常虹,焦斌,顾辛生,自适应和声搜索算法及在数恒化化中的应用 [J].控制工程,2012,19(3):455-458 ba),随机产生两个整数ⅸ<j≤n及一个小数∈0,1]。若< [4]佥永强,苏伓智,李子阳.基于和声搜索的边坡瘾定性投影寻踪聚 0.5,交换b和b;否则,在向量B"中将解分量x插入到x 类分析[J].水利学报,2007(S1):682-686 之后,形成新的向量B",再将向量B编码即可获得微调后的「5]李亮,迟世春,林皋.改进和声溲索算法及其在土坡稳定分析中的 解向量Ⅹ。 应用[J.土木工程学报,2006,39(5):107-111 3)和声记忆库更新 [6』张风荣,潘全科,虎泶波,等,基于和卢退火算法的多维函数优化 釆取概率更新策略,具休步骤详见2.2节。 LJ」.计算机应月研究,2010,27(3):853-855,859 [7 GEEM Z W, KIMJ H, LOGANA TG V. Harmony search optimiza- 3.3实例 tion: application to pipe network design[ J. Intemational Journal of 为了验证改进和声溲索算法的优越性,以文献[l7]中30 Model Simulation, 2002, 22(2): 125-133 和50个城市的TSP为例,分别利用基HS算法、文献12提8KMJH, GEEMZ W,KMEs. Parameter estimation of the nonli near muskingum model using haRmony search[J]. Journal of the 出的IHS算法和本文提出的DMHS算法进行求解。参数设置 American Water Resources Association, 2001, 37(5): 1131 为:和声记忆库大小HMS=20,和声保留概率HR=0.95;音调 微调概率PR=03,其动态调整区间为0.1,0.7,算法最大迭[91 GEEM 7 W, LEEKS, PARK Y. Applicalion of harmony search lo 代次数为300000代。重复实验10次,获得的优化结果如表1 vehicle routing J|. American Journal of Applied Sciences, 2005 所示。 2(12):1552-1557 表1各算法优化TSP的计算结果 [10 LEE K S, GEEM Z W. A new meta-heuristic algorithm for continuous 30个城市TP 50个城市TsP 比较项目 HS DMHS IHS DMHS Computer Methods in Applied Mechanics and Engineering 平均值530.792526.020480.793659.187655.361593.327 2005.194(36-38):3902-3933 最小值482234447.468423.741581.683578.699523.960 L11 GEEM Z W. Optimal cost design of water distribution networks using harmony search[ J. Engineering Optimization, 2006, 38(3): 259 标准差90.588148.320116.541172.219139.381133.793 280 平均运行 21.26 37.75 [12 MAHDAVI M, FESANGHARY M, DAMANGIR E An improved har- mony search algorithm for solving optimization problems[ J 1. Applied 由表1可知,DMHS算法在优化过程中耗时相对于HS和 Mathematics and computation, 2007, 188(2): 1567-1579 HS算法略有增加,主要是由计算和声记忆库群休多样性引起[13] MAHDAVIM. Global-best harmony search[. Applied Mathema 的,其时间复杂度较小,完全可以接受,然而优化结果获得了显 tics and Computation, 2008, 198(2): 643-656 著改善。不同算法优化50个城市TP的收敛曲线详见图1。[4] FESANGHARYA M, MAHDAVIB M, JOLANDANC MM,etal.Hy 1600 bridizing harmony search algorithm with sequential quadratic program 1400 DMHS 图1000 in Applied Mechanics and Engineering, 2008, 197( 33-40): 3080 3091 [15]李军华,黎明,袁丽华.遗传算法求解TSP的种群多样性研究 [J].小型微型计算机系统 迭代次数/万代 [l6]王玉亭,孙剑,李俊青,等.顺序表示编码的和声退火混合算決求 图1不同算法优化50个城市TSP的收敛曲线 解TSP[J].微电子学与计算机,2010,27(10):41-49 由图1可知,DMHS算法具有更好的优化性能,不容易陷[17]王凌.智能先化算法及其应用[M,北京:清华大学出版社,2001 入局部最优。综合以上分析,DMHS算法明显优于基本HS和 193-195.

...展开详情
试读 3P 论文研究-多样性保持的和声搜索算法及其TSP求解.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-多样性保持的和声搜索算法及其TSP求解.pdf 16积分/C币 立即下载
1/3
论文研究-多样性保持的和声搜索算法及其TSP求解.pdf第1页

试读结束, 可继续阅读

16积分/C币 立即下载