學位論文

Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912

Browse

Subject: search.filters.subject.evolutionary algorithm

Search Results

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    以雙族群遺傳演算法求解旅行小偷問題
    (2021) 王碩英; Wang, Shuo-Ying
    旅行推銷員問題與 0-1 背包問題都是著名的離散最佳化問題。旅行推銷員問題欲求旅行推銷員行走各城市的最短路徑。0-1 背包問題求解物品挑選利益最大化。旅行小偷問題將旅行推銷員問題與 0-1 背包問題結合，使得需同時求解路徑排序與物品組合。在旅行推銷員問題與 0-1 背包問題各自的文獻中，常見以啟發式演算法求解。然而，若是以啟發式演算法直接求解旅行小偷問題，將面臨巨大的搜尋空間。因此，我們提出雙族群式的遺傳演算法，分別專注搜尋兩個子問題，以此縮小搜尋空間。每間隔一段時間，兩個族群使用遷移機制進行資訊的交換，達到互相幫助的效果。搜尋單一子問題過程中，好的解碼函式能夠讓個體在另一子問題中獲得更好的基因。因此，我們針對解碼函式中的參數使用自適應控制機制，以提升個體解碼後的品質。本研究詳細探討自適應控制機制的作用與效果，實驗結果證明使用自適應控制機制能夠提升演化搜尋最佳解，並且我們觀察自適應控制的參數演化圖，在不同測試資料中，都能演化收斂在合理的數值。本研究探討雙族群演化方式的作用與效果，實驗證明相較單一族群的演化方式，使用雙族群式遺傳演算法效果更好。我們觀察雙族群遺傳演算法中，兩個族群在演化互助的過程，也確認遷移機制能夠提升雙族群遺傳演算法的演化結果。最後我們所提出之雙族群遺傳演算法相比近年文獻演算法更為優秀，代表雙族群遺傳演算法在近年求解旅行小偷問題的演算法中頗具競爭力。
  • No Thumbnail Available
    Item
    強化親代選擇機制之平行化高目標演化式演算法
    (2013) 陳少文; sao-wen chen
    當一個最佳化問題的求解目標數為兩個以上時，我們稱其為多目標最佳化問題 (multi-objective optimization problems)，若目標數為四或四個以上時，則稱其為高目標最佳化問題 (many-objective optimization problems)。現實世界的最佳化問題中存在著許多高目標最佳化問題，傳統的多目標最佳化演算法只適合求解目標數四以下的問題，設計一個能夠求解高目標最佳化問題的演算法是目前演化式領域中的研究重點。 我們以非凌越性排序基因演算法 (NSGA-III) 為基底，深入觀察該演算法特性，改善親代選擇機制 (mating selection) 中選取親代的方式，優先改進族群中相對較差的區域，並搭配鄰域選取 (neighborhood-based selection) 概念，得到不錯的成效；在環境選擇機制 (environmental selection) 中，我們嘗試同時維持族群在目標空間與決策空間中的分散度，並使用其他方法替代原本 NSGA-III 演算法的選取機制，雖然成效不彰，但在實驗中我們觀察到了一些有趣的現象；我們更以島嶼模型 (island model) 將演算法平行化，透過預先分配給各島嶼屬於邊框權重向量的機制，在維持演算法原本求解能力的同時，還能加快整體的執行速度。 本論文所提出的各種改進機制可以互相搭配使用，以最佳版本的親代選擇機制配合平行化機制的狀況下 (ESP-NSGA-III)，與原版的 NSGA-III相比，求解 DTLZ1~4 並改變其問題目標數共 15 個測試問題中，在 Mann Whitney U 統計檢定下，我們的演算法有著 11 勝 3 和 1 負的優良表現。