中国指挥与控制学会会刊 
1 决策树
决策树是一个属性结构的预测模型,代表对象属性和对象值之间的一种映射关系。它是一种自顶向下的递归算法,结构上类似于常见的流程图,由一定数量的节点和分枝构成[8]。一个决策树通常包括三类节点:根节点(root node)、内部节点(internal node)和叶节点(leaf node)。通常,用方形框表示根节点和内部节点,里面标注相应的决策属性;用椭圆形框表示叶子节点,里面标注相应的行为结果,如图1 所示。
其中,根节点是整个决策树中唯一的、起始的节点,从根节点开始向下分枝;内部节点代表决策属性的集合,其中每一个内部节点都表示一个决策属性;每个叶子节点,代表着一个可能的行为结果;根节点到叶子节点的路径,则代表一条相应的规则。
2 基于决策树的作战实体行为规则描述可能性分析
作战仿真系统的关键是作战模型,而规则是作战模型的核心内容,是对作战系统内主要实体及其之间关系的明确描述。在面向实际作战系统的建模仿真中,规则明确了作战实体的行为特性,决定了仿真的输入和输出[12]。为提高仿真模型的可信度和可理解性,需要选择适当的建模方法,对作战实体的行为规则进行建模,方便军事人员直观地识别、理解和描述,也利于模型开发人员高效地构建相应的模型。
从仿真实现的角度来看,作战实体的行为规则是由一系列的行为状态和状态生成规则构成。行为状态可理解为作战实体在仿真世界中所表现出来的任务内容相对单一的某种行为能力[3],如坦克分队的隐蔽、机动、进攻和防御等。状态生成规则决定了作战实体所呈现出来的行为状态,可理解为影响行为状态的一系列决策属性的取值,如弹药保障分队处于待命状态,可能是由于未收到其他作战分队弹药补充的请求,也可能是由于收到弹药补充申请但目前战场时机不太合适。而基于决策树描述作战实体行为规则,是在分析作战实体行为状态的基础上,明确了影响行为状态的决策属性,通过决策属性的取值来确定作战实体对应的行为状态,进而生成整个决策树,形式化地描述作战实体的行为规则。此外,决策树具有非常直观的结构,能够通过图形化的方式对目标系统的内在逻辑进行直观表现,比较便捷地实现对各种既定模型规则的有效表示。
综上所述,通过决策树对作战实体行为规则进行形式化建模是可行的,并且具有以下的特点:
1)能够以直观和形象的表现方式对行为规则进行展现,提升仿真模型的构建效率,实现行为规则的形式化表达。
2)基于决策树提取的行为规则易于理解,能够表示成“IF-THEN”的形式,实现行为规则的格式化表达。
3)最终可形成完整的树形结构,且树的节点层次越高,该属性节点对行为状态的影响就越大。反之,节点层次越低,该属性节点的影响就越小。
3 基于决策树的作战实体行为规则形式化描述方法
3.1 基于决策树的作战实体行为规则形式化模型
根据决策树的规则,定义描述模型的组成元素,作战实体的行为状态集S,决策属性集F,决策属性值集Z,决策属性排序集A以及行为状态描述函数g。在规则描述模型中,对这些元素作以下假设。
1)行为状态集S。用于表示由作战实体的行为状态构成的全集,需要根据现实仿真对象的行为特征以及建模人员确定的仿真边界来具体确定。如弹药保障分队行为状态可分为待命、弹药补充等,装甲步兵分队行为状态可分为隐蔽、运动、进攻、防御等。设有n个行为状态,S={s1,s2,…,sn}。
2)决策属性集F。主要描述影响作战实体进入该行为状态的属性的集合,如影响弹药保障分队弹药补充的属性有是否接受补充申请、申请分队当前剩余弹药量情况、补充时机等。设有m个属性,F={f1,f2,…fm}。
3)决策属性值集Z。主要是描述每个决策属性的取值,可以是离散的,也可以是连续的,如补充时机可以是离散的数值,即有利和不利。设决策属性fi对应的数值有v个, ={z1,z2,…,zv}。
4)决策属性排序集A。和决策属性集相同,也有m个决策属性,A={a1,a2,…am},其中,ax表示排序为x的属性在决策属性集F中的位置,1≤x≤m。因此,排序后的决策属性集F'={ , ,… }。主要有两种方式进行排序。
① 专家分析法:根据已有的经验和知识,围绕作战实体行为状态的特征,分析各决策属性在时间上和逻辑上的关系,从而确定各决策属性的排序。
② 决策属性排序算法:通过机器学习的决策树分类算法,采用基于信息熵[13]的方法作为决策属性排序标准,如常见的ID3、C4.5算法。
设T为一个包含t个数据样本的集合,对于n个行为状态si,i∈1,2,…,n,令ti=card(si),则对给定的行为状态所需的期望信息为
I(t1,t2,…,tn)=- pilog2(pi)
其中,pi=si/s是任意样本数据表现为行为状态si的概率。
决策属性fi对应的数值有v个,则用该决策属性将T划分为v个子集{T1,T2,…,Tv},其中Tj包含了T集合中决策属性fi取tj值的数据样本。根据这种划分的期望信息称作fi的熵,计算公式如下
E(fi)= I(t1j,…,tnj)
通过决策属性fi对当前节点进行相应样本集合划分计算信息增益,计算公式如下
Gain(fi)=I(t1,t2,…,tn)-E(fi)
因此,需要计算每个决策属性的信息增益,选择最高的排在首位,对剩余的决策属性也采用此方法,最终得到决策属性排序集。
5)行为状态描述函数g。定义为作战实体的行为状态和各决策属性取值之间的关系。可以表达为
S(t)=g(Za1(t),Za2(t),…,Zam(t))
其中,S(t)∈S,Za1(t)∈Za1,Za2(t)∈Za2,…,Zam(t)∈Zam。
3.2 基于决策树的作战实体行为规则形式化描述流程
从上面对行为规则形式化建模的论述可以看出,首先要对仿真对象进行分析,搞清楚所要研究的问题,接着研究作战实体的行为状态,理清影响行为状态的决策属性,并确定决策属性的取值及排序,最后生成决策树,提取相应的行为规则,具体如图2 所示。
从上面的论述可以看出,基于决策树的作战实体行为规则形式化描述的方法步骤如下:
Step1:分析作战实体的行为特征,研究相应的行为状态,确定影响行为状态的决策属性及其取值空间,形成行为状态集、决策属性集和决策属性值集;
Step2:运用专家分析法,根据行为规则的决策属性在时间上或逻辑上的相互联系,对决策属性按影响程度进行排序;或者运用决策属性排序算法,根据已有的样本数据,计算各决策属性的信息增益,选择最高的排在首位,剩余决策属性也按照此方法进行排序,形成决策属性排序集;
Step3:将首个排序的决策属性作为根节点,根据该决策属性的取值画出相应的分枝;
Step4:在每个分枝下,将下个顺序的决策属性作为其内部节点,根据该决策属性的取值继续画出相应的分枝。需要注意:一是若该内部节点的取值不影响其子节点的选择,继续选择下个顺序的决策属性作为其内部节点,直至所有决策属性被添加至内部节点;二是若内部节点已全部添加至决策树,还要在其分枝下添加相应的行为状态作为叶节点;
Step5:重复Step4,直至构造出作战实体行为的整个决策树;
Step6:根据生成的决策树,使用“IF-THEN”形式提取相应的行为规则。
3.3 弹药保障分队行为规则描述实例
弹药保障分队的主要职责是弹药补充。在战斗实施阶段,主要是根据弹药消耗限额的规定,以及部队弹药消耗、损失、现有和申请补充数量,结合本级库存、运输条件、上级补充的可能及部队将要执行的作战任务的可能消耗等情况,经过计算和分析判断,科学合理地选择补充时机,确定补充数量,组织实施补充[14]。本文以弹药保障分队为例,介绍基于决策树的作战实体行为规则描述方法。
Step1:确定行为状态、决策属性及取值
在战斗实施阶段,弹药保障分队主要表现为2个行为状态,即待命和弹药补充,行为状态集则定义为S弹药保障分队={待命,弹药补充}。影响行为状态的因素比较多,这里根据弹药保障行动的特征定义了4个决策属性,即
F弹药保障分队={收到补充申请,剩余弹药量,补充时机,具备运补条件}
决策属性值集则分别定义为:Z收到补充申请={是,否},Z剩余弹药量={充足,一般,不足},Z补充时机={有利,不利},Z具备运补条件={是,否},如表1 所示。
表1 决策属性集及取值说明 |
| 决策属性 | 取值说明 | 备注 |
|---|---|---|
| 收到补充申请 | 是;否 | 描述是否收到作战部队补充弹药的申请 |
| 剩余弹药量 | 充足;一般; 不足 | 描述申请弹药补充的作战部队的当前剩余弹药量 |
| 补充时机 | 有利;不利 | 描述弹药保障分队当前进行弹药补充时机的好坏,由战斗发展情况、部队作战需要和敌对我威胁程度等综合确定 |
| 具备运补条件 | 是;否 | 描述弹药保障分队是否具备运输补充弹药的条件,如有足够的弹药和运力 |
Step2:确定决策属性排序
这里采用专家分析法确定决策属性的排序,即根据弹药保障行动的行为逻辑和决策流程,排序后的决策属性依次为收到补充申请、剩余弹药量、补充时机和具备运补条件,决策属性排序集为
F'弹药保障分队=F弹药保障分队={收到补充申请,剩余弹药量,补充时机,具备运补条件}。
Step3:选择根节点
根据决策属性排序集,选择“收到补充申请”作为根节点,相应的值集Z收到补充申请={是,否},即画出两个决策分枝,如图3 所示。
Step4:添加内部节点
根据决策属性排序集,选择“剩余弹药量”作为根节点下的内部节点,如图4 a)所示;在右分枝下,若未收到部队弹药补充申请,“剩余弹药量”的取值不影响下一步决策,因此需要选择下一个决策属性“补充时机”,替代“剩余弹药量”作为内部节点,如图4 b)所示;同样地,“补充时机”的取值也不影响下一步决策,因此选择“具备运补条件”作为内部节点,如图4 c)所示;在右分枝下,决策属性选择完成,需要添加行为状态集中的值作为叶节点,此刻行为状态为“待命”。在左分枝下,剩余弹药量影响下一步决策,且集值Z剩余弹药量={充足,一般,不足},即画出三个决策分枝,如图4 d)所示。
Step5:重复Step4的步骤,直至构造出弹药保障分队的行为决策树,如图5 所示。
Step6:提取行为规则
从决策树的根节点到任何一个叶节点之间所形成的一条路径,提取对应的行为规则,用“IF-THEN”形式表示,最后可提取以下7条行为规则:
1)IF 收到补充申请=“否” THEN “待命”;
2)IF 收到补充申请=“是” AND 剩余弹药量=“充足” THEN “待命”;
3)IF 收到补充申请=“是” AND 剩余弹药量=“一般” AND 补充时机=“不利” THEN “待命”;
4)IF 收到补充申请=“是” AND 剩余弹药量=“一般” AND 补充时机=“有利” AND 具备运补条件=“是” THEN “弹药补充”;
5)IF 收到补充申请=“是” AND 剩余弹药量=“一般” AND 补充时机=“有利” AND 具备运补条件=“否” THEN “待命”;
6)IF 收到补充申请=“是” AND 剩余弹药量=“不足” AND 具备运补条件=“是” THEN “弹药补充”;
7)IF 收到补充申请=“是” AND 剩余弹药量=“不足” AND 具备运补条件=“否” THEN “待命”。
4 基于决策树的作战实体行为规则建模工具设计
主要是通过基于决策树的行为规则形式化建模,生成行为规则模型,作为构建作战实体模型的行为组件,包括以下6个功能模块,如图6 所示。
1)行为规则模型管理模块:用于定义行为规则的模型构成框架,并管理整个建模活动周期中的所有产品,主要包括行为规则模型的项目生成、查询、删除和调用等功能。
2)行为状态定义发布模块:用于定义作战实体的行为状态,包括该行为状态的具体内容和需要明确的参数及取值,并能够发布所定义的行为状态。
3)决策属性定义发布模块:用于定义影响行为状态的决策属性,包括该决策属性的名称、内容、取值和排序,并能够发布所定义的决策属性。
4)决策树生成发布模块:在行为状态和决策属性定义的基础上,提供可视化的界面,辅助生成决策树,并能够发布所生成的决策树。
5)行为规则定义发布模块:能够根据生成的决策树,定义作战实体的行为规则,并可以发布所定义的行为规则。
6)行为规则模型代码生成发布模块:能够生成行为规则模型的实现代码框架,并提供与相应软件开发平台之间的关联,直接驱动仿真模型的程序开发。
5 结束语
本文在介绍决策树方法的基础上,分析了基于决策树形式化描述作战实体行为规则的可行性,提出了基于决策树的作战实体行为规则形式化描述方法,为作战实体行为规则的格式化表达和形式化描述提供了具体的解决途径;通过对基于决策树的作战实体行为规则建模工具框架进行设计,探索了行为规则建模的工程实现。下一步的主要研究工作是,针对现有决策属性排序算法时间复杂度较大和精度不高的情况,改善决策树算法,利用已有的样本数据自动生成决策树,提取行为规则,辅助军事人员和模型开发人员构建精准的作战模型,提高建模的效率。