《結合自主搜尋機制的約束求解方法研究》是依託吉林大學，由張永剛擔任項目負責人的面上項目。
基本介紹
- 中文名：結合自主搜尋機制的約束求解方法研究
- 項目類別：面上項目
- 項目負責人：張永剛
- 依託單位：吉林大學
項目摘要,結題摘要,
項目摘要
當前，約束滿足問題在人工智慧領域發揮了重要的作用。近五年來，約束求解方法的發展極為迅速，各種不同的變數、值選擇啟發式、約束傳播技術、搜尋框架、分支策略不斷湧現，選擇求解一類問題的高效算法（或算法組合）成為約束程式研究者面對的新抉擇。而新近提出並廣受重視的自主搜尋機制的出現為破解以上難題提供了新思路。本課題申請基於研究組對約束傳播和約束求解方法的前期研究，主要研究約束滿足問題的團、對稱等結構化特徵的探查及推理方法，擬確立基於回溯搜尋的約束求解算法的參數化框架，並利用機器學習方法建立針對特定問題類的算法組合的自主選擇策略和算法調控策略，最終建立面向具體問題結構的結合自主搜尋機制的高效的求解方法，並嘗試將其套用於調度、配置領域等稍大規模具體問題的求解，探索所提出的理論和方法的實際套用價值。
結題摘要
當前，約束滿足問題在人工智慧領域發揮了重要的作用。本項目基於研究組對約束傳播和約束求解方法的前期研究，主要研究約束滿足問題的團、對稱等結構化特徵的探查及推理方法，擬確立基於回溯搜尋的約束求解算法的參數化框架，並利用機器學習方法建立針對特定問題類的算法組合的自主選擇策略和算法調控策略，最終建立面向具體問題結構的結合自主搜尋機制的高效的求解方法，並嘗試將其套用於調度、配置領域等稍大規模具體問題的求解，探索所提出的理論和方法的實際套用價值。具體包括:研究了約束滿足問題適應自主搜尋的結構特性；研究約束求解中的相容性技術，並提出多種改進的高效求解算法；提出了基於啟發式搜尋的自適應改進算法，包括蟻群最佳化、教與學算法、差分進化算法，並將這些自適應算法與經典算法相結合;對Mistral求解器的搜尋策略的進行多方面擴展，提高了求解能力;研究了著名的Mistral和Choco約束求解工具，並在約束表示和約束求解方法方面拓展了兩個平台，建立了基於二者的約束組合求解框架；將約束組合求解框架套用於求解城市布局和醫院人力資源調度問題，取得了較好的效果。
