一种影响图的期望效用的并行计算方法

技术领域

本发明属于人工智能，涉及影响图的期望效用的一种并行计算方法。

背景技术

影响图是不确定决策表示和分析的重要工具，已经广泛应用到不确定性决策分析领域。影响图是联合效用函数的一种直观、紧凑的表示形式，形式化地表示为。简单地说，一个影响图是由随机结点集C，决策结点集D及效用结点集合V组成的有向无环图G，P={p(A|pa(A))|A∈C}是一组每个随机结点A在父节点pa(A)条件下的条件概率，U={u(pa(V_i))|V_i?V}是一组与每个效用结点V_i在父节点pa(V_i)条件下的效用函数。按照最大期望效用的原则，基于影响图的决策就是计算最大期望效用和最优策略，其中策略空间?是所有可能策略δ={δ₁,δ₂,…,δ_n}的集合，δ_i是每一个决策节点D_i在其父节点pa(D_i)条件下的一个决策行为。计算最大期望效用的核心就是计算所有策略的期望效用。传统的求解方法通过规范、非遗忘以及单效用结点限制影响图的结构进而限制策略空间，仅考虑局部最优决策组合，并且迭代地计算期望效用。运行在Hadoop分布式文件系统HDFS可以为基于MapReduce并行计算影响图的期望效用提供基础。针对影响图中的每个随机节点A_i，以<key，value>的形式作为一行存储到HDFS的F_ID中，key为a_ipa(a_i)，value为p(a_i|pa(a_i))，对于G中的效用节点V，以<key，value>的形式作为一行存储到Hbase的表F_ID中，key为pa(V)，value为。

发明内容

针对影响图决策的核心问题，本发明提出一种基于分布式文件系统HDFS和MapReduce并行地计算影响图期望效用的方法，为大规模影响图的求解以及非规范影响图求解全局最优策略提供一种有效的方法，为影响图的决策和应用提供一种新的技术基础。

本发明基于分布式文件系统HDFS和MapReduce，提出一种并行地计算影响图的最大期望效用的方法，该方法包括以下步骤：

步骤1：并行地计算影响图的联合效用函数；

步骤2：对影响图的所有策略，并行地计算它们的期望效用；

步骤1中，通过以下步骤完成影响图的联合效用函数的并行计算：

步骤1.1：将影响图的随机节点和决策节点的所有可能的组合以F_T存储到分布式文件系统HDFS中，每个组合为F_T的一行；

步骤1.2：使用Map函数并行查询F_ID每一行，并与F_T进行比较，结果以<key，value>的形式作为一行存储到HDFS的F_T；

步骤1.3：使用Reduce函数对文件F_T中相同key的value相乘，得到联合效用；

步骤2中，通过以下步骤完成期望效用的并行计算：

步骤2.1：将所有的策略以F_strategy存储到HDFS中，每个策略为一行；

步骤2.2：对步骤1.3结果使用Map函数并行查询每一行，并与F_strategy进行比较，结果以<key，value>的形式作为一行存储到F_strategy中；

步骤2.3：使用Reduce函数对F_strategy中相同key的value相加，得到每一个策略的期望效用。

附图说明

图1“石油投机分子问题”影响图，节点S表示探测结果s₁=diffuse,s₂=open,s₃=close，O某个地点地下石油蕴藏情况o₁=dry,o₂=wet,o₃=soaking，T是探测行为且t1=yes,t2=no，D是开采行为且d1=yes,d2=no。

具体实施方式

以下结合附图“石油投机分子问题”影响图，对依据本发明提供的具体实施方式，详细说明如下。

表1存储“石油投机分子问题”影响图的F_ID

步骤1.针对影响图“石油投机分子问题”的分布式存储F_ID，并行地计算影响图的联合效用函数；

将影响图的随机节点和决策节点的所有可能的组合以F_T存储到分布式文件系统HDFS中，每个组合为F_T的一行；

取出key=o₁,可知F_T中包含o₁的行有o₁d₁s₁t₁，o₁d₁s₁t₂，……,等12行，将它们分别作为key，将F_ID中当前行的值0.5，作为value，以<key,value>的形式将<o₁d₁s₁t₁,0.5>，<o₁d₁s₁t₂,0.5>，…..,12行存储下来，以同样的方法，对于表1中其它行，将相应的<key,value>存储到F_T中，

使用Reduce函数对文件F_T中相同key的value相乘，从而得到联合效用函数：EU(o₁d₁s₁t₁)=-24，EU(o₁d₁s₁t₂)=-35/3,……

步骤2.针对影响图“石油投机分子问题”，并行地计算影响图的期望效用函数；

将所有的策略以F_strategy存储到HDFS中，每个策略为一行；

使用Map函数并行查询步骤1结果的每一行，并与F_strategy进行比较，对结果的第一行o₁d₁s₁t₁，将d₁s₁t₁作为key，将F_T中当前行的值-24，作为value，以<key,value>的形式将<d₁s₁t₁,-24>，以同样的方法，对于表1中其它行，将相应的<key,value>存储到F_strategy中，

使用Reduce函数对文件F_strategy中相同key的value相加，从而得到每一个策略的期望效用，EU(d₁s₁t₁)=-16.6，EU(d₁s₁t₂=)=20/3，EU(d₁s₂t₁)=8，EU(d₁s₂t₂)=20/3，EU(d₁s₃t₁)=18.6，EU(d₁s₃t₂)=20/3，EU(d₂s₁t₁)=-4.1，EU(d₂s₁t₂)=0，EU(d₂s₂t₁)=-3.5，EU(d₂s₂t₂)=0，EU(d₂s₃t₁)=-2.4，EU(d₂s₃t₂)=0，

表2存储所有可能组合的文件F_T

表3存储所有策略的文件F_strategy