닫기
Loading..

전자정보연구정보센터 ICT 융합 전문연구정보의 집대성

국내 논문지

홈 홈 > 연구문헌 > 국내 논문지 > 한국정보과학회 논문지 > 정보과학회 논문지 B : 소프트웨어 및 응용

정보과학회 논문지 B : 소프트웨어 및 응용

Current Result Document : 7 / 10 이전건 이전건   다음건 다음건

한글제목(Korean Title) 순회 판매원 문제에서 개미 군락 시스템을 이용한 효율적인 경로 탐색
영문제목(English Title) Efficient Path Search Method using Ant Colony System in Traveling Salesman Problem
저자(Author) 홍석미   이영아   정태충  
원문수록처(Citation) VOL 30 NO. 09 PP. 0862 ~ 0866 (2003. 10)
한글내용
(Korean Abstract)
조합 최적화 문제인 순회 판매원 문제(Traveling Salesman Problem, TSP)를 유전자 알고리즘(Genetic Algorithm)과 Local Search Heuristic인 Lin-Kernighan(LK) Heuristic[1]을 이용하여 접근하는 것은 최적 해를 구하기 위해 널리 알려진 방법이다. 본 논문에서는 TSP 문제를 해결하기 위한 또 다른 접근법으로 ACS(Ant Colony System) 알고리즘을 소개하고 새로운 페로몬 갱신 방법을 제시하고자 한다. ACS 알고리즘은 다수의 개미들이 경로를 만들어 가는 과정에서 각 에지상의 페로몬 정보를 이용하며, 이러한 반복적인 경로 생성 과정을 통해 최적 해를 발견하는 방법이다. ACS 기법의 전역 갱신 단계에서는 생성된 모든 경로들 중 전역 최적 경로에 속한 에지들에 대하여 페로몬을 갱신한다. 그러나 본 논문에서는 전역 갱신 규칙이 적용되기 전에 생성된 모든 에지에 대하여 페로몬을 한번 더 갱신한다. 이 때 페로몬 갱신을 위해 각 에지들의 발생 빈도수를 이용한다. 개미들이 생성한 전체 에지들의 발생 빈도수를 페로몬 정보에 대한 가중치(weight)로 부여함으로써 각 에지들에 대하여 통계적 수치를 페로몬 정보로 제공할 수 있었다. 또한 기존의 ACS 알고리즘보다 더 빠른 속도로 최적 해를 찾아내며 더 많은 에지들이 다음 번 탐색에 활용될 수 있게 함으로써 지역 최적화에 빠지는 것을 방지할 수 있다. 
영문내용
(English Abstract)
Traveling Salesman Problem( TSP ) is a combinational optimization problem, Genetic Algorithm(GA) and Lin-Kernighan(LK) Heuristic[1] that is Local Search Heuristic are one of the most commonly used methods to resolve TSP. In this paper, we introduce ACS(Ant Colony System) Algorithm as another approach to solve TSP and propose a new pheromone updating method. ACS uses pheromone information between cities in the process where many ants make a tour, and is a method to find a optimal solution through recursive tour creation process. At the stage of Global Updating of ACS method, it updates pheromone of edges belonging to global best tour of created all edge. But we perform once more pheromone update about created all edges before global updating rule of original ACS is applied. At this process, we use the frequency of occurrence of each edges to update pheromone. We could offer stochastic value by pheromone about each edges, giving all edges´ occurrence frequency as weight about pheromone. This finds an optimal solution faster than existing ACS algorithm and prevent a local optima using more edges in next time search.
키워드(Keyword) ACS   TSP   빈도수   가중치   최적화  
원문 PDF 다운로드