《圖著色若干變種問題的下界及其智慧型搜尋算法的研究》是依託華中科技大學，由金燕擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：圖著色若干變種問題的下界及其智慧型搜尋算法的研究
- 項目類別：青年科學基金項目
- 項目負責人：金燕
- 依託單位：華中科技大學
中文摘要,結題摘要,
中文摘要
圖著色的最小和問題、頻寬著色和頻寬多重著色問題這三個圖著色變種問題是強NP難問題，具有廣泛的實際套用價值。圖著色變種問題上界的現實求解算法的研究在近十年有所發展，但問題下界的研究尚在起步階段。本項目在問題上界的研究基礎上，提出對問題下界及其智慧型搜尋算法的研究，以期通過計算實驗方式找到大規模問題實例的最優解。具體研究內容包括：(1)擬通過放鬆約束條件提出問題下界的求解模型；(2)分析搜尋空間內高質量的解的分布情況；(3)設計高效的周期性更新的雙親混合擬人算法。本項目為獲得大規模的圖著色變種問題的最優解提供更加廣闊的思路，對相關實際套用領域的發展起到推動作用。
結題摘要
圖著色及其變種問題是典型的NP難問題，在信號頻率分配、人員排班、車輛調度、車間作業調度等科學和工程領域具有廣泛的套用價值。本項目基於大規模鄰域搜尋算法和混合進化算法等智慧型搜尋算法對圖著色及其變種問題展開了深入研究，突破了當前研究對大規模問題實例的局限和不足之處。本項目的主要研究內容包括：從本質上分析大規模圖問題的特性，提出了新穎有效的求解方案。設計了基於最大獨立集抽取及回放疊代混合搜尋的方法求解大規模圖著色的最小和問題的上下界，通過計算實驗方式找到大規模問題實例的最優解。該方法改進了19個大圖的上界和12個下界，得到了目前國際上的最好結果。在問題模型方面，將拉丁方塊補全問題轉化成圖著色問題，並使用圖著色混合進化算法求解大規模算例，得到了比原問題求解方案更好的結果。增加了圖著色求解方案的通用性，擴展了約束最佳化問題的求解途徑。本項目的研究成果對混合進化算法在圖著色問題及套用上將起到積極的推動作用，為獲得大規模的組合最佳化問題的求解方案提供更加廣闊的思路。
