Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman Problem
We propose a novel heuristic algorithm based on the methods of advanced Harmony Search and Ant Colony Optimization (AHS-ACO) to effectively solve the Traveling Salesman Problem (TSP). The TSP, in general, is well known as an NP-complete problem, whose computational complexity increases exponentially...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2013/123738 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832552660921745408 |
|---|---|
| author | Ho-Yoeng Yun Suk-Jae Jeong Kyung-Sup Kim |
| author_facet | Ho-Yoeng Yun Suk-Jae Jeong Kyung-Sup Kim |
| author_sort | Ho-Yoeng Yun |
| collection | DOAJ |
| description | We propose a novel heuristic algorithm based on the methods of advanced Harmony Search and Ant Colony Optimization (AHS-ACO) to effectively solve the Traveling Salesman Problem (TSP). The TSP, in general, is well known as an NP-complete problem, whose computational complexity increases exponentially by increasing the number of cities. In our algorithm, Ant Colony Optimization (ACO) is used to search the local optimum in the solution space, followed by the use of the Harmony Search to escape the local optimum determined by the ACO and to move towards a global optimum. Experiments were performed to validate the efficiency of our algorithm through a comparison with other algorithms and the optimum solutions presented in the TSPLIB. The results indicate that our algorithm is capable of generating the optimum solution for most instances in the TSPLIB; moreover, our algorithm found better solutions in two cases (kroB100 and pr144) when compared with the optimum solution presented in the TSPLIB. |
| format | Article |
| id | doaj-art-9ff881fd902d4ce5b165cb779b619f07 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-9ff881fd902d4ce5b165cb779b619f072025-02-03T05:58:09ZengWileyJournal of Applied Mathematics1110-757X1687-00422013-01-01201310.1155/2013/123738123738Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman ProblemHo-Yoeng Yun0Suk-Jae Jeong1Kyung-Sup Kim2Department of Industrial Information Engineering, Yonsei University, Seoul 120-749, Republic of KoreaDepartment of Business School, Kwangwoon University, Seoul 139-701, Republic of KoreaDepartment of Industrial Information Engineering, Yonsei University, Seoul 120-749, Republic of KoreaWe propose a novel heuristic algorithm based on the methods of advanced Harmony Search and Ant Colony Optimization (AHS-ACO) to effectively solve the Traveling Salesman Problem (TSP). The TSP, in general, is well known as an NP-complete problem, whose computational complexity increases exponentially by increasing the number of cities. In our algorithm, Ant Colony Optimization (ACO) is used to search the local optimum in the solution space, followed by the use of the Harmony Search to escape the local optimum determined by the ACO and to move towards a global optimum. Experiments were performed to validate the efficiency of our algorithm through a comparison with other algorithms and the optimum solutions presented in the TSPLIB. The results indicate that our algorithm is capable of generating the optimum solution for most instances in the TSPLIB; moreover, our algorithm found better solutions in two cases (kroB100 and pr144) when compared with the optimum solution presented in the TSPLIB.http://dx.doi.org/10.1155/2013/123738 |
| spellingShingle | Ho-Yoeng Yun Suk-Jae Jeong Kyung-Sup Kim Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman Problem Journal of Applied Mathematics |
| title | Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman Problem |
| title_full | Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman Problem |
| title_fullStr | Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman Problem |
| title_full_unstemmed | Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman Problem |
| title_short | Advanced Harmony Search with Ant Colony Optimization for Solving the Traveling Salesman Problem |
| title_sort | advanced harmony search with ant colony optimization for solving the traveling salesman problem |
| url | http://dx.doi.org/10.1155/2013/123738 |
| work_keys_str_mv | AT hoyoengyun advancedharmonysearchwithantcolonyoptimizationforsolvingthetravelingsalesmanproblem AT sukjaejeong advancedharmonysearchwithantcolonyoptimizationforsolvingthetravelingsalesmanproblem AT kyungsupkim advancedharmonysearchwithantcolonyoptimizationforsolvingthetravelingsalesmanproblem |