求解大規模約束滿足問題的混合進化算法研究

《求解大規模約束滿足問題的混合進化算法研究》是依託華中科技大學，由呂志鵬擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：求解大規模約束滿足問題的混合進化算法研究
• 項目類別：青年科學基金項目
• 項目負責人：呂志鵬
• 依託單位：華中科技大學

項目摘要

大規模約束滿足問題（CSP）是人工智慧、運籌學以及計算機科學研究領域的一個重要分支，是工業套用中廣泛面臨的困難問題。因此，設計求解CSP問題的高效算法具有重要的理論價值和實際意義。本課題以頻率分配問題和大學課程時間表調度問題為研究介質，採用將禁忌算法和進化算法相結合，將問題本質結構融合到啟發式算法中，設計求解CSP問題的高效混合進化算法。研究工作主要包括：實現求解CSP問題的自適應禁忌算法，算法根據歷史搜尋信息動態調整禁忌表長度；實現禁忌算法與進化算法相結合的自適應平衡機制；設計具有語義功能的多親交叉算符，以產生在未搜尋區域內有前途的初始解；群體更新時同時考慮解的優度以及解之間的距離，維護具有多樣性的精英群體，以達到算法集中性和疏散性的平衡。本課題有望設計出求解頻率分配問題和大學課程時間表調度問題的高效混合進化算法，並總結出其在求解大規模CSP問題中的一般規律。

結題摘要

約束滿足問題廣泛地出現在理論研究和工業套用的各個領域。同時，許多約束最佳化問題往往可以轉化為約束滿足問題來進行求解。由於這些問題已被證明為NP難問題，精確算法只能用來求解規模非常小的問題實例或者具有特殊結構的實例。而基於啟發式的最佳化算法可以在有限的計算時間內對大多數不同規模和結構的問題實例找到高質量的解。 本項目主要研究求解約束滿足問題的高效混合進行算法。混合進化算法將基於單個解策略的局部搜尋算法與基於群體的進化算法相結合，以達到集中性和疏散性之間更好的平衡，往往可以達到更高的搜尋效率。 本項目主要圍繞幾個典型的約束滿足問題和約束最佳化問題進行研究，如頻率分配問題、頻寬著色問題、人員排班問題、SAT問題、作業調度問題、負載均衡問題。對於這些典型的約束滿足問題和約束最佳化問題，設計了求解這些問題的自適應局部搜尋算法和混合進化算法。通過與當前國際文獻中的最好的算法結果進行詳細地對比和分析，表明了所提出的算法在優度和效率兩方面的優勢。特別地，本項目中所提出的算法對以上問題均改進了若干國際文獻中的最好結果。 同時，針對不同問題的特性，在算法設計方面提出了一些針對問題特性的操作算符，如交叉算符、學習機制、擾動策略等，並對這些針對問題特性的操作算符進行了分析，表明了這些算符或策略對算法性能的重要性和影響。總之，通過本項目的研究，不僅有助於我們設計出求解大規模約束滿足問題的高效混合進化算法，還可以幫助我們理解算法中哪些策略是通用的，這些通用策略加以提升就可以用來求解其它的約束滿足問題，而哪些策略是針對所求解的具體問題的。