一種基于因果圖啟發(fā)式的并行概率規(guī)劃方法.pdf

1、并行概率規(guī)劃（PPP）是近年來智能規(guī)劃領(lǐng)域中的研究熱點(diǎn)。在并行概率規(guī)劃問題中，放松了經(jīng)典規(guī)劃對(duì)所描述問題的嚴(yán)格約束，使得動(dòng)作具有并發(fā)性和不確定性，從而能夠更好的描述現(xiàn)實(shí)問題。然而，現(xiàn)有的兩種針對(duì)PPP的主要求解方法都具有明顯的缺點(diǎn)。一種是基于模擬抽樣的方法，以規(guī)劃器PROST為代表，求解質(zhì)量相對(duì)較好，但求解速度慢；另一種是基于迭代深化的方法，以規(guī)劃器Glutton為代表，求解速度相對(duì)較快，但求解質(zhì)量差。因此，我們嘗試使用新的方法來求解這

2、類問題，并行概率規(guī)劃問題不強(qiáng)求最優(yōu)解，解題空間規(guī)模巨大，這些特點(diǎn)正是啟發(fā)式搜索所擅長(zhǎng)的應(yīng)用領(lǐng)域，從而高效的啟發(fā)式搜索方法成為我們的選擇。目前，因果圖啟發(fā)式（CGH）是啟發(fā)式規(guī)劃方法中的佼佼者，并且該方法已經(jīng)在經(jīng)典規(guī)劃領(lǐng)域中有不錯(cuò)的表現(xiàn)。而且考慮到PPP問題采用RDDL語言來描述，在RDDL語言中使用條件概率函數(shù)（CPF）來描述動(dòng)作效果及狀態(tài)轉(zhuǎn)移，而CPF的結(jié)構(gòu)形式則恰好可以較為直觀的用于構(gòu)建因果圖（CG），所以我們引入因果圖來對(duì)基于RD

3、DL描述的PPP問題進(jìn)行啟發(fā)式求解。本文的主要啟發(fā)式算法稱為CGHRDDL，整體求解方法是使用rddlsim來模擬狀態(tài)演化以及使用CGHRDDL引導(dǎo)搜索。具體的求解方法分為以下四步：首先從領(lǐng)域描述構(gòu)建出因果圖及領(lǐng)域轉(zhuǎn)換圖（DTG）；然后根據(jù)CG和DTG，計(jì)算單個(gè)狀態(tài)變量任意一對(duì)取值之間的轉(zhuǎn)換代價(jià)；接著在rddlsim的模擬演化過程中，由CGHRDDL推送具有最佳估值的后繼狀態(tài)，其中狀態(tài)的啟發(fā)值定義為狀態(tài)軌跡的轉(zhuǎn)換代價(jià)和立即回報(bào)值的加權(quán)總

4、和；最后累加在限定輪數(shù)內(nèi)rddlsim狀態(tài)演化的回報(bào)值，即為最終的求解質(zhì)量。在PPP基準(zhǔn)領(lǐng)域上的實(shí)驗(yàn)結(jié)果表明，在不允許手工干預(yù)和參數(shù)調(diào)整的前提下，本文設(shè)計(jì)方法的求解效果要好于PROST和Glutton。更進(jìn)一步地，與其它的基本啟發(fā)式相比，CGHRDDL的求解質(zhì)量高于隨機(jī)搜索，求解速度快于爬山法。這些都表明在經(jīng)典規(guī)劃領(lǐng)域中高效的啟發(fā)式搜索策略可以擴(kuò)展用來求解這一類非經(jīng)典規(guī)劃問題。而非經(jīng)典規(guī)劃問題由其特征可知更加具有現(xiàn)實(shí)意義和應(yīng)用前景，更值