決策策略選擇（決策策略選擇）

基本概述

近年來(lái)，隨著互聯(lián)網(wǎng)上Web 服務(wù)的大量出現(xiàn)，提供相同功能的Web 服務(wù)也越來(lái)越多，但這些Web 服務(wù)在非功能屬性上仍然存在差別。如何在這些服務(wù)中進(jìn)行合理的選擇，對(duì)成功地構(gòu)建面向服務(wù)應(yīng)用(service oriented applications)具有非常重要的意義，是一個(gè)極具挑戰(zhàn)性的問(wèn)題。

目前，針對(duì)Web 服務(wù)選擇的研究，大都是基于QoS (quality of service)模型的。QoS 的性能指標(biāo)包括執(zhí)行時(shí)間、費(fèi)用、服務(wù)可靠性、有效性、用戶(hù)滿(mǎn)意度等，此外，還可能有一些特定領(lǐng)域的其他屬性。一個(gè)用戶(hù)可決定挑選最便宜的或最快的服務(wù)，或者是多QoS 目標(biāo)的折中。文獻(xiàn)[4]根據(jù)工作流任務(wù)的結(jié)構(gòu)特點(diǎn)對(duì)其進(jìn)行分區(qū)，按照任務(wù)量和通信量將總工作流截止日期和總工作流花費(fèi)分為每個(gè)任務(wù)分區(qū)上的子截止日期和子花費(fèi)，在考慮用戶(hù)多個(gè)QoS 要求及工作流任務(wù)間通信時(shí)間的基礎(chǔ)上，提出基于信任與花費(fèi)的綜合效益函數(shù)，給出信任與花費(fèi)權(quán)值的確定方法以及一個(gè)以綜合效益最優(yōu)為目標(biāo)的調(diào)度算法—TCD，算法通過(guò)追求局部最優(yōu)達(dá)到全局多目標(biāo)優(yōu)化調(diào)度。文獻(xiàn)[6]提出了一個(gè)在滿(mǎn)足截止日期的約束下追求最小花費(fèi)或在滿(mǎn)足花費(fèi)的約束下追求最短執(zhí)行時(shí)間的單目標(biāo)優(yōu)化調(diào)度算法。還有的方法，生硬地為QoS 的各個(gè)性能指標(biāo)賦予相應(yīng)的權(quán)重，形成一個(gè)單目標(biāo)函數(shù)來(lái)求解。還有的方法以用戶(hù)的歷史經(jīng)驗(yàn)為基礎(chǔ)計(jì)算用戶(hù)之間的相似程度，根據(jù)其他用戶(hù)的經(jīng)驗(yàn)對(duì)某個(gè)用戶(hù)的決策做出指導(dǎo)。

這些方法雖然都考慮到了用戶(hù)多QoS 要求，但沒(méi)有考慮到不同用戶(hù)的不同側(cè)重點(diǎn)，如：有的用戶(hù)寧愿花費(fèi)更多的錢(qián)去享受更快的Web 服務(wù)；有的用戶(hù)不在乎服務(wù)的快慢，但希望花費(fèi)少些；有的用戶(hù)更加注重該服務(wù)的口碑（用戶(hù)滿(mǎn)意度）等。

基于貝葉斯決策的多QoS 目標(biāo)的Web 服務(wù)選擇策略是在已有的具有相同功能的服務(wù)集的基礎(chǔ)上，選擇最可能讓自己滿(mǎn)意的一個(gè)Web 服務(wù)來(lái)執(zhí)行。該策略將機(jī)器學(xué)習(xí)領(lǐng)域的經(jīng)典方法：貝葉斯決策理論，運(yùn)用到Web 服務(wù)的選擇中來(lái)，可以充分利用用戶(hù)自己的經(jīng)驗(yàn)庫(kù)（即自己曾經(jīng)選擇的Web 服務(wù)的QoS 信息及是否令自己滿(mǎn)意），學(xué)習(xí)自己以往的經(jīng)驗(yàn)，做出更可能讓用戶(hù)滿(mǎn)意的選擇。

不同的用戶(hù)眼中的最優(yōu)Web 服務(wù)是不同的，有的用戶(hù)更在乎執(zhí)行時(shí)間，有的用戶(hù)更在乎費(fèi)用，有的用戶(hù)更在乎服務(wù)的用戶(hù)滿(mǎn)意度。但對(duì)于同一個(gè)用戶(hù)來(lái)說(shuō)，它的興趣一定遵循同一概率分布的。用戶(hù)曾經(jīng)選擇的 Web 服務(wù)及當(dāng)時(shí)對(duì)該服務(wù)是否滿(mǎn)意的集合，即“經(jīng)驗(yàn)庫(kù)”中隱含著自己的偏好信息。基于貝葉斯決策的多QoS 目標(biāo)的Web 服務(wù)選擇策略，利用貝葉斯決策理論，在用戶(hù)自己的經(jīng)驗(yàn)庫(kù)中進(jìn)行學(xué)習(xí)，進(jìn)而做出更可能讓用戶(hù)滿(mǎn)意的選擇。

2.1貝葉斯理論介紹

貝葉斯理論是一種運(yùn)用概率手段來(lái)進(jìn)行推理的方法，被廣泛用于機(jī)器學(xué)習(xí)領(lǐng)域。它基于如下的假定，即待考查的量遵循某概率分布，且可根據(jù)這些概率及已觀察到的數(shù)據(jù)進(jìn)行推理，以作出最優(yōu)的決策。它通過(guò)對(duì)已知分類(lèi)數(shù)據(jù)的學(xué)習(xí)，來(lái)預(yù)測(cè)訓(xùn)練數(shù)據(jù)的分類(lèi)。作為一種基于概率的統(tǒng)計(jì)學(xué)習(xí)和決策理論框架內(nèi)的基礎(chǔ)方法，貝葉斯理論已得到了廣泛的應(yīng)用。

2.2 模型的建立

該方法以消費(fèi)者的歷史經(jīng)驗(yàn)為基礎(chǔ)，通過(guò)概率統(tǒng)計(jì)的手段，計(jì)算出消費(fèi)者并未使用過(guò)的Web 服務(wù)能讓自己的滿(mǎn)意程度。基于貝葉斯決策的多QoS 目標(biāo)的Web 服務(wù)選擇策略的過(guò)程如圖1 所示，主要分為以下幾部分。

（1）當(dāng)用戶(hù)要執(zhí)行某個(gè)活動(dòng)時(shí), 首先列出這個(gè)活動(dòng)對(duì)應(yīng)的所有具有相同功能的Web 服務(wù)以及各服務(wù)的QoS 性能指標(biāo)。.

（2）利用貝葉斯決策模型和自己的經(jīng)驗(yàn)庫(kù)，計(jì)算各個(gè)Web 服務(wù)可能讓自己滿(mǎn)意的概率。

（3）挑選其中讓自己滿(mǎn)意概率最大的Web 服務(wù)。

（4）選擇該Web 服務(wù)，執(zhí)行。

（5）執(zhí)行結(jié)束，留下自己的反饋意見(jiàn)（滿(mǎn)意或不滿(mǎn)意）。將該服務(wù)的QoS 性能指標(biāo)，以及自己的反饋意見(jiàn)（是否滿(mǎn)意）存入自己的經(jīng)驗(yàn)庫(kù)中，將相關(guān)信息提交給“服務(wù)管理中心”，更新該服務(wù)的QoS性能指標(biāo)。

首先，該模型基于機(jī)器學(xué)習(xí)領(lǐng)域的經(jīng)典方法：貝葉斯理論。該方法有嚴(yán)密的推導(dǎo)和證明，已被廣泛的應(yīng)用于多個(gè)領(lǐng)域。所以該模型的理論基礎(chǔ)是非常堅(jiān)實(shí)的。

其次，選擇Web 服務(wù)時(shí)，不需要用戶(hù)的介入。需要用戶(hù)做的工作僅僅是在Web 服務(wù)執(zhí)行完了以后，作出評(píng)價(jià)（“滿(mǎn)意”或“不滿(mǎn)意”）。所以該模型更具有智能性。

最后，該模型是一個(gè)動(dòng)態(tài)的模型，隨著時(shí)間的推移，如果用戶(hù)的偏好慢慢發(fā)生變化，該模型所做出的抉擇也會(huì)根據(jù)用戶(hù)經(jīng)驗(yàn)庫(kù)的更新慢慢偏移。

面對(duì)眾多功能相同，但在非功能屬性上仍然存在差別的Web 服務(wù)，如何進(jìn)行合理的選擇，對(duì)成功地構(gòu)建面向服務(wù)應(yīng)用具有非常重要的意義。本文在總結(jié)了當(dāng)前基于多QoS 目標(biāo)的Web 服務(wù)選擇策略發(fā)展現(xiàn)狀的基礎(chǔ)上，介紹了一種基于貝葉斯的多QoS 目標(biāo)的Web 服務(wù)選擇策略。該方法具有理論基礎(chǔ)堅(jiān)實(shí)、智能性、動(dòng)態(tài)性的優(yōu)點(diǎn)。

基于馬爾科夫決策的決策策略選擇

概述

目標(biāo)選擇是軍事決策過(guò)程的重要組成部分，現(xiàn)代戰(zhàn)爭(zhēng)中的目標(biāo)選擇問(wèn)題要置于打擊目標(biāo)體系的作戰(zhàn)過(guò)程中分析。目標(biāo)體系( Target System of System，TSoS) 是由多個(gè)作戰(zhàn)系統(tǒng)構(gòu)成的集合，每個(gè)作戰(zhàn)系統(tǒng)實(shí)現(xiàn)一定任務(wù)并對(duì)體系使命產(chǎn)生影響。打擊目標(biāo)體系的目的是使體系崩潰，打擊過(guò)程由于存在資源約束等原因被劃分為多個(gè)階段，因此如何打擊目標(biāo)體系是具有復(fù)雜目標(biāo)關(guān)聯(lián)的多階段目標(biāo)選擇問(wèn)題。傳統(tǒng)目標(biāo)選擇方法多是通過(guò)層次分析法等對(duì)目標(biāo)進(jìn)行評(píng)估和排序，沒(méi)多屬性決策理論有考慮目標(biāo)間復(fù)雜關(guān)聯(lián)，為處理該問(wèn)題，目前主要采用貝葉斯網(wǎng)絡(luò)描述目標(biāo)體系內(nèi)影響關(guān)聯(lián)。故障樹(shù)方法但以上方法均未考慮目標(biāo)選擇的多階段決策特征，沒(méi)有利用行動(dòng)中間結(jié)果調(diào)整目標(biāo)。目標(biāo)選擇的動(dòng)態(tài)性在動(dòng)態(tài)武器目標(biāo)分配問(wèn)題和軍事行動(dòng)規(guī)劃問(wèn)題中得到研究。蔡懷平等研究了動(dòng)態(tài)武器目標(biāo)分配問(wèn)題中的馬爾科夫性，解武杰等 將馬爾可夫過(guò)程用于分析防空武器目標(biāo)選擇策略; Boutilier 等在馬爾科夫決策過(guò)程(Markov Decision Process，MDP) 基礎(chǔ)上提出決策理論規(guī)劃方法 對(duì)具有階段決策的軍事行動(dòng)進(jìn)行建模 但沒(méi)有考慮目標(biāo)關(guān)聯(lián)和相應(yīng)的復(fù)雜打擊效果，不能直接用于求解打擊目標(biāo)體系過(guò)程中的目標(biāo)選擇問(wèn)題。陽(yáng)東升等 利用動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)描述了戰(zhàn)場(chǎng)重心及作戰(zhàn)行動(dòng)間影響關(guān)系，但搜索空間很大時(shí)求解效率不高，王長(zhǎng)春等用復(fù)雜網(wǎng)絡(luò)仿真方法分析體系對(duì)抗過(guò)程，但是建模過(guò)程較復(fù)雜。

1 目標(biāo)選擇問(wèn)題描述

為分析目標(biāo)選擇問(wèn)題，需分析打擊目標(biāo)對(duì)目標(biāo)體系狀態(tài)的影響。與或樹(shù)使用圖形化能將復(fù)雜問(wèn)題分解為多個(gè)簡(jiǎn)單子問(wèn)題，因此使用與或樹(shù)描述體系中狀態(tài)間的影響關(guān)系。目標(biāo)體系的狀態(tài)包括三類(lèi)要素狀態(tài): 目標(biāo)單元狀態(tài) GT 、目標(biāo)系統(tǒng)能力狀態(tài) GN 和目標(biāo)體系能力狀態(tài) GS 。目標(biāo)單元是目標(biāo)體系中最基礎(chǔ)的要素，能被直接摧毀，如單部雷達(dá)，其狀態(tài)用葉節(jié)點(diǎn)集 GT ={ gTi } ( 1≤i≤I) 描述，I 為目標(biāo)單元數(shù)量，單元?dú)?，gTi = 1; 單元正常，gTi = 0。目標(biāo)系統(tǒng)是多個(gè)目標(biāo)單元或子系統(tǒng)的集合，之間相互關(guān)聯(lián)，顯現(xiàn)某種作戰(zhàn)能力，如預(yù)警能力。其狀態(tài)用非終端節(jié)點(diǎn)集 GN = { gNj } ( 1 ≤j ≤J) 描述，J 為目標(biāo)系統(tǒng)數(shù)量，系統(tǒng)能完成任務(wù)，gNj = 1; 不能完成任務(wù)，gNj = 0。其包含的目標(biāo)單元和子系統(tǒng)能力狀態(tài)作為其在與或樹(shù)中子節(jié)點(diǎn)，通過(guò)邏輯與、或關(guān)系，對(duì)系統(tǒng)能力狀態(tài)產(chǎn)生影響。

目標(biāo)體系是多個(gè)目標(biāo)系統(tǒng)的集合，體現(xiàn)出支持某個(gè)使命的能力，如防空使命能力。體系能力狀態(tài)使用根節(jié)點(diǎn) GS 描述，體系能達(dá)成使命，GS =1; 不能達(dá)成，GS = 0。其包含的各目標(biāo)系統(tǒng)能力作為其子節(jié)點(diǎn)，通過(guò)邏輯與、或關(guān)系對(duì)體系能力狀態(tài)產(chǎn)生影響。

2目標(biāo)選擇過(guò)程建模

2． 1 問(wèn)題假設(shè)

(1) 打擊目標(biāo)體系過(guò)程分為若干個(gè)作戰(zhàn)階段，使用有限資源，目的是使體系失效;

(2) 目標(biāo)體系狀態(tài)為進(jìn)攻方完全感知，目標(biāo)選擇決策僅與當(dāng)前階段狀態(tài)有關(guān)，在當(dāng)前狀態(tài)被觀察后，進(jìn)攻方選擇打擊目標(biāo);

(3) 打擊每個(gè)目標(biāo)具有一定成功概率，消耗一定資源，每個(gè)階段打擊多個(gè)目標(biāo)，使得目標(biāo)體系狀態(tài)在下一階段發(fā)生概率遷移。

2． 2 目標(biāo)選擇決策模型

在符合以上假設(shè)時(shí)，打擊過(guò)程中目標(biāo)體系狀態(tài)的變化可認(rèn)為是一個(gè)離散時(shí)間隨機(jī)過(guò)程，其變化過(guò)程的狀態(tài)轉(zhuǎn)移概率由打擊目標(biāo)行動(dòng)所控制，因此目標(biāo)選擇決策成為一個(gè)離散時(shí)間馬爾科夫決策過(guò)程，其最優(yōu)決策就是每階段要選擇打擊哪些目標(biāo)，使目標(biāo)體系失效的概率最大化。本文使用 DTMDP 模型描述打擊目標(biāo)體系的目標(biāo)選擇決策過(guò)程，即以下多元組:S是有限狀態(tài)集，S = { ( t，R，G) } ，t 指當(dāng)前第t階段，R = ( R1 ，…，Rk ，…，RK ) 描述資源的狀態(tài)向量，Rk 為第 k 類(lèi)資源數(shù)量，G = ( g1T ，…，gTI ，g1N ，…，gNJ ，GS ) ，表示體系的狀態(tài)向量。S0 是初始狀態(tài)。ST 是終止?fàn)顟B(tài)集，對(duì)應(yīng)于資源、時(shí)間消耗完畢，或目標(biāo)體系失效的狀態(tài)，在此狀態(tài)下打擊過(guò)程結(jié)束。A是所有行動(dòng)組成的有限集，A( s) 是在狀態(tài) s下可采取的行動(dòng)集，a A( s) 包含多個(gè)目標(biāo)單元打擊任務(wù) { Taski } ( 1 ≤i ≤I) ，Taski 成功概率為Pi ，即 Pi ( GTi = 1 | Taski ) = Pi 。若 Rk ( s，Taski ) 表示Taski 在狀態(tài) s 下消耗第 k 種資源的數(shù)量，Lk 表示第 k 種資源在每階段的最大允許使用數(shù)量，是在可用行動(dòng) a 下?tīng)顟B(tài)轉(zhuǎn)移 s→s'的概率函數(shù)，表示在打擊行動(dòng) a 下，狀態(tài)在下一階段變化的可能性。

2．3 模型復(fù)雜度分析

打擊目標(biāo)體系過(guò)程中的目標(biāo)選擇模型和以往基于MDP 的目標(biāo)選擇或軍事計(jì)劃模型 存在著以下區(qū)別:

(1)問(wèn)題假設(shè)不同。以往模型中假設(shè)目標(biāo)間無(wú)關(guān)聯(lián)，而本模型假設(shè)目標(biāo)間相互影響;

(2)終止?fàn)顟B(tài)不同。以往模型是以最大化毀傷目標(biāo)為期望值，而本模型是以達(dá)成目標(biāo)體系失效為目的;

(3)狀態(tài)空間不同。以往模型的狀態(tài)空間是所有目標(biāo)的狀態(tài)，而本模型的狀態(tài)空間包含了目標(biāo)單元、系統(tǒng)能力、體系能力三類(lèi)要素狀態(tài)，使得狀態(tài)空間復(fù)雜度增加;

(4)時(shí)間尺度不同。以行動(dòng)階段而非具體時(shí)間來(lái)描述打擊目標(biāo)體系過(guò)程，并假設(shè)行動(dòng)能夠在單階段內(nèi)完成，簡(jiǎn)化了行動(dòng)空間描述;

(5)狀態(tài)遷移函數(shù)不同。以往模型只需計(jì)算各目標(biāo)的狀態(tài)遷移，而本模型中的狀態(tài)遷移還需考慮不同層次間要素的狀態(tài)影響關(guān)系。

3求解算法

3． 1 求解框架

本問(wèn)題狀態(tài)空間巨大，并且只關(guān)注求解從目標(biāo)體系初始狀態(tài)到達(dá)終止?fàn)顟B(tài)的行動(dòng)策略，而 MDP 值迭代或策略迭代方法需對(duì)全狀態(tài)空間進(jìn)行遍歷，因此求解效率較低，這就需要使用啟發(fā)式搜索算法來(lái)求解。RTDP ( Real Time Dynamic Programming) [18] 的 改 進(jìn) 算 法 LRTDP ( LabeledRTDP) 方法要比其他如 LAO* 等求解 MDP 的啟發(fā)式搜索算法要更有效率 因此本文使用LRTDP 方法求解該模型。

RTDP 是基于試驗(yàn)( trials-based) 的方法，每次試驗(yàn)從初始狀態(tài)開(kāi)始，基于當(dāng)前狀態(tài)值的啟發(fā)式，根據(jù)貪婪策略選擇行動(dòng)，然后根據(jù)行動(dòng)的概率結(jié)果隨機(jī)創(chuàng)建后續(xù)狀態(tài)，直至到達(dá)目的狀態(tài)，然后進(jìn)行反向值迭代。

3． 2 啟發(fā)式

設(shè)計(jì)了基于行動(dòng)成功概率、行動(dòng)執(zhí)行時(shí)間和資源邊界的啟發(fā)式提供對(duì) V0 ( S) 的最佳估計(jì)值，使得對(duì)所有狀態(tài) s，V0 ( S) V( S) ，以促進(jìn)LRTDP 中算法的收斂，但由于打擊目標(biāo)體系過(guò)程中的目標(biāo)選擇模型和傳統(tǒng)規(guī)劃模型在狀態(tài)空間、遷移函數(shù)上的區(qū)別，該啟發(fā)式不能直接應(yīng)用于前者。針對(duì)打擊目標(biāo)體系過(guò)程特點(diǎn)，分別設(shè)計(jì)新的啟發(fā)式來(lái)計(jì)算從目標(biāo)體系當(dāng)前狀態(tài) S 到達(dá)目標(biāo)體系失效狀態(tài)的最小失敗概率 minV( S，fail) 和最小資源消耗需求 minV ( S，resource) ，并進(jìn)行加權(quán)組合，以得到對(duì) V0 ( S) 的最佳估計(jì)值。啟發(fā)式考慮了時(shí)間代價(jià)不同，由于打擊目標(biāo)的時(shí)間消耗為單個(gè)階段，從當(dāng)前狀態(tài)到達(dá)目標(biāo)體系失效狀態(tài)的最小時(shí)間消耗需求 minV( S，time) 總是為單個(gè)階段，因此在新啟發(fā)式中沒(méi)有考慮時(shí)間代價(jià)。

( 1) 到達(dá)目標(biāo)體系能力失效狀態(tài)的最小失敗概率為判斷從當(dāng)前狀態(tài)到達(dá)體系失效狀態(tài)的最小失敗概率，先求得最大成功概率，即從當(dāng)前狀態(tài)下預(yù)期能采取的所有打擊目標(biāo)行動(dòng)能夠達(dá)成的體系失效概率。當(dāng)目標(biāo)體系與或樹(shù)中非葉子節(jié)點(diǎn) g 具有子節(jié)點(diǎn)集 SG = { sgk } ( 1 ≤k ≤K) ( K 為子節(jié)點(diǎn)數(shù)量)時(shí)，其中 Prok 表示使得第 k 個(gè)子節(jié)點(diǎn)失效的最大成功概率，sgk 描述第 k 個(gè)子節(jié)點(diǎn)是否失效，失效時(shí)取 1，正常時(shí)取 0。其基本過(guò)程為:

1) 與或樹(shù)自根節(jié)點(diǎn)向下遍歷各節(jié)點(diǎn);

2) 取得各節(jié)點(diǎn)的狀態(tài)，當(dāng)節(jié)點(diǎn)狀態(tài)為失效，則該節(jié)點(diǎn)的毀傷概率為 1，當(dāng)節(jié)點(diǎn)狀態(tài)為正常，取得其所有子節(jié)點(diǎn)的失效概率值，根據(jù)子節(jié)點(diǎn)間的與或關(guān)系計(jì)算使該節(jié)點(diǎn)失效的概率值;

3) 直至遍歷至葉節(jié)點(diǎn)，獲得對(duì)應(yīng)打擊目標(biāo)行動(dòng)的成功概率( 即節(jié)點(diǎn)失效概率值) ，然后遞歸計(jì)算使根節(jié)點(diǎn)失效的成功概率值。用1 減去使根節(jié)點(diǎn)失效的最大成功概率值即得到使目標(biāo)體系失效的最小失敗概率。

(2) 到達(dá)目標(biāo)體系失效狀態(tài)的最小消耗為求解到達(dá)目標(biāo)體系失效狀態(tài)的最小消耗資源，我們假設(shè)從當(dāng)前狀態(tài)開(kāi)始，所采取的每次打擊行動(dòng)都能成功摧毀目標(biāo)。根據(jù)與或樹(shù)的結(jié)構(gòu)層次計(jì)算能夠?qū)е履繕?biāo)體系失效所需的行動(dòng)集的最小消耗資源。當(dāng)目標(biāo)體系與或樹(shù)中非葉子節(jié)點(diǎn) g 具有子節(jié)點(diǎn)集 SG = { sgk } ( 1 ≤k ≤K) ( K 為子節(jié)點(diǎn)數(shù)量)時(shí)，當(dāng) SG 為與關(guān)系時(shí)，使 g 失效的最小資源消耗Res 為：當(dāng) SG 為或關(guān)系時(shí):Res = min( { ( 1 － sgk ) ·Resk } ) ，1≤k≤K ( 14) 其中 Resk 表示使得第 k 個(gè)子節(jié)點(diǎn)失效的最小資源消耗，sgi 描述第 k 個(gè)子節(jié)點(diǎn)是否失效，失效時(shí)取 1，正常時(shí)取 0。其基本過(guò)程為:

1) 與或樹(shù)自根節(jié)點(diǎn)向下遍歷各節(jié)點(diǎn);

2) 當(dāng)節(jié)點(diǎn)狀態(tài)為失效，則該節(jié)點(diǎn)資源消耗為0，當(dāng)節(jié)點(diǎn)狀態(tài)為正常，則取得其所有子節(jié)點(diǎn)消耗資源值，根據(jù)子節(jié)點(diǎn)間與或關(guān)系綜合得到該節(jié)點(diǎn)資源消耗值;

3) 直至遍歷到葉節(jié)點(diǎn)，獲得對(duì)應(yīng)打擊目標(biāo)行動(dòng)的消耗資源，然后遞歸計(jì)算使根節(jié)點(diǎn)( 體系能力) 失效的資源消耗值。

比賽中決策策略選擇

概述

多智能體系統(tǒng)(Multi-Agent Systems, MAS)的研究是當(dāng)前人工智能領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題和重要的發(fā)展方向。足球機(jī)器人比賽已經(jīng)成了MAS 研究的一個(gè)標(biāo)準(zhǔn)平臺(tái)。機(jī)器人足球發(fā)展的宏偉目標(biāo)就是要實(shí)現(xiàn)自學(xué)習(xí)、自適應(yīng)以及具有很強(qiáng)魯棒性的實(shí)時(shí)多智能機(jī)器人系統(tǒng), 力爭(zhēng)經(jīng)過(guò)大約50年左右的發(fā)展，使機(jī)器人足球隊(duì)能夠打敗當(dāng)時(shí)人類(lèi)的世界冠軍足球隊(duì)。以Mirosot 系列機(jī)器人系統(tǒng)為例，給出了一種分層遞階控制設(shè)計(jì), 并針對(duì)在視覺(jué)子系統(tǒng)不采集對(duì)方球員信息的情況下, 提出了實(shí)力對(duì)比函數(shù)的概念, 通過(guò)這個(gè)函數(shù)實(shí)時(shí)的根據(jù)場(chǎng)上的情況判斷雙方球隊(duì)的形式變化情況, 以提高決策子系統(tǒng)的智能性。

1決策系統(tǒng)的設(shè)計(jì)

1.1決策系統(tǒng)的分析

足球機(jī)器人的決策子系統(tǒng)扮演著教練員和運(yùn)動(dòng)員的職責(zé)。在真實(shí)的綠茵場(chǎng)上, 作為教練員要根據(jù)球場(chǎng)上的實(shí)際情況來(lái)部署球員, 同時(shí)也根據(jù)不同的對(duì)手, 選擇不同的隊(duì)形。足球機(jī)器人賽場(chǎng)上，決策者也應(yīng)該根據(jù)不同的球隊(duì)采取不同的策略，對(duì)于錯(cuò)綜復(fù)雜的球場(chǎng)形勢(shì), 運(yùn)用靈活的策略。一個(gè)好的決策系統(tǒng)不可能一勞永逸地一次性開(kāi)發(fā)完成，是一個(gè)不斷完善的過(guò)程，因此，構(gòu)建一個(gè)可持續(xù)開(kāi)發(fā)、合理的決策框架就顯得尤為重要。分層遞進(jìn)控制方式對(duì)決策思路進(jìn)行邏輯上的分層。一般來(lái)說(shuō)，決策思路是先確定機(jī)器人之間的協(xié)作關(guān)系，然后根據(jù)配合的要求確定每個(gè)機(jī)器人的運(yùn)動(dòng)方式。分層的具體方式可以有一定的不同。

比賽時(shí)，視覺(jué)子系統(tǒng)每 40ms 左右將球場(chǎng)上各機(jī)器人的位姿和球的信息傳入計(jì)算機(jī) ,決策子系統(tǒng)根據(jù)傳入的視覺(jué)信息分析球場(chǎng)上的情況 , 做出相應(yīng)的決策，轉(zhuǎn)化為每個(gè)機(jī)器人的左右輪速, 通過(guò)通信子系統(tǒng)發(fā)送給每個(gè)機(jī)器人。當(dāng)決策子系統(tǒng)收到視覺(jué)輸入信息后, 對(duì)其進(jìn)行預(yù)處理, 根據(jù)球和本方機(jī)器人的位置對(duì)場(chǎng)上攻防形勢(shì)進(jìn)行分析, 并將所作的決策分解為各個(gè)任務(wù)———這是決策的第一層。根據(jù)分解完的任務(wù)從隊(duì)形庫(kù)中為本方機(jī)器人確定一個(gè)隊(duì)形———這是決策的第二層。根據(jù)隊(duì)形所需的角色以及我方機(jī)器人的位置 , 將每個(gè)角色分配給具體的機(jī)器人———這是決策的第三層。之后將左右輪速發(fā)送給對(duì)應(yīng)的每個(gè)機(jī)器人。

1 .2 決策系統(tǒng)的設(shè)計(jì)

決策系統(tǒng)的設(shè)計(jì)過(guò)程是一個(gè)由基層到高層逐步構(gòu)造的過(guò)程, 就是如何來(lái)實(shí)現(xiàn)決策系統(tǒng)分析結(jié)果?；谏鲜鲎闱驒C(jī)器人決策分析過(guò)程, 采用如下的足球機(jī)器人決策系統(tǒng)設(shè)計(jì)。

在比賽過(guò)程中 , 我們所要求小車(chē)的基本運(yùn)動(dòng)就是跑位、轉(zhuǎn)向, 繼而在此基礎(chǔ)上, 讓小車(chē)按照決策者的意圖來(lái)完成一些復(fù)雜動(dòng)作, 最后實(shí)現(xiàn)決策者的整個(gè)策略思想。本設(shè)計(jì)采用面向?qū)ο蟮某绦蛟O(shè)計(jì)把整個(gè)決策系統(tǒng)劃分 3 個(gè)類(lèi), 他們由基層到高層(即由頂?shù)降?分別為：基本動(dòng)作類(lèi)、技術(shù)動(dòng)作類(lèi)、決策類(lèi), 他們是從頂?shù)降滓来卫^承, 高層可以繼承基層, 但基層不能繼承高層, 高層類(lèi)中方法的實(shí)現(xiàn)需要基層類(lèi)中方法的支持, 基本動(dòng)作函數(shù)類(lèi)的方法完成如原地轉(zhuǎn)動(dòng)、轉(zhuǎn)到定角、轉(zhuǎn)到定點(diǎn)、到定點(diǎn)、到達(dá)定點(diǎn)有一定的速度函數(shù)等等, 其屬性是可調(diào)參數(shù)的結(jié)構(gòu)體 ;技術(shù)動(dòng)作函數(shù)類(lèi)中封裝一些比較高級(jí)的動(dòng)作, 如完成射門(mén)、防守、邊界處理等功能；組合動(dòng)作函數(shù)類(lèi)是更高層次的類(lèi), 其方法用來(lái)完成多車(chē)協(xié)作動(dòng)作, 如點(diǎn)球大戰(zhàn)、爭(zhēng)球等動(dòng)作 ; 決策類(lèi)是整個(gè)決策系統(tǒng)的最高層, 是整個(gè)決策的核心部分 ,就是用這些底層類(lèi)來(lái)實(shí)現(xiàn)決策者的意圖，如信息預(yù)處理、態(tài)勢(shì)分析、角色分配、動(dòng)作實(shí)現(xiàn)等。由上設(shè)計(jì)實(shí)現(xiàn)過(guò)程，可以看出，我們可以根據(jù)決策者不同的需求，逐步完善這些底層函數(shù)類(lèi)，各個(gè)函數(shù)類(lèi)的補(bǔ)充只是改動(dòng)本身，并不影響其他類(lèi)，從而提高了整個(gè)決策系統(tǒng)的可維護(hù)性和可擴(kuò)充性，為決策者提供了一個(gè)施展各種策略思想的平臺(tái)。

2決策策略的動(dòng)態(tài)選擇算法

實(shí)力對(duì)比函數(shù)的提出

由于決策系統(tǒng)所能得到的信息僅是由視覺(jué)系統(tǒng)傳遞來(lái)的球的位置以及本方球員的位置和方向信息，因此如何判斷對(duì)方球隊(duì)的情況則變成了是一個(gè)不容易解決的問(wèn)題。如果不對(duì)對(duì)方球隊(duì)情況進(jìn)行判斷, 無(wú)論場(chǎng)上形式如何變化我方總是采用一成不變的策略則會(huì)降低整個(gè)球隊(duì)的智能性, 本系統(tǒng)通過(guò)實(shí)力對(duì)比函數(shù)來(lái)判斷場(chǎng)上情況的變化 , 并根據(jù)不同的情況做出不同的策略選擇, 從而提高了系統(tǒng)的智能性。

3實(shí)驗(yàn)結(jié)果

在MiroSot 足球機(jī)器人系統(tǒng)中對(duì)本文提出的決策策略動(dòng)態(tài)選擇算法進(jìn)行了驗(yàn)證, 其中 Team1 在進(jìn)行決策策略選擇的時(shí)候采用傳統(tǒng)的決策策略選擇方法。Team2 ,Team3 ,Team4 也采用傳統(tǒng)的決策策略選擇方法, 并且 3 支球隊(duì)的實(shí)力一個(gè)比一個(gè)強(qiáng)(通過(guò)實(shí)驗(yàn)得出球隊(duì)的強(qiáng)弱)。比賽結(jié)果如下表1 所示:

表1 比賽結(jié)果(選用本文算法之前)

在選用的決策策略動(dòng)態(tài)選擇算法之后 ,Team1 分別對(duì) Team2 ,Team3 ,Team4 的比賽結(jié)果如表 2 所示:

從實(shí)驗(yàn)的比賽結(jié)果可以看出, 在采用了決策策略動(dòng)態(tài)選擇算法之后同樣一支球隊(duì)在和比它實(shí)力弱球隊(duì)的比賽時(shí)會(huì)加強(qiáng)進(jìn)攻從而可以大比分的戰(zhàn)勝對(duì)手, 在和它實(shí)力相當(dāng)?shù)那蜿?duì)比賽時(shí)會(huì)適當(dāng)?shù)姆峙溥M(jìn)攻和防守的比重 ,從而有機(jī)會(huì)戰(zhàn)勝對(duì)手 , 在和比自己實(shí)力強(qiáng)的球隊(duì)比賽時(shí)會(huì)加強(qiáng)防守在不輸球的情況下適時(shí)進(jìn)攻。而實(shí)現(xiàn)的, 先進(jìn)技術(shù)手段的引入可能而且應(yīng)該給企業(yè)帶來(lái)效率和效益。信息化是企業(yè)發(fā)展的必然，是重大的機(jī)遇和挑戰(zhàn) ,我們要抓住信息化帶來(lái)的機(jī)遇 ,在“信息化帶動(dòng)工業(yè)化”的國(guó)家戰(zhàn)略指導(dǎo)下，加強(qiáng)對(duì)國(guó)民經(jīng)濟(jì)與社會(huì)信息化的組織領(lǐng)導(dǎo) ,加快制定并實(shí)施國(guó)家信息化的總體規(guī)劃, 推動(dòng)經(jīng)濟(jì)與社會(huì)各個(gè)領(lǐng)域信息化的進(jìn)程。通過(guò)信息化不斷提高企業(yè)核心競(jìng)爭(zhēng)力, 強(qiáng)化綜合國(guó)力的微觀基礎(chǔ) , 這正是我國(guó)加入世貿(mào)組織、應(yīng)對(duì)經(jīng)濟(jì)全球化挑戰(zhàn)的關(guān)鍵所在。

囚徒困境下的決策策略選擇

概述

美國(guó)決策研究專(zhuān)家黑斯蒂(Hastie，R)認(rèn)為判斷與決策是人類(lèi)根據(jù)自己的愿望和信念選擇行動(dòng)的過(guò)程。決策(decision making)從狹義上說(shuō)是一個(gè)動(dòng)態(tài)過(guò)程，是個(gè)體運(yùn)用感知覺(jué)、記憶、思維等認(rèn)知能力，對(duì)情境做出選擇，確定策略的過(guò)程。廣義的決策則包含判斷與決策兩個(gè)部分。博弈論中“囚徒困境”下的決策就是一個(gè)很有代表性的例子.

囚徒困境簡(jiǎn)介及其傳統(tǒng)策略

囚徒困境也稱(chēng)社會(huì)兩難情境，是博弈論中的經(jīng)典案例，指兩個(gè)嫌疑犯被警察抓到，但警方?jīng)]有掌握確切的證據(jù)，警察就分別找他們談話(huà)：“如果你們都不認(rèn)罪的話(huà)，我們將讓你們都入獄一年；如果一個(gè)認(rèn)罪，另一個(gè)不認(rèn)罪的話(huà)，那么我們將判不認(rèn)罪的那個(gè)十年的徒刑，認(rèn)罪的將無(wú)罪釋放；如果兩人都認(rèn)罪的話(huà)，我們將基于你們的誠(chéng)實(shí)把每個(gè)人的徒刑降為五年，請(qǐng)你們各自權(quán)衡。”在這種情形下，兩個(gè)疑犯都將面臨著一個(gè)具有決定意義的兩難選擇。

亞當(dāng)·斯密(Adam Smith)曾提出了理性經(jīng)濟(jì)人的假設(shè)，一是經(jīng)濟(jì)人是自私自利的；二是經(jīng)濟(jì)人的行為是理性的，即他們根據(jù)處境來(lái)判斷自身的利益，追求個(gè)人利益盡可能最大化。在一個(gè)標(biāo)準(zhǔn)的囚徒困境中，可以用下面這個(gè)矩陣來(lái)表示：

兩個(gè)囚犯面臨同樣的選擇——無(wú)論同伙選擇什么，他們最好都選擇認(rèn)罪。因?yàn)椋绻锊徽J(rèn)罪，那么他們就無(wú)罪釋放，否則，他們起碼會(huì)被判十年徒刑。在一般情況下，假定每個(gè)囚徒都是理性的，他們的選擇通常會(huì)出現(xiàn)以下兩種可能情形：以A 為例，第一種可能是：B 認(rèn)罪，這時(shí)如果A 也認(rèn)罪，那么他們都要入獄5 年；如果A 不認(rèn)罪，則A 將被判十年，B 無(wú)罪釋放，兩相比較下，對(duì)于A 來(lái)說(shuō)，認(rèn)罪顯然是最優(yōu)策略。第二種是：B 不認(rèn)罪，這時(shí)如果A 認(rèn)罪，那么B 將被判十年，A 將無(wú)罪釋放，如果A 也不認(rèn)罪，那么他們都將被判一年，這種情形下，A 的最優(yōu)策略也是認(rèn)罪。由此可見(jiàn)，對(duì)雙方而言，每一個(gè)囚犯從個(gè)人利益出發(fā)，不考慮他人，他們都將選擇認(rèn)罪。但如果雙方都不認(rèn)罪，那么等待他們的將是一年的牢獄之苦。也就是說(shuō)，對(duì)個(gè)人最有利的認(rèn)罪策略，卻不是集體(A 和B)的最佳策略。

囚徒困境中彰顯的人性特點(diǎn)和理性信任觀

囚徒困境中個(gè)人的理性選擇卻是集體的非理性選擇，從人性的角度來(lái)看，就會(huì)發(fā)現(xiàn)其中包含著人性惡的傾向。如果A 是善的，那么會(huì)出現(xiàn)兩種情況，第一種情況是A 堅(jiān)持不認(rèn)罪也不供出B，B 同樣也是堅(jiān)持不認(rèn)罪也不供出A；第二種情況是，A 堅(jiān)持不認(rèn)罪，B 認(rèn)罪。

如果A 是惡的，那么也會(huì)出現(xiàn)兩種情況，第一種情況是A 認(rèn)罪也供出B，而B(niǎo) 不認(rèn)罪。第二種情況是A 認(rèn)罪也供出B，B 也認(rèn)罪且也供出A 。

從善的角度考慮問(wèn)題，可能得到最好的(1 年)和最糟的(10 年)的處罰結(jié)果；從惡的角度考慮，可能得到最好的(0 年)和最糟的(5年)的處罰結(jié)果。A、B 雙方都從自己的利益考慮，選擇惡的可能性會(huì)更大些。由此從囚徒困境中看到了人性惡的傾向。

在很多情況下，人面對(duì)的是一種集體條件下的困境，即博弈的雙方可能是兩大集團(tuán)或更多的人，相同的博弈者可能會(huì)不斷地重復(fù)面對(duì)相似的困境，“有條件的合作策略”將可能是理性經(jīng)濟(jì)人的最優(yōu)策略。

重復(fù)為博弈產(chǎn)生了新的動(dòng)力結(jié)構(gòu)。通過(guò)重復(fù)，博弈者就可能按對(duì)手以往的選擇而決定當(dāng)前的選擇。例如，存在一種所謂的“一觸即發(fā)”策略，即“只要你背叛，我隨后將永遠(yuǎn)背叛”，當(dāng)雙方保持背叛的狀態(tài)時(shí)，就失去了雙方獲益的機(jī)會(huì)。而如果雙方合作，其前提是雙方的相互信任，就可能爭(zhēng)取到雙方獲益的機(jī)會(huì)。還存在另一種所謂的“一報(bào)還一報(bào)”的策略，以合作開(kāi)始，然后模仿對(duì)方上一步選擇的策略。該策略以信任開(kāi)始，決不首先背叛。時(shí)間嵌入性理論表明，今天的行為(合作或背叛)，將影響再次相遇時(shí)所做的選擇。信任是使關(guān)系更持久、更穩(wěn)固的最優(yōu)選擇。

現(xiàn)實(shí)生活中的“囚徒困境”及其應(yīng)對(duì)策略

囚徒困境在現(xiàn)實(shí)社會(huì)中廣泛存在，而且情形要復(fù)雜的多。如汽車(chē)尾氣與空氣質(zhì)量的問(wèn)題。要保持空氣清潔，汽車(chē)主人就要對(duì)車(chē)安裝防污染的過(guò)濾裝置，需要自己負(fù)擔(dān)費(fèi)用。而理性個(gè)體既想享受清潔的空氣，又不愿為此付出代價(jià)。還有民眾生育觀的多子多福與人口膨脹的問(wèn)題，上車(chē)不排隊(duì)擁擠的問(wèn)題等等。

要想克服重復(fù)條件下的囚徒困境，就要從集體成員的主觀條件入手，使成員在新的基礎(chǔ)上做出最優(yōu)決策，打破原有的納什均衡，建立新的有價(jià)值的納什均衡(納什均衡是經(jīng)濟(jì)學(xué)家Nash 提出的，若有N 個(gè)人參加博弈，那么在給定他人戰(zhàn)略的情況下，在每一個(gè)參與人選擇的最優(yōu)戰(zhàn)略所形成的戰(zhàn)略組合中，沒(méi)有任何一個(gè)參與人有積極性選擇其他戰(zhàn)略，也沒(méi)有任何人有積極性打破這種均衡)。為此可以采取以下措施：

1、利用強(qiáng)化的作用。制定規(guī)則或提供獎(jiǎng)懲措施，通過(guò)正強(qiáng)化的作用，引導(dǎo)決策者改變自己原有的決策偏好，向著有利于集體利益的方向發(fā)展，做出對(duì)集體而言的最優(yōu)策略。

2、創(chuàng)造良好的文化氛圍。囚徒困境說(shuō)到底其實(shí)也是一種道德困境，要解決這種道德困境，就要從根本入手，創(chuàng)造良好的文化氛圍，逐步改變?nèi)w的道德觀、價(jià)值觀、主觀偏好。深刻認(rèn)識(shí)囚徒困境的弊端，充分利用強(qiáng)化手段，在良好的社會(huì)文化氛圍中創(chuàng)造人人都能從全局的利益出發(fā)，團(tuán)結(jié)合作，使全社會(huì)建立起一種新的有利于全體成員的有價(jià)值的納什均衡。