基于优化蚁群算法在碰撞检测中应用探究

《基于优化蚁群算法在碰撞检测中应用探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于优化蚁群算法在碰撞检测中应用探究摘要：传统的蚁群算法具有搜索时间长的缺点，在实际应用中受到限制。故该文提出了基于信息素扩散模型的蚁群算法，简化了信息素扩散，并改进了基本蚁群算法的信息素更新方式。最后将该改进算法应用在碰撞检测当中，通过手术中手术器械与人体的碰撞反映的仿真验算，验证了基于信息素扩散模型的蚁群算法在碰撞检测中能提高碰撞的效率和精确度，为实际的应用提供理论依据与指导。关键词：蚁群算法；信息素扩散模型；信息素更新中图分类号：TP301文献标识码：A文章编号：1009-3044(2012)28-6758-03碰撞检测作为虚拟现实系统中的一个关键组成部分，主要的任务是判断物体模型之

2、间、模型与场景之间是否发生了碰撞，以及给出碰撞位置、穿刺深度等信息［1］。智能算法在碰撞检测领域中的应用，即是利用智能优化算法判断两物体碰撞的最优路径和方式，其中主要应用的算法有遗传算法，粒子群算法和蚁群算法等。对于算法在碰撞领域中的应用，首先要了解该智能优化算法能解决什么问题，以及如何进行优化，本文在理论研究基础上，结合碰撞检测的实际特点，对传统的蚁群算法进行改进与设计，最后通过对手术中手术器械与人体的碰撞反映的仿真，验证了基于信息素扩散模型的蚁群算法在碰撞检测中能提高碰撞的效率和精确度，即能以较短的时间内寻找到器械与人体的最优接触方式，有效地降低了手术中的失误。1蚁群算法简介人工蚁群算

3、法［2］是受到人们对自然界中真实的蚁群集体行为研究成果的启发而提出的一种基于蚁群的模拟进化算法，属于随机搜索算法，由意大利学者M.Dorigo等人于1991年首先提出。仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递，从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行为，个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表

4、现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法正是模拟了这样的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解。基本蚁群算法(AntSystem,As)是Dorigo等人提出最早的，也是最基本的蚁群算法［3］。该算法可描述如下：设［m］是蚁群中蚂蚁的数量，［dij］(i,j=l,2,,n)表示城市［i］和城市［j］之间的距离，［Iij(t)］表示t时刻在城市［i］与城市［j］路径上信息素的浓度。初始时刻，各条路径上信息素的浓度相等，［Iij(0)］=［c］(c为常数)。蚂蚁通过概率策

5、略选择下一个要访问的城市，令［pkij(t)］表示在t时刻蚂蚁k从城市［i］转移到城市［j］的概率，则蚁群算法具有很多的优点，能并行化计算，能与其他智能算法结合，能有较强的鲁棒性等。但蚁群算法本身仍然存在有一些缺点，最主要的缺点就是该算法需要很长的搜索时间，如果规模增大，算法的时间复杂度也就增大。因此文献［5］采取了限定信息量允许值的上下限；文献［6］采取了有条件地接受信息素，而不是任何一个蚂蚁的信息素都接受，并更改路径上的信息量。这些优化算法在一定程度上减少了蚁群算法的缺点，故本文将基于信息素扩散模型的蚁群算法应用在碰撞检测中，提高碰撞的效率和精确度，下文对基于该模型的碰撞检测进行分析。

6、2基于信息素扩散模型的蚁群算法在碰撞检测中的应用两个碰撞的模型是两个特征集合，在解空间里就是两个模型的坐标点，那么判断两物体是否发生碰撞就相当于是判断两个物体间是否至少有一对特征对间的距离是否达到碰撞的条件，即三维空间至少存在一对特征对的两个点，两点间有一条最优的路径。文献［7］中的基于信息素扩散模型的蚁群算法，在一定程度上加快了收敛速度，但效率却比较低，而且模型比较复杂，没有进行信息素的局部更新，只是进行全局更新。本文提出一种信息素扩散优化模型并很好得进行全局和局部的更新。设蚂蚁在原点［。］处，信息素将会以原点为中心进行扩散，即在扩散的范围内都会接受到信息，信息素的浓度设定为：Io］,本

7、文提出的扩散算法主要采用高斯模型，则圆内的任意距离圆心为d接收到的信息浓度［Id］为：蚂蚁在爬行中都会向邻近路径扩散信息素，同时更新路径上的信息素。有两个相距［dab］距离的两个点［a］和［b］,令蚂蚁［k］在点［c］的信息素浓度为［Io］,蚂蚁一旦爬行经过，则蚂蚁会以点［c］为中心向周围扩散信息素，则信息素扩散都会对（［a］,［b］）产生影响，设变化量分别为［△Ikab］,设［c］点到路径（［a］,［b］）的平均距离为