求解最小支配集問題的禁忌遺傳混合算法
2024-05-23 08:35:27吳歆韻彭瑞熊才權
湖北工業大學學報 2024年2期
吳歆韻 彭瑞 熊才權
［摘要］ 將最小支配集問題轉換為一系列判定問題[CD2]k支配集問題，并提出一種禁忌遺傳混合算法對k-DS問題進行求解。此算法將禁忌搜索算法和遺傳算法兩種啟發式算法結合起來，互補不足。高效的鄰域結構保證了算法的運行效率，禁忌策略防止算法過早陷入局部最優陷阱，遺傳算法框架進一步增強了算法的疏散性。經過與現有求解最小支配集算法的結果進行分析比較，禁忌遺傳混合算法的結果較其它算法更優。
［關鍵詞］ 最小支配集； NP難問題； 禁忌遺傳混合算法； k支配集
［中圖分類號］ TP393［文獻標識碼］ A
