A novel two-stage hybrid swarm intelligence optimization algorithm and application
详细信息 查看全文
- 作者：Wu Deng (124567) dw7689@gmail.com
Rong Chen (1)
Bing He (3)
Yaqing Liu (16)
Lifeng Yin (2)
Jinghuan Guo (1) - 关键词：Genetic algorithms – ; Particle swarm optimization – ; Ant colony optimization – ; Swarm intelligence – ; Traveling salesman problem – ; Two ; stage hybrid algorithm
- 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
- 出版年：2012
- 出版时间：October 2012
- 年：2012
- 卷：16
- 期：10
- 页码：1707-1722
- 全文大小：630.4 KB
- 参考文献：1. Acampora G, Gaeta M, Loia V (2011) Combining multi agent paradigm and memetic computing for personalized and adaptive learning experiences. Comput Intell J 27(2):141–165
2. Adachi N, Yoshida Y (1995) Accelerating genetic algorithms: protected chromosomes and parallel processing. In: Proceedings of the first international conference on genetic algorithms in engineering systems: innovations and applications, pp 1–20
3. Albayrak M, Allahverdi N (2011) Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms. Expert Syst Appl 38(3):1313–1320
4. Assareh E, Behrang MA, Assari MR, Ghanbarzadeh A (2010) Application of PSO (particle swarm optimization) and GA (genetic algorithm) techniques on demand estimation of oil in Iran. Energy 35(12):5223–5229
5. Banaszak D, Dale GA, Watkins AN, Jordan JD(2009) An optical technique for detecting fatigue cracks in aerospace structures. In: Proc 18th ICIASF, pp 1–7
6. Bullnheimer B, Hartl RF, Strauss C( (1997) A new rank based version of the ant system—a computational study. Cent Eur J Oper Res Econ 7(1):25–38
7. Chen SM, Chien CY (2011) Parallelized genetic ant colony systems for solving the traveling salesman problem. Expert Syst Appl 38(4):3873–3883
8. Cheng CB, Mao CP (2007) A modified ant colony system for solving the travelling salesman problem with time windows. Math Comput Model 46(9–10):1225–1235
9. Chu SC, Huang HC, Shi Y, Wu SY, Shieh CS (2008) Genetic watermarking for zerotree-based applications. Circuits Syst Signal Process 27(2):171–182
10. Cochrane EM, Beasley JE (2003) The co-adaptive neural network approach to the Euclidean traveling salesman problem. Neural Netw 16(10):1499–1525
11. Colorni A, Dorigo M, ManiezzoV (1991) Distributed optimization by ant colonies. In: Proceedings of the first European conference on artificial life, Paris, France, pp 134–142
12. Deng W, Li W, Yang XH (2011) A novel hybrid optimization algorithm of computational intelligence techniques for highway passenger volume prediction. Expert Syst Appl 38(4):4198–4205
13. Deng W, Chen R, Gao J et al (2012) A novel parallel hybrid intelligence optimization algorithm for function approximation problem. Comput Math Appl 63(1):325–336
14. Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1(1):53–66
15. Ellabib I, Calamai P, Basir O (2007) Exchange strategies for multiple ant colony system. Inf Sci 177(5):1248–1264
16. Fan SKS, Liang YC, Zahara E (2006) A genetic algorithm and a particle swarm optimizer hybridized with Nelder–Mead simplex search. Comput Ind Eng 50(4):401–425
17. Geng XT, Chen ZH, Yang W, Shi DQ, Zhao K (2011) Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl Soft Comput 11(1):3680–3689
18. Grimaldi AE, Gandelli A, Grimaccia F, Musseeta M, Zich RE (2005) A new hybrid technique for the optimization of large-domain electromagnetic problems. In: Antennas and propagation society international symposium, pp 61–64
19. Guvenc U, Duman S, Saracoglu B, Ozturk A (2011) A hybrid GA–PSO approach based on similarity for various types of economic dispatch problems. Electron Electr Eng Kaunas: Technologija 2(108):109–114
20. Held M, Karp RM (1970) The traveling salesman problem and minimum spanning trees. Oper Res 18:1138–1162
21. Hendtlass T (2003) Preserving diversity in particle swarm optimization. Lect Notes Comput Sci 2718:4104–4108
22. Hoffman AJ, Wolfe P (1985) History. In: Lawler L, Rinooy K, Shmoys D (eds) The traveling salesman problem. Wiley, Chichester, pp 1–16
23. Holland JH (1975) Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press
24. Hua Z, Huang F (2006) A variable-grouping based genetic algorithm for large-scale integer programming. Inf Sci 176(19):2869–2885
25. Kao YT, Zahara E (2008) A hybrid genetic algorithm and particle swarm optimization for multimodal functions. Appl Soft Comput 8(2):849–857
26. Kaveh A, Talatahari S (2009) Particle swarm optimizer, ant colony strategy and harmony search scheme hybridized for optimization of truss structures. Comput Struct 87(5–6):267–283
27. Kennedy J, Eberhart R (1995) Particle swarm optimization, Proceedings of the IEEE international conference on neural networks, IEEE Press, Piscataway, pp 1942–1948
28. Kuo H, Horng SJ, Kao TW, Lin TL et al (2010) Hybrid swarm intelligence algorithm for the travelling salesman problem. Expert Syst Appl 27(3):166–179
29. Lim KK, Ong YS, Lim MH, Chen XS, Agarwal A (2008) Hybrid ant colony algorithms for path planning in sparse graphs. Soft Comput 12(10):981–1004
30. Liu F, Zeng G (2009) Study of genetic algorithm with reinforcement learning to solve the TSP. Expert Syst Appl 36(3):6995–7001
31. Lo CC, Hus CC (1998) Annealing framework with learning memory. IEEE Trans Syst Man Cybern Part A 28(5):1–13
32. Marinakis Y, Marinaki M, Dounias G (2010) A hybrid particle swarm optimization algorithm for the vehicle routing problem. Eng Appl Artif Intell 23(4):463–472
33. Masutti TA, de Castro LN (2009) A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem. Inf Sci 179(10):1454–1468
34. Mavrovouniotis M, Yang SX (2011) A memetic ant colony optimization algorithm for the dynamic travelling salesman problem. Soft Comput 15(7):1405–1425
35. Mehmet Ali MK, Kamoun F (1993) Neural networks for shortest tour computation and routing in computer networks. IEEE Trans Neural Netw 4(5):941–953
36. Naimi HM, Taherinejad N (2009) A new robust and efficient ant colony algorithms: using new interpretation of local updating process. Expert Syst Appl 36(1):481–488
37. Niknam T, Ranjbar AM, Shirani AR (2005) A new approach for distribution state estimation based on ant colony algorithm with regard to distributed generation. J Intell Fuzzy Syst 16(2):119–131
38. Onwubolu GC, Clerc M (2004) Optimal path for automated drilling operations by a new heuristic approach using particle swarm optimization. Int J Prod Res 42(3):473–491
39. Paulo HS, Maria TAS, S茅rgio S (2007) A new approach to solve the traveling salesman problem. Neurocomputing 70(4–6):1013–1021
40. Sarhadi H, Ghoseiri K (2010) An ant colony system approach for fuzzy traveling salesman problem with time windows. Int J Adv Manuf Technol 50(9–12):1203–1215
41. Shen G, Zhang YQ (2011) A new evolutionary algorithm using shadow price guided operators. Appl Soft Comput 11(2):1983–1992
42. Shi XH, Liang YC, Lee HP, Lu C, Wang QX (2007) Particle swarm optimization-based algorithms for TSP and generalized TSP. Inf Process Lett 103(5):169–176
43. Shuang B, Chen JP, Li ZB (2011) Study on hybrid PS–ACO algorithm. Appl Intell 34(1):64–73
44. Singh A, Baghel AS (2009) A new grouping genetic algorithm approach to the multiple traveling salesperson problem. Soft Comput 13(1):95–101
45. Somhom S, Modares A, Enkawa T (1997) A self-organizing model for the traveling salesman problem. J Oper Res Soc 48(4–6):919–928
46. St眉tzle T, Hoos HH (2000) MAX–MIN ant system. Future Gener Comput Syst 16(8):889–914
47. Taher N, Babak A (2010) An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Appl Soft Comput 10(1):183–197
48. Tasgetiren MF, Suganthan PN, Pan QK, Liang YC (2007) A genetic algorithm for the generalized traveling salesman problem. In: Proceedings of the 2007 IEEE congress on evolutionary computation, pp 2382–2389
49. Tsai CF, Tsai CW, Tseng CC (2004) A new hybrid heuristic approach for solving large traveling salesman problem. Inf Sci 166(1–4):67–81
50. Wang KP, Huang L, Zhou CG, Pang W (2003) Particle swarm optimization for traveling salesman problem. In: International conference on machine learning and cybernetics, pp 1583–1585
51. Wang X, Gao XZ, Ovaska SJ (2007) A hybrid optimization algorithm based on ant colony and immune principles. Int J Comput Sci Appl 4(3):30–44
52. Xing LN, Chen YW, Yang KW et al (2008) A hybrid approach combining an improved genetic algorithm and optimization strategies for the asymmetric traveling salesman problem. Eng Appl Artif Intell 21(8):1370–1380
53. Yannis M, Magdalene M (2010) A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem. Comput Oper Res 37(3):432–442
54. Zahara E, Kao YT (2009) Hybrid Nelder–Mead simplex search and particle swarm optimization for constrained engineering design problems. Expert Syst Appl 36(2):3880–3886 - 作者单位：1. Informational Science and Technology Institute, Dalian Maritime University, 116026 Dalian, China2. Software Institute, Dalian Jiaotong University, 116028 Dalian, China3. Foreign Language Institute, Dalian Jiaotong University, 116028 Dalian, China4. Key Laboratory of Intelligent Computing and Signal Processing, Anhui University, Ministry of Education, 230039 Hefei, China5. State Key Laboratory of Power Transmission Equipment and System Security and New Technology, College of Electrical Engineering, Chongqing University, 400044 Chongqing, China6. Artificial Intelligence Key Laboratory of Sichuan Province, Sichuan University of Science and Engineering, 643000 Zigong, China7. Key Laboratory of Advanced Design and Intelligent Computing, Dalian University, Ministry of Education, 116622 Dalian, China
- ISSN：1433-7479
文摘
This paper presents a novel two-stage hybrid swarm intelligence optimization algorithm called GA–PSO–ACO algorithm that combines the evolution ideas of the genetic algorithms, particle swarm optimization and ant colony optimization based on the compensation for solving the traveling salesman problem. In the proposed hybrid algorithm, the whole process is divided into two stages. In the first stage, we make use of the randomicity, rapidity and wholeness of the genetic algorithms and particle swarm optimization to obtain a series of sub-optimal solutions (rough searching) to adjust the initial allocation of pheromone in the ACO. In the second stage, we make use of these advantages of the parallel, positive feedback and high accuracy of solution to implement solving of whole problem (detailed searching). To verify the effectiveness and efficiency of the proposed hybrid algorithm, various scale benchmark problems from TSPLIB are tested to demonstrate the potential of the proposed two-stage hybrid swarm intelligence optimization algorithm. The simulation examples demonstrate that the GA–PSO–ACO algorithm can greatly improve the computing efficiency for solving the TSP and outperforms the Tabu Search, genetic algorithms, particle swarm optimization, ant colony optimization, PS–ACO and other methods in solution quality. And the experimental results demonstrate that convergence is faster and better when the scale of TSP increases.