學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
7 results
Search Results
Item 求解高維多目標最佳化問題的演化演算法效能評析(2024) 曾則儒; Tseng, Tser-Ru演化演算法在求解多目標最佳化問題有很好的表現，也被廣泛使用於各領域的實際應用問題。然而當決策變數的個數增加至數百個甚至數千個時，指數成長的搜尋空間會對多目標演化演算法的求解能力形成嚴峻的挑戰；因此，近年來演化計算領域有越來越多的學者投入高維多目標演化演算法的設計。然而，我們發現到此領域的研究文獻在評估演算法效能時未能使用統一的實驗設定，此舉可能造成實驗結果的偏頗與失真。本論文自文獻中挑選八個具有代表性的高維多目標演化演算法，使用兩套公開測試函式集 LSMOP 與 LMF，檢視這些演算法在四種問題維度和四種計算資源所組合的十六種實驗環境下的求解效能。經由公平且完整的實驗測試，我們得以正確評比演算法的效能與特質，也對各種演算法設計的異同處與其對於求解效能的影響提出解釋與探討。Item 以 AGE-MOEA-II與改良版環境選擇求解多目標最佳化問題(2024) 張家慈; Chang, Chia-Tzu多目標最佳化問題是現實應用的常見形式，求解問題時需要同時考慮多個目標之間的取捨關係。多目標演化演算法是求解多目標最佳化問題的常用方法，這類演算法中的關鍵機制就是平衡解族群的收斂性和多樣性。在近年發表的演算法中，AGE-MOEA-II 演算法通過估計柏拉圖前緣的形狀，並依形狀來定義解的多樣性和收斂性，展現了出色的效能表現。然而AGE-MOEA-II 仍有其值得改進之處，本論文結合了其它現有演算法的設計，一方面刪減無益於收斂性的解個體，一方面修改其應對凸型柏拉圖前緣時的多樣性評估機制。我們使用 13 個公開測試函式進行實驗，實驗結果顯示本論文所引入的機制可有效提升求解品質；與六個現有演算法相比，本論文所提出的改良版 AGE-MOEA-II 在兩項常見的效能指標 IGD 與 HV 都有更好的表現。Item 以多目標演化演算法求解動態電力調度之成本及汙染問題(2022) 柯炫任; Ko, Hsuan-Jen在科技發達的社會中，人類對電力的依賴日漸增加。由於目前綠色能源之發展仍在進行，火力發電仍為電力供給的主要方法。動態電力調度之成本及汙染問題為有限制的多目標連續型最佳化問題，給定若干個發電機組資訊和一天二十四小時的電力需求，需求取每小時中各機組的發電量配置。發電配置必須滿足每小時的電力需求，也必須符合各發電機組的負載範圍及調降安全範圍；目標則為同時最小化發電成本和空污排放量。綜合上述，動態電力調度之成本及汙染問題為一具挑戰性之最佳化問題，且有實務應用價值，是非常值得研究的問題。本論文提出多目標差分演化演算法以求解動態電力調度之成本及汙染問題，針對演算法中的合法性修復、環境選擇、計算資源分配及突變選擇四項重要機制進行探究。我們以六組公開測試模型檢驗上述四項機制對求解效能之影響，實驗結果顯示本論文所使用之機制均有良好成效。最後，本論文之方法和十五個既有方法相比，展現優秀的求解能力。Item 以雙族群遺傳演算法求解旅行小偷問題(2021) 王碩英; Wang, Shuo-Ying旅行推銷員問題與 0-1 背包問題都是著名的離散最佳化問題。旅行推銷員問題欲求旅行推銷員行走各城市的最短路徑。0-1 背包問題求解物品挑選利益最大化。旅行小偷問題將旅行推銷員問題與 0-1 背包問題結合，使得需同時求解路徑排序與物品組合。在旅行推銷員問題與 0-1 背包問題各自的文獻中，常見以啟發式演算法求解。然而，若是以啟發式演算法直接求解旅行小偷問題，將面臨巨大的搜尋空間。因此，我們提出雙族群式的遺傳演算法，分別專注搜尋兩個子問題，以此縮小搜尋空間。每間隔一段時間，兩個族群使用遷移機制進行資訊的交換，達到互相幫助的效果。搜尋單一子問題過程中，好的解碼函式能夠讓個體在另一子問題中獲得更好的基因。因此，我們針對解碼函式中的參數使用自適應控制機制，以提升個體解碼後的品質。本研究詳細探討自適應控制機制的作用與效果，實驗結果證明使用自適應控制機制能夠提升演化搜尋最佳解，並且我們觀察自適應控制的參數演化圖，在不同測試資料中，都能演化收斂在合理的數值。本研究探討雙族群演化方式的作用與效果，實驗證明相較單一族群的演化方式，使用雙族群式遺傳演算法效果更好。我們觀察雙族群遺傳演算法中，兩個族群在演化互助的過程，也確認遷移機制能夠提升雙族群遺傳演算法的演化結果。最後我們所提出之雙族群遺傳演算法相比近年文獻演算法更為優秀，代表雙族群遺傳演算法在近年求解旅行小偷問題的演算法中頗具競爭力。Item 以演化演算法設計卡牌遊戲之組牌策略：以 Legends of Code and Magic 為例(2021) 楊雅茹; Yang, Ya-Ju遊戲人工智慧的研究非常熱門，其中有許多卡牌遊戲的相關研究，像是著名的爐石戰記 (Hearthstone)和魔法風雲 (Magic: the Gathering)。本研究挑選了一款Legends of Code and Magic (LoCM) 卡牌遊戲，LoCM分為選牌與戰鬥兩階段，指定兩位玩家進行對戰，先將對手英雄血量歸零則獲勝。 LoCM在2019年IEEE Congress on Evolutionary Computation (CEC)和IEEE Conference on Games (COG) 被接受議題研究及舉辦競賽。本研究只專注於選牌部分，建立一個自動選牌的策略，戰鬥方法則取用COG 2020 第二名及第四名的方法。文中提出三種選牌法，直接評分法、屬性評分法與屬性牌型評分法，並搭配兩種演化演算法。另外，進行個體適應值穩定度分析，探討遊戲場次數量不同帶來的影響，而大量的遊戲會帶來龐大的計算成本，因此，針對遊戲進行平行化處理，大幅減少計算時間。在傳統的卡牌遊戲中，牌型是組建牌組相當重要的因素，牌型之間存在著相互剋制的關係，選擇對的牌型剋制敵方在遊戲中有非常佔優勢，因此，文中分析不同選牌法的牌型及選牌時帶來的優、缺點。最後，與COG 2020的前六名玩家進行對戰排名。Item 基於繪圖處理器之疊代層級平行演化演算法軟體框架(2014) 何泳陖生活中常會遇到最佳化問題滿例如搭乘交通工具從甲地前往乙地，可選擇的交通工具組合可能有很多種，選擇考慮的因素有最快抵達或交通費最低等等。此類問題經常使用演化演算法來求解，而撰寫一個完整的演化演算法需耗費一些時間。 NVIDIA公司致力於平行環境CUDA的開發，使用者可以將C++程式碼修改成可運行CUDA程式碼。以現今的平行計算技術，使用不高的成本購入可運行CUDA的硬體，加速數十倍至數百倍是有可能的，數小時的實驗加速後可能僅需數分鐘即可完成。 本論文開發一個演化演算法的軟體框架，PEAC(Parallel Evolutionary Algorithms base on CUDA)，提供演化演算法的基本設定，也提供演化演算法中常見的運算子供使用。讓使用者可以降低撰寫程式碼的時間。也不需要額外花費時間學習CUDA的程式開發。Item 高目標演化演算法中參考點之探究(2018) 李震昱; Lee, Chen-Yu多目標最佳化問題是近年演化計算領域裡熱門的研究主題，我們的日常生活周遭也充滿了多目標最佳化的問題：想要吃得好又想要錢花得少、想用較少的次數搬完東西但是又不想太費力，許多事都可以用多目標最佳化的角度來思考，其中目標數更多更複雜的高目標最佳化問題在近年獲得了許多關注，如何設計出有效率並且效能良好的高目標最佳化演化演算法已經成為了近年重要的課題。 近年發表的 NSGA-III 與 VaEA 在高目標最佳化問題都有優秀的表現，本論文對這二個演算法進行分析與討論，並嘗試不同的參考點策略來進行改良：使用 IPBI 函數改變搜尋行為，使其能在參考點分布與問題前緣形狀不符合的時候仍然有能力搜尋到最佳解；改變 VaEA 演算法的初始參考點策略，使其能夠獲得更佳的極限值；將 VaEA 的動態參考點概念與環境選擇機制與 NSGA-III 結合成新的混合演算法。實驗結果也顯示我們嘗試的各種參考點策略能夠根據問題有效改善演算法的效能。