群體仿真中基于決策樹的路徑自動(dòng)評價(jià)研究

張聰聰，宋承祥，丁艷輝

（1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院 山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南250014；2.山東省教育廳，山東 濟(jì)南250011）

0 引 言

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

1 相關(guān)研究

1.1 群體仿真

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

1.2 決策樹

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

2 路徑自動(dòng)評價(jià)模型

在群體仿真中，對大規(guī)模粒子運(yùn)動(dòng)產(chǎn)生的群體路徑進(jìn)行合理準(zhǔn)確的評價(jià)具有十分必要的意義。因此，本文提出一種路徑自動(dòng)評價(jià)模型。首先對應(yīng)用群體智能算法的群體粒子產(chǎn)生的一組路徑進(jìn)行分析，提取出路徑評價(jià)的標(biāo)準(zhǔn)，然后再與路徑評價(jià)算法相結(jié)合，建立路徑自動(dòng)評價(jià)模型，最后在搭建的仿真平臺上通過路徑自動(dòng)評價(jià)模型進(jìn)行群體路徑優(yōu)劣的選擇。

2.1 路徑自動(dòng)評價(jià)標(biāo)準(zhǔn)

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

2.1.1 速度屬性

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

（1）首先考慮群體粒子在整個(gè)運(yùn)動(dòng)過程中的路程速度V路程，其中si表示第i 個(gè)粒子xi的路程，ti表示第i 個(gè)粒子xi在整個(gè)運(yùn)動(dòng)過程中花費(fèi)的時(shí)間

（2）把群體粒子從運(yùn)動(dòng)的開始位置到結(jié)束位置的直線距離記為集合L＝ ｛l1，l2，l3，…，ln｝，其中l(wèi)i表示第i個(gè)粒子xi在整個(gè)過程中的直線距離。記群體粒子在此直線距離中的速度為V直線

（3）在群體粒子的整個(gè)運(yùn)動(dòng)過程當(dāng)中，各個(gè)粒子不斷地進(jìn)行迭代。在這里，本文定義了一個(gè)群體粒子的迭代速度V迭代，通過迭代速度來評價(jià)粒子迭代對群體粒子運(yùn)動(dòng)路徑的影響。記粒子的迭代次數(shù)集合為IR＝ ｛ir1，ir2，ir3，…，irn｝。

2.1.2 拐點(diǎn)屬性

在群體仿真場景當(dāng)中，一般希望粒子的運(yùn)動(dòng)軌跡盡可能的平滑，認(rèn)為劇烈的彎曲和轉(zhuǎn)折是應(yīng)該盡量避免的，因此在每個(gè)粒子運(yùn)動(dòng)軌跡上單位距離長度的拐點(diǎn)個(gè)數(shù)可以作為評價(jià)運(yùn)動(dòng)路徑優(yōu)劣標(biāo)準(zhǔn)的屬性。記拐點(diǎn)集合為PO＝｛po1，po2，po3，…，pon｝，其中poi為第i個(gè)粒子xi運(yùn)動(dòng)過程中出現(xiàn)的拐點(diǎn)數(shù)，記單位距離的拐點(diǎn)數(shù)為N拐點(diǎn)

2.1.3 密度屬性

一組群體粒子在迭代過程中可能會由于彼此間的距離過小而出現(xiàn) “扎堆”現(xiàn)象，這樣會造成粒子運(yùn)動(dòng)緩慢，運(yùn)動(dòng)所產(chǎn)生的軌跡路徑也會非常的密集，影響其在群體仿真中群體路徑的生成。因此，將粒子迭代時(shí)的密度作為路徑自動(dòng)評價(jià)標(biāo)準(zhǔn)的屬性。

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

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

2.2 路徑評價(jià)算法

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

步驟1 計(jì)算樣本分類的熵

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

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

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

步驟3

式中：Gain（X）——屬性X 的信息增益。在本文中，屬性X 的個(gè)數(shù)由路徑自動(dòng)評價(jià)標(biāo)準(zhǔn)的6個(gè)屬性來決定。

3 仿真實(shí)驗(yàn)

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

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

表1 一般位置的參數(shù)

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

對以該坐標(biāo)為目的坐標(biāo)位置的群體粒子分別作10－100次、間隔為10的路徑自動(dòng)評價(jià)，其正確率與傳統(tǒng)的路徑評價(jià)方式的對比如圖2所示。

圖2 一般位置的評價(jià)正確率

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

表2 特殊位置的參數(shù)

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

在以特殊目標(biāo)坐標(biāo)為目的坐標(biāo)位置的群體粒子運(yùn)動(dòng)中，也分別進(jìn)行10組初值為10次、間隔為10的路徑自動(dòng)評價(jià)，其評價(jià)的正確率與傳統(tǒng)評價(jià)方式的正確率對比如圖4所示。

圖4 特殊位置的評價(jià)正確率

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

4 結(jié)束語

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

［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）.［王永興，丁睿，姚林泉.移動(dòng)機(jī)器人全局路徑規(guī)劃的盲人摸路算法 ［J］.計(jì)算機(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ìn)螢火蟲算法的動(dòng)態(tài)自動(dòng)聚集路徑規(guī)劃方法 ［J］.計(jì)算機(jī)應(yīng)用研究，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）. ［田劍，胡月明，王長委，等.聚類支持下決策樹模型在耕地評價(jià)中的應(yīng)用 ［J］.農(nóng)業(yè)工程學(xué)報(bào)，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）.［潘琛，杜培軍，羅艷，等.一種基于植被指數(shù)的遙感影像決策樹分類方法 ［J］.計(jì)算機(jī)應(yīng)用，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）.［王磊，楊超，盧寶榮.利用決策樹方法建立轉(zhuǎn)基因植物環(huán)境生物安全評價(jià)診斷平臺 ［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ìn) ［J］.計(jì)算機(jī)工程與設(shè)計(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）.［毛國君，段麗娟，王實(shí)，等.數(shù)據(jù)挖掘原理與算法 ［M］.北京：清華大學(xué)出版社，2007：2－37.］

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