(3.239.33.139) 您好!臺灣時間:2021/03/05 19:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:呂明峻
研究生(外文):Ming-Chun Lu
論文名稱:基於分群與資源分配之全域和區域的自適應調整:一個嶄新的實數最佳化方法
論文名稱(外文):Global and Local Adaptation with Clustering Embedded Resource Allocation (GLACERA): A Novel Approach for Continuous Optimization
指導教授:于天立
指導教授(外文):Tian-Li Yu
口試委員:陳和麟雷欽隆陳穎平
口試委員(外文):Ho-Lin ChenChin-Laung LeiYing-Ping Chen
口試日期:2019-07-10
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:英文
論文頁數:65
中文關鍵詞:實數最佳化多模態最佳化分群多臂吃角子老虎技術IEEE CEC 2005IEEE CEC 2013
DOI:10.6342/NTU201901855
相關次數:
  • 被引用被引用:0
  • 點閱點閱:27
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
實數最佳化與現實生活中的問題息息相關。而這些問題因為多模態(multimodal)和崎嶇不平(rugged)等因素變得複雜,促使研究者發展更好和更有效率的解決方法。本論文提出一個名叫”基於分群與資源分配之全域和區域的自適應調整”的新方法。我們感興趣的是趨勢不被崎嶇不平所干擾的問題,也就是區域最佳解能引導我們找到全域最佳解。這些問題可以任意地旋轉、平移和放大縮小,並且可以擁有任意維度。為了能夠更有效率的解決這些問題,本論文提出一個新的分群方法來幫助分辨區域最佳解。接著,我們提出一個新的多臂吃角子老虎技術(multi-armed bandit)技術,來分配資源給各個區域最佳解,使得獲得全域最佳解的機率最大化。然而,在分配資源的過程中,會遇到探索(exploration)和開發(exploitation)的平衡問題。因此,我們提出了一個新的算式來平衡開發和探索的比例。最後,我們探討族群大小來增進我們演算法的表現,並且將測試在兩套標準IEEE CEC 2005和IEEE CEC 2013的結果與四個目前最佳最常用的演算法進行比較。
Continuous optimization problems, which are highly related to real-world problems are complex as they are multimodal and rugged that motivate re-searchers to develop better and more efficient problem-solving methods. In this thesis, we introduce a new algorithm called Global and Local Adaptation with Clustering Embedded Resource Allocation (GLACERA) for continuous optimization. We are interested in problems that their ruggedness do not affect tendency, which means that local optima can give us clues to find global optimum. The problem’s dimension, rotation, shift and scale can be arbitrary.To solve problems more efficiently, a new clustering technique is proposed in this thesis to help identify potential local optima. Then, a new multi-armed bandit technique, aiming to reach global optimum with greater probability,is presented to allocate resources for each local optimum. However, allocating resources to exploit different local optima leads to the common dilemma between exploration and exploitation. As a result, we proposed a new formula to calibrate the ratio between exploration and exploitation according to remaining function evaluations. Finally, the population size is discussed to improve the performance of our algorithm. We compare our algorithm with four milestone algorithms that are commonly used for continuous optimization. The results are evaluated with the continuous optimization benchmark problems of IEEE CEC 2005 and IEEE CEC 2013.
誌謝 i
中文摘要 iii
Abstract v
1 Introduction 1
1.1 ThesisObjectives .............................. 2
1.2 Roadmap .................................. 3
2 Motivation 5
2.1 Ruggedness................................. 6
2.2 Coarse-grained vs Fine-grained....................... 8
2.3 Resource Allocation............................. 10
3 Related Work 13
3.1 CMA-ES .................................. 13
3.1.1 Evolution Strategy ......................... 13
3.1.2 Rank-μ-Update........................... 15
3.1.3 Rank-One-Update ......................... 16
3.1.4 Combining Rank-μ-Update and Rank-One-Update . . . . . . . . 17
3.1.5 Step-Size Control.......................... 17
3.1.6 Summary of CMA-ES ....................... 18
3.2 SPSO .................................... 19
3.2.1 Initialization of the Particles .................... 19
3.2.2 The Velocity Update Equations .................. 20
3.2.3 Confinement ............................ 21
3.2.4 The Adaptive Random Topology.................. 21
3.3 ACOR .................................... 22
3.3.1 Solution Construction ....................... 22
3.3.2 Pheromone Update......................... 23
3.4 AMaLGaM ................................. 23
3.4.1 Adaptive Variance Scaling(AVS) ................. 23
3.4.2 Standard Deviation Ratio(SDR).................. 24
3.4.3 Anticipated Mean Shift(AMS)................... 24
3.4.4 Summary of AMaLGaM...................... 24
4 The GLACERA Algorithm 25
4.1 Global Explore and Local Exploit ..................... 25
4.1.1 GlobalExplore ........................... 25
4.1.2 LocalExploit............................ 26
4.1.3 Summary of Global Explore and Local Exploit . . . . . . . . . . 26
4.2 ClusteringTechniques ........................... 27
4.2.1 K-Means Clustering ........................ 27
4.2.2 Clustering with Dominant Number................. 28
4.2.3 Clustering with Distance...................... 29
4.2.4 Performance of Clustering Techniques. . . . . . . . . . . . . . . 30
4.3 Multi-armed Bandit Algorithm....................... 32
4.3.1 The Multi-armed Bandit Problem ................. 33
4.3.2 The Modified Bandit Technique .................. 35
4.4 Resource Allocation............................. 37
5 Experiments 47
5.1 Experiments Settings ............................ 47
5.2 IEEE CEC 2005 Benchmark Results.................... 49
5.3 IEEE CEC 2013 Benchmark Results.................... 51
6 Parameters Discussion 59
7 Conclusion 61
Bibliography 63
N. Hansen, S. D. M ̈uller, and P. Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES).Evolutionary Computation, 11(1):1–18, 2003.
M. Clerc. Standard particle swarm optimization.Retrieved from https://hal.archives-ouvertes.fr/hal-00764996/, 2012.
K. Socha and M. Dorigo. Ant conlony optimization for continuous domains.European journal of operational research, 185(3):1155–1173, 2008.
P. Bosman, J. Grahl, and D. Thierens. Benchmarking parameter-free AMaLGaM on functions with and without noise.Evolutionary Computation, 21(3):445–469, 2013.
J. Doye, M. Miller, and D. Wales. The double-funnel energy landscape of the 38-atom Lennard-Jones cluster.JOURNAL OF CHEMICAL PHYSICS, 110(14):6896–6906, 1999.
S. Lloyd. Least squares quantization in PCM.IEEE Transactions on Information Theory, 28(2):129–137, 1982.
P. N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y. P. Chen, A. Auger, and S. Tiwari. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Technical Report 2005005, Nanyang Technological University, Singapore, 2006.
J.-J. Liang, B.-Y. Qu, P. N. Suganthan, and A. Hern ́andez-D ́ıaz. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization. Technical Report 201212, Nanyang Technological University, Singapore,2013.
H. Simon. The architecture of complexity.Proceedings of the American Philosophical Society, 106(6):467–482, 1962.
I. Rechenberg .Evolutionsstrategie. Frommann-Holzboog, 1973.
M. Schumer and K. Steiglitz. Adaptive step size random search.IEEE Transactions on Automatic Control, 13(3):270–276, 1968.
J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of ICNN’95 - International Conference on Neural Networks, volume 4, pages 1942–1948, 1995.
S. Cheng, H. Lu, X.-J. Lei, and Y.-H. Shi. A quarter century of particle swarm optimization. Complex & Intelligent Systems, 4(3):227–239, 2018.
M. Dorigo, V. Maniezzo, and A. Colorni. Ant system: optimization by a colony of cooperating agents.IEEE Transactions on Systems, Man, and Cybernetics, Part B(Cybernetics), 26(1):29–41, 1996.
H. Robbins. Some aspects of the sequential design of experiments.Herbert Robbins Selected Papers, pages 169–177, 1985.
J. Vermorel and M. Mohri. Multi-armed bandit algorithms and empirical evaluation. In Machine Learning: ECML 2005, pages 437–448, 2005.
P. Auer. Using confidence bounds for exploitation-exploration trade-offs. The Journal of Machine Learning Research, 3:397–422, 2003.
P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multi armed bandit problem. Machine learning, 47(2-3):235–256, 2002.
C.-C. Yen. Multi-armed bandit based 2-layer covariance adaptation matrix evolution strategy. Master’s thesis, National Taiwan University, 2014.
M.ˇCrepinˇsek, S.-H. Liu, and M. Mernik. Exploration and exploitation in evolutionary algorithms: A survey. ACM Comput. Surv., 45(3):35:1–35:33, 2013.
J.-Y. Lin and Y.-P. Chen. Analysis on the collaboration between global search and local search in memetic computation.IEEE Transactions on Evolutionary Computation, 15(5):608–623, 2011.
J.-Y. Lin and Y.-P. Chen. When and what kind of memetic algorithms perform well. In 2012 IEEE Congress on Evolutionary Computation, pages 1–8, 2012.
J.-Y. Lin and Y.-P. Chen. On the effect of population size and selection mechanism from the viewpoint of collaboration between exploration and exploitation. pages 16–23, 2013.
Covariance Matrix Adaptation Evolution Strategy for non-linear numerical optimization in Python. https://pypi.org/project/cma/.
N. Hansen. The CMA Evolution Strategy: A Comparing Review, pages 75–102. Springer Berlin Heidelberg, 2006.
M. Zambrano-Bigiarini, M. Clerc, and R. Rojas. Standard Particle Swarm Optimisation 2011 at CEC-2013: A baseline for future PSO improvements. In 2013 IEEE Congress on Evolutionary Computation, pages 2337–2344, 2013.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔