田 仲，李加祥

(海軍大連艦艇學(xué)院，遼寧 大連 116018)

影響網(wǎng)絡(luò)(Influence Nets，INs)已經(jīng)廣泛應(yīng)用于基于效果作戰(zhàn)(Effects-Based Operations，EBO)領(lǐng)域的相關(guān)試驗(yàn)［1］。其主要功能是輔助建模人員對不確定的環(huán)境中作戰(zhàn)行動和效果之間的因果影響關(guān)系進(jìn)行建模和分析，從而建立特定環(huán)境下各元素之間的定性與定量關(guān)系［2-3］。INs建模的主要目的是為了對一系列作戰(zhàn)行動方案(Course Of Actions，COA)進(jìn)行評估和優(yōu)選，從而獲得最有可能達(dá)成期望效果的行動方案。

目前，INs中行動方案優(yōu)選的常用方法是窮舉搜索法和靈敏度分析法。窮舉搜索法需要遍歷整個方案空間，雖然理論上一定能夠找到最優(yōu)方案，但所需的搜索時(shí)間也將隨可行行動個數(shù)的增加而成指數(shù)增長，所以只能適用于可行行動數(shù)量較少的情況，當(dāng)可行行動數(shù)量較多時(shí)，該方法將無法有效應(yīng)用。靈敏度分析法通過對單個可行行動對期望效果的影響來判定該行動對期望效果的靈敏度，從而進(jìn)一步確定較優(yōu)(不一定是最優(yōu))的行動方案。該方法執(zhí)行效率較高，但是僅從單個可行行動的角度進(jìn)行分析，并沒有考慮行動之間的相互關(guān)系，難免會造成最終結(jié)果的不合理。為了克服上述方法的不足，本文提出了一種適用于INs的基于貪婪算法的行動方案優(yōu)選方法。

1 影響網(wǎng)絡(luò)模型

影響網(wǎng)絡(luò)在拓?fù)浣Y(jié)構(gòu)上是一個有向無環(huán)圖，圖中的節(jié)點(diǎn)表示隨機(jī)變量，節(jié)點(diǎn)之間的有向邊表示變量之間的因果影響關(guān)系。INs作為貝葉斯網(wǎng)絡(luò)(Bayesian Networks，BNs)的一種變體，是不確定情況下因果影響關(guān)系建模的常用概率網(wǎng)絡(luò)，現(xiàn)已經(jīng)廣泛應(yīng)用于人工智能領(lǐng)域，解決了BNs存在的大量條件概率獲取困難和概率推理困難［4］。INs采用因果強(qiáng)度邏輯［5-6］(Causal Strength Logic，CAST Logic)作為知識獲取界面，通過CAST參數(shù)可以轉(zhuǎn)換為所需的條件概率表，從而支持概率推理。INs具有以下特點(diǎn):1)影響網(wǎng)的節(jié)點(diǎn)由一系列隨機(jī)變量組成，所有變量都具有二進(jìn)制特性;2)各節(jié)點(diǎn)之間通過有向邊聯(lián)接;3)每條邊都對應(yīng)一組CAST參數(shù)(h，g)，該參數(shù)表示聯(lián)接節(jié)點(diǎn)之間的影響強(qiáng)度;4)每個非根節(jié)點(diǎn)都有相應(yīng)的基準(zhǔn)概率，而每個根節(jié)點(diǎn)都有相應(yīng)的先驗(yàn)概率。

INs定義如下:

影響網(wǎng)絡(luò)可以描述為以下四元組 (V，E，C，B)，其中，V表示節(jié)點(diǎn)的集合，E表示有向邊的集合，C表示節(jié)點(diǎn)之間的影響強(qiáng)度集合，E→{(h，g)，－1≤h，g≤1}，B表示隨機(jī)變量的基準(zhǔn)概率和先驗(yàn)概率集合，其中V →［0，1］。

基于效果作戰(zhàn)中因果影響關(guān)系建模是通過對一系列作戰(zhàn)行動和期望效果之間的因果關(guān)系進(jìn)行描述來完成的。可行行動(事件)在TIN中表示為根節(jié)點(diǎn)(沒有輸入節(jié)點(diǎn))，決策者的期望效果(或目標(biāo))表示為葉節(jié)點(diǎn)(沒有輸出的節(jié)點(diǎn))。根節(jié)點(diǎn)用直角方框表示，而非根節(jié)點(diǎn)則用圓角方框表示。行動之間影響強(qiáng)度用CAST邏輯參數(shù)(h，g)表示，其中，h表示當(dāng)父節(jié)點(diǎn)對應(yīng)隨機(jī)變量取值為1時(shí)對子節(jié)點(diǎn)對應(yīng)隨機(jī)變量取值為1的影響強(qiáng)度，g表示當(dāng)父節(jié)點(diǎn)對應(yīng)隨機(jī)變量取值為0時(shí)對子節(jié)點(diǎn)對應(yīng)隨機(jī)變量取值為1的影響強(qiáng)度。如果h＞0并且g≤0，那么表示父節(jié)點(diǎn)對子節(jié)點(diǎn)具有促進(jìn)影響作用，用有向尖箭頭表示;如果h≤0并且 g＞0，那么表示父節(jié)點(diǎn)對子節(jié)點(diǎn)具有抑制影響作用，用有向圓箭頭表示。如圖1所示，節(jié)點(diǎn)A，B，C代表可行行動，X代表效果節(jié)點(diǎn)(目標(biāo)節(jié)點(diǎn))。行動A的執(zhí)行對效果X有促進(jìn)影響作用，而行動B的執(zhí)行對效果X有抑制作用，h和g的值表示影響強(qiáng)度的大小用。

圖1 一個簡單的影響網(wǎng)絡(luò)

下面以一個影響網(wǎng)絡(luò)為例，分別采用靈敏度分析方法和基于貪婪算法的優(yōu)選方法對COA進(jìn)行優(yōu)選。

2 靈敏度分析方法

本文給定的影響網(wǎng)絡(luò)模型如圖2所示，每條邊對應(yīng)一組CAST參數(shù)，通過這些參數(shù)可轉(zhuǎn)換為所需的條件概率表，從而支持概率推理，轉(zhuǎn)換算法請參考文獻(xiàn)［4，5］。在該INs中，所有可行行動的先驗(yàn)概率設(shè)置為0．1，所有事件的基準(zhǔn)概率設(shè)置為0．5。

靈敏度分析算法如表1所示，該算法從所有可行行動(A-H)中依次選擇單個行動a，將a的先驗(yàn)概率設(shè)置為0和1，其余行動先驗(yàn)概率保持不變，分別計(jì)算兩種情況下期望效果的概率值P(E0)和P(E1)，由此得到效果概率差值Diff(a)，差值絕對值較大所對應(yīng)的行動a被認(rèn)為對期望效果有較大的影響，靈敏度分析計(jì)算結(jié)果如表2所示。

圖2 影響網(wǎng)絡(luò)模型

表1 靈敏度分析算法

表2 靈敏度分析結(jié)果

假設(shè)決策人員認(rèn)為事件“O”的發(fā)生的概率越大越好，則可行行動C，E和H將被選擇作為行動方案的元素進(jìn)行進(jìn)一步評估，因?yàn)樗鼈兊膱?zhí)行使得“O”發(fā)生的概率增加。而從結(jié)果中可以得知，實(shí)際情況則是可行行動C，D，E和H的同時(shí)執(zhí)行使得“O”的發(fā)生概率最大。造成這種偏差的原因在于靈敏度分析方法僅考察了單個行動對期望效果的影響，而忽視了各行動之間的相互聯(lián)系。行動方案是由多個可行行動組合而成的，單個行動的執(zhí)行雖然可能降低期望效果的概率值，但是該行動和其它行動的組合執(zhí)行卻能在整體上提高期望效果的概率值，因此，靈敏度分析方法的特點(diǎn)使得在處理上述問題時(shí)所得的結(jié)果不一定合理。

3 基于貪婪算法的行動方案優(yōu)選方法

貪婪算法(Greedy Algorithm)是一種尋求最優(yōu)解問題簡單、快速的設(shè)計(jì)技術(shù)。該算法的特點(diǎn)是分多個階段依次進(jìn)行，每一階段中都尋求當(dāng)前情況下的局部最優(yōu)解，并以迭代的方式做出相繼的貪婪選擇，每做一次選擇就將求解的問題簡化為一個規(guī)模更小的子問題，最終可以得到問題的一個整體最優(yōu)解或者是整體最優(yōu)解的近似解?；谪澙匪惴ǖ男袆臃桨竷?yōu)選方法如表3所示，該方法從行動組合的角度出發(fā)，考慮了各行動之間的相互關(guān)系，每次迭代都選取當(dāng)前階段最優(yōu)的行動組合，從而快速找到最有可能達(dá)成期望效果的可行行動方案集合。

本文給定的影響網(wǎng)絡(luò)模型如圖2所示，指定效果概率閾值t=0．8。算法開始首先將所選行動集合S設(shè)置為null，接下來將所有可行行動的先驗(yàn)概率設(shè)置為0，計(jì)算期望事件“O”的邊緣概率P(O)=0．63。然后依次將每一個所選行動的先驗(yàn)概率設(shè)置為1，其余行動的先驗(yàn)概率設(shè)置為0，計(jì)算“O”的效果概率差值。例如，當(dāng)P(A)為1時(shí)，其余所有行動的先驗(yàn)概率為0，此時(shí)P(O)為0．51，說明A的執(zhí)行降低了“O”的效果值，其差值為0．12(0．63-0．51)。同理，可計(jì)算出其余結(jié)果如表4中第1列所示，可以看出，當(dāng)行動H為True其余行動為False時(shí)，P(O)具有最大值0．78。因此，按照表3中算法步驟5，將 H從 A中去除并加入 S，令 H為 True，P(O)=0．78，轉(zhuǎn)入步驟4進(jìn)行下一次迭代。第二次迭代計(jì)算結(jié)果如表4中第2列所示，可以看出，當(dāng)H和C執(zhí)行，而其余行動不執(zhí)行的情況下“O”的效果概率值最大，并比H單獨(dú)執(zhí)行時(shí)有所增加，說明該行動組合將有助于期望效果的提高。由于P(O)=0．84＞t，也說明該行動組合是一組可行的行動方案。將C從A中去除并加入 S，令 H，C 為 True，P(O)=0．84，然后轉(zhuǎn)入下一次迭代。

表3 基于貪婪算法的行動方案優(yōu)選方法

表4 基于貪婪算法的優(yōu)選方法結(jié)果

重復(fù)迭代過程直至計(jì)算結(jié)束，剩余計(jì)算結(jié)果如表4中3-6列所示。值得注意的是第5列的情況，當(dāng)H，C，E，D 執(zhí)行，其余行動為不執(zhí)行時(shí) P(O)=0．89，在此種情況下，雖然剩余任何行動(A，B，F(xiàn)，G)的執(zhí)行都無法再次提高P(O)，但是所選行動集合中加入B后P(O)=0．85 ＞ t，說明 H、C、E、D、B 執(zhí)行，A、F、G 不執(zhí)行時(shí)的行動組合也是一組可行的行動方案，因此B也被加入S，并進(jìn)行下一次迭代。如表5所示，在整個迭代過程中，共得到了5組可行方案，其中“﹁”表示“非”，例如，﹁A表示不執(zhí)行行動A，而C則表示執(zhí)行行動C。

表5 可行行動方案集合

上例如果采用窮舉搜索方法遍歷整個解空間，需要搜索28=256種可能的行動組合，最終可得到所有6組可行方案。而如表4中所示，采用本文提出的方法只需要搜索33種行動組合就找到了6組可行方案中的5組。通常情況下，如果可行行動的數(shù)目為n，該算法最多只需進(jìn)行n(n+1)/2次迭代就可找到一組較優(yōu)的行動方案，在保證搜索質(zhì)量的同時(shí)也大量減少了搜索時(shí)間。

4 結(jié)束語

本文針對影響網(wǎng)絡(luò)中現(xiàn)有方法在行動方案優(yōu)選問題時(shí)存在的不足，提出了一種基于貪婪算法的行動方案優(yōu)選方法。該方法可以快速從一系列可行行動組合中找到達(dá)成期望效果概率值滿足指定概率閾值的可行行動方案集合，增強(qiáng)了影響網(wǎng)絡(luò)建模的分析能力，并有效支持行動方案的優(yōu)選。

［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．