臺灣博碩士論文加值系統

本論文提出一篇具高度多樣性族群的自適應差分進化演算法，藉由提高族群的多樣性，來增加探勘與探索的能力，讓演算法能有效的解決單目標最佳化問題。
為了提高族群的多樣性來協助演算法進行演化，本論文在基本型差分進化演算法中加入數個機制，藉以提高演算法的搜索能力。首先演算法在搜索過程中，主要使用菁英制度的突變策略進行搜索，此突變策略可以降低陷入局部最佳解的機會與過早收斂的狀況。如果當演算法在演化的過程中，因族群陷入局部最佳解而無法進行演化時，將會啟動真隨機亂數突變機制，提高族群跳脫局部最佳解的能力以及探索未搜索範圍的機會。在交配機制中，基本型交配機制雖擁有讓向量群集中的能力，但是廣度探索的能力較弱，為改善廣度探索的能力，因而提出局部交配機制，此機制將可大大提升演算法於複雜型問題的廣度探索能力。
在實驗方法中，本研究採用CEC2005測試函數作為數據比較之基準，藉以測試本研究所提出的方法與近代改良型差分進化演算法做比較。在實驗結果中，大部分的測試函數裡，本研究所提出的方法都能搜索到最佳解或者找到優於其他演算法的解，尤其當維度增加時，本論文在大部分的測試函數中，依舊可以搜索到比其他演算法還要好的解。

This paper proposed an adaptive differential evolution algorithm with high diversity population (ADE-HP). The proposed method can increase diversity of population and increase vectors’ searching ability for solving single-objective numerical optimization problems.
In order to increase diversity of population in original DE, several mechanisms are proposed. First, Elitist mechanism can avoid vectors are guided to the same position (global best particle) and can prevent vectors form fall into local optimum even early convergence. Second, Real rand mechanism can give higher ability to jump out from local optimum and provide varied information to help particles toward to potential unsearched solution space for solution exploration. Finally, in order to increase vectors’ explore probability, the partial crossover mechanism is proposed.
25 test functions of CEC 2005 were adopted for experiments through a reasonable average and fitness evaluations. From the results, it can be observed that the proposed method can efficiently find better solutions than recent DE works for solving optimization problems.

致謝 I
摘要 II
ABSTRACT III
目錄 IV
表目錄 VI
圖目錄 VII
第1章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 3
1.3 論文架構 5
第2章 基本理論探討 7
2.1 最佳化問題 7
2.2 基本型演化式演算法 10
2.3 基本型演化式演算法之特性比較 17
2.4 差分進化演算法之改良與文獻回顧 18
第3章 具高度多樣性族群的自適應差分進化演算法 24
3.1 菁英突變(ELITIST MUTATION) 24
3.2 真實隨機亂數突變(REAL RANDOM) 25
3.3 局部交配(PARTIAL CROSSOVER) 27
3.4 邊界檢查機制(BOUNDARY CHECK) 28
3.5 自適應參數調整(ADAPTIVE PARAMETERS ADJUSTMENT) 30
3.6 流程圖(FLOWCHART) 32
第4章 實驗結果 35
4.1 測試函數 35
4.2 實驗環境與參數設定 46
4.3 實驗結果與比較 51
第5章 結論 74
參考文獻 76
作者簡歷 82

[1] J. Q. Yang, J. G. Yang and G. L. Chen, "Solving Large-Scale TSP Using Adaptive Clustering Method," in Proc. Second International Symposium on Computational Intelligence and Design (ISCID '09), Changsha, 2009.
[2] J. P. Wang and M. J. Hu, "A Solution for TSP Based on Artificial Fish Algorithm," in Proc. International Conference on Computational Intelligence and Natural Computing (CINC '09), Wuhan, 2009.
[3] Y. Zhang, P. P. Xie amd H. Li, "Multi-scale colour 3D satellite imagery and global 3D Web mapping," in Proc. Urban Remote Sensing Joint Event, Paris, 2007.
[4] S. Canavan, X. Zhang, L. J. Yin and Y. Zhang, "3D face sketch modeling and assessment for component based face recognition," in Proc. 2011 International Joint Conference on Biometrics (IJCB), Washington, DC, 2011.
[5] L. Chen, "Pattern classification by assembling small neural networks," in Proc. 2005 IEEE International Joint Conference on Neural Networks (IJCNN '05), Québec, Canada, 2005.
[6] S. Razavi and B. A. Tolson, "A New Formulation for Feedforward Neural Networks," IEEE Transactions on Neural Networks, pp. 1588 - 1598, 2011.
[7] L. B. Booker, D. E. Goldberg and J. H. Holland, "Classifier systems and genetic algorithms," Artificial Intelligence, p. 235–282, 1989.
[8] 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, pp. 29 - 41, 1996.
[9] R. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in Proc. Sixth International Symposium on Micro Machine and Human Science (MHS '95), Nagoya, 1995.
[10] R. Storn and K. V. Price, "Differential evolution—A simple and efficient adaptive scheme for global optimization over continuous spaces," in Proc. ICSI, Berkeley, CA, Tech. Rep. TR-95-012. [Online]. Available:http://http.icsi.berkeley.edu/~storn/litera.html, 1995.
[11] D. Karaboga, “An Idea Based On Honey Bee Swarm for Numerical Optimization,” TECHNICAL REPORT-TR06, 2005.
[12] S. T. Liu and C. Kao, "Network flow problems with fuzzy arc lengths," IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, pp. 765 - 769, 2004.
[13] A. K. Bangla and A.K. Castanon, "Accelerated dual coordinate algorithms for separable convex cost network flow problems," in Proc. 2012 IEEE 51st Annual Conference on Decision and Control (CDC), Maui, HI, 2012.
[14] G. Reynoso-Meza, X. Blasco, J. Sanchis and M. Martinez, "Multiobjective optimization algorithm for solving constrained single objective problems," in Proc. 2010 IEEE Congress on Evolutionary Computation (CEC), Barcelona, 2010.
[15] T. Y. Sun, W. C. Wu, S. J. Tsai, C. C. Liu, S. Y. Chiu and S. T. Hsieh, "Particle swarm optimizer for multi-objective problems based on proportional distribution and cross-over operation," in Proc. IEEE International Conference on Systems, Man and Cybernetics, Singapore, 2008.
[16] Y. Shi and R. Eberhart, "A modified particle swarm optimizer," in Proc. The 1998 IEEE International Conference on Evolutionary Computation Proceedings, Anchorage, AK, 1998.
[17] X. Bi and Y. Wang, "An improved artificial bee colony algorithm," in Proc. 2011 3rd International Conference on Computer Research and Development (ICCRD), Shanghai, 2011.
[18] R. Storn and K. Price, "Minimizing the real functions of the ICEC'96 contest by differential evolution," in Proceedings of IEEE International Conference on Evolutionary Computation, Nagoya, 1996.
[19] R. Storn and K. Price, "Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces," Journal of Global Optimization, pp. 341 - 359, 1997.
[20] D. Karaboga and B. Akay, "Artificial Bee Colony (ABC) Algorithm on Training Artificial Neural Networks," in Proc. IEEE 15th Signal Processing and Communications Applications, Eskisehir, 2007.
[21] A. K. Qin and P. N. Suganthan, "Self-adaptive differential evolution algorithm for numerical optimization," in Proc. The 2005 IEEE Congress on Evolutionary Computation, Edinburgh, 2005.
[22] J. Brest, S. Greiner, B. Boskovic, M. Mernik and V. Zumer, "Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems," IEEE Transactions on Evolutionary Computation, pp. 646 - 657, 2006.
[23] J. Zhang and A. C. Sanderson, "Self-Adaptive Differential Evolution with Fast and Reliable Convergence Performance," in Proc. IEEE Congress on Evolutionary Computation, Singapore, 2007.
[24] A. K. Qin, L. V. Huang and P. N. Suganthan, "Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization," IEEE Transactions on Evolutionary Computation, pp. 398 - 417, 2009.
[25] J. Zhang and A. C. Sanderson, "JADE: Adaptive Differential Evolution With Optional External Archive," IEEE Transactions on Evolutionary Computation, pp. 945 - 958, 2009.
[26] Q. K. Pan, P. N. Suganthan, L. W., L. Gao, R. Mallipeddi, "A differential evolution algorithm with self-adapting strategy and control parameters," Computers & Operations Research, p. 394–408, 2011.
[27] R. Mallipeddi, P. N. Suganthan, Q. K. Pan and M. F. Tasgetiren, "Differential evolution algorithm with ensemble of parameters and mutation strategies," Applied Soft Computing, p. 1679–1696, 2011.
[28] W. Gong, Z. Cai, C. X. Ling and C. Li, "Enhanced Differential Evolution With Adaptive Strategies for Numerical Optimization," IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, pp. 397 - 413, 2011.
[29] S. M. Islam, S. Das, S. Ghosh, S. Roy and P. N. Suganthan, “An Adaptive Differential Evolution Algorithm With Novel Mutation and Crossover Strategies for Global Numerical Optimization,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, pp. 482 - 500, 2012.
[30] S. T. Hsieh, S. Y. Chiu and S. J. Yen, "Real Random Mutation Strategy for Differential Evolution," in Proc. 2012 Conference on Technologies and Applications of Artificial Intelligence (TAAI), Tainan, 2012.
[31] M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, New York: Wiley, 1997.
[32] J. T. Tsai, T. K. Liu and J. H. Chou, "Hybrid Taguchi-genetic algorithm for global numerical optimization," IEEE Transactions on Evolutionary Computation, pp. 365 - 377, 2004.
[33] C. O. Imoru, "The power mean and the logarithmic mean," Int. J. Math. Math. Sci., vol. 2, no. 5, pp. 337-343, 1982.
[34] [Online]. Available: http://www.ntu.edu.sg/home/EPNSuga. [Accessed 25 02 2014].
[35] 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, Singapore: Nanyang Technol. Univ., 2005.