基于優(yōu)化的蟻群算法在碰撞檢測(cè)中的應(yīng)用研究

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