以詢問式學習機制改良粒子群演算法應用於動態環境之研究

Particle Swarm Optimization with Query-Based Learning in Dynamic Environment

張竹君(Chu-Chun Chang)

指導教授 ： 張瑞益

國立臺灣大學/工學院/工程科學及海洋工程學研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.10555

摘要

多數現實世界的問題會因環境變動而改變，因此動態最佳化技術近年來逐漸受到重視。本論文提出一種詢問式學習粒子群演算法，根據最佳化過程所產生的歷史資料，學習問題環境特性並對演算法做出對應的改良，藉此改善不同特性之動態最佳化問題求解表現。本論文提出兩種主要改良方式，其一是根據環境變化特性自適應調整參數以及其二是預測最佳解位置變化。透過實驗知名動態最佳化基準GDBG所提供六種不同特性之動態環境變化設定，驗證本論文所提出之詢問式學習力自尋演算法能夠有效的從歷史資料中學習到問題特性，並以適當的回應來捕捉或預測環境變化後的最佳解位置，提高演算法的精準度以及廣度。實驗結果顯示所提出的演算法相對於原始mQSO演算法的解題效果改善了約11.37%，尤其在週期變化的動態最佳化問題中，詢問式學習方法有效地找到了最佳解的可能區域，而提升了約35.06%。

關鍵字

粒子群演算法 ； 動態最佳化 ； 詢問式學習

並列摘要

There is a growing interest in dynamic optimization problems as the optimal solution of real-world problem is usually changing over time. There are many challenges when facing DOPs. This thesis proposes a pilot study on Dynamic Particle Swarm Optimization with Query-Based Learning. We provide two QBL approaches, one with quantum parameter adaptation (QBLQPA) and another with optima prediction (QBLOP), to improve the optimizing behavior in dynamic environment. The main idea is to analyze the problem characteristics and to work out strategies with the obtained characteristics. By learning the problem characteristics from the historical data, our approaches evaluate whether the situation meets the prerequisites of QBL and activate the appropriate approach from the oracle to improve the optimization algorithm, particle swarm optimization. The well-known dynamic optimization benchmark, generalized dynamic benchmark generator system, is used to test the performance of our algorithm and the experimental results show that QBLQPA can adjust the number of quantum particles according to the shift severity of changing optima, and QBLOP can predict optimal position when finding some regular patterns in recurrent changes. Proposed algorithm can deal with different dynamic changes and outperforms original algorithm and its variant mPSODE reaching, on average, 11.37% and 8.00% improvement respectively. For the recurrent problems, our algorithm especially improves the solving ability by 35.06% with good prediction of possible optimal region.

並列關鍵字

Particle swarm optimization ； Dynamic optimization ； Query based learning

參考文獻

REFERENCE

[1] E. Vellasques, R. Sabourin, and E. Granger, "Gaussian mixture modeling for dynamic particle swarm optimization of recurrent problems." pp. 73-80.

[2] T. T. Nguyen, S. Yang, and J. Branke, “Evolutionary dynamic optimization: A survey of the state of the art,” Swarm and Evolutionary Computation, vol. 6, pp. 1-24, 2012.

[3] C. Cruz, J. R. González, and D. A. Pelta, “Optimization in dynamic environments: a survey on problems, methods and measures,” Soft Computing, vol. 15, no. 7, pp. 1427-1448, 2011.

[4] H. Ben-Romdhane, E. Alba, and S. Krichen, “Best practices in measuring algorithm performance for dynamic optimization problems,” Soft Computing, vol. 17, no. 6, pp. 1005-1017, 2013.