臺灣博碩士論文加值系統

演化式演算法常用於求解組合性問題，大多數的演算法可求得不錯的求解品質。為了能有效率的求解全域最佳化問題，近年來多數的學者採用啟發式演算法來求解。但隨著問題複雜度的提升，啟發式演算法容易產生過早收斂或失去群族多樣性的問題。有鑑於此本研究提出運用資料探勘於帝國競爭演算法(Applying Data Mining technology in Imperialist Competitive Algorithm, DMICA)，主要基於帝國競爭演算法(Imperial Competitive Algorithm, ICA)的概念，以隨機组合的方式產生初始解，接著K-means分群演算法，將各可行解依照漢明距離的算法，分別跟各群的中心點計算相似度並做分群，再來透過資訊增益的亂度(Entropy)計算，找出關鍵位置優先探勘區塊後，依據這些區塊來組合人造解。並透過組合性標竿問題中的旅行銷售員問題(Traveling Salesman Problem)來驗證DMICA的求解品質及穩定性。由實驗結果顯示，證明本研究所提出之方法為一個具備競爭力之演化式演算法。

Evolutionary algorithms are often use to solve the combination problems. In recent years, researcher used heuristic algorithms to solve optimization problem. Most of the algorithms can achieve a good solution quality, but due to the combination of problems the complexity of solution is gradually increased, therefore, the evolution algorithm is likely to occur premature convergence or loss group of ethnic diversity. This study presents the DMICA (Applying Data Mining technology in Imperialist Competitive Algorithm). The concept of ICA (Imperial Competitive Algorithm) is based on random combination of ways to generate the initial solution, followed by K-means clustering algorithm. Each feasible solution is in accordance to the algorithm hamming distance, respectively with the center of each cluster. The information gain method used to identify the key priority position for mining blocks; we assemble these blocks to make an artificial chromosome. To verify the quality and stability of proposed DMICA, we applied proposed approach on benchmark problem of TSP. The results show that the proposed method is a competitive type of evolutionary algorithm.

書名頁 i
論文口試委員審定書 ii
授權書 iii
中文摘要 vi
英文摘要 vii
誌謝 viii
目錄 ix
表目錄 xi
圖目錄 xii
第一章、緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究流程 3
1.4 研究架構 4
第二章、文獻探討 5
2.1 旅行銷售員問題(Traveling Salesman Problem) 5
2.1.1 旅行銷售員問題之定義 5
2.1.2 旅行銷售員問題之分類 5
2.1.3 旅行銷售員問題之求解方法 6
2.2 K-means分群演算法(K-means Clustering) 7
2.3 資訊增益(Information Gain) 9
2.4 帝國競爭演算法(Imperial Competitive Algorithm) 11
2.4.1 同化作用 13
2.4.2 競爭作用 15
2.4.3 帝國競爭演算法之相關研究 16
2.5 基因演算法(Genetic Algorithm) 17
2.5.1 基因演算法之架構 17
2.5.2 基因演算法之應用 21
第三章、問題定義與介紹 22
3.1 參數與變數定義 22
3.2 數學模式建構 22
第四章、研究方法 25
4.1 DMICA流程 25
4.2 產生初始群集(Generate initial groups) 27
4.3 建構區塊(Build block) 30
4.3.1 計算亂度(Calculate entropy) 31
4.3.2 區塊探勘(Block mining) 32
4.4 組合人造解(Combine artificial chromosomes) 33
4.5 資源調配(Allocation of resources) 34
4.6 群體重組(Chromosomes recombination) 35
4.7 菁英選擇(Tournament selection) 36
第五章、研究結果 37
5.1 參數設定 37
5.2 驗證實驗 37
第六章、結論與未來展望 50
6.1 結論 50
6.2 未來展望 51
參考文獻 52

[1] C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity: Courier Corporation, 1998.
[2] Ĺim, O. K., and J. S. Arora, “An active set RQP algorithm for engineering design optimization,” Computer Methods in Applied Mechanics and Engineering, vol. 57, no. 1, pp. 51-65, 1986.
[3] Arshad, S., and Yang, S., “A hybrid genetic algorithm and inver over approach for the travelling salesman problem,” Evolutionary Computation, IEEE Congress on. IEEE, 2010.
[4] Whitely, L. D., Starkweather, T., and D’Ann Fuquay., “Scheduling problems and traveling salesman: The genetic edge recombination operator,” Third International Conference on Genetic Algorithms, pp. 133-140, 1989.
[5] Flood, M. M., “The Traveling Salesman Problem,” Operations Research, vol.4, pp. 64-75, 1956.
[6] Tasan, A. S. and Gen, M., “A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries,” Computers & Industrial Engineering, vol.62, no. 3 pp.755-761, 2012.
[7] C. Changdar, G. S. Mahapatra, and R. K. Pal, “An improved genetic algorithm based approach to solve constrained knapsack problem in fuzzy environment, vol. 42, pp. 2276-2286, 2015.
[8] S R. Zamani, "A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem,", vol. 229, pp. 552-559, 2013.
[9] Garey, M. R., Johnson, D.S., “Some simplified NP-complete graph problems,” Theoretical Computer Science, Vol. 1, pp. 237–267, 1976.
[10] Y. Deng, Y. Liu, and D. Zhou, "An improved genetic algorithm with initial population strategy for symmetric TSP," Mathematical Problems in Engineering, vol. 2015, p. 212794, 2015.
[11] O. Pedro, R. Saldanha, and R. Camargo, "A Tabu Search Approach for the Prize Collecting Traveling Salesman Problem," Electronic Notes in Discrete Mathematics, vol. 41, pp. 261-268, 2013.
[12] M. Mavrovouniotis and S. Yang, "Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors," Applied Soft Computing, vol. 13, pp. 4023-4037, 2013.
[13] Dasgupta, D., Ji, Z., and González, F. A., “Artificial Immune System Research in the Last Five Tears,” Proceedings of the Congress on Evolutionary Computation Conference, pp. 123-130, 2003.
[14] Y. Wang, D. Tian, and Y. Li, "An Improved Simulated Annealing Algorithm for Traveling Salesman Problem," in Proceedings of the 2012 International Conference on Information Technology and Software Engineering, vol. 211, pp. 525-532, 2013.
[15] Y.-x. Gao, Y.-m. Wang, and Z.-l. Pei, "An improved particle swarm optimisation for solving generalised travelling salesman problem," International Journal of Computing Science and Mathematics, vol. 3, pp. 385-393, 2012.
[16] A. Ahmad and L. Dey, "A k-mean clustering algorithm for mixed numeric and categorical data," Data & Knowledge Engineering, vol. 63, pp. 503-527, 2007.
[17] M. Norouzi, D. M. Blei, and R. R. Salakhutdinov, "Hamming distance metric learning," in Advances in neural information processing systems, 2012, pp. 1061-1069.
[18] Y. Tsujimura and M. Gen, "Entropy-based genetic algorithm for solving TSP," in Knowledge-Based Intelligent Electronic Systems, 1998. Proceedings KES'98. 1998 Second International Conference on, 1998, pp. 285-290.
[19] S. Xu, Y. Wang, and A. Huang, "Application of Imperialist Competitive Algorithm on Solving the Traveling Salesman Problem," Algorithms, vol. 7, pp. 229-242, 2014.
[20] Bodin, L. D., Golden, B. L., Assas, A., Ball, M., “Routing and scheduling of vehicles and crews: the state of art,” Computer and Operations Research, Vol.10, pp. 63-211, 1983.
[21] G. Laporte, “The vehicle routing problem: An overview of exact and approximate algorithms,” European Journal of Operational Research, vol. 59, no. 2, pp. 345-358, 1992.
[22] Boxer, L. M., et al. "Identification and characterization of a factor that binds to two human sarcomeric actin promoters." Journal of Biological Chemistry 264.2 (1989): 1284-1292.
[23] Hwang, H., Bake, W., Lee, M. K., “Clustering algorithms for order picking in an automated storage and retrieval system,” International Journal of Production Research, Vol. 26, pp. 189-201, 1988.
[24] Gibson, D. R., Sharp, G. P., “Order batching procedures,” European Journal of Operational Research, Vol. 58, pp. 57-67, 1992.
[25] 徐嘉吟，「應用改良的最大最小螞蟻系統於旅行推銷員問題」，碩士論文，國立高雄應用科技大學工業工程與管理系，2009。
[26] 曾世邦，蔡崇煒，江明朝，楊竹星，「針對大型旅行推銷員問題的菁英和絃搜尋法」，嘉南科技大學第十七屆資訊管理暨實務研討會，2011。
[27] MacQueen, James. "Some methods for classification and analysis of multivariate observations." Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.
[28] Quinlan, J. Ross. "Induction of decision trees." Machine learning 1.1 (1986): 81-106.
[29] HSSINA, Badr, et al. "A comparative study of decision tree ID3 and C4.5." International Journal of Advanced Computer Science and Applications 4.2 (2014).
[30] 楊正三，葉明龍，莊麗月，陳禹融 & 楊正宏. (2008). 利用資訊增益與瀰集演算法於基因微陣列之特徵選取與分類問題. 資訊科技國際期刊, 2 (2), 50-62.
[31] Atashpaz-Gargari, Esmaeil, and Caro Lucas. "Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition." Evolutionary Computation, 2007. CEC 2007. IEEE Congress on. IEEE, 2007.
[32] William, J. D. and Jackson, J. S., The Essential World History 6th Ed., Cengage Learning, 2010.
[33] Nazari-Shirkouhi, S., et al. "Solving the integrated product mix-outsourcing problem using the imperialist competitive algorithm." Expert Systems with Applications 37.12 (2010): 7615-7626.
[34] Mohammad A., Majid Y., Narges M. D., “Solving the Traveling Salesman Problem by an Efficient Hybrid Metaheuristic Algorithm,” Journal of Advances in Computer Research, Vol. 3(3), pp. 75-84, 2012.
[35] Bahrami, H., Feaz, K., & Abdechiri, M. (2010). Adaptive Imperialist Competitive Algorithm (AICA). In Proceedings of The 9th IEEE International Conference on Cognitive Informatics, ICCI.
[36] Forouharfard, S., and M. Zandieh. "An imperialist competitive algorithm to schedule of receiving and shipping trucks in cross-docking systems." The International Journal of Advanced Manufacturing Technology 51.9-12 (2010): 1179-1193.
[37] Ahmadi, Mohammad Ali, et al. "Evolving artificial neural network and imperialist competitive algorithm for prediction oil flow rate of the reservoir." Applied Soft Computing 13.2 (2013): 1085-1098.
[38] Holland, J. H., “Genetic algorithms and the optimal allocation of trials,” SIAM Journal on Computing, vol. 2, no. 2, pp. 88-105, 1973.
[39] Goldberg, David E., and Holland, J. H., “Genetic algorithms and machine learning,” Machine learning, vol.3, no. 2, pp.95-99, 1988.
[40] Meng, X., and Song, B., “Fast genetic algorithms used for PID parameter optimization” In Automation and Logistics, 2007 IEEE International Conference on, pp. 2144-2148.
[41] 楊翔珍，「建構分群與演化式模糊決策樹於股價趨勢之預測」，碩士論文，元智大學工管所，2007。
[42] Kubota, N., Shimojima, K., Fukuda, T., “The Role of Virus Infection in Virus-Evolutionary Genetic Algorithm,” Evolutionary Computation, Proceedings of IEEE International Conference, pp. 182-187, 1996.
[43] Zhang, Z. Z., Huang, W. H., Lin, J. J., Chang, P. C., “A Puzzle-Based Artificial Chromosome Genetic Algorithm for the Traveling Salesman Problem,” Conference on Technologies and Applications of Artificial Intelligence. pp. 299-304, 2011.
[44] Pop, P. C., Matei, O. and Sitar, C. P., “ An improved hybrid algorithm for solving the generalized vehicle routing problem,” Neurocomputing, vol.109, pp.76-83, 2013.
[45] 毛俊彬，「利用蟻群最佳化演算法於含時窗限制之旅行推銷員問題」，碩士論文，朝陽科技大學工業與工程管理系，2006。
[46] Miller, B. L. and Goldberg, D. E., “Genetic algorithms, tournament selection, and the effects of noise,” Complex Systems, vol. 9, no. 3, pp. 193-212, 1995.
[47] Chen, Meng-Hui, Pei-Chann Chang, and Jou-Han Chen. "Block Based On Imperial Competitive Algorithm for Traveling Salesman Problem." Proceedings of World Academy of Science, Engineering and Technology. No. 77. World Academy of Science, Engineering and Technology, 2013.
[48] Huang, Wei-Hsiu, Pei-Chann Chang, and Lien-Chun Wang. "A Fast Block-based Evolutional Algorithm for Combinatorial Problems." Proceedings of World Academy of Science, Engineering and Technology. No. 67. World Academy of Science, Engineering and Technology, 2012.