순회 판매원 문제 해결을 위한 개미집단 최적화 알고리즘 개선
Improvement of Ant Colony Optimization Algorithmto Solve Traveling Salesman Problem
2
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
It is one of the known methods to obtain the optimal solution using the Ant Colony Optimization Algorithm for the Traveling Salesman Problem (TSP), which is a combination optimization problem. In this paper, we solve the TSP problem by proposing an improved new ant colony optimization algorithm that combines genetic algorithm mutations in existing ant colony optimization algorithms to solve TSP problems in many cities. The new ant colony optimization algorithm provides the opportunity to move easily fall on the issue of developing local optimum values of the existing ant colony optimization algorithm to global optimum value through a new path through mutation. The new path will update the pheromone through an ant colony optimization algorithm. The renewed new pheromone serves to derive the global optimal value from what could have fallen to the local optimal value. Experimental results show that the existing algorithms and the new algorithms are superior to those of existing algorithms in the search for optimum values of newly improved algorithms.
Abstract
It is one of the known methods to obtain the optimal solution using the Ant Colony Optimization Algorithm for the Traveling Salesman Problem (TSP), which is a combination optimization problem. In this paper, we solve the TSP problem by proposing an improved new ant colony optimization algorithm that combines genetic algorithm mutations in existing ant colony optimization algorithms to solve TSP problems in many cities. The new ant colony optimization algorithm provides the opportunity to move easily fall on the issue of developing local optimum values of the existing ant colony optimization algorithm to global optimum value through a new path through mutation. The new path will update the pheromone through an ant colony optimization algorithm. The renewed new pheromone serves to derive the global optimal value from what could have fallen to the local optimal value. Experimental results show that the existing algorithms and the new algorithms are superior to those of existing algorithms in the search for optimum values of newly improved algorithms.
참고문헌 (12)
- Aziz, Z.A, "Ant Colony Hyper-heuristics for Travelling Salesman Problem", Procedia Computer Science, 76, pp.534~538 (2015)
- 조승용, "Ant Colony Optimization Heuristics and Graph Optimization Algorithms of an Aisle-Based Order Picking System", 한국SCM학회지, 11(2), pp.13~19 (2011), 한국SCM학회
- Colorni, A, "Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle", pp.134~142 (1992), Elsevier Publishing
- 홍석미, "순회 판매원 문제에서 개미 군락 시스템을 이용한 효율적인 경로 탐색", 정보과학회논문지 : 소프트웨어 및 응용, 30(10), pp.862~866 (2003), 한국정보과학회
- 김인겸, "방문판매원 문제에 적용한 개선된 개미 군락 시스템", 정보처리학회 논문지, 12(7), pp.823~828 (2005), 한국정보처리학회
- 김정섭, "유전 알고리즘을 이용한 Work-In-Process 수준 최적화", 한국산업경영시스템학회지, 40(1), pp.79~86 (2017), 한국산업경영시스템학회
- An Improved Cultural Algorithm with Local Search for Traveling Salesman Problem, "Kim, Y.J.", Korea Information Science Society, 267~271 (2008)
- Lee, K.K, "A Genetic Algorithm for the Traveling Salesman Problem", Journal of The Korea Information Science Society, 22(4), pp.559~566 (1995)
- Lee, K.M., "A Genetic Algorithm for Traveling Salesman Problem with Precedence Constraints", Journal of KISS(A) : Computer System and Theory, 25(4), pp.362~368 (1998)
- 이승관, "순회 외판원 문제를 풀기 위한 전역 최적 경로의 중복 간선을 고려한 개미 집단 시스템", 한국컴퓨터정보학회논문지, 16(3), pp.203~210 (2011), 한국컴퓨터정보학회
- 이상운, "외판원 문제의 다항시간 알고리즘", 한국컴퓨터정보학회논문지, 18(12), pp.75~82 (2013), 한국컴퓨터정보학회
- Yan, Y.Z., "German Reyes, A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem", Applied Soft Computing, 60, pp.256~267 (2017)