研究生: |
張漢利 Hendri Sutrisno |
---|---|
論文名稱: |
運用於高維度計算問題之群集共生有機搜索演算法 A Clustering-Based Symbiotic Organisms Search for High-Dimensional Problems |
指導教授: |
楊朝龍
Chao-Lung Yang |
口試委員: |
歐陽超
Chao Ou-Yang 郭人介 Ren-Jieh Kuo 楊朝龍 Chao-Lung Yang |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2018 |
畢業學年度: | 106 |
語文別: | 英文 |
論文頁數: | 59 |
中文關鍵詞: | 啟發式演算法 、最佳化 、共生有機演算搜索演算法 、高維度計算問題 |
外文關鍵詞: | clustering-based symbiotic organisms search, high-dimensional problems |
相關次數: | 點閱:257 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
共生有機搜索演算法(SOS)算是一個新穎但是強大的啟發式優化方法。已有研究指出SOS具有比基因演算法(GA)以及粒子群體演算法(PSO)更佳的表現,但是尚未有任何研究針對其運算時間以及處理高維度問題時的效率進行探討。本研究提出一個以分群為主要架構的SOS(CSOS)的SOS方法,來解決高維度最佳化問題。CSOS的運作原理為運用內建的K-means分群演算法以及一個兩階層的互動模式來達成。K-means分群演算法用於替母體的可行解進行分群,並創造出子母體的環境。至於兩階層互動模式則分為兩部分--群內互動以及群間互動。在群內互動中,所有群內的可行解將會被強迫與其他可行解互動,增加群內探索的機率。而群間互動中,將是分群後的可行解群移動至目前已知最佳解,使得模型能更快收斂。本研究將用36個具有標準性的數學問題測試CSOS、GA、PSO以及SOS,並將其運算效率做比較。研究結果顯示CSOS在搜尋解的品質上優於其他演算法,而且比SOS更是節省了12%-75%的運算時間。本研究也研究如何挑選CSOS中的合適分群數。研究結果建議對於低維度問題,取母體資料10%的筆數較佳, 而高維度問題則增加到母體資料的30%筆數較佳。此外, 建議的分群數在往後也能納入CSOS的經驗法則中。針對高維度問題更進一步來說,CSOS不僅能找出更高品質的可行解,也能減輕維度災難(Curse of Dimension)帶來的影響,而且模型收斂的速度也較SOS快。
Symbiotic organisms search (SOS) is a relatively new yet powerful metaheuristic optimization approach. SOS was found outperforming the genetic algorithm (GA) and the particle swarm optimization (PSO), but there are no reports on its computational time and its performance on high-dimensional problems. This paper proposes the clustering-based SOS (CSOS), an innovative algorithm based on SOS, mainly built for high-dimensional optimization problems. CSOS works with a built-in ?-means clustering procedure and two-layer interaction patterns. The ?-means clustering method are used to cluster the solutions in population, to create a multi-subpopulation environment. The interaction pattern in CSOS is distinguished into in-cluster and between-cluster interaction. With in-cluster interaction, the solutions are forced to interact with other solution in their cluster, so the possibility to explore its own cluster is increased. The between-cluster concept is used to move the clustered solutions to the best known solution, so the model could be faster converged. CSOS later is tested on 36 mathematical benchmark problems and its performance is compared to GA, PSO, and SOS. The results show that CSOS successfully outperforms the others in searching quality, and even 12-75% faster than SOS. This research also studies how to determine the number of clusters in CSOS. The suggested number of clusters for low-dimension problems is 10%, and 30% of population size for high-dimension problems. The suggested number of clusters later can be used as a rule of thumb information for CSOS. More specific on high-dimension problems, not only producing a better solution quality, CSOS can alleviate the dimensionality effect, and converge faster than SOS.
[1] M.-H. Tayarani-N, X. Yao, and H. Xu, "Meta-Heuristic Algorithms in Car
Engine Design: A Literature Survey," IEEE Transactions on Evolutionary
Computation, vol. 19, no. 5, pp. 609-629, 2015.
[2] S. Chen, J. Montgomery, and A. Bolufé-Röhler, "Measuring the curse of
dimensionality and its effects on particle swarm optimization and
differential evolution," Applied Intelligence, vol. 42, pp. 514-526, 2014.
[3] G. A. Trunfio, "Metaheuristics for Continuous Optimization of High-
Dimensional Problems: State of the Art and Perspectives," in Big Data
Optimization: Recent Developments and Challenges, A. Emrouznejad, Ed.
Switzerland: Springer, 2016, pp. 437-460.
[4] M.-Y. Cheng and D. Prayogo, "Symbiotic Organisms Search: A new
metaheuristic optimization algorithm," Computers and Structures, vol. 139,
pp. 98-112, 2014.
[5] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine
Learning. Massachusetts: Addison Wesley, 1989.
[6] R. L. Haupt and S. E. Haupt, Practical genetic algorithms. John Wiley &
Sons, 2004.
[7] J. H. Holland, "Adoption in natural and artificial systems," ed. Ann Harbor,
MI: The University of Michigan Press, 1975.
[8] Z. Qiongbing and D. Lixin, "A new crossover mechanism for genetic
algorithms with variable-length chromosomes for path optimization
problems," Expert Systems with Applications, vol. 60, pp. 183-189, 2016.
[9] A. E. Eiben and C. H. M. v. Kemenade, "Diagonal crossover in genetic
algorithms for numerical optimization," Control and Cybernatics, vol. 26,
no. 3, pp. 447-465, 1997.
[10] M. Mehra, M. L. Jayalal, A. J. Arul, S. Rajeswari, K. K. Kuriakose, and S.
A. V. S. Murty, "Study on Different Crossover Mechanisms of Genetic
Algorithm for Test Interval Optimization for Nuclear Power Plants,"
International Journal of Intelligent Systems and Applications, vol. 1, pp. 20-
28, 2014.
[11] J. Kennedy and R. Eberhart, "Particle Swarm Optimization," in Proceedings
of IEEE International Conference on Neural Networks, 1995, vol. IV, pp.
1942–1948: IEEE.
[12] W. Guo, G. Chen, and X. Feng, "A New Strategy of Acceleration
Coefficients for Particle Swarm Optimization," in Proceedings of the 10th
International Conference on Computer Supported Cooperative Work in
Design, 2006, vol. 5, pp. 72-76.
[13] X.-F. Xie, W.-J. Zhang, and Z.-L. Yang, "A Dissipative Particle Swarm
Optimization," in Proceedings of the 2002 Congress on Evolutionary
Computation, 2002: IEEE.
[14] D. Mandal, S. P. Ghoshal, and A. K. Bhattacharjee, "Radiation pattern
optimization for concentric circular antenna array with central element
feeding using craziness‐based particle swarm optimization," International
Journal of RF and Microwave Computer-Aided Engineering, vol. 20, no. 5,
pp. 577-586, 2010.
[15] B. Das, V. Mukherjee, and D. Das, "DG placement in radial distribution
network by symbiotic organisms search algorithm for real power loss
minimization," Applied Soft Computing, vol. 49, no. 49, pp. 920-936, 2016.
[16] D. Prasad and V. Mukherjee, "A novel symbiotic organisms search
algorithm for optimal power flow of power system with FACTS devices,"
Engineering Science and Technology, an International Journal, vol. 19, no.
19, pp. 79-89, 2016.
[17] U. Sadek, A. Sarjas, A. Chowdhury, and R. Svecko, "Improved adaptive
fuzzy backstepping control of a magnetic levitation system based on
Symbiotic Organism Search," Applied Soft Computing, vol. 56, no. 56, pp.
19-33, 2017.
[18] G. G. Tejani, V. J. Savsani, and V. K. Patel, "Adaptive symbiotic organisms
search (SOS) algorithm for structural design optimization," Computational
Design and Engineering, vol. 3, no. 3, pp. 226-249, 2016.
[19] D. T. T. Do and J. Lee, "A modified symbiotic organisms search (mSOS)
algorithm for optimization of pin-jointed structures," Applied Soft
Computing, vol. 61, no. 61, pp. 683-699, 2017.
[20] M. Abdullahi, M. A. Ngadi, and S. i. M. Abdulhamid, "Symbiotic Organism
Search optimziation based task scheduling in cloud computing
environment," Future Generation Computer Systems, vol. 56, no. 56, pp.
640-650, 2016.
[21] A. E.-S. Ezugwu, A. O. Adewumi, and M. E. Frincu, "Simulated annealing
based symbiotic organisms search optimization algorithm for traveling
salesman problem," Expert Systems With Applications, vol. 77, no. 77, pp.
189-210, 2017.
[22] V. F. Yu, A. A. N. P. Redi, C.-L. Yang, E. Ruskartina, and B. Santosa,
"Symbiotic organisms search and two solution representations for solving
the capacitated vehicle routing problem," Applied Soft Computing, vol. 52,
no. 52, pp. 567-572, 2017.
[23] D. C. Secui, "A modified Symbiotic Organisms Search algorithm for large
scale economic dispatch problem with valve-point effects," Energy, vol. 113,
no. 113, pp. 366-384, 2016.
[24] S. J. Nanda and N. Jonwal, "Robust nonlinear channel equalization using
WNN trained by symbiotic organism search algorithm," Applied Soft
Computing, vol. 57, no. 57, pp. 197-209, 2017.
[25] D.-H. Tran, M.-Y. Cheng, and D. Prayogo, "A novel Multiple Objective
Symbiotic Organisms Search (MOSOS) for time-cost-labor utilization
tradeoff problem," Knowledge-Based Systems, vol. 94, no. 94, pp. 132-145,
2016.
[26] A. Panda and S. Pani, "A Symbiotic Organisms Search algorithm with
adaptive penalty function to solve multi-objective constrained optimization
problems," Applied Soft Computing, vol. 46, no. 46, pp. 344-360, 2016.
[27] C. Li and S. Yang, "A Clustering Particle Swarm Optimizer for Dynamic
Optimization," in 2009 IEEE Congress on Evolutionary Computation,
Trondheim, Norway, 2009, pp. 439-446: IEEE.
[28] G. Liu, Y. Li, X. Nie, and H. Zheng, "A novel clustering-based differential
evolution with 2 multi-parent crossovers for global optimization," Applied
Soft Computing, vol. 12, no. 2, pp. 663-681, 2012.
[29] M. Jamil and X.-S. Yang, "A literature survey of benchmark functions for
global optimisation problems," Int. J. of Mathematical Modelling and
Numerical Optimisation, vol. 4, no. 2, pp. 150-194, 2013.