基于因子間依賴關(guān)系的啟發(fā)式規(guī)劃研究.pdf

1、隨著智能規(guī)劃越來越多在實際問題中的應(yīng)用，更多的學(xué)者開始關(guān)注和研究智能規(guī)劃，人們從多個角度去完善，并提出了多種規(guī)劃策略，其中，啟發(fā)式規(guī)劃方法作為智能規(guī)劃領(lǐng)域的重要問題之一，在近十幾年受到了眾多學(xué)者的關(guān)注和研究。目前具有代表性的啟發(fā)式規(guī)劃器有:FF、LPG和Fast-Downward等。由于Fast-Downward將規(guī)劃問題轉(zhuǎn)化為一個多值規(guī)劃任務(wù)，提出并采用了基于因果圖的啟發(fā)函數(shù)，得到了較高的搜索效率。但Fast-Downward的主要缺

2、點在于其采用的基于因果圖的啟發(fā)函數(shù)將目標(biāo)因子相互獨立作為一個假設(shè)前提，然而在眾多的規(guī)劃問題中，各個目標(biāo)因子之間往往存在相互依賴關(guān)系，造成計算出的啟發(fā)代價比真實代價值大。針對Fast-Downward存在的不足，本文在充分考慮了因子間依賴關(guān)系的基礎(chǔ)上，提出一種基于子目標(biāo)排序和有利值提取的啟發(fā)函數(shù)(HBSH)。
　　 首先，根據(jù)目標(biāo)因子間存在的依賴關(guān)系，依次從目標(biāo)集中提取出子目標(biāo)，得到一個有序的子目標(biāo)序列，即目標(biāo)因子合理的實現(xiàn)順序。

3、接下來以子目標(biāo)序列中子目標(biāo)的啟發(fā)代價依次作為啟發(fā)值來引導(dǎo)搜索，以達到提高啟發(fā)函數(shù)準(zhǔn)確性、加快啟發(fā)函數(shù)計算速度的目的;其次，通過對目標(biāo)因子間存在的有利依賴關(guān)系的分析，結(jié)合Fast-Downward中的域轉(zhuǎn)移圖技術(shù)，提出一種計算目標(biāo)集在某一狀態(tài)下存在的有利值的算法，在啟發(fā)函數(shù)每次計算啟發(fā)代價時都加入有利值提取技術(shù)，這樣可得到更加準(zhǔn)確的啟發(fā)代價;最后采用最佳優(yōu)先貪心算法來進行規(guī)劃求解。
　　 在Linux平臺下，采用C++語言對給出的