群體仿真中基于決策樹的路徑自動評價研究

張聰聰，宋承祥，丁艷輝

（1.山東師范大學 信息科學與工程學院 山東省分布式計算機軟件新技術重點實驗室，山東 濟南250014；2.山東省教育廳，山東 濟南250011）

0 引 言

在群體仿真的過程中，如何對大量的可以看成相同質點的一群個體進行路徑規劃［1］是一項十分重要的工作。其中，如何對群體路徑進行擇優，也就是對群體粒子運動所生成的多組路徑進行評價是路徑規劃中十分關鍵的一步。在傳統的群體仿真路徑選擇中，一般情況下是通過手工或者經驗來判斷每組群體粒子運動生成路徑的好壞，有時候還需要一組一組的代入實際應用仿真或者動畫制作中進行判斷選擇。這樣通過觀察或者代入得到的結果存在著選擇效率低、速度慢、缺乏有效依據、正確率低等缺點。針對上述人工評價群體路徑的不足，本文提取出對于群體路徑有著關鍵影響的屬性，也就是路徑評價模型的標準，建立了基于決策樹算法的路徑自動評價模型。仿真實驗結果表明，本文方法改善了傳統評價方法的缺陷，具有較高的實用性和有效性。

1 相關研究

1.1 群體仿真

近年來，大規模的群體公共安全事件時有發生。所以，有關如何能夠在事件發生時，采取及時有效的措施來減少、甚至解決群體沖突的研究具有十分重要的意義。群體仿真作為計算機圖形學領域和虛擬現實領域的關鍵技術之一，對于模擬仿真此類大規模突發事件具有獨特的優勢。因此，群體仿真技術再次成為學術界研究關注的熱點。通過在群體仿真中模擬群體行為，進而來預測群體將要產生的行為，從而達到提前準備應對突發事件的目的。路徑規劃是群體仿真的基礎和核心。由于在群體智能算法中，群內的個體之間可以相互交互，并且能夠對外界環境的改變做出自發響應。因此，相比較于其它算法，群智能算法［2－4］在群體仿真的路徑規劃中有著巨大的優勢。本文針對群體仿真中群體粒子聚集行為產生的群體路徑進行研究，通過在群體仿真環境中評價出一組或幾組符合要求的群體運動路徑，為之后實際應用場景的仿真和群體動畫的制作提供合適的群體路徑模型，避免在應用群體路徑時可能出現偏離實際或不能符合要求的現象，從而節約仿真實驗或者動畫制作的選擇和調錯成本，并且同時優化了群體仿真中群體粒子運動軌跡的整體流暢度。

1.2 決策樹

隨著人工智能的迅速發展，決策樹在各個領域得到廣泛的應用。文獻 ［5］提出在聚類支持下，使用決策樹建立耕地評價模型，最終的實驗結果表明，改進方法提高了評價的精確度、魯棒性和易理解性。文獻 ［6］選擇綠色植被指數 （GVI）等10個指數作為分類特征構建決策樹進行遙感分類，通過其研究結果表明，新方法提高了分類的總體精度。當前轉基因產品成為談虎色變的嚴峻問題，如何客觀有效的對生物安全進行評價呢？文獻 ［7］提出應用決策樹來建立轉基因植物黃精生物安全評價診斷平臺來準確客觀的進行轉基因植物環境生物安全評價，該平臺為推動轉基因技術的安全利用提供了一個可行方案。由于決策樹在各個領域都表現出優異的性能，因此本文將其引入進來，進行群體路徑的評價，來改善傳統群體路徑選擇評價的缺陷。

2 路徑自動評價模型

在群體仿真中，對大規模粒子運動產生的群體路徑進行合理準確的評價具有十分必要的意義。因此，本文提出一種路徑自動評價模型。首先對應用群體智能算法的群體粒子產生的一組路徑進行分析，提取出路徑評價的標準，然后再與路徑評價算法相結合，建立路徑自動評價模型，最后在搭建的仿真平臺上通過路徑自動評價模型進行群體路徑優劣的選擇。

2.1 路徑自動評價標準

在路徑自動評價模型中，路徑自動評價標準的選擇至關重要，由于影響群體粒子運動行為的因素很多，本文通過分析群體粒子運動的軌跡，提取出影響其運動軌跡的關鍵屬性，作為路徑自動評價的標準。在這里，假設整個仿真場景中群體粒子集合為X＝ ｛x1，x2，x3，…，xn｝，群體粒子運動路程集合為S＝ ｛s1，s2，s3，…，sn｝，群體粒子從初始位置到目的位置所用的時間集合為T＝ ｛t1，t2，t3，…，tn｝。

2.1.1 速度屬性

在粒子運動過程中，速度的快慢是影響其運動軌跡的重要因素。但是在群體粒子運動場景當中，單純的關注某個粒子的速度沒有意義，所以在這里考慮整個群體粒子的速度。通過分析整體速度的變化，來判斷評價群體粒子的運動軌跡。

（1）首先考慮群體粒子在整個運動過程中的路程速度V路程，其中si表示第i 個粒子xi的路程，ti表示第i 個粒子xi在整個運動過程中花費的時間

（2）把群體粒子從運動的開始位置到結束位置的直線距離記為集合L＝ ｛l1，l2，l3，…，ln｝，其中li表示第i個粒子xi在整個過程中的直線距離。記群體粒子在此直線距離中的速度為V直線

（3）在群體粒子的整個運動過程當中，各個粒子不斷地進行迭代。在這里，本文定義了一個群體粒子的迭代速度V迭代，通過迭代速度來評價粒子迭代對群體粒子運動路徑的影響。記粒子的迭代次數集合為IR＝ ｛ir1，ir2，ir3，…，irn｝。

2.1.2 拐點屬性

在群體仿真場景當中，一般希望粒子的運動軌跡盡可能的平滑，認為劇烈的彎曲和轉折是應該盡量避免的，因此在每個粒子運動軌跡上單位距離長度的拐點個數可以作為評價運動路徑優劣標準的屬性。記拐點集合為PO＝｛po1，po2，po3，…，pon｝，其中poi為第i個粒子xi運動過程中出現的拐點數，記單位距離的拐點數為N拐點

2.1.3 密度屬性

一組群體粒子在迭代過程中可能會由于彼此間的距離過小而出現 “扎堆”現象，這樣會造成粒子運動緩慢，運動所產生的軌跡路徑也會非常的密集，影響其在群體仿真中群體路徑的生成。因此，將粒子迭代時的密度作為路徑自動評價標準的屬性。

（1）這里取T／2時的粒子密度ρ。記T／2時得場景的區域面積為ST，粒子數為NT，其中T 為粒子的迭代周期

（2）在群體粒子的運動中，要求粒子的整體運動看起來分布比較均勻，粒子間相鄰不能太緊密或者太疏松，因此本文定義了T／2時的粒子間的緊湊程度PC 來表示此刻粒子之間距離的關系。記T／2時，各個粒子與中心粒子間的距離集合為PL＝ ｛pl1，pl2，pl3，…，pln｝

2.2 路徑評價算法

路徑評價算法和路徑自動評價標準組成了路徑自動評價模型。在本文中，選擇決策樹中的ID3算法來評價路徑。在眾多的決策樹構造算法中，ID3算法最具有代表性和影響力，也最為經典［7，8］。其核心思想是利用信息增益作為決策樹節點屬性選擇標準［9］，在決策樹各級結點上選擇屬性時，通過計算信息增益來選擇屬性，以使在每一個非葉子結點進行測試時，能獲得關于被測試記錄最大的分類信息，從而構造出決策樹來進行分類。所以ID3算法的關鍵是進行 信 息 增 益 的 計 算，步 驟 如 下［9－11］：

步驟1 計算樣本分類的熵

式中：S——樣本集合，樣本大小記為s，b 表示屬性的可能取值，其中pi表示S 中類別屬于i的概率。

步驟2 計算屬性X 劃分后子集的熵E（Sd，X）＝－

式中：｜S｜——樣本集合的大小，d——屬性X 可能取值的種類，｜xj｜——屬性X 中取值為j的集合大小，Sd表示整個集合S 中屬性為X、值為j的子集。

步驟3

式中：Gain（X）——屬性X 的信息增益。在本文中，屬性X 的個數由路徑自動評價標準的6個屬性來決定。

3 仿真實驗

為了驗證決策樹算法在路徑自動評價問題上的有效性和可用性，本文在微軟的Visual Studio.NET 2003 開發平臺上，基于HOOPS和ACIS環境進行了仿真實驗，通過生物 地 理 學 優 化 算 法 （biogeography－based optimization，BBO［12］）中的聚集現象來驗證群體路徑自動評價的效果，并在Matlab7.0中進行改進后路徑評價方法和傳統路徑評價方法的對比。在本文實驗中，對群體粒子運動目標坐標位置的場景進行一般位置和特殊位置的討論，設定在系統參數模板上的粒子數目為27，并且步長設定為10，在這里只考慮粒子在平面中的運動。

（1）一般位置，群體粒子運動的終點不出現在仿真場景的邊界和邊界交叉處。將粒子聚集運動的目標三維坐標設為 （x，0，z）。其中x、y 皆不能為0，例如當x 設為67，z設為117時，具體參數見表1。此時群體粒子運動生成的待評價路徑如圖1所示。

表1 一般位置的參數

圖1 待評價的群體粒子的路徑 （一般位置）

對以該坐標為目的坐標位置的群體粒子分別作10－100次、間隔為10的路徑自動評價，其正確率與傳統的路徑評價方式的對比如圖2所示。

圖2 一般位置的評價正確率

（2）特殊位置，取群體粒子運動的終點在仿真場景的邊界交叉處。將粒子聚集運動的目標三維坐標設為 （1，0，1），即該目標坐標在仿真場景的右下角。由于粒子不會在邊界上直接運動，所以靠近邊界最小的值為1而非是0。具體參數見表2。此時粒子運動生成的待評價路徑如圖3所示。

表2 特殊位置的參數

圖3 待評價的群體粒子的路徑 （特殊位置）

在以特殊目標坐標為目的坐標位置的群體粒子運動中，也分別進行10組初值為10次、間隔為10的路徑自動評價，其評價的正確率與傳統評價方式的正確率對比如圖4所示。

圖4 特殊位置的評價正確率

考慮群體粒子目標坐標位置的兩種情況，一種是在仿真場景中的一般位置，另一種是在場景邊界處交匯處。然后對兩種情況分別進行傳統路徑評價方式與基于決策樹的路徑自動評價方式的評價正確率的對比，圖2和圖4的結果表明，本文提出的路徑自動評價模型方法能夠大大的提高路徑評價的正確率，并且隨著評價次數的增多，評價的正確率也隨之上升。同時在以一般位置為目標坐標位置的群體粒子運動產生的好的路徑概率大于特殊位置，通過路徑自動評價模型只需要幾秒就能評價一組路徑，而傳統的評價方法則至少需要十幾秒甚至幾十秒的時間來做評價判斷，因此本文提出的路徑自動評價模型能有效的解決人工評價的效率限制問題。

4 結束語

本文通過分析群體仿真中影響路徑選擇的關鍵屬性，進而建立了以這些屬性作為評價標準的路徑評價模型，最后通過引入決策樹來實現對群體路徑的自動評價。在實驗過程中，首先通過仿真環境產生群體粒子的運動路徑，并且對一般和特殊兩個目標點的位置展開分析討論。最后在Matlab中進行傳統評價方法與改進后評價方法的準確率對比。實驗結果表明：本文提出的改進方法解決了群體仿真中傳統路徑評價方式存在的速度慢、準確率低、缺乏有效依據的問題，對評價標準給出了合理的依據并且能夠有效的提高路徑評價的正確率、大大加快了評價的效率。目前，本文提出的評價方法有待進一步研究完善，考慮在非群體智能算法下的實現和更換其它相關的評價算法。

［1］WANG Yongxing，DING Rui，YAO Linquan.The blind groping algorithm：Global path planning for mobile robot ［J］.Computer Simulation，2010，27 （5）：157－161 （in Chinese）.［王永興，丁睿，姚林泉.移動機器人全局路徑規劃的盲人摸路算法 ［J］.計算機仿真，2010，27 （5）：157－161.］

［2］Sedighizadeh D，Masehian E.Particle swarm optimization methods，taxonomy and applications ［J］.International Journal of Computer Theory and Engineering，2009，1 （5）：486－502.

［3］Daneshyari M，Yen G G.Cultural－based multiobjective particle swarm optimization ［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2011，41 （2）：553－567.

［4］LIU Peng，LIU Hong，ZHENG Xiangwei，et al.Approach for dynamic group automatic aggregation path planning based on improved FA ［J］.Application Research of Computers，2011，28 （11）：4148－4149 （in Chinese）. ［劉 鵬，劉 弘，鄭 向 偉，等.基于改進螢火蟲算法的動態自動聚集路徑規劃方法 ［J］.計算機應用研究，2011，28 （11）：4148－4149.］

［5］TIAN Jian，HU Yueming，WANG Changwei，et al.Application of evaluation in farmland with decision tree model based on clustering［J］.Transactions of the Chinese Society of Agricultural Engineering，2007，23 （12）：58－62 （in Chinese）. ［田劍，胡月明，王長委，等.聚類支持下決策樹模型在耕地評價中的應用 ［J］.農業工程學報，2007，23 （12）：58－62.］

［6］PAN Chen，DU Peijun，LUO Yan，et al.Decision tree classification of remote sensing images based on vegetation indices［J］.Journal of Computer Applications，2009，29 （3）：777－780 （in Chinese）.［潘琛，杜培軍，羅艷，等.一種基于植被指數的遙感影像決策樹分類方法 ［J］.計算機應用，2009，29（3）：777－780.］

［7］Kwok S W，Carter C.Multiple decision trees ［J］.Machine Intelligence and Pattern Recognition，1990，9：327－335.

［8］Pereira F，Mitchell T，Botvinick M.Machine learning classifiers and FMRI：A tutorial overview ［J］.Neuroimage，2009，45 （1）：S199－S209.

［9］WANG Lei，YANG Chao，LU Baorong.Establishing diagnostic platform for environmental biosafety assessment of genetically modified plants based on the decision－tree method ［J］.Biodiversity Science，2010，18 （3）：215－226 （in Chinese）.［王磊，楊超，盧寶榮.利用決策樹方法建立轉基因植物環境生物安全評價診斷平臺 ［J］.生物多樣性，2010，18 （3）：215－226.］

［10］WANG Xiaowei，JIANG Yuming.Analysis and improvement of ID3decision tree algorithm ［J］.Computer Engineering and Design，2011，32 （9）：3069－3076 （in Chinese）. ［王小巍，蔣玉明.決策樹ID3算法的分析與改進 ［J］.計算機工程與設計，2011，32 （9）：3069－3076.］

［11］MAO Guojun，DUAN Lijuan，WANG Shi，et al.Principle and algorithm of data mining ［M］.Beijing：Tsinghua University Press，2007：2－37 （in Chinese）.［毛國君，段麗娟，王實，等.數據挖掘原理與算法 ［M］.北京：清華大學出版社，2007：2－37.］

［12］Simon D.Biogeography－based optimization ［J］.IEEE Trans Evolutionary Computation，2008，12 （6）：702－713.