다방향 병렬 개미 군집화 알고리즘을 사용한 효과적인 경로산출 프레임웍 (Effective Routing Generation Framework using Multi-directional and Parallel Ant Colony Optimization)

서지정보

· 발행기관 : 한국지능시스템학회
· 수록지 정보 : 한국지능시스템학회 논문지 / 28권 / 5호 / 523 ~ 530페이지
· 저자명 : 오은서, 이현수

초록

복잡도가 높은 대규모 네트워크에서 경로를 산출하는 것은 네트웍의 복잡도가 증가함에 따라 지수적인 알고리즘복잡도를 요구하는 대표적인 NP-Complete 문제로서, 노드 수가 많을 경우 대부분의 알고리즘이 성능이 저하되는이슈를 보여준다. 이러한 이슈를 보완하기 위하여 본 연구에서의 기존의 개미 군집화 알고리즘을 보완하여, 새로운 개미 군집화 알고리즘인 다방향 병렬 개미 군집화 알고리즘을 제안한다. 일반적인 개미 군집화 알고리즘은시작점에서 출구를 찾는 단일 출발 방식을 지향하는 하는 반면, 제시된 알고리즘은 다수의 지점에서 동시에 경로를산출하며, 각 반복횟수 동안 출발지점을 효율적으로 업데이트 하는 기법을 제시한다. 이를 위해 세부적인 알고리즘및 페로몬 업데이트, 탐색 노드의 업데이트 방법을 기술한다. 제시된 알고리즘의 유효성을 입증하기 위하여미로형태의 수치제어 실험 및 이에 대한 분석을 기존 개미 군집화 알고리즘과 비교하여 분석하여 보여준다.

영어초록

The route generation in a large scale network is a representative NP-Complete problem requiring non-deterministic solution time with the polynomial increase of the problem complexity, and most of the algorithms have the issue that the higher complexity links to the decreased performances. In order to overcome the issue, the paper modifies the existing Ant Colony Optimization (ACO) algorithm and proposed a new and efficient algorithm - Multi-directional and Parallel Ant Colony Optimization (MACO) algorithm. While the existing algorithm starts the search in the same point per each iteration, the proposed MACO algorithm send the ant agents in multiple nodes, simultaneously.
Then, the starting nodes are updated effectively during the iterations. In order to clarify the proposed algorithm, the detailed algorithms such as the pheromone updating method and the updates of the searching nodes are provided.
The effectiveness of the proposed MACO algorithm is proven with the numerical studies of various network examples and the comparisons with the existing ACO algorithm.

참고자료

· 없음