基于子目標排序和啟發(fā)式搜索的若干規(guī)劃技術(shù)研究.pdf

1、智能規(guī)劃是人工智能領(lǐng)域一個非常活躍的研究分支。近十幾年中，智能規(guī)劃發(fā)展非常迅速，在規(guī)劃問題的描述和問題求解兩方面研究都取得了新的突破，但在求解大規(guī)模規(guī)劃問題以及規(guī)劃搜索效率上，仍然有很多問題有待解決。本文從子目標排序和啟發(fā)式搜索剪枝策略兩方面出發(fā)，研究了提高規(guī)劃問題求解效率的相關(guān)方法和技術(shù)，主要工作包括：
　　 ⑴子目標排序?qū)澐趾颓蠼獯笠?guī)模復雜的規(guī)劃問題具有重要意義。但現(xiàn)有的排序理論約束條件過于嚴格，對大部分的基準測試領(lǐng)域問題

2、都不適用。本文提出了一種新的排序關(guān)系稱為可納子目標排序(ASO)。給出了可納排序的形式化定義。隨后，介紹了原子依賴關(guān)系理論和原子依賴圖技術(shù)，給出了可納排序關(guān)系成立的一個充分條件并給出了嚴格的證明過程。給出了一種多項式時間復雜度的算法用于近似計算可納排序關(guān)系。通過在多個國際規(guī)劃大賽基準測試領(lǐng)域問題上的實驗，結(jié)果表明我們的方法能有效的求解各類大規(guī)模的規(guī)劃問題，并能極大的改善規(guī)劃性能。
　　 ⑵前向啟發(fā)式搜索和放寬規(guī)劃方法被很多領(lǐng)域無

3、關(guān)的規(guī)劃器所采用，被認為是一種有效的規(guī)劃范型。FF規(guī)劃器利用放寬規(guī)劃圖計算狀態(tài)的啟發(fā)式估值，并提取有利動作集合進行前向搜索的剪枝。本文提出了一種新的高質(zhì)量的領(lǐng)域無關(guān)剪枝策略，該策略根據(jù)放寬規(guī)劃圖的動作層和命題層之間的關(guān)系，提取出所謂的直接效用動作集合，此集合之外的其它動作都被剪枝。直接效用動作集合比FF的有利動作集合更加精簡且更具啟發(fā)性，能指導前向搜索集中在那些離目標更近的狀態(tài)。利用直接效用動作我們開發(fā)了一種新的lookahead搜索鄰