臺灣博碩士論文加值系統

啟發式演算法是一種新穎的最佳化演算法，通常是由自然界中取得靈感，近年來也有許多學者提出各種啟發式演算法，並使用來解決許多最佳化的問題，例如基因演算法(GA)，人工蜂群演算法(ABC)，粒子群最佳化演算法（PSO），烏鴉演算法（CSA），鯨魚演算法（WOA）。其中以粒子群最佳化演算法最廣泛使用，但不同演算法也有不同的缺點，像是粒子群最佳化演算法容易過早收斂，陷入局部最佳解，而基因演算法的編碼困難以及不確定性。因此若能提出一種可以增加計算的能力以及增加粒子的多樣性，是必能夠解決現有演算法的問題。所以本論文提出了一種混合式演算法，名為鯨魚粒子群聚演算法（Whale Particle Optimization Algorithm, WPO），其結合了鯨魚演算法以及粒子群最佳化演算法的優點，目的在於增加粒子的多樣性，且有能力跳出局部最佳解。為了評估提出的演算法，本論文使用了四種最佳化問題來評估所提出演算法的效能，分別為函數最佳化、影像分割、流線型工廠排程、以及資料分群。選用的測試資料將會使用幾個現實生活中的資料及來評估提出的演算法。而結果證明，本論文提出的演算法跟現有的演算法相比，具有很好的競爭力。

Metaheuristic algorithm is a novel optimization algorithm. It’s usually inspired by natural phenomena. In recent years, many scholars have also proposed various metaheuristic algorithms and used them to solve many optimization problems, such as genetic algorithm (GA), artificial bee colony (ABC), particle swarm optimization algorithm (PSO), crow search algorithm (CSA), whale optimization algorithm (WOA), PSO is the most widely used among them, because the concept of PSO is simple and easy to implement. However, different algorithms also have different weakness. For example, PSO tends to premature convergence and stuck in the local optimal solution. GA is difficult to choose of genetic encoding and complicated parameter adjustment. Therefore, if an algorithm which can increase the computational power and increase the diversity between particles be proposed, it must be able to solve the problems of existing algorithms. As a consequence, this paper purposes a hybrid algorithm named whale particle optimization algorithm (WPO), which combines the advantages of whale optimization algorithm and particle swarm optimization algorithm. The goal of the purpose algorithm is to increase the diversity and has the ability to jump out of the local optimal solution. In order to evaluate the performances, this paper use four optimization problems including function evaluations, image segmentation, permutation flow shop scheduling problems, and data clustering. The proposed algorithms are evaluated using real-world benchmarks. The results indicate that the proposed algorithms are very competitive compared to the existing algorithms.

摘要 i
Abstract ii
致謝 iii
目錄 v
表目錄 vii
圖目錄 viii
1、 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 2
1.3 論文架構 3
2、 文獻回顧 4
2.1 啟發式演算法（Metaheuristic Algorithms） 4
2.1.1 粒子群最佳化演算法（Particle Swarm Optimization, PSO） 5
2.1.2 鯨魚演算法（Whale Optimization Algorithm, WOA） 6
2.1.3 烏鴉演算法（Crow Search Algorithm, CSA） 9
2.2 K-均值算法（K-means） 11
2.3 模糊C均值聚類演算法（Fuzzy C-means） 11
2.4 函數最佳化（Function Evaluations） 13
2.5 影像分割（Image Segmentation） 13
2.5.1 峰值信噪比（Peak signal-to-noise ratio, PSNR） 13
2.6 流線型工廠排程（Permutation Flow Shop Scheduling Problems） 14
2.6.1 NEH演算法 15
2.6.2 排程問題的局部搜尋 15
2.6.3 標準差 16
2.7 資料分群（Data Clustering） 16
2.7.1 正確率 17
3、 研究方法 19
3.1 初始化粒子 19
3.2 同步執行 19
3.3 更新粒子 20
3.4 混合運算（Hybrid Operator） 20
3.5 演算法總結 21
4、 研究結果與分析 25
4.1 使用資料集 25
4.2 參數設定 29
4.3 比較結果 30
4.3.1 函數最佳化比較結果 30
4.3.2 影像分割比較結果 39
4.3.3 流線型工廠排程比較結果 40
4.3.4 資料分群比較結果 42
5、 結論與未來展望 43
6、 參考文獻 44

[1] A. Ahmad, & S. S. Khan, (2019). Survey of state-of-the-art mixed data clustering algorithms. IEEE Access, 7, 31883-31902.
[2] Y. L. Abdel-Magid, M. A. Abido, S. Al-Baiyat, & A. H. Mantawy, (1999). Simultaneous stabilization of multimachine power systems via genetic algorithms. IEEE transactions on Power Systems, 14(4), 1428-1439.
[3] A. Askarzadeh, (2016). A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm. Computers & Structures, 169, 1-12.
[4] S. Arora, & S. Singh, (2019). Butterfly optimization algorithm: a novel approach for global optimization. Soft Computing, 23(3), 715-734.
[5] E. Aarts, E. H. Aarts, & J. L. Lenstra, (Eds.). (2003). Local search in combinatorial optimization. Princeton University Press.
[6] J. C. Bezdek, (2013). Pattern recognition with fuzzy objective function algorithms. Springer Science & Business Media.
[7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, & C. Stein, (2009). Introduction to algorithms. MIT press.
[8] L. Chen, C. P. Chen, & M. Lu, (2011). A multiple-kernel fuzzy c-means algorithm for image segmentation. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 41(5), 1263-1274.
[9] M. Dolatabadi, & Y. Damchi, (2019). Graph Theory Based Heuristic Approach for Minimum Break Point Set Determination in Large Scale Power Systems. IEEE Transactions on Power Delivery, 34(3), 963-970.
[10] M. Dorigo, M. Birattari, & T. Stutzle, (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4), 28-39.
[11] J. C. Dunn, (1973). A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters.
[12] J. Derrac, S. García, D. Molina, & F. Herrera, (2011). A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 1(1), 3-18.
[13] R. Enayatifar, A. H. Abdullah, & I. F. Isnin, (2014). Chaos-based image encryption using a hybrid genetic algorithm and a DNA sequence. Optics and Lasers in Engineering, 56, 83-93.
[14] R. Eberhart, & J. Kennedy, (1995, November). Particle swarm optimization. In Proceedings of the IEEE international conference on neural networks (Vol. 4, pp. 1942-1948).
[15] F. W. Glover, & G. A. Kochenberger, (Eds.). (2006). Handbook of metaheuristics (Vol. 57). Springer Science & Business Media.
[16] D. E. Goldberg, & J. H. Holland, (1988). Genetic algorithms and machine learning.
[17] F. Han, J. Jiang, Q. H. Ling, & B. Y. Su, (2019). A survey on metaheuristic optimization for random single-hidden layer feedforward neural network. Neurocomputing, 335, 261-273.
[18] Y. Hu, & S. X. Yang, (2004, April). A knowledge based genetic algorithm for path planning of a mobile robot. In IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA'04. 2004 (Vol. 5, pp. 4350-4355). IEEE.
[19] K. W. Huang, Z. X. Wu, H. W. Peng, M. C. Tsai, Y. C. Hung, & Y. C. Lu, (2019). Memetic Particle Gravitation Optimization Algorithm for Solving Clustering Problems. IEEE Access, 7, 80950-80968.
[20] K. W. Huang, & Z. X. Wu, (2018). CPO: A Crow Particle Optimization Algorithm. International Journal of Computational Intelligence Systems, 12(1), 426-435.
[21] J. A. Hartigan, & M. A. Wong, (1979). Algorithm AS 136: A k-means clustering algorithm. Journal of the Royal Statistical Society. Series C (Applied Statistics), 28(1), 100-108.
[22] J. Kennedy, (2006). Swarm intelligence. In Handbook of nature-inspired and innovative computing (pp. 187-219). Springer, Boston, MA.
[23] A. H. Khan, S. Li, & X. Luo, (2019). Obstacle avoidance and tracking control of redundant robotic manipulator: An rnn based metaheuristic approach. IEEE Transactions on Industrial Informatics.
[24] D. Karaboga, & B. Basturk, (2007). A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of global optimization, 39(3), 459-471.
[25] R. C. T. Lee, R. C. Chang, Y. T. Tsai, & S. S. Tseng, (2005). Introduction to the Design and Analysis of Algorithms. Tata McGraw-Hill.
[26] H. Liu, R. Zhao, H. Fang, F. Cheng, Y. Fu, & Y. Y. Liu, (2017). Entropy-based consensus clustering for patient stratification. Bioinformatics, 33(17), 2691-2698.
[27] K. Mistry, L. Zhang, S. C. Neoh, C. P. Lim, & B. Fielding, (2016). A micro-GA embedded PSO feature selection approach to intelligent facial emotion recognition. IEEE transactions on cybernetics, 47(6), 1496-1509.
[28] S. Mirjalili, S. M. Mirjalili, & A. Lewis, (2014). Grey wolf optimizer. Advances in engineering software, 69, 46-61.
[29] S. Mirjalili, (2015). Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm. Knowledge-based systems, 89, 228-249.
[30] S. Mirjalili, & A. Lewis, (2016). The whale optimization algorithm. Advances in engineering software, 95, 51-67.
[31] N. Mladenović, & P. Hansen, (1997). Variable neighborhood search. Computers & operations research, 24(11), 1097-1100.
[32] W. Niu, Z. Zhuo, X. Zhang, X. Du, G. Yang, & M. Guizani, (2019). A heuristic statistical testing based approach for encrypted network traffic identification. IEEE Transactions on Vehicular Technology, 68(4), 3843-3853.
[33] F. Neri, & C. Cotta, (2012). Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2, 1-14.
[34] M. Nawaz, E. E. Enscore Jr, & I. Ham, (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.
[35] D. L. Pham, C. Xu, & J. L. Prince, (2000). Current methods in medical image segmentation. Annual review of biomedical engineering, 2(1), 315-337.
[36] T. Sousa, A. Silva, & A. Neves, (2004). Particle swarm based data mining algorithms for classification tasks. Parallel computing, 30(5-6), 767-783.
[37] C. L. Srinidhi, P. Aparna, & J. Rajan, (2019). Automated Method for Retinal Artery/Vein Separation via Graph Search Metaheuristic Approach. IEEE Transactions on Image Processing, 28(6), 2705-2718.
[38] Y. Sun, B. Xue, M. Zhang, & G. G. Yen, (2019). Evolving deep convolutional neural networks for image classification. IEEE Transactions on Evolutionary Computation.
[39] Y. Shi, & R. Eberhart, (1998, May). A modified particle swarm optimizer. In 1998 IEEE international conference on evolutionary computation proceedings. IEEE world congress on computational intelligence (Cat. No. 98TH8360) (pp. 69-73). IEEE.
[40] M. Sezgin, & B. Sankur, (2004). Survey over image thresholding techniques and quantitative performance evaluation. Journal of Electronic imaging, 13(1), 146-166.
[41] M. F. Tasgetiren, Y. C. Liang, M. Sevkli, & G. Gencyilmaz, (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European journal of operational research, 177(3), 1930-1947.
[42] E. Taillard, (1993). Benchmarks for basic scheduling problems. european journal of operational research, 64(2), 278-285.
[43] D. W. Van der Merwe, & A. P. Engelbrecht, (2003, December). Data clustering using particle swarm optimization. In The 2003 Congress on Evolutionary Computation, 2003. CEC'03. (Vol. 1, pp. 215-220). IEEE.
[44] Z. X. Wu, K. W. Huang, & A. S. Girsang, (2018, November). A Whole Crow Search Algorithm for Solving Data Clustering. In 2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI) (pp. 152-155). IEEE.
[45] X. S. Yang, (2008). Firefly algorithm. Nature-inspired metaheuristic algorithms, 20, 79-90.
[46] X. S. Yang, & S. Deb, (2009, December). Cuckoo search via Lévy flights. In 2009 World congress on nature & biologically inspired computing (NaBIC) (pp. 210-214). IEEE.
[47] G. Y. Zhu, C. Ding, & W. B. Zhang, (2020). Optimal foraging algorithm that incorporates fuzzy relative entropy for solving many-objective permutation flow shop scheduling problems. IEEE Transactions on Fuzzy Systems.
[48] G. Zames, N. M. Ajlouni, N. M. Ajlouni, N. M. Ajlouni, J. H. Holland, W. D. Hills, & D. E. Goldberg, (1981). Genetic algorithms in search, optimization and machine learning. Information Technology Journal, 3(1), 301-302.