结合蚁群算法和禁忌搜索算法的混合优化算法.pdf

所需积分/C币:29 2019-07-23 16:05:44 873KB .PDF
214
收藏 收藏
举报

针对元件的抓取路径规划问题,提出一种以最小化时间为目的,结合蚁群算法和禁忌搜索算法的混合优化算法。首先,将基于机器视觉抓取元件的问题确定为有约束的旅行商问题(TSP);然后,分析了元件大小和抓取放置过程对于路径规划的综合影响,对路径选择概率和禁忌域进行了适应性改进;其次,一方面引入了2-opt局部优化以及信息素惩罚、奖励机制以改善蚂蚁的搜索能力,另一方面对信息挥发因子作适应性改进以提高蚂蚁的自适应能力;最后,针对基本算法和改进的混合优化算法,仿真实验和平台实验分别进行了性能指标和抓取时间的对比分析。实验结果表明,仿真环境下,与蚁群优化( ACO)算法和禁忌搜索(TS)算法相比,混合优化算法的平均迭代次数降低了约50%,且其他性能较为优越,平台测试的抓取用时测试结果也说明了混合优化算法较随机结果和基本算法的优越性,可以快速完成元件抓取任务。   工业摄像机作为工业机器人的视觉传感器,是工业生产需要的柔性制造系统( Flexible Manufacture System, FMS)、自动化工厂( Factory Automation, FA)的重要环节,是实现“中国制造2025”的自动化工具。
第3期 杨继东等:基孑视觉抓取的并联桁架机器人最伊路径控制 915 (「r:、()r2(t)1)2·(「m(t)1「7:()1) 最优解作比较。前老较优,则需要增加该条路径的信总浓 2∑(n(z)()].(m(7n(1)),度,引4人i算子,吸引下一代更多的蚂蚁到该条路径上来, 提高其收敛速度,保证在有限的迭代次数里求出较优的初始 d∈ allot2∩ m e allowsise 解,更新信息素公式如下所示: 0, s s allouy∪ m s allousize (扌+1)=(1-p)()+△7;+△7 5) 其中;概率选取的过程是从抓取位置讠到放置位置(用t表 ∑△rn,△7= prize/min_ lenth 示),然后再从放置位置j再到下一个抓取位置这样的抓取、 蚁群同时可能陷入死路,失去全局最优解搜索能力,为了 放置、抓取过程为单次循环过程来进行概率选取。根据抓取元避免之后的蚁群再次陷入死路,对于迭代次数超过4次最短 件直径大小来选择放置位置( allows ize表示),然后返回下 路径仍然未更新的死路(路径长度 min lenth表示)进行信 个抓取位置(ao表示),如此改进可以有效避免单次选取带息素的弱,引入 punish算子,△ra公式如下所示: 来的陷入局部最优解。 ATrr = punish/min_Lenth 3.1.2禁忌域适应性的改进 prie为奖励系数, punish为惩罚系数,为设定的固定参 由丁研究问题是有约束的TsP,在禁忌域建立过程中,本数,prze大小影响收敛速度,puis大小影响全局最优解的寻 文建立交换允许表,在进行禁忌交换时加以利用。交换允许求能力。为了在有限的迭代次数甲,为禁忌搜索提供较好的初 表可以用ame表示如表1所示,它是一个二维表,第1始解,可以适当地增大 punis/t,减小Puih,提高收敛速度,全 行、第1列表示2个元件交换前的序号。 局最优解搜索能力佼靠禁忌搜索来改善。 表1交换允许表 Tab. 1 Allow swapping table -1-[+ 元件序号12 1+1i+ 000 000 0001 0 图32-qpt局部优化原理 11 0000 0001 0 000 000000 e-opt local optimization principle 0 3.23入信息挥发因子适应性优化 0000001 蚁群算法的信息素发挥因子p设定为固定值,如式(2)所 000001 00 示,p设定较小时会造成快速陷入局部最优解,失去全局搜索能 1700000000↓;p设定较大时会造成收敛速度过慢,降低工作效率因此,将p 00000001 设定为与蚁群算法迭代次数相适应的函数,如式(9)所示 行列节点交叉处的值表示禁忌交换时是否被允许。值为 “1”表示允许交换,值为“0”表示不允许交换。产生两个随机 1-c“,0.1≤p≤0.7 交换位置,根据位置对应的初始解的数值在交换允许表屮对 p<0.1 0.7 应的“0”“1”确定该组交英是含可以被接受,且当交换对应的 >0.7 初始解数值在区间[2-10时,各交换位置的后一位同时进其中:A为设定参数,NC为蚁群算法搜索的迭代次数,NCn 行交换。如初始解为(1-7-169-172-124-138-19-10-18-614- 为最大迭代次数,同时设定上下限为(0.7,0.1),使其值保持 5153111,如随机产生的交换位置为(2,0),对应的初始在一定的范围。起始时,择较大的信息素挥发因子,提高蚁 解的数值为7,10,在交换允许表的对应数值为“1”,允许交群算法搜索全局最优解的能力,动态改变p,使其随着迭代次 换,日对应的包始解的数值准冈间[2,0],因此初始解数值数的增加个断减小,提高其收敛速度,同吋算了过程中引人 16,18对应位置同时进行交换。 兀C~,提高算子自适应能力。 3.2蚁群算法优化 全此,对机器视觉抓取过程最优路径的规划所需要的实 3.2.12-opt局部优化 验平台,利用蚁群算法提高收敛速度同时为禁忌搜索提供较 将2引人群算法,对于蚂蚁所构建出的路径较短的优的初始解,通过祭忌搜索求解全局最优解,形成混合优化算 路径执行29pt算法来进行当前解的局部优化,这样既可以法,同时根据抓取路径的具体特点对混合优化算法进行适应 避兔算法陷入局部最优解,又能加快收敛,同时针对路径较优性改进。改进的混合优化算法流程如图4所示。 的前n2个解路径进行2局部优化,减少引入2-算法来4实验结果 引起的计算时间过长的现象过程大致如下:对于节选路径 i'、i+1、i+1、…、j、∫、j+1、疒+1,假设选定+1、j为交换 本文将实验结果分为仿真结果和平台实验仿真主要是 位置、区间内的路径进行抓取位置反向处理,放置位置跟随处论证本文论述的混合优化算法的实验效果,平台实验旨在说 理,如下、、沪…i+1、+1、j+、了+1,如图3所示。明该算法在机器视觉抓取过程实现最优路径的优化效果进 选取结果满足以下条件的较短路径,进行进一步改良。行整体方案验证。 l+ly+lz+…+l-nx-+l+1+l++1< 4.1仿真结果 lu,+vi+ +l+1+l+x+1 本文的仿真环境为 Window10系统下 Matlab R20l6b,主要 3.2.2引入信息素惩罚、奖励机制 是将本文得到的混合优化算法和蚁群算法禁忌搜索算法进行对 蚁群在每一次路径搜索完成时,都会产生一条当代全局比分析,从而测试改进算法的效果。位置设定如村关工作所描 最优解,用 min Lenth表示,同时这条最优解会和先前全局述,各参数根据经验和多次实验得到,初始值设定如表2所示。 916 计算机应用 第39卷 表2初始参数设定 绪束 Iab. 2 Initial paramctcr scttin 参数 值 初始化参数 出优解 蚂蚁个数m 对每只蚂蚁确定起始位 信息素重要程度因子a 置,随机选取下个抓取位置 <足终什原哪 启发素重要程度因子B 释放的信息素总量Q 依次判断抓管置元牛直随机交换当前解的两个位 径类型,概率选择放置位 奖系数 prize 置和卜·次机取位置 置产生交换解痈定候选解 怎罚系数pun 改进蚁群算法最大迭代次数NC 每只蚂蚊完成一次概率访闻 交换位 置对应当前解在交换 禁忌算法最大迭代次数NCm 100 选取前一半的蚂蚁 允许表? 在仿真环境下,选馭最短路径和平均路径因素,将改进的 进行20p局部优化 混合优化算法和蚁群算法、禁忌搜索算法进行刈比混合优化 重新对各个路径长度进 满藐视原则? 算法生成的途径图、最短路径和平均路径效果如图5所示 行计算,录当前最伏 混合优化算法的到的最优路径为:13-13-7-16-10-198 解和长度平均值 侯逵解繁忌表属性判浙 182-116-149-17-5154-12-1,最优路径长度为157991,月根 据最短路径对比图看出三种算法不同程度反映了其收敛能力 引入适应性信息素挥发孔将非禁忌装对象的最佳解作 为当前解,并用该对象替换先 和寻求全局最优路径能力,可以得到以下结论 前进入禁忌表的对象 )混合优化算法随着程序的执行,快速收敛,在迭代10 匚更新信息素 将满足藐視原则的最佳解作 次左右陷人死路,在30代左右,用死路作为禁忌搜索的初始 为当前解替换先前进入禁 解,加强全局搜索能力,在45代左右得到最优解。 代次数达到>[总表的对象夏新最优状态 2〕混合优化算汰相比蚁群算法牧敛速度明显提高,寻找 到的最短路径明显较优。 生最优解,剖始 化禁忌搜索算法 3)混合优化算法相比禁忌搜索算在30代左右收敛逗度提 图4改进的混合优化算法流程 高,之后经历10代左右达到最优解,收敛速度快,得到路径较优 4 Flow chart of improved hybrid optimization algorithm 混合优化算法优化路径 最算距离13219) 160 4 倉优化复法 混合优化算法 索算法 禁忌搜索算法 6 6Q9 蚁群算法 蚁群算法 起164 15 10815 兀件位置磺坐标 迭代次数 代次数 a}抓攻路径 (b)最短路径距离对比 (c)平均路径距离对比 图5几种算法仿真结果 Fir. 5 Simula 结合平均距离对比图可以验证以上说法,同时看出混合将该混合优化算法应用于机器视觉抓取元件寻求最优路径较 优化算法得到的路径距离的稳定性较优。 A(O、1S更优 将三种算法同时应用于本文研究的机器视觉抓取园形玻 表3彷真结果对比 璃元件问题,选取多组元件进行不同位置的抓取,每红进行 Tab. 3 Comparison of simulation results 20次测试测试结果如表3所示。 均达优平均 从表3中可以看出,改逃的蚁群算法结合禁忌搜索算法 距离算法平均解最优解标准差 月时/s迭代 的混合优化算法在抓取不同距离位置的儿件时均有更好的寻近距ACs158.0387157.910.06951125 优结果,且寻优结果和距离无关。同组比较,混合优化算法得离位ACO159.7532158.3410.14846.220078 到较优的最优解且稳定性较好,与ACO和rS相比,混合优化置组s158.82215799100.28980.894383 算法的平均迭代次数降低了约50%,且算法用时较短。禁总中距AC0941.93041191970.02521.161038 搜索算法虽然也可以达到相同的最优解,且算法用时较短,但离位ACO413.4665412.12290.12116.284088 是得到最优解的稳定性不足,收敛速度不足。蚁群算法得到 置组 TS412.5228411.91970.23400.7233 的最优解过早地收斂,全局洩索能力不足。综上仿真结果来远距 ACo-tS66.34896663260.02001.427340 看,混合优化算法寻优能力优于蚁群算法和禁忌搜索算法,且 离位ACO669.0034667.56820.09156.434981 寻优过程中与元件放置位置到码盘位置的距离无关,因此在 普组T67.589266.33260.17540.852490 第3期 杨继东等:基孑视觉抓取的并联桁架机器人最伊路径控制 917 4.2平台实验 ZHANG D M, YANG J Q, et al. Ant colony optimization algorithm 将 Matlab生成的混合优化算法封装成函数供visu Studio2013调用,做平台抓取实验。抓取起始点定义在光源 (8):1658-1663 中心点,在对现有抓取起始点,元件抓取点以及码盘放置点进5]陈丹,白军,石国良.一科新的四自由度 SCARA机器人手眼标定 行1~19依次排序,得钊路径为1-8-19-2-113-124-13-7-16 方法J传感器与微系统:2018,37(2):72-75.( CHEN D,BAI 10-18-9-17-5-146-15-1,完成全部抓取所需要的时问为 J, SHI I. A new mel hud of four DOF SCARA robot hHnd-eye cali bration [J]. Transducer arid Microsystem Technologies, 2018, 37 20.23s,样机取放结果如图6所示。 (2):72-75.) 6]高海昌,冯博琴,朱利智能优化算法求解TP问题[J.控制与 是 决策,2006,21(3):241-247.(GA0HC, FENG B Q,ZHUL Reviews of the meta-heuristic algorithms for TSP I J]. Control and Decision,2006,21(3):241-247 7]吴斌史忠樘.一种基丁蚁群算法的TSP问题分段求解算法[J 计算机学报,201,24(12):1328-133.(WB,HH7.A arl.t ry algoriThm h:dstl parlin ior algorillim fsr TSP [J]. Chinese Joumal of Computers, 2001, 24(12): 1328-1333 t12 [8] MULLEN R J, MONEKOSSQ)D, BARMAN S, Hl. al. A Irv iew uf 图6样机取放结果 anl. algurilhI N J]. Experl Syslells wilh Applic a i N, 2009, 36 Fig. 6 g llt of protot pI 9]吴庆洪,张额,马宗民.蚁群算法综述[.徵计算机信息,2011 冋时保持起始点放置位置不变,选取三组较放置位置不 27(9): 1-2.(WUQH, ZHANGY, MAZM. Review of ant. colo 同距离的元件进行对比,同样做三种算法的对比实验,每种进 ny optimization [ J. Microcomputer Information, 2011, 27(9):1 打10组,取抓取时间的平均值,得到结果如表4所示。 表4不同算法样机抓取时间平均值对比 10 CIORNEI I, KYRIAKIDES E. Ilybrid ant clouy-genetic algorithm Tah. 4 Average grasping lime t'xarison (f pmIl ype: by GAAPD) for global continuous optimization [J. IEEE Transac different algorithms tions on SYstems, Man, and Cybernetics. Part B, Cybernetics 岀离随机路径蚁群算法禁忌搜索算法混合优化算法 2012.2(1):234-245 中距离(本组)21.3423.61 20.98 1r出,魏云霞,薛宏全等,基于优胜劣汰规则的异类多种群蚁 近距离 18,6519.11 17,68 17.08 群算法[J计算机「程201,38(18):182-185.( ZHANG P 远距离25.3226.4324.21 23.56 WEIYX, XUE H Q, et al. Heterogeneous multiple colonies ant lony algorithm based on survival of fittest rules [J]. Computer 由距离组之间的对比实验可以看出,距离对于各种算法 Engineering.2012,38(18):182-185.) 影响差异不大,说明寻优结果与距离无关,验证仿真头验的结[121王凌智能优化算法及其应用M]北京:清华大学出版社 果。算法之问的对比可知,随机路径的用时要优于暾群算法, 2001: 67-68.(WANG L. Intelligent Optimization Agorithm and 其原因在于蚁群算法身耗时较路径优化节省的时间更长。 Its Application [M]. Beijing: Tsinghua University Press, 2001 混合优化算法较蚁群算法和禁忌搜索算法抓取用时更短,且 与随机路径相比,混合优化算法平均耗时缩短了6.68%。 3]刘以,贺国光牟辆路径问题的禁忌搜索算法研允[J.计算机 工程与应用2007,43(241;179-181,(LUX,HEGG, Study 5结语 on tabu acarch algorithm for stochastic vchiclc routing problemI JI Computer Engineering and Application, 2007, 43(24 ): 179 本研究基于杌器视觉定位元件,将元件抓取、放置过程转 换为有约束的TsP,通过仿真结果和平台实验表明结合蚁群141彭茂.一种求解TP问题的改进禁忌搜萦算法[J计算技术与 优化算法和禁忌搜索算法的混合优化算法在机器视觉定位抓 自动化,2012,31(1):78-81.( PENG M. Improved labu search 取、放置的过程中,较随札抓取、蚁群算法和禁忌搜索算法来 algorithm for solving traveling salesman problem J]. Computing 讲,抓取路径得以优化,抓取效率有效提高。 Technology and Automation, 2012, 31(1 ): 78-81. 参考文献( References [15]张勇.基于改进蚁群算法物流配送路径优化的研究J.控制 L1]李尧,石红瑞.基于图像认别和遗传算法的ipod机器人最优轨 FL, 2015, 22(2): 252-25(ZHANG Y. Study of optimizing logis- 迹控制[J.计算机应用,2016,36(S1):106-109.(LIY,SHIH tic distribution routing based on improved ant colony algorithm JI of china,,2015,22(2):252 ug ilion anll gaelic: algorithm [J]. Journal of Couler Applic: a Is,2016,36S1):100-109.) This work is partially supported by the National Natural Science Foun- [2] DORIGO M, GAMBARDELLA M L. Ant colonies for the: travelling dation of China(51375507) salesman problem [J]. Biosystems, 1997, 43 (2): 73-8 [3]叶小勇,雷勇,侯海军蚁群算法在全局最优路径寻优中的应用 YANG Jidong, born in 1966, M. S, associate professor. His re- [J.系统仿真学报,2007,19(24):5643-5647.(YEXY, LEI seurch interests include mechatronics desig, intelligent manufacturing and Y, HOU H J. Application of ant colony algorithm in global optim path searching I J]. Joumal of System Simulation, 2007, 19(24): SUN Zhaoyi, born in 1992, M. S. candidate. His research interests 5643-5647.) include automated control, machine vision, intelligent algorith [4]张慕雪,张达敏,饧菊靖,等.基于禁忌搜索的蚊群算法优化算法 WANG Fellong bom in 1994, M.S. candidate. His research in 「J.通信技术.20178,50(8):1658-1663.( ZHANG M X, terests include automated control, mechatronics desig

...展开详情
试读 5P 结合蚁群算法和禁忌搜索算法的混合优化算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
结合蚁群算法和禁忌搜索算法的混合优化算法.pdf 29积分/C币 立即下载
1/5
结合蚁群算法和禁忌搜索算法的混合优化算法.pdf第1页

试读结束, 可继续读1页

29积分/C币 立即下载