完全圖哈密爾頓圈遺傳算法的MATLAB模擬實現

劉奕君, 張 立2, 趙 強

(1.徐州醫學院醫學信息學院，江蘇 徐州 221000；2.徐州醫學院醫學影像學院，江蘇 徐州 221000)

· 計算機軟件理論、技術與應用·

完全圖哈密爾頓圈遺傳算法的MATLAB模擬實現

劉奕君1, 張 立2, 趙 強1

(1.徐州醫學院醫學信息學院，江蘇 徐州 221000；2.徐州醫學院醫學影像學院，江蘇 徐州 221000)

求解完全圖上的哈密爾頓圈是典型的組合優化問題，遺傳算法是解決此類NP問題的一種較理想的方法。對基本的遺傳算法進行改進，在選擇操作和變異操作中加入貪心優化思想，使算法獲得更優的全局最優解。在MATLAB環境下模擬實現了哈密爾頓圈的經典問題——TSP( travelling salesman problem)旅行商問題，從而驗證了該算法的可行性和正確性。

哈密爾頓圈；遺傳算法；貪心思想；MATLAB；全局最優解

設G(V，E)是一個連通圖，若G中一條回路通過G的每個點恰好1次，這樣的回路稱為哈密爾頓回路，記作H回路。對于H回路問題，傳統的窮舉搜索法、貪心法、動態規劃法等串行算法，都面臨著所謂“組合爆炸”問題[1]。對于這類NP(non-deterministic polynomial)問題，可用并行求解法或演化算法等。演化算法[2-3]是用計算機模擬大自然的演化過程，特別是生物進化過程，以求解復雜問題的一類計算模型，其基本思想是Darwin的進化論和Mendel的遺傳學說。該類算法可通過逐步的演化過程，使群體進化到包含或接近最優解的狀態。遺傳算法即典型的演化算法[4]，提供了一種求解復雜系統優化問題的通用框架，不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科[5-8]。……