求解机器人路径规划的智能优化算法

智能优化算法

专毫讨论

赵敏等:一种求解机器人路径规划的智能优化算法

第4期

求高,对批量化焊接生产有高品质的要求,对焊接过程有高节拍、高效率的要求。

在焊接机器人工作过程中,焊枪从原始位置出发,途经各个焊点,最终回到原始位置,完成一个工作循环。这与旅行商问题(TSP:Travel

Sale

Problem)

的数学模型非常类似,因此,可以将问题转化成TSP的数学模型,并使用相应智能优化算法焊接路径。旅行商问题(TSP)是一个经典的组合优化问题li-21,问题要求求得一条遍历所有城市的最短回路,属于NP难问题。随着城市数目增多,无法在有限时间内用常规方法求解。随着人们对生物进化现象的研究,提出了许多用于解决复杂的组合优化问题仿生进化算法。20世纪90年代,意大利学者Dorigo等人受自然界真实蚁群集体寻径的启发,提出了蚁群算法131,成功解决了TSP问题和其他许多组合优化问题。该算法不依赖于具体问题的数学描述,具有全局优化能力和本质上的并行性,具备更强的鲁棒性、求解时间短、易于计算机实现等优点闭,特别适合于在离散优化问题的解空间进行多点非确定性搜索,因此被广泛用于求解组合优化问题【4】。

2蚁群算法求解TSP问题

自然界中的蚂蚁总是能发现巢穴到食物源的最短路径。经过生物学家研究,发现蚂蚁之间是通过一种称为信息素(pheromone)的化学物质来互相通信,并互相影响。蚂蚁从巢穴出发寻找食物,找到食物后沿原路返回,并在走过的路径卜释放信息激素,同时信息激素按照一定的比例挥发,蚂蚁走过的路径越短,信息激素浓度越高,而后续蚂蚁选择这条路径的概率就越大,由此构成一个学习信息的正反馈过程从而逐渐逼近最优解。基于蚂蚁这种行为而提出的蚁群算法是一种随机搜索算法,具有群体合作、正反馈选择、并行计算三大特点,并且可以根据需要为人工蚁加入前瞻、回溯等自然蚁所没有的特点。它主要由四个部分组成[sl:状态转移策略、信息素局部更新、信息素全局更新、局部搜索算法。

,1个城市的TSP问题就是寻找通过n个城市各一次且最后回到出发点的最短路径。设m是蚁群中蚂蚁的总数量,也“√=1,2,…n)表示城市i和城市,之间的欧式距离,fu(?、7)表示迭代Ⅳ次时在城市i和f路径的信息素浓度。初始迭代时,各条路径上信息素的浓度相同,设rdO)=h(h为常数)。蚂蚁k(k=1,2,…,m)在运动过程中根据各条路径上的信息素浓

万方数据

度决定转移方向,彤(J7、『)表示第J『v代蚂蚁k从城市i

转移到城市,的概率,其计算公式为州

—丝竖础生_『,。∈以加e五

1n

彤㈣=

;j棚。'7i(?、7)卢

(1)

EoⅡ/.otoedk

otherwise

式中allowedk={l,2,…,n}-tabuk为蚂蚁k下一步可以选择的城市。与实际蚁群不同,人工蚁群系统具有记忆功能,tabuk用于记录蚂蚁k本代所走过的城市,tabut随蚂蚁不断选择下一个城市而做动态调整。进化代数Ⅳ每增加一次,各条路径上的信息素就要挥发一次,用参数(1一P)表示信息素的挥发程度,所有蚂蚁完成一次迭代循环,各路径上信息素浓度根据式(2)和式(3)作调整。

Ir“,v+1)=P _r“fV)+(1一P) △fg,P∈(o,1)

(2)

I△TF=乞Ar≯(J7、7)

^=l

式中

△r≯为第k只蚂蚁在第Ⅳ次迭代循环中留

在路径莎上的信息素浓度;Ari为本次循环所有m只蚂蚁在路径i『卜所释放的信息索浓度之和。Dorigo曾给出3种不同模型,分别称为Acs(AantAcyele

sys)、

Aqs(Aantquanti哆system)、Ads(Aant

density

system),

他们的差别在于的△r矿计算表达式不同。

,Acs模型

,Aqs模型if:/j∈tabu(N)

ri2

,Ads模型

otherwise

式中Q为常数;厶为第k只蚂蚁在本次迭代中所走过路径的长度;Q,h,口,卢,P根据求解规模确定其取值。上述=三种模型中,后两者利用的是局部信息,而前者利用的是整体信息。算法停止条件可以用同定进化代数Ⅳ眦或者当解的变化不明显时便停止计算。蚁群算法求解机器人焊接路径规划流程如图2所示,按照该流程图进行编程测试,图中J7、『~表示最大迭代次数。3

蚁群算法求解机器人焊接路径规划

本研究主要讨论由多台机器人进行不同工位

的白车身焊接,且所有焊点已经分好组,即各个机器人分配的焊点数已定前提下进行单台机器人的焊接路径规划16)。其中每台机器人的焊接过程可以

Word文档免费下载Word文档免费下载:求解机器人路径规划的智能优化算法 (共5页,当前第2页)

求解机器人路径规划的智能优化算法相关文档

最新文档

返回顶部