基于貪婪算法的影響網(wǎng)絡(luò)行動(dòng)方案優(yōu)選

田 仲，李加祥

(海軍大連艦艇學(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］。其主要功能是輔助建模人員對(duì)不確定的環(huán)境中作戰(zhàn)行動(dòng)和效果之間的因果影響關(guān)系進(jìn)行建模和分析，從而建立特定環(huán)境下各元素之間的定性與定量關(guān)系［2-3］。INs建模的主要目的是為了對(duì)一系列作戰(zhàn)行動(dòng)方案(Course Of Actions，COA)進(jìn)行評(píng)估和優(yōu)選，從而獲得最有可能達(dá)成期望效果的行動(dòng)方案。

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

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

影響網(wǎng)絡(luò)在拓?fù)浣Y(jié)構(gòu)上是一個(gè)有向無(wú)環(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)作為知識(shí)獲取界面，通過(guò)CAST參數(shù)可以轉(zhuǎn)換為所需的條件概率表，從而支持概率推理。INs具有以下特點(diǎn):1)影響網(wǎng)的節(jié)點(diǎn)由一系列隨機(jī)變量組成，所有變量都具有二進(jìn)制特性;2)各節(jié)點(diǎn)之間通過(guò)有向邊聯(lián)接;3)每條邊都對(duì)應(yīng)一組CAST參數(shù)(h，g)，該參數(shù)表示聯(lián)接節(jié)點(diǎn)之間的影響強(qiáng)度;4)每個(gè)非根節(jié)點(diǎn)都有相應(yīng)的基準(zhǔn)概率，而每個(gè)根節(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)系建模是通過(guò)對(duì)一系列作戰(zhàn)行動(dòng)和期望效果之間的因果關(guān)系進(jìn)行描述來(lái)完成的?？尚行袆?dòng)(事件)在TIN中表示為根節(jié)點(diǎn)(沒(méi)有輸入節(jié)點(diǎn))，決策者的期望效果(或目標(biāo))表示為葉節(jié)點(diǎn)(沒(méi)有輸出的節(jié)點(diǎn))。根節(jié)點(diǎn)用直角方框表示，而非根節(jié)點(diǎn)則用圓角方框表示。行動(dòng)之間影響強(qiáng)度用CAST邏輯參數(shù)(h，g)表示，其中，h表示當(dāng)父節(jié)點(diǎn)對(duì)應(yīng)隨機(jī)變量取值為1時(shí)對(duì)子節(jié)點(diǎn)對(duì)應(yīng)隨機(jī)變量取值為1的影響強(qiáng)度，g表示當(dāng)父節(jié)點(diǎn)對(duì)應(yīng)隨機(jī)變量取值為0時(shí)對(duì)子節(jié)點(diǎn)對(duì)應(yīng)隨機(jī)變量取值為1的影響強(qiáng)度。如果h＞0并且g≤0，那么表示父節(jié)點(diǎn)對(duì)子節(jié)點(diǎn)具有促進(jìn)影響作用，用有向尖箭頭表示;如果h≤0并且 g＞0，那么表示父節(jié)點(diǎn)對(duì)子節(jié)點(diǎn)具有抑制影響作用，用有向圓箭頭表示。如圖1所示，節(jié)點(diǎn)A，B，C代表可行行動(dòng)，X代表效果節(jié)點(diǎn)(目標(biāo)節(jié)點(diǎn))。行動(dòng)A的執(zhí)行對(duì)效果X有促進(jìn)影響作用，而行動(dòng)B的執(zhí)行對(duì)效果X有抑制作用，h和g的值表示影響強(qiáng)度的大小用。

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

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

2 靈敏度分析方法

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

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

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

表1 靈敏度分析算法

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

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

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

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

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

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

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

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

表5 可行行動(dòng)方案集合

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

4 結(jié)束語(yǔ)

本文針對(duì)影響網(wǎng)絡(luò)中現(xiàn)有方法在行動(dòng)方案優(yōu)選問(wèn)題時(shí)存在的不足，提出了一種基于貪婪算法的行動(dòng)方案優(yōu)選方法。該方法可以快速?gòu)囊幌盗锌尚行袆?dòng)組合中找到達(dá)成期望效果概率值滿(mǎn)足指定概率閾值的可行行動(dòng)方案集合，增強(qiáng)了影響網(wǎng)絡(luò)建模的分析能力，并有效支持行動(dòng)方案的優(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．