群体仿真中基于决策树的路径自动评价研究

张聪聪，宋承祥，丁艳辉

（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.