求解多極值連續型最佳化問題之演化演算法設計

Design of Evolutionary Algorithm for Solving Multimodal Continuous Optimization Problems

黃敬庭(Huang Jing-Ting)

指導教授 ： 蔣宗哲

國立臺灣師範大學/理學院/資訊工程學系/碩士(2023年)

https://doi.org/10.6345/NTNU202300305

摘要

多極值連續型最佳化問題需要在決策空間中找出數個相異的全域最佳解，許多現實問題皆是多極值問題，如：桁架 (truss) 結構最佳化、藥物分子設計及工廠排程問題等，在此類問題中找到相異的全域最佳解可以幫助決策者了解問題背後隱藏的因素，或是提供備選方案以備不時之需。近幾年演化演算法逐漸成為解最佳化問題的主流演算法，此類方法利用解個體之間彼此交換資訊、產生新的解個體以此來使族群逐漸往全域最佳解收斂，但收斂意味者族群多樣性喪失或陷入區域最佳解而無法找出其它潛力解，因此如何避免收斂並維持族群多樣性以搜尋不同的區域，是利用演化演算法解多極值最佳化問題的其中一項重要議題。
本論文提出了使用混合利基法之潛力區域探索演算法框架 (Promising Area Exploration based on Hybrid Niching, PAEHN)，探討如何將主要族群分為多個子族群以搜尋解空間中的相異區域。在演化過程中記錄潛力解區域，當子族群都已收斂或停滯時，在潛力解區域附近重新產生主要族群以搜尋更多最佳解。此框架可套用不同的演化演算法進行演化，本論文使用 SHADE 作為基底演算法，SHADE 為自適應參數控制的差分演算法且已被證實於連續型單目標最佳化問題具有良好的效率。實驗結果得知 PAEHN 在容許誤差小的情況下具有良好的競爭力；而在容許誤差大的情況下具有相當強的優勢，於 20 個測試問題中有 18 個問題可以找出所有的全域最佳解，且 PAEHN 不需要使用問題的任何先備知識。

關鍵字

演化演算法 ； 多極值連續型最佳化 ； 利基演算法 ； 子族群 ； 差分演化演算法

並列摘要

none

並列關鍵字

none

參考文獻

[1] R. Storn and K. Price, “Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces,” Global Optimization, vol. 11, pp. 341-359, 1997.

[2] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proceedings of ICNN'95 - International Conference on Neural Networks, vol. 4, pp. 1942-1948, 1995.

[3] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, 1st ed. USA: Addison-Wesley Professional, 1989.

[4] P. Moscato “On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms.” Caltech Concurrent Computation Program, C3P Report, vol. 826, 1989.

[5] K. A. De Jong, “An analysis of the behavior of a class of genetic adaptive systems,” Ph.D. Dissertation, University of Michigan, 1975.