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

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

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

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