現在位置首頁 > 博碩士論文 > 詳目
論文中文名稱:基於MapReduce之改良式兩階段螞蟻演算法 [以論文名稱查詢館藏系統]
論文英文名稱:A Two Stages Enhanced Ant Colony Optimization based on MapReduce [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:資訊與財金管理系碩士班
畢業學年度:105
畢業學期:第二學期
出版年度:106
中文姓名:李博逸
英文姓名:Bo-Yi Li
研究生學號:104AB8002
學位類別:碩士
語文別:中文
口試日期:2017/06/15
論文頁數:62
指導教授中文名:王貞淑
口試委員中文名:蕭文龍;丁一賢
中文關鍵詞:組合優化平行運算MapReduce粒子群優化螞蟻最佳化
英文關鍵詞:combinatorial optimizationparallel computingMapReduceParticle Swarm OptimizationAnt Colony Optimization
論文中文摘要:組合優化的問題大量的遍佈於現今科技社會之中,因為技術發展與大數據的影響,導致組合優化問題日趨複雜與難解。面對上述兩項影響,主要可以透過萬用啟發式演算法(Meta-Heuristics)以及Hadoop MapReduce平行運算來解決。因此,本研究設計了一個以螞蟻族群演算法為主體,混合粒子群演算法概念,並加入費洛蒙最大最小限制與擾動機制,提出改良式兩階段螞蟻演算法,並實作於Hadoop MapReduce。
本研究以旅行商問題與背包問題進行驗證,經實驗驗證後可以發現,在背包問題中幾乎可以求得最佳解,在旅行商問題中與最佳解之差異皆在5%之內,而且皆使用較少迭代數,並擁有較高的求解穩定性。而在Hadoop MapReduce平行運算下,本演算法面對越複雜問題,在兩階段運算時間表現上的耗時相較於單機時越少。
論文英文摘要:There are many combinatorial optimization problems in the present science and technology society. Because of the impact of technological development and big data, combinatorial optimization problems become more and more complex. There are Meta-Heuristics and Hadoop MapReduce to solve the two effects. Therefore, this paper design a two stages enhanced ant colony optimization based on MapReduce, which based on ant colony optimization and added the concept of particle swarm optimization, the maximum and minimum limit of pheromones and perturbation mechanism.
This study takes Travelling salesman problem and Knapsack problem to verify this algorithm. Experiment shows that the algorithm can achieve almost the best solution in Knapsack problem and solve it within 5% of the best solution in Travelling salesman problem, takes less iterations and has higher stability. For more complex problem, this two-stage computing method in Hadoop MapReduce version consumes less time and performance is better than the stand-alone version.
論文目次:摘要 i
ABSTRACT ii
致謝 iv
目錄 v
表目錄 vii
圖目錄 viii
第一章、 緒論 1
1.1、 研究背景與動機 1
1.2、 研究目的 4
1.3、 論文架構 5
1.4、 研究限制 7
第二章、 文獻探討 8
2.1、 粒子群演算法(Particle Swarm Optimization,PSO) 8
2.2、 螞蟻最佳化演算法(Ant Colony Optimization,ACO) 10
2.3、 MapReduce 15
2.4、 粒子群演算法與螞蟻最佳化演算法於MapReduce之研究 16
第三章、 研究設計 18
3.1、 改良式兩階段螞蟻演算法設計 18
3.2、 研究流程 20
3.3、 基於MapReduce實作改良演算法之探索階段 22
3.4、 基於MapReduce實作改良演算法之追循階段 23
第四章、 實驗設計 24
4.1、 實驗流程設計 24
4.2、 背包問題 26
4.1.1. 問題描述 26
4.1.2. 數學模型 26
4.1.3. 演算法之問題設計 26
4.3、 旅行商問題 28
4.2.1. 問題描述 28
4.2.2. 數學模型 28
4.2.3. 演算法之問題設計 29
第五章、 實驗結果 30
5.1、 實驗環境 30
5.2、 實驗資料 31
5.3、 實驗參數設定 31
5.4、 實驗結果 34
5.4.1. 背包問題實驗結果 34
5.4.2. 旅行商問題實驗結果 44
第六章、 結論與未來展望 56
6.1、 結論 56
6.2、 未來展望 57
參考文獻 58
論文參考文獻:1. 徐誠佑與陳茂生(2003).螞蟻演算法求解零壹多限制式背包問題.國立清華大學工業工程與工程管理學系研究所學位論文,1-80
2. 莊凱智與黃士滔(2011).應用改良式粒子群演算法於旅行銷售員問題. 國立高雄應用科技大學工業工程與管理系研究所學位論文,1-98
3. 劉昱德與黃士滔.比較三種萬用啓發式演算法於 TSP 問題之探討.工程科技與教育學刊, 2011, 8.3: 443-452.
4. 簡銓蔚與胡黃德(2013).粒子群演算法應用於具容量限制的開放式車輛途程問題.元智大學工業工程與管理學系研究所學位論文,1-67
5. 梁文榮與陳明賢與高有成(2015).基於ACO和PSO的混合算法求解VRPTW問題.大同大學資訊經營學系研究所學位論文,1-103
6. 楊世強與王貞淑(2016).基於MapReduce於分散式基因演算法之應用與研究.國立臺北科技大學資訊與財金管理系碩士班學位論文,1-62
7. 贾瑞玉, & 李亚龙. (2013). 基于 MapReduce 的量子蚁群算法. Computer Engineering and Applications, 49(19).
8. 黄务兰, & 张涛. (2016). 基于改进遗传算法的带时间窗车辆路径问题研究. 微型机与应用, 35(13), 21-24.
9. Aljarah, I., & Ludwig, S. A. (2012, November). Parallel particle swarm optimization clustering algorithm based on mapreduce methodology. In Nature and Biologically Inspired Computing (NaBIC), 2012 Fourth World Congress on (pp. 104-111). IEEE.
10. Chen, X., & Li, Y. (2006, June). Smooth path planning of a mobile robot using stochastic particle swarm optimization. In 2006 International Conference on Mechatronics and Automation (pp. 1722-1727). IEEE.
11. Clerc, M. (2004). Discrete particle swarm optimization, illustrated by the traveling salesman problem. In New optimization techniques in engineering (pp. 219-239). Springer Berlin Heidelberg.
12. Cook, S. A. (1971, May). The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing (pp. 151-158). ACM.
13. Dawkin, R. (1976). The selfish gene. Oxford ni versity Press, 1, 976.
14. Dean, J., & Ghemawat, S. (2008). MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1), 107-113.
15. Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy.
16. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.
17. Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66.
18. Eberhart, R. C., & Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In Proceedings of the sixth international symposium on micro machine and human science (Vol. 1, pp. 39-43).
19. Garey, M. R., & Johnson, D. S. (2002). Computers and intractability (Vol. 29). New York: wh freeman.
20. Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & operations research, 13(5), 533-549.
21. Glover, F. (1989). Tabu search-part I. ORSA Journal on computing, 1(3), 190-206.
22. Glover, F. (1990). Tabu search—part II. ORSA Journal on computing, 2(1), 4-32.
23. Gunasekaran, A., Marri, H. B., McGaughey, R. E., & Nebhwani, M. D. (2002). E-commerce and its impact on operations management. International journal of production economics, 75(1), 185-197.
24. Hromkovič, J. (2013). Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics. Springer Science & Business Media.
25. Ismkhan, H. (2017). Effective heuristics for ant colony optimization to handle large-scale problems. Swarm and Evolutionary Computation, 32, 140-149.
26. Karp, R. M. (1972). Reducibility among combinatorial problems (pp. 85-103). springer US.
27. Khan, I., Maiti, M. K., & Maiti, M. (2017, January). Coordinating Particle Swarm Optimization, Ant Colony Optimization and K-Opt Algorithm for Traveling Salesman Problem. In International Conference on Mathematics and Computing (pp. 103-119). Springer, Singapore.
28. Li, T., Lai, X., & Wu, M. (2006). An improved two-swarm based particle swarm optimization algorithm. In Intelligent Control and Automation, 2006. WCICA 2006. The Sixth World Congress on (Vol. 1, pp. 3129-3133). IEEE.
29. López, L. F. M., Blas, N. G., & Albert, A. A. (2017). Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations. Soft Computing, 1-16.
30. Ma, F., & Chen, X. B. (2006, June). Application of varying population size particle swarm optimization algorithm to AGC of power systems. In 2006 6th World Congress on Intelligent Control and Automation (Vol. 1, pp. 3310-3314). IEEE.
31. Marinakis, Y., Migdalas, A., & Sifaleras, A. (2017). A hybrid Particle Swarm Optimization–Variable Neighborhood Search algorithm for Constrained Shortest Path problems. European Journal of Operational Research, 261(3), 819-834.
32. Mathews, G. B. (1896). On the partition of numbers. Proceedings of the London Mathematical Society, 1(1), 486-490.
33. Mohan, A., & Remya, G. (2014). A Parallel Implementation of Ant Colony Optimization for TSP based on MapReduce Framework. International Journal of Computer Applications, 88(8).
34. Mohsen, A. M. (2016). Annealing Ant Colony Optimization with Mutation Operator for Solving TSP. Computational Intelligence and Neuroscience, 2016.
35. Patel, A. B., Birla, M., & Nair, U. (2012, December). Addressing big data problem using Hadoop and Map Reduce. In 2012 Nirma University International Conference on Engineering (NUiCONE) (pp. 1-5). IEEE.
36. Sadasivam, G. S., & Selvaraj, D. (2010, December). A novel parallel hybrid PSO-GA using MapReduce to schedule jobs in Hadoop data grids. In Nature and Biologically Inspired Computing (NaBIC), 2010 Second World Congress on (pp. 377-382). IEEE.
37. Samà, M., Pellegrini, P., D’Ariano, A., Rodriguez, J., & Pacciarelli, D. (2016). Ant colony optimization for the real-time train routing selection problem. Transportation Research Part B: Methodological, 85, 89-108.
38. Shi, Y., & Eberhart, R. (1998, May). A modified particle swarm optimizer. In Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence., The 1998 IEEE International Conference on (pp. 69-73). IEEE.
39. Shi, Y., & Eberhart, R. C. (1999). Empirical study of particle swarm optimization. In Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on (Vol. 3). IEEE.
40. Sicilia, J. A., Quemada, C., Royo, B., & Escuín, D. (2016). An optimization algorithm for solving the rich vehicle routing problem based on Variable Neighborhood Search and Tabu Search metaheuristics. Journal of Computational and Applied Mathematics, 291, 468-477.
41. Stutzle, T., & Hoos, H. (1997, April). MAX-MIN ant system and local search for the traveling salesman problem. In Evolutionary Computation, 1997., IEEE International Conference on (pp. 309-314). IEEE.
42. Stützle, T., & Hoos, H. H. (2000). MAX–MIN ant system. Future generation computer systems, 16(8), 889-914.
43. Tan, Q., He, Q., & Shi, Z. (2012, June). Parallel max-min ant system using mapreduce. In International Conference in Swarm Intelligence (pp. 182-189). Springer Berlin Heidelberg.
44. Wu, B., Wu, G., & Yang, M. (2012, May). A mapreduce based ant colony optimization approach to combinatorial optimization problems. In Natural Computation (ICNC), 2012 Eighth International Conference on (pp. 728-732). IEEE.
45. Zhu, L., Li, Q., & He, L. (2012). Study on cloud computing resource scheduling strategy based on the ant colony optimization algorithm. IJCSI International Journal of Computer Science Issues, 9(5), 1694-0814.
論文全文使用權限:同意授權於2019-07-13起公開