An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks
Abstract
:1. Introduction
2. Related Works
3. Introduction of Ant Colony Algorithm
3.1. Working Principle of Ant Colony Algorithm
3.2. Path Probability Selection
3.3. Pheromone Update
3.4. Algorithm Flow
- (1)
- First, the required parameters are initialized by the algorithm. Set the cycle times of Nc = 0, the maximum number of iterations Nc Max, and Path initialization information (where , C is constant, = 0).
- (2)
- m ants will be placed in n cities, and each ant accesses the next node j by route choice probability , where j belongs to .
- (3)
- The path length of each ant is calculated, and the optimal solution of the current search is recorded.
- (4)
- Modify the pheromone according to the update formula.
- (5)
- On the path of the pheromone increment and Nc cycles were set for the , .
- (6)
- If Nc Max > , then jump to Step (2).
- (7)
- If the condition is satisfied, the current optimal solution will be output.
Algorithm 1. Ant Colony Algorithm Based on TSP Problems. |
1: Parameters Initialization |
2: Ants visit next node via path selection probability |
3: The number of cycles increased |
4: Taboo index number increased |
5: |
6: do { |
7: Path length is determined by ants |
8: |
9: |
10: Pheromones are secreted |
11: |
12: |
13: while(!haveFinishedIteNum( )) |
14: |
15: is empty |
16: End |
4. Improvement of Ant Colony Algorithm
4.1. Shortcomings of Ant Colony Algorithm
4.2. The Improved Ant Colony Algorithm
4.2.1. The Improvement of Path Selection Probability
- when q is greater than , the formula is:
- when q is less than or equal to , the formula is
4.2.2. Improved Pheromone Update
Algorithm 2. The Improved Algorithm Based on TSP Problems. |
1: Parameters Initialization |
2: do { |
3: Nc = Nc + 1 |
4: do { |
5: visit next city via the new path selection probability |
6: Tabu_list = Modify( ) |
7: } while (! IsTableFull( )) |
8: Path length is determined by ants |
9: |
10: |
11: |
12: |
13: |
14: Tabu_list is empty |
15: }while(!haveFinishedIterateNum( )) |
16: |
17: End |
5. Performance Evaluation
5.1. Simulation Environment
5.2. Comparison of Simulation Results
5.3. Application Analysis of the Applied Improved Ant Colony Algorithm
6. Conclusions and Future Works
- Ant colony algorithm is a probabilistic algorithm, which can learn from other mature intelligent optimization algorithm. It is conducive to the birth of a new type of ant colony algorithm from a mathematical point of view to further analysis.
- Most of them are aimed at improving the convergence of ant colony algorithm. There are some limitations on the innovation of the algorithm itself.
- The application depth of ant colony algorithm is not enough because most simulation experiments are carried out under specific experimental conditions, while the actual situation is dynamic. Thus, the relevant issues have yet to be further expanded.
- Compared with other algorithms, the ant colony algorithm has the characteristics such as good distributed computing mechanism and strong robustness, so it can be combined with other algorithms to put forward a more powerful algorithm.
Acknowledgments
Author Contributions
Conflicts of Interest
References
- Dorigo, M. Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico Di Milano, Milan, Italy, 1992. [Google Scholar]
- Chen, H.; Li, J. Review of outlier detection. Da Zhong Ke Ji 2005, 9, 96–97. [Google Scholar]
- Zhu, X.; Li, F. Several intelligent algorithms for solving traveling salesman problem. Comput. Digit. Eng. 2010, 38, 32–35. [Google Scholar]
- Lin, D.; Wang, D.; Li, Y. Two-level degradation hybrid algorithm for multiple traveling salesman problem. Appl. Res. Comput. 2011, 28, 2876–2879. [Google Scholar]
- Wang, Z.; Bai, Y.; Yue, L. An Improved Ant Colony Algorithm for Solving TSP Problems. Math. Pract. Theory 2012, 42, 133–140. [Google Scholar]
- Dorigo, M.; Maniezzo, V.; Colorni, A. Ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern Part B 1996, 26, 29–41. [Google Scholar] [CrossRef] [PubMed]
- Wang, H.; Tong, Y.; Tan, S. Research progress on outlier mining. CAAI Trans. Intell. Syst. 2006, 1, 67–73. [Google Scholar]
- Li, Y.; Li, H.; Qian, X. A Review and Analysis of Outlier Detection Algorithms. Comput. Eng. 2002, 28, 5–6. [Google Scholar]
- Cagnina, L.C.; Susana, C.E.; Carlos, A.C.C. Solving constrained optimization problems with a hybrid particle swarm optimization algorithm. Eng. Optim. 2011, 43, 843–866. [Google Scholar] [CrossRef]
- Duan, H. The Principle and Application of Ant Colony Algorithm; Science Press: Beijing, China, 2005. [Google Scholar]
- Xu, J.; Cao, X.; Wang, X. Polymorphic Ant Colony Algorithm. J. Univ. Sci. Technol. China 2005, 35, 59–65. [Google Scholar]
- Zao, B.; Wang, L. The analysis of the convergence of ant colony optimization algorithm. Front. Electr. Electron. Eng. 2007, 2, 268–272. [Google Scholar]
- Wang, Q.; Li, W. Study of TSP Problem Solving Based on Improved Quantum Ant Colony Algorithm. Microprocessors 2015, 3, 31–33. [Google Scholar]
- Sun, J. Research on Ant Colony Algorithm for Solving Traveling Salesman Problem; Wuhan University of Technology: Wuhan, China, 2005. [Google Scholar]
- Zhang, K.; Zhang, Y.; Wan, S. Application of an Improved Competitive Ant Colony Algorithm in TSP. Comput. Digit. Eng. 2016, 44, 396–399. [Google Scholar]
- Jiang, Y. The Application of an Improved Ant Colony Optimization for TSP; South-central University for Nationalitie: Wuhan, China, 2009. [Google Scholar]
- Sun, K.; Wu, H.; Wang, H. Hybrid ant colony and particle swarm algorithm for solving TSP. Comput. Eng. Appl. 2012, 48, 60–63. [Google Scholar]
- Hu, X.; Huang, X. Solving TSP with Characteristic of Clustering by Ant Colony Algorithm. J. Syst. Simul. 2004, 16, 2683–2686. [Google Scholar]
- Chen, W.; Jiang, Y. Improving ant colony algorithm and particle swarm algorithm to solve TSP problem. Inf. Technol. 2016, 2016, 162–165. [Google Scholar]
- Kai, P.; Huang, Q.; Shao, C. Solving Model Based on Particle Swarm Optimization and Artificial Fish Swarm Algorithm. J. Sichuan Univ. Sci. Eng. 2017, 30, 27–32. [Google Scholar]
- Zhang, X.; Li, X.; Sun, Y. An adaptive ACO algorithm based on PR for solving traveling salesman problem. J. Univ. Sci. Technol. Liaoning 2016, 39, 468–475. [Google Scholar]
- Rosenkrantz, D.J.; Stearns, R.E.; Ii, P.M.L. An analysis of several heuristics for thetraveling salesman problem. Siam J. Comput. 1977, 6, 563–581. [Google Scholar] [CrossRef]
- Gambardella, L.M.; Dorigo, M. Ant-Q: A Reinforcement Learning approach to the traveling salesman problem. In Proceedings of the Twelfth International Conference on Machine Learning, Tahoe City, CA, USA, 9–12 July 1995; Volume 170, pp. 252–260. [Google Scholar]
- Liu, H.; Hu, X.; Zhao, J. Ant colony optimization algorithm with path choice of dynamic transition. Comput. Eng. 2010, 36, 201–203. [Google Scholar]
- Colorni, A.; Dorigo, M.; Maniezzo, V. Distributed Optimization by Ant Colonies. In Proceedings of the First European Conference on Artificial Life, Pairs, France, 11–13 December 1991; pp. 134–142. [Google Scholar]
- Feng, Y. An improved ant colony algorithm on TSP problem. Electron. Test 2014, 2014, 38–40. [Google Scholar]
- Wang, L.; Zhu, Q. An Efficient Approach for Solving TSP: The Rapidly Convergent Ant Colony Algorithm. In Proceedings of the Fourth International Conference on Natural Computation, Jinan, China, 18–20 October 2008; pp. 448–452. [Google Scholar]
- Yoshikawa, M.; Terai, H. Architecture for High-Speed Ant Colony Optimization. In Proceedings of the IEEE International Conference on Information Reuse and Integration, Las Vegas, IL, USA, 13–15 August 2007; pp. 1–5. [Google Scholar]
- Fang, F.; Shen, Z.; Yao, J. A new LEACH-based routing algorithm for wireless sensor networks. Mech. Electr. Eng. J. 2008, 25, 100–103. [Google Scholar]
- Akyildiz, I.F.; Su, W.; Sankarasubramaniam, Y.; Cayirci, E. A survey on sensor networks. IEEE Commun. Mag. 2002, 40, 102–114. [Google Scholar] [CrossRef]
© 2017 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Xiong, N.; Wu, W.; Wu, C. An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. Sustainability 2017, 9, 985. https://0-doi-org.brum.beds.ac.uk/10.3390/su9060985
Xiong N, Wu W, Wu C. An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. Sustainability. 2017; 9(6):985. https://0-doi-org.brum.beds.ac.uk/10.3390/su9060985
Chicago/Turabian StyleXiong, Naixue, Wenliang Wu, and Chunxue Wu. 2017. "An Improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks" Sustainability 9, no. 6: 985. https://0-doi-org.brum.beds.ac.uk/10.3390/su9060985