基于節(jié)點多樣性和動態(tài)參考閾值的智能規(guī)劃方法研究.pdf

1、在人工智能領(lǐng)域，智能規(guī)劃作為一個多領(lǐng)域交叉的學(xué)科，逐漸成為了人們研究的熱點。智能規(guī)劃在人際互動、知識及邏輯推理、游戲設(shè)定、航天航空、智能機器人等領(lǐng)域得到應(yīng)用，備受人們關(guān)注。近年來具有代表性的啟發(fā)式規(guī)劃系統(tǒng)有:FF、Fast-Downward、LAMA等。LAMA規(guī)劃系統(tǒng)是一個很重要的規(guī)劃系統(tǒng)，在智能規(guī)劃發(fā)展史上具有重大意義，它采用路標作為偽啟發(fā)式函數(shù)，充分地挖掘了啟發(fā)式信息，提高了規(guī)劃系統(tǒng)的性能。
　　 啟發(fā)式搜索在智能規(guī)劃中表

2、現(xiàn)出良好的性能。最優(yōu)優(yōu)先算法GBFS(greedybest-first search)是LAMA規(guī)劃系統(tǒng)中非常重要的算法，它提高了搜索的效率和質(zhì)量。但是GBFS算法本身還存在一定的不足，由于算法本身具有的貪婪性，啟發(fā)式搜索容易陷入局部最優(yōu)狀態(tài)。針對這一問題，本文提出了一種基于增加節(jié)點多樣性和動態(tài)參考閾值的方法IBFS(improved best-first search)，在一定程度上克服了GBFS算法不足。
　　 首先，在GB

3、FS算法中，搜索總是在當前狀態(tài)下選取啟發(fā)值最小的狀態(tài)節(jié)點來擴展，這樣選擇的狀態(tài)節(jié)點并不一定是全局最優(yōu)，易使搜索陷入了局部最優(yōu)，搜索大量無用的節(jié)點，而且搜索不會從當前的狀態(tài)中跳出，以至搜索得到的規(guī)劃解并不是全局最優(yōu)規(guī)劃解。本文利用路標啟發(fā)函數(shù)增加節(jié)點選擇的多樣性，在當前評估的狀態(tài)中選擇多個狀態(tài)節(jié)點，增加了節(jié)點的評估個數(shù)，減少了搜索算法陷入局部最優(yōu)狀態(tài)的概率，有效地提高規(guī)劃的性能，使搜索有更大的機會得到全局最優(yōu)規(guī)劃解。其次，本文算法為了更好

4、地克服局部最優(yōu)狀態(tài)，采用了一種動態(tài)參考閾值的方法來進一步提高算法的性能。動態(tài)參考閾值的算法是經(jīng)過調(diào)整優(yōu)先隊列，通過隨機方式得到一個參考閾值，利用這個參考閾值來重新構(gòu)建新的優(yōu)先隊列，然后在這個新的優(yōu)先隊列中去尋找一個要擴展的目標節(jié)點。通過這種方式，可以使搜索在全局狀態(tài)中去選取，增加節(jié)點跳出局部最優(yōu)狀態(tài)的概率，使規(guī)劃解的質(zhì)量更好。
　　 在Linux平臺下，我們采用C++語言對本文的改進算法IBFS進行了實現(xiàn)，并將其應(yīng)用在LAMA規(guī)