模式數(shù)據(jù)庫在智能規(guī)劃中的應(yīng)用.pdf

1、在很多經(jīng)典的智能規(guī)劃問題的求解過程中，經(jīng)常要借助于啟發(fā)式搜索。但事實(shí)上，目前的啟發(fā)式搜索雖然能找到解卻還無法找到最優(yōu)解。原因在于所采用的啟發(fā)函數(shù)提供的估值或者太弱以至于在找到解之前就耗盡資源，或者不可采納即高估了解耗散從而不易幫助搜索算法找到最優(yōu)解所在的分支。與此同時(shí)，模式數(shù)據(jù)庫啟發(fā)式在一些極具挑戰(zhàn)性的最優(yōu)規(guī)劃問題的求解過程中起了很大的作用，能夠幫助搜索算法找到問題的最優(yōu)解。 為了改進(jìn)模式數(shù)據(jù)庫啟發(fā)式的效率，本文首先介紹了模式數(shù)

2、據(jù)庫啟發(fā)式的由來及其基本應(yīng)用思路，然后我們對(duì)智能規(guī)劃領(lǐng)域里傳統(tǒng)的構(gòu)造模式數(shù)據(jù)庫的方法進(jìn)行了改進(jìn)：首先通過分析和移除一些在實(shí)際問題空間里不可能存在對(duì)應(yīng)的完整狀態(tài)的模式有效地減少了模式數(shù)據(jù)庫的構(gòu)造時(shí)間，并提高了模式數(shù)據(jù)庫啟發(fā)式提供的啟發(fā)值的緊致性，使得模式數(shù)據(jù)庫啟發(fā)式能更好的指導(dǎo)搜索算法以求得問題的最優(yōu)解；然后在規(guī)劃問題領(lǐng)域包含的變量數(shù)較多的情況下，舍棄了傳統(tǒng)的用一維數(shù)組來存儲(chǔ)模式數(shù)據(jù)庫的方法，采用了平衡二叉樹來存儲(chǔ)模式數(shù)據(jù)庫以達(dá)到充分利用

3、系統(tǒng)環(huán)境所擁有的空間從而能夠解決變量數(shù)更多的規(guī)劃問題。為了比較模式數(shù)據(jù)庫構(gòu)造方法改進(jìn)前后的效果，本文設(shè)計(jì)了一個(gè)規(guī)劃器，通過使用規(guī)劃器解決積木世界領(lǐng)域及物流領(lǐng)域的規(guī)劃問題來研究改進(jìn)前后模式數(shù)據(jù)庫啟發(fā)式在搜索過程中所起的作用。實(shí)驗(yàn)證明了如果規(guī)劃領(lǐng)域包含的不同合并謂詞組含有重疊的謂詞，則在該規(guī)劃領(lǐng)域通過改進(jìn)后的構(gòu)造方法構(gòu)造出的模式數(shù)據(jù)庫計(jì)算時(shí)間更少，在變量較多的情況下對(duì)空間的需求更小，其提供的啟發(fā)值對(duì)搜索算法的指導(dǎo)性更強(qiáng)。我們還將實(shí)驗(yàn)結(jié)果與F