摘要：傳統(tǒng)的蟻群算法具有搜索時間長的缺點(diǎn)，在實(shí)際應(yīng)用中受到限制。故該文提出了基于信息素?cái)U(kuò)散模型的蟻群算法，簡化了信息素?cái)U(kuò)散，并改進(jìn)了基本蟻群算法的信息素更新方式。最后將該改進(jìn)算法應(yīng)用在碰撞檢測當(dāng)中，通過手術(shù)中手術(shù)器械與人體的碰撞反映的仿真驗(yàn)算，驗(yàn)證了基于信息素?cái)U(kuò)散模型的蟻群算法在碰撞檢測中能提高碰撞的效率和精確度，為實(shí)際的應(yīng)用提供理論依據(jù)與指導(dǎo)。
　　關(guān)鍵詞：蟻群算法；信息素?cái)U(kuò)散模型；信息素更新
　　中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2012）28-6758-03
　　碰撞檢測作為虛擬現(xiàn)實(shí)系統(tǒng)中的一個關(guān)鍵組成部分，主要的任務(wù)是判斷物體模型之間、模型與場景之間是否發(fā)生了碰撞，以及給出碰撞位置、穿刺深度等信息[1]。
　　智能算法在碰撞檢測領(lǐng)域中的應(yīng)用，即是利用智能優(yōu)化算法判斷兩物體碰撞的最優(yōu)路徑和方式，其中主要應(yīng)用的算法有遺傳算法，粒子群算法和蟻群算法等。對于算法在碰撞領(lǐng)域中的應(yīng)用，首先要了解該智能優(yōu)化算法能解決什么問題，以及如何進(jìn)行優(yōu)化，本文在理論研究基礎(chǔ)上，結(jié)合碰撞檢測的實(shí)際特點(diǎn)，對傳統(tǒng)的蟻群算法進(jìn)行改進(jìn)與設(shè)計(jì)，最后通過對手術(shù)中手術(shù)器械與人體的碰撞反映的仿真，驗(yàn)證了基于信息素?cái)U(kuò)散模型的蟻群算法在碰撞檢測中能提高碰撞的效率和精確度，即能以較短的時間內(nèi)尋找到器械與人體的最優(yōu)接觸方式，有效地降低了手術(shù)中的失誤。
　　1 蟻群算法簡介
　　人工蟻群算法[2]是受到人們對自然界中真實(shí)的蟻群集體行為研究成果的啟發(fā)而提出的一種基于蟻群的模擬進(jìn)化算法，屬于隨機(jī)搜索算法，由意大利學(xué)者M(jìn).Dorigo等人于1991年首先提出。仿生學(xué)家經(jīng)過大量細(xì)致觀察研究發(fā)現(xiàn)，螞蟻個體之間是通過一種稱之為外激素（pheromone）的物質(zhì)進(jìn)行信息傳遞，從而能相互協(xié)作，完成復(fù)雜的任務(wù)。蟻群之所以表現(xiàn)出復(fù)雜有序的行為，個體之間的信息交流與相互協(xié)作起著重要的作用。螞蟻在運(yùn)動過程中，能夠在它所經(jīng)過的路徑上留下該種物質(zhì)，而且螞蟻在運(yùn)動過程中能夠感知這種物質(zhì)的存在及其強(qiáng)度，并以此指導(dǎo)自己的運(yùn)動方向，螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻個體之間就是通過這種信息的交流達(dá)到搜索食物的目的。蟻群算法正是模擬了這樣的優(yōu)化機(jī)制，即通過個體之間的信息交流與相互協(xié)作最終找到最優(yōu)解。
　　基本蟻群算法（Ant System，As）是Dorigo等人提出最早的，也是最基本的蟻群算法[3]。該算法可描述如下：設(shè)[m]是蟻群中螞蟻的數(shù)量，[dij]（i，j=1，2，……，n）表示城市[i]和城市[j]之間的距離，[Iij（t）]表示t時刻在城市[i]與城市[j]路徑上信息素的濃度。初始時刻，各條路徑上信息素的濃度相等，[Iij（0）]=[c]（c為常數(shù)）。螞蟻通過概率策略選擇下一個要訪問的城市，令[pkij（t）]表示在t時刻螞蟻k從城市[i]轉(zhuǎn)移到城市[j]的概率，則
　　蟻群算法具有很多的優(yōu)點(diǎn)，能并行化計(jì)算，能與其他智能算法結(jié)合，能有較強(qiáng)的魯棒性等。但蟻群算法本身仍然存在有一些缺點(diǎn)，最主要的缺點(diǎn)就是該算法需要很長的搜索時間，如果規(guī)模增大，算法的時間復(fù)雜度也就增大。因此文獻(xiàn)[5]采取了限定信息量允許值的上下限；文獻(xiàn)[6]采取了有條件地接受信息素，而不是任何一個螞蟻的信息素都接受，并更改路徑上的信息量。這些優(yōu)化算法在一定程度上減少了蟻群算法的缺點(diǎn)，故本文將基于信息素?cái)U(kuò)散模型的蟻群算法應(yīng)用在碰撞檢測中，提高碰撞的效率和精確度，下文對基于該模型的碰撞檢測進(jìn)行分析。
　　2 基于信息素?cái)U(kuò)散模型的蟻群算法在碰撞檢測中的應(yīng)用
　　兩個碰撞的模型是兩個特征集合，在解空間里就是兩個模型的坐標(biāo)點(diǎn)，那么判斷兩物體是否發(fā)生碰撞就相當(dāng)于是判斷兩個物體間是否至少有一對特征對間的距離是否達(dá)到碰撞的條件，即三維空間至少存在一對特征對的兩個點(diǎn)，兩點(diǎn)間有一條最優(yōu)的路徑。
　　文獻(xiàn)[7]中的基于信息素?cái)U(kuò)散模型的蟻群算法，在一定程度上加快了收斂速度，但效率卻比較低，而且模型比較復(fù)雜，沒有進(jìn)行信息素的局部更新，只是進(jìn)行全局更新。本文提出一種信息素?cái)U(kuò)散優(yōu)化模型并很好得進(jìn)行全局和局部的更新。
　　設(shè)螞蟻在原點(diǎn)[o]處，信息素將會以原點(diǎn)為中心進(jìn)行擴(kuò)散，即在擴(kuò)散的范圍內(nèi)都會接受到信息，信息素的濃度設(shè)定為[Io]，本文提出的擴(kuò)散算法主要采用高斯模型，則圓內(nèi)的任意距離圓心為d接收到的信息濃度[Id]為：
　　螞蟻在爬行中都會向鄰近路徑擴(kuò)散信息素，同時更新路徑上的信息素。有兩個相距[dab]距離的兩個點(diǎn)[a]和[b]，令螞蟻[k]在點(diǎn)[c]的信息素濃度為[Io]，螞蟻一旦爬行經(jīng)過，則螞蟻會以點(diǎn)[c]為中心向周圍擴(kuò)散信息素，則信息素?cái)U(kuò)散都會對（[a]，[b]）產(chǎn)生影響，設(shè)變化量分別為[ΔIkab]，設(shè)[c]點(diǎn)到路徑（[a]， [b]）的平均距離為[d-]，則結(jié)合式（3）推得：
　　這樣，采用這種新的信息素?cái)U(kuò)散方法更新局部信息，更加快速，靈活。同時本文采用設(shè)定最優(yōu)解的上限，選取一次循環(huán)中的[ε]個最優(yōu)解，如有[m]個螞蟻，則[ε]=0.1[m]，這樣避免局部收斂，解決了停滯現(xiàn)象。
　　蟻群優(yōu)化流程圖：
　　3 實(shí)驗(yàn)結(jié)果與分析
　　實(shí)驗(yàn)環(huán)境設(shè)定了一個簡單的動態(tài)場景，兩個由10000個三角面片組成已經(jīng)碰撞的手臂模型，如圖 2 所示。采用 C++語言對算法進(jìn)行編程，對手術(shù)中器械與人體碰撞反映進(jìn)行仿真驗(yàn)算，驗(yàn)證了該算法不僅能尋找到最優(yōu)的碰撞路徑，同時與基本的蟻群算法相比，縮短了檢測時間，有效的提高了碰撞的效率性和準(zhǔn)確性。
　　由上圖可知，通過蟻群算法尋找到最優(yōu)的碰撞方式，使肱骨和橈骨有效的接合，而不至于錯位或?qū)硬簧?，從而有效的修?fù)骨折，驗(yàn)證了該算法在碰撞檢測中的可行性。另外，試驗(yàn)采取三組特征對，計(jì)算碰撞檢測時間，如表1所示。
　　由表1可知，隨著采樣特征值的增多，要搜索的空間越大，搜索的時間也就越長，但采用本文算法能減小檢測時間，提高碰撞的效率。
　　4 結(jié)束語
　　本文提出了一種基于優(yōu)化的蟻群算法，改進(jìn)了信息素的擴(kuò)散模型，提高了計(jì)算效率，提升了收斂速度。最后將其應(yīng)用在碰撞檢測，通過仿真驗(yàn)證該算法在碰撞檢測中的可行性，與傳統(tǒng)蟻群算法相比較，該算法能減小檢測時間，提高碰撞效率。本文僅僅仿真了簡單的兩物的碰撞檢測，之后的研究方向是多模塊的碰撞，將能應(yīng)用在粉碎性骨折的修復(fù)當(dāng)中。
　　參考文獻(xiàn)：
　　[1] ERICSON CHRISTER.Real-time collision detection[M].Morgan Kaufmann Publishers Inc， 2005.
　　[2] 段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，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].計(jì)算機(jī)學(xué)報(bào)，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].系統(tǒng)仿真學(xué)報(bào)，2003，15（10）：1418-1425.
　　[7] 黃國銳，曹先彬，王煦法.基于信息素?cái)U(kuò)散的蟻群算法[J].電子學(xué)報(bào)，2004，32（5）：865-86