以雙族群遺傳演算法求解旅行小偷問題

Abstract

旅行推銷員問題與 0-1 背包問題都是著名的離散最佳化問題。旅行推銷員問題欲求旅行推銷員行走各城市的最短路徑。0-1 背包問題求解物品挑選利益最大化。旅行小偷問題將旅行推銷員問題與 0-1 背包問題結合，使得需同時求解路徑排序與物品組合。在旅行推銷員問題與 0-1 背包問題各自的文獻中，常見以啟發式演算法求解。然而，若是以啟發式演算法直接求解旅行小偷問題，將面臨巨大的搜尋空間。因此，我們提出雙族群式的遺傳演算法，分別專注搜尋兩個子問題，以此縮小搜尋空間。每間隔一段時間，兩個族群使用遷移機制進行資訊的交換，達到互相幫助的效果。搜尋單一子問題過程中，好的解碼函式能夠讓個體在另一子問題中獲得更好的基因。因此，我們針對解碼函式中的參數使用自適應控制機制，以提升個體解碼後的品質。本研究詳細探討自適應控制機制的作用與效果，實驗結果證明使用自適應控制機制能夠提升演化搜尋最佳解，並且我們觀察自適應控制的參數演化圖，在不同測試資料中，都能演化收斂在合理的數值。本研究探討雙族群演化方式的作用與效果，實驗證明相較單一族群的演化方式，使用雙族群式遺傳演算法效果更好。我們觀察雙族群遺傳演算法中，兩個族群在演化互助的過程，也確認遷移機制能夠提升雙族群遺傳演算法的演化結果。最後我們所提出之雙族群遺傳演算法相比近年文獻演算法更為優秀，代表雙族群遺傳演算法在近年求解旅行小偷問題的演算法中頗具競爭力。none