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

【前言】基于优化的蚁群算法在碰撞检测中的应用研究由文秘帮小编整理而成，但愿对你的学习工作带来帮助。1 蚁群算法简介 人工蚁群算法[2]是受到人们对自然界中真实的蚁群集体行为研究成果的启发而提出的一种基于蚁群的模拟进化算法，属于随机搜索算法，由意大利学者M.Dorigo等人于1991年首先提出。仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称之为外激素（...

摘要：传统的蚁群算法具有搜索时间长的缺点，在实际应用中受到限制。故该文提出了基于信息素扩散模型的蚁群算法，简化了信息素扩散，并改进了基本蚁群算法的信息素更新方式。最后将该改进算法应用在碰撞检测当中，通过手术中手术器械与人体的碰撞反映的仿真验算，验证了基于信息素扩散模型的蚁群算法在碰撞检测中能提高碰撞的效率和精确度，为实际的应用提供理论依据与指导。

关键词：蚁群算法；信息素扩散模型；信息素更新

中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2012）28-6758-03

碰撞检测作为虚拟现实系统中的一个关键组成部分，主要的任务是判断物体模型之间、模型与场景之间是否发生了碰撞，以及给出碰撞位置、穿刺深度等信息[1]。

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

1 蚁群算法简介

人工蚁群算法[2]是受到人们对自然界中真实的蚁群集体行为研究成果的启发而提出的一种基于蚁群的模拟进化算法，属于随机搜索算法，由意大利学者M.Dorigo等人于1991年首先提出。仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称之为外激素（pheromone）的物质进行信息传递，从而能相互协作，完成复杂的任务。蚁群之所以表现出复杂有序的行为，个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法正是模拟了这样的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解。

基本蚁群算法（Ant System，As）是Dorigo等人提出最早的，也是最基本的蚁群算法[3]。该算法可描述如下：设[m]是蚁群中蚂蚁的数量，[dij]（i，j=1，2，……，n）表示城市[i]和城市[j]之间的距离，[Iij（t）]表示t时刻在城市[i]与城市[j]路径上信息素的浓度。初始时刻，各条路径上信息素的浓度相等，[Iij（0）]=[c]（c为常数）。蚂蚁通过概率策略选择下一个要访问的城市，令[pkij（t）]表示在t时刻蚂蚁k从城市[i]转移到城市[j]的概率，则

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

2 基于信息素扩散模型的蚁群算法在碰撞检测中的应用

两个碰撞的模型是两个特征集合，在解空间里就是两个模型的坐标点，那么判断两物体是否发生碰撞就相当于是判断两个物体间是否至少有一对特征对间的距离是否达到碰撞的条件，即三维空间至少存在一对特征对的两个点，两点间有一条最优的路径。

文献[7]中的基于信息素扩散模型的蚁群算法，在一定程度上加快了收敛速度，但效率却比较低，而且模型比较复杂，没有进行信息素的局部更新，只是进行全局更新。本文提出一种信息素扩散优化模型并很好得进行全局和局部的更新。

设蚂蚁在原点[o]处，信息素将会以原点为中心进行扩散，即在扩散的范围内都会接受到信息，信息素的浓度设定为[Io]，本文提出的扩散算法主要采用高斯模型，则圆内的任意距离圆心为d接收到的信息浓度[Id]为：

蚂蚁在爬行中都会向邻近路径扩散信息素，同时更新路径上的信息素。有两个相距[dab]距离的两个点[a]和[b]，令蚂蚁[k]在点[c]的信息素浓度为[Io]，蚂蚁一旦爬行经过，则蚂蚁会以点[c]为中心向周围扩散信息素，则信息素扩散都会对（[a]，[b]）产生影响，设变化量分别为[ΔIkab]，设[c]点到路径（[a]， [b]）的平均距离为[d-]，则结合式（3）推得：

这样，采用这种新的信息素扩散方法更新局部信息，更加快速，灵活。同时本文采用设定最优解的上限，选取一次循环中的[ε]个最优解，如有[m]个蚂蚁，则[ε]=0.1[m]，这样避免局部收敛，解决了停滞现象。

蚁群优化流程图：

3 实验结果与分析

实验环境设定了一个简单的动态场景，两个由10000个三角面片组成已经碰撞的手臂模型，如图 2 所示。采用 C++语言对算法进行编程，对手术中器械与人体碰撞反映进行仿真验算，验证了该算法不仅能寻找到最优的碰撞路径，同时与基本的蚁群算法相比，缩短了检测时间，有效的提高了碰撞的效率性和准确性。

由上图可知，通过蚁群算法寻找到最优的碰撞方式，使肱骨和桡骨有效的接合，而不至于错位或对接不上，从而有效的修复骨折，验证了该算法在碰撞检测中的可行性。另外，试验采取三组特征对，计算碰撞检测时间，如表1所示。

由表1可知，随着采样特征值的增多，要搜索的空间越大，搜索的时间也就越长，但采用本文算法能减小检测时间，提高碰撞的效率。

4 结束语

本文提出了一种基于优化的蚁群算法，改进了信息素的扩散模型，提高了计算效率，提升了收敛速度。最后将其应用在碰撞检测，通过仿真验证该算法在碰撞检测中的可行性，与传统蚁群算法相比较，该算法能减小检测时间，提高碰撞效率。本文仅仅仿真了简单的两物的碰撞检测，之后的研究方向是多模块的碰撞，将能应用在粉碎性骨折的修复当中。

参考文献：

[1] ERICSON CHRISTER.Real-time collision detection[M].Morgan Kaufmann Publishers Inc， 2005.

[2] 段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.

[3] ClolmiM.Dorig，V.maniezzo Distributed optimization by ant colonies[C].proeeedings of the[1st]European Conference on Aitificial Life， 1991：134-142.

[4] 吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报，2001，24（12） ：1328-1333.

[5] Stutzl T，Hoos H H.The MAX-MIN ant system and local search for the for the traveling salesman problem[C].In Proc IEEE International conference on Evolutionary Computation（ICEC’97）， Indianapolis， USA， 1997：309-314.

[6] 陈峻，秦玲，陈宏建，等.具有感觉和知觉特征的蚁群算法[J].系统仿真学报，2003，15（10）：1418-1425.

[7] 黄国锐，曹先彬，王煦法.基于信息素扩散的蚁群算法[J].电子学报，2004，32（5）：865-868.