大規(guī)模Markov決策過(guò)程基于性能勢(shì)的并行算法研究與應(yīng)用.pdf

1、隨著科技的發(fā)展,在當(dāng)今社會(huì)中,廣泛存在著一類復(fù)雜的隨機(jī)動(dòng)態(tài)系統(tǒng),即離散事件動(dòng)態(tài)系統(tǒng)(DEDS).Markov決策過(guò)程(MDP)是DEDS建模常見(jiàn)的方法,其性能優(yōu)化問(wèn)題一直是學(xué)者研究的重要方向.Markov性能勢(shì)理論的提出,為MDP的分析和研究提供了一種新的理論框架.在性能勢(shì)理論的基礎(chǔ)上,不僅可以建立基于已知模型參數(shù)的理論計(jì)算來(lái)尋求最優(yōu)策略,而且可以在模型參數(shù)未知時(shí)利用基于樣本軌道的仿真和在線學(xué)習(xí)算法來(lái)求解. 在實(shí)際大規(guī)模的Mar

2、kov系統(tǒng)中,串行執(zhí)行優(yōu)化算法的時(shí)間往往很長(zhǎng),甚至問(wèn)題求解不可行.采用并行計(jì)算是提高M(jìn)DP執(zhí)行效率最直接最有效的一種方式.一方面,并行求解能真正縮減算法的計(jì)算時(shí)間;另一方面,在MDP仿真優(yōu)化時(shí),并行仿真不僅能加快收斂速度,還有可能得到更為精確的解.因此MDP并行計(jì)算的實(shí)現(xiàn)對(duì)實(shí)際大規(guī)模MDP的性能優(yōu)化具有重要的指導(dǎo)作用,本論文主要對(duì)MDP并行算法展開(kāi)研究,研究?jī)?nèi)容包括基于性能勢(shì)的MDP理論迭代算法和仿真優(yōu)化方法的并行化實(shí)現(xiàn). 對(duì)于

3、MDP理論計(jì)算的并行化實(shí)現(xiàn),文章給出了并行數(shù)值迭代算法,該算法將狀態(tài)空間劃分為若干個(gè)狀態(tài)子空間,每個(gè)處理節(jié)點(diǎn)只在一個(gè)狀態(tài)子空間上運(yùn)算,從而降低優(yōu)化求解時(shí)間.針對(duì)隨機(jī)劃分狀態(tài)空間方法易使處理節(jié)點(diǎn)間負(fù)載嚴(yán)重不平衡,并行效率低下的問(wèn)題,論文提出了一種啟發(fā)式的劃分策略.該劃分策略將處理器等待時(shí)間作為目標(biāo)函數(shù),通過(guò)極小化所有處理器的等待時(shí)間來(lái)劃分和分配狀態(tài)空間.實(shí)驗(yàn)結(jié)果表明采用啟發(fā)式劃分方法的并行性能要優(yōu)于采用隨機(jī)劃分方法. 對(duì)于MDP仿

4、真算法的并行化實(shí)現(xiàn),論文討論了并行Q學(xué)習(xí)和NDP并行優(yōu)化方法.首先,文章在性能勢(shì)理論框架內(nèi),提出了獨(dú)立并行Q學(xué)習(xí)算法和狀態(tài)劃分并行Q學(xué)習(xí)算法,重點(diǎn)討論了算法中的關(guān)鍵參數(shù)的設(shè)計(jì),即同步點(diǎn)如何選擇的同步策略和如何合成Q因子的Q值構(gòu)建策略,探討了一種固定步長(zhǎng)結(jié)合一定偏移量的同步策略,并分析了并行中Q值構(gòu)建策略的確定原則,給出了幾種Q值構(gòu)建策略的選擇方法.在NDP并行優(yōu)化中,論文以神經(jīng)網(wǎng)絡(luò)集成有關(guān)理論為出發(fā)點(diǎn),采用多個(gè)神經(jīng)元網(wǎng)絡(luò)并行仿真學(xué)習(xí)來(lái)提