《基於自適應約束傳播的約束求解方法研究》是依託吉林大學，由張永剛擔任項目負責人的面上項目。
基本介紹
- 中文名：基於自適應約束傳播的約束求解方法研究
- 項目類別：面上項目
- 項目負責人：張永剛
- 依託單位：吉林大學
項目摘要,結題摘要,
項目摘要
針對物流、電力、通訊、交通和人力資源管理等領域廣泛存在的大規模約束滿足問題，建立高效而又具有自適應特性的約束求解方法是人工智慧領域中的前沿課題。本課題在對約束傳播和約束求解已有多年研究工作基礎上，充分考慮問題本身固有特性，採用靜態探查和動態探查兩種方式，獲取單個約束在套用多種不同約束傳播方法後發生變數論域值刪除以及論域清空等有用信息，提出約束傳播級別的啟發式策略，進而形成以自適應約束傳播為主要特徵的一系列約束求解方法。由於我們將建立的求解方法是以適應問題固有特性為基本原則，基於此，嘗試把這一系列方法套用於時間表調度等實際套用比較廣泛而又公認難解的問題，設計面向具體問題的全局約束，探索求解具有較大規模套用領域問題的高效算法。
結題摘要
針對物流、電力、通訊、交通和人力資源管理等領域廣泛存在的大規模約束滿足問題，建立高效而又具有自適應特性的約束求解方法是人工智慧領域中的前沿課題。 本課題在對約束傳播和約束求解已有多年研究工作基礎上，充分考慮問題本身固有特性，採用靜態探查和動態探查兩種方式，獲取單個約束在套用多種不同約束傳播方法後發生變數論域值刪除以及論域清空等有用信息，提出約束傳播級別的啟發式策略，進而構建了以自適應約束傳播為主要特徵的一系列約束求解方法。 主要研究成果包括： 1.在現有約束傳播算法研究的基礎上，提出了基於比特位操作的自適應約束傳播算法AC_MaxRPC_Bitwise及ADAPTAC-LmaxRPC，實驗結果表明，算法在總體性能上明顯優於AC及原自適應約束傳播算法； 2.結合look-ahead值啟發式，提出一種新的約束求解算法AdaptBranchLVO，實驗結果表明，新提出算法在效率上明顯優於已有的自適應分支求解算法; 3.提出算法AdaptBranchsurv，實驗結果表明，算法AdaptBranchsurv能顯著提高約束求解的效率; 4.提出一種更加輕便的、更適合用於搜尋的maxRPC算法及其輕量版本，實驗結果表明，新提出的maxRPC算法非常具有競爭力； 5.提出了基於啟發式搜尋的不完備性算法，主要在蟻群最佳化元啟發式約束求解算法的基礎上提出了改進，實驗結果表明，改進後的算法求解效率得到大幅度提高. 在此算法研究基礎上，深入分析了約束求解器Choco, Mistral 的結構,並對其進行擴展，進而構造出兩個具有較高性能的通用算法測試平台，為下一步把這一系列方法套用於時間表調度等實際套用比較廣泛而又公認難解的問題奠定基礎，對於探索求解具有較大規模套用領域問題的高效算法具有重要意義。
