學位論文
Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912
Browse
10 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 以改良式粒子群演算法進行分類問題之特徵選擇(2023) 呂政儒; Lu, Cheng-Ju特徵選擇是分類問題中降低問題維度的一種重要前處理技術，能消除冗餘和不相關的特徵，留下有用的特徵進行分類，提高分類準確率。隨著資料集維度增加，搜尋空間將急遽加大，這對各種最佳化演算法來說是一個挑戰。本研究希望能提出演算法，以小量計算資源找到一組少量且具有良好分類效果的特徵子集。研究基於當今主流的粒子群演算法，加入搜尋空間調整相關設計、參考相對優秀粒子的較差粒子調整策略，以及一個具方向性的新粒子群產生策略，該策略使用外部族群更新與紀錄演化過程中找到的多組特徵子集，並將其作為產生新粒子群的參考點。實驗結果與文獻演算法比較後，顯示所提出之演算法機制與設計具有良好的分類效能與較少的特徵數。Item 求解多極值連續型最佳化問題之演化演算法設計(2023) 黃敬庭; Huang, Jing-Ting多極值連續型最佳化問題需要在決策空間中找出數個相異的全域最佳解，許多現實問題皆是多極值問題，如：桁架 (truss) 結構最佳化、藥物分子設計及工廠排程問題等，在此類問題中找到相異的全域最佳解可以幫助決策者了解問題背後隱藏的因素，或是提供備選方案以備不時之需。近幾年演化演算法逐漸成為解最佳化問題的主流演算法，此類方法利用解個體之間彼此交換資訊、產生新的解個體以此來使族群逐漸往全域最佳解收斂，但收斂意味者族群多樣性喪失或陷入區域最佳解而無法找出其它潛力解，因此如何避免收斂並維持族群多樣性以搜尋不同的區域，是利用演化演算法解多極值最佳化問題的其中一項重要議題。本論文提出了使用混合利基法之潛力區域探索演算法框架 (Promising Area Exploration based on Hybrid Niching, PAEHN)，探討如何將主要族群分為多個子族群以搜尋解空間中的相異區域。在演化過程中記錄潛力解區域，當子族群都已收斂或停滯時，在潛力解區域附近重新產生主要族群以搜尋更多最佳解。此框架可套用不同的演化演算法進行演化，本論文使用 SHADE 作為基底演算法，SHADE 為自適應參數控制的差分演算法且已被證實於連續型單目標最佳化問題具有良好的效率。實驗結果得知 PAEHN 在容許誤差小的情況下具有良好的競爭力；而在容許誤差大的情況下具有相當強的優勢，於 20 個測試問題中有 18 個問題可以找出所有的全域最佳解，且 PAEHN 不需要使用問題的任何先備知識。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 以協同演化演算法求解單目標大規模全域最佳化問題(2020) 周彥辰; Jou, Yann-Chern隨著科學技術的進步及大數據的時代來臨，我們面臨的最佳化問題越來越龐大，變數也越來越多，甚至多達上千個；隨著最佳化問題的維度增加，大部分演化演算法的性能將因此迅速惡化而陷入高維度災難。因此，近年來有越來越多的演化計算領域學者投入大規模全域最佳化問題的研究並應用於求解生活中的實際問題。 本研究結合目前兩大主流應用於大規模單目標實數最佳化的方法—協同演化框架 (CC) 和SHADE演算法，提出CBCCLS-mSHADE-RDG3 演算法。從大量的參數調整實驗到演算法行為設計與驗證，一步一步將CC與SHADE演算法結合。於CC框架下，我們採用RDG3 演算法做為問題分解策略；使用CBCC3 進行計算資源的分配，給予對整體適應值貢獻度高的子族群更多必須的計算資源提升演算法效能；以改良版 mSHADE演化子族群。另外，我們提出一個新穎的設計，於 CBCC3 架構下，對適應值貢獻度高的子族群除了使用mSHADE演算法進行演化外，我們以額外區域搜尋演算法MTS-LS1 協助提升最佳解之品質。此獨特設計從實驗結果驗證得知，不僅可以穩定LSGO問題解的品質，更可以提升求解部分可疊加分解問題的效能，整體演算法表現與近兩年的LSGO比賽優勝演算法相比頗具競爭力。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 結合成新的混合演算法。實驗結果也顯示我們嘗試的各種參考點策略能夠根據問題有效改善演算法的效能。