求解最小支配集問題的禁忌遺傳混合算法

吳歆韻 彭瑞 熊才權

［摘要］ 將最小支配集問題轉(zhuǎn)換為一系列判定問題[CD2]k支配集問題，并提出一種禁忌遺傳混合算法對k-DS問題進行求解。此算法將禁忌搜索算法和遺傳算法兩種啟發(fā)式算法結合起來，互補不足。高效的鄰域結構保證了算法的運行效率，禁忌策略防止算法過早陷入局部最優(yōu)陷阱，遺傳算法框架進一步增強了算法的疏散性。經(jīng)過與現(xiàn)有求解最小支配集算法的結果進行分析比較，禁忌遺傳混合算法的結果較其它算法更優(yōu)。

［關鍵詞］ 最小支配集； NP難問題； 禁忌遺傳混合算法； k支配集

［中圖分類號］ TP393［文獻標識碼］ A