基于贪婪算法的影响网络行动方案优选

田 仲，李加祥

(海军大连舰艇学院，辽宁 大连 116018)

影响网络(Influence Nets，INs)已经广泛应用于基于效果作战(Effects-Based Operations，EBO)领域的相关试验［1］。其主要功能是辅助建模人员对不确定的环境中作战行动和效果之间的因果影响关系进行建模和分析，从而建立特定环境下各元素之间的定性与定量关系［2-3］。INs建模的主要目的是为了对一系列作战行动方案(Course Of Actions，COA)进行评估和优选，从而获得最有可能达成期望效果的行动方案。

目前，INs中行动方案优选的常用方法是穷举搜索法和灵敏度分析法。穷举搜索法需要遍历整个方案空间，虽然理论上一定能够找到最优方案，但所需的搜索时间也将随可行行动个数的增加而成指数增长，所以只能适用于可行行动数量较少的情况，当可行行动数量较多时，该方法将无法有效应用。灵敏度分析法通过对单个可行行动对期望效果的影响来判定该行动对期望效果的灵敏度，从而进一步确定较优(不一定是最优)的行动方案。该方法执行效率较高，但是仅从单个可行行动的角度进行分析，并没有考虑行动之间的相互关系，难免会造成最终结果的不合理。为了克服上述方法的不足，本文提出了一种适用于INs的基于贪婪算法的行动方案优选方法。

1 影响网络模型

影响网络在拓扑结构上是一个有向无环图，图中的节点表示随机变量，节点之间的有向边表示变量之间的因果影响关系。INs作为贝叶斯网络(Bayesian Networks，BNs)的一种变体，是不确定情况下因果影响关系建模的常用概率网络，现已经广泛应用于人工智能领域，解决了BNs存在的大量条件概率获取困难和概率推理困难［4］。INs采用因果强度逻辑［5-6］(Causal Strength Logic，CAST Logic)作为知识获取界面，通过CAST参数可以转换为所需的条件概率表，从而支持概率推理。INs具有以下特点:1)影响网的节点由一系列随机变量组成，所有变量都具有二进制特性;2)各节点之间通过有向边联接;3)每条边都对应一组CAST参数(h，g)，该参数表示联接节点之间的影响强度;4)每个非根节点都有相应的基准概率，而每个根节点都有相应的先验概率。

INs定义如下:

影响网络可以描述为以下四元组 (V，E，C，B)，其中，V表示节点的集合，E表示有向边的集合，C表示节点之间的影响强度集合，E→{(h，g)，－1≤h，g≤1}，B表示随机变量的基准概率和先验概率集合，其中V →［0，1］。

基于效果作战中因果影响关系建模是通过对一系列作战行动和期望效果之间的因果关系进行描述来完成的。可行行动(事件)在TIN中表示为根节点(没有输入节点)，决策者的期望效果(或目标)表示为叶节点(没有输出的节点)。根节点用直角方框表示，而非根节点则用圆角方框表示。行动之间影响强度用CAST逻辑参数(h，g)表示，其中，h表示当父节点对应随机变量取值为1时对子节点对应随机变量取值为1的影响强度，g表示当父节点对应随机变量取值为0时对子节点对应随机变量取值为1的影响强度。如果h＞0并且g≤0，那么表示父节点对子节点具有促进影响作用，用有向尖箭头表示;如果h≤0并且 g＞0，那么表示父节点对子节点具有抑制影响作用，用有向圆箭头表示。如图1所示，节点A，B，C代表可行行动，X代表效果节点(目标节点)。行动A的执行对效果X有促进影响作用，而行动B的执行对效果X有抑制作用，h和g的值表示影响强度的大小用。

图1 一个简单的影响网络

下面以一个影响网络为例，分别采用灵敏度分析方法和基于贪婪算法的优选方法对COA进行优选。

2 灵敏度分析方法

本文给定的影响网络模型如图2所示，每条边对应一组CAST参数，通过这些参数可转换为所需的条件概率表，从而支持概率推理，转换算法请参考文献［4，5］。在该INs中，所有可行行动的先验概率设置为0．1，所有事件的基准概率设置为0．5。

灵敏度分析算法如表1所示，该算法从所有可行行动(A-H)中依次选择单个行动a，将a的先验概率设置为0和1，其余行动先验概率保持不变，分别计算两种情况下期望效果的概率值P(E0)和P(E1)，由此得到效果概率差值Diff(a)，差值绝对值较大所对应的行动a被认为对期望效果有较大的影响，灵敏度分析计算结果如表2所示。

图2 影响网络模型

表1 灵敏度分析算法

表2 灵敏度分析结果

假设决策人员认为事件“O”的发生的概率越大越好，则可行行动C，E和H将被选择作为行动方案的元素进行进一步评估，因为它们的执行使得“O”发生的概率增加。而从结果中可以得知，实际情况则是可行行动C，D，E和H的同时执行使得“O”的发生概率最大。造成这种偏差的原因在于灵敏度分析方法仅考察了单个行动对期望效果的影响，而忽视了各行动之间的相互联系。行动方案是由多个可行行动组合而成的，单个行动的执行虽然可能降低期望效果的概率值，但是该行动和其它行动的组合执行却能在整体上提高期望效果的概率值，因此，灵敏度分析方法的特点使得在处理上述问题时所得的结果不一定合理。

3 基于贪婪算法的行动方案优选方法

贪婪算法(Greedy Algorithm)是一种寻求最优解问题简单、快速的设计技术。该算法的特点是分多个阶段依次进行，每一阶段中都寻求当前情况下的局部最优解，并以迭代的方式做出相继的贪婪选择，每做一次选择就将求解的问题简化为一个规模更小的子问题，最终可以得到问题的一个整体最优解或者是整体最优解的近似解。基于贪婪算法的行动方案优选方法如表3所示，该方法从行动组合的角度出发，考虑了各行动之间的相互关系，每次迭代都选取当前阶段最优的行动组合，从而快速找到最有可能达成期望效果的可行行动方案集合。

本文给定的影响网络模型如图2所示，指定效果概率阈值t=0．8。算法开始首先将所选行动集合S设置为null，接下来将所有可行行动的先验概率设置为0，计算期望事件“O”的边缘概率P(O)=0．63。然后依次将每一个所选行动的先验概率设置为1，其余行动的先验概率设置为0，计算“O”的效果概率差值。例如，当P(A)为1时，其余所有行动的先验概率为0，此时P(O)为0．51，说明A的执行降低了“O”的效果值，其差值为0．12(0．63-0．51)。同理，可计算出其余结果如表4中第1列所示，可以看出，当行动H为True其余行动为False时，P(O)具有最大值0．78。因此，按照表3中算法步骤5，将 H从 A中去除并加入 S，令 H为 True，P(O)=0．78，转入步骤4进行下一次迭代。第二次迭代计算结果如表4中第2列所示，可以看出，当H和C执行，而其余行动不执行的情况下“O”的效果概率值最大，并比H单独执行时有所增加，说明该行动组合将有助于期望效果的提高。由于P(O)=0．84＞t，也说明该行动组合是一组可行的行动方案。将C从A中去除并加入 S，令 H，C 为 True，P(O)=0．84，然后转入下一次迭代。

表3 基于贪婪算法的行动方案优选方法

表4 基于贪婪算法的优选方法结果

重复迭代过程直至计算结束，剩余计算结果如表4中3-6列所示。值得注意的是第5列的情况，当H，C，E，D 执行，其余行动为不执行时 P(O)=0．89，在此种情况下，虽然剩余任何行动(A，B，F，G)的执行都无法再次提高P(O)，但是所选行动集合中加入B后P(O)=0．85 ＞ t，说明 H、C、E、D、B 执行，A、F、G 不执行时的行动组合也是一组可行的行动方案，因此B也被加入S，并进行下一次迭代。如表5所示，在整个迭代过程中，共得到了5组可行方案，其中“﹁”表示“非”，例如，﹁A表示不执行行动A，而C则表示执行行动C。

表5 可行行动方案集合

上例如果采用穷举搜索方法遍历整个解空间，需要搜索28=256种可能的行动组合，最终可得到所有6组可行方案。而如表4中所示，采用本文提出的方法只需要搜索33种行动组合就找到了6组可行方案中的5组。通常情况下，如果可行行动的数目为n，该算法最多只需进行n(n+1)/2次迭代就可找到一组较优的行动方案，在保证搜索质量的同时也大量减少了搜索时间。

4 结束语

本文针对影响网络中现有方法在行动方案优选问题时存在的不足，提出了一种基于贪婪算法的行动方案优选方法。该方法可以快速从一系列可行行动组合中找到达成期望效果概率值满足指定概率阈值的可行行动方案集合，增强了影响网络建模的分析能力，并有效支持行动方案的优选。

［1］ Wagenhals，L W．，Levis，A．H．Modeling Support of Effect-Based Operations in War Games［C］．Proceedings of the Command and Control Research and Technology Symposium，2002．

［2］ Wagenhals L W，Levis A H．Course of Action Analysis in a Cultural Landscape Using Influence nets［C］．Proceedings of the IEEE Symposium on Computational Intelligence for Security and Defense Applications，Honolulu，2007．

［3］ Wagenhals L W．Influence Nets and Bayesian Net Approaches for Course of Action［R］．Adversary Behavioral Modeling Maxwell AFB．Montgomery AL．2008．

［4］ Copper G F．The Computation Complexity of Probabilistic Inference Using Bayesian Belief Networks［J］．Artificial Intelligence，1990，42;393-405．

［5］ Chang，K．C，Lehner，P．E，Levis，A．H．，Zaidi，S．A．K，and Zhao，X，On Causal Influence Logic，Technical Report，George Mason University，Center of Excellence for C3I，Dec．1994．

［6］ Rosen，J．A，and Smith，W．L，Influence Net Modeling with Causal Strengths:An Evolutionary Approach［C］，Proceedings of the Command and Control Research and Technology Symposium， Naval Post Graduate School，Monterey CA，Jun．1996．