검색 상세

유전 알고리즘을 이용한 동적으로 변하는 그래프에 대한 최단 경로 찾기

Finding Shortest Path for Dynamically Changing Graph Using a Genetic Algorithm

  • 이정규 (Jungkyu Lee, 컴퓨터공학과)

초록/요약

본 연구에서는 그래프의 간선 비용이 동적으로 변하는 그래프에 대해서 최단 경로를 찾는 알고리즘에 대해 알아본다. 특히 그래프 상에서 목적지를 향해 일주하는 에이전트가 알 수 있는 그래프의 정보의 범위에 따라 크게 두 가지 접근 방식을 제시한다. 에이전트에게 그래프에 대한 지역 정보(local information)만이 제공될 때, 에이전트는 강화학습을 통해서 동적으로 변하는 그래프에 대한 최적 라우팅 정책(optimal routing policy)을 학습한다. 여기서 지역 정보란 에이전트가 현재 위치하고 있는 노드에 대한 인접 노드의 정보와 인접 노드와의 간선 비용을 의미한다. 에이전트에게 그래프에 대한 고정적인 물리적인 정보(physical information)가 제공될 때에는, 에이전트는 다익스트라 알고리즘을 통해 고정적인 그래프에 대한 최적 라우팅 정책을 학습한다. 여기서 그래프의 물리적인 정보란, 그래프의 노드의 위치 좌표를 의미한다. 위의 두 경우 모두 그래프의 학습 후, 유전자 알고리즘은 결과로 얻은 최적 라우팅 정책과 동적으로 변하는 그래프의 개체군적 정보(populational information)을 이용하여 최단 경로를 계산한다. 여기서 그래프의 개체군적 정보란, 유전자 알고리즘이 경로 계산 시 요구하는 그래프의 정보를 말한다. 본 연구에서는 시뮬레이션을 통해 제안한 알고리즘의 성능을 측정, 검증하였다.

more

초록/요약

In this paper, we present an algorithm to find the shortest path for dynamically changing graphs. The edge costs of a graph are changed dynamically over time. The proposed algorithm consists of two phases: “learning phase” to learn a dynamically changing graph and “adaptation phase” to adapt the current graph conditions using a Genetic Algorithm. There are two cases of learning phase according to the available information on dynamically changing graph: If the agent only has the local information on dynamically changing graph, the it learns the optimal routing policy in learning phase by reinforcement learning. If the agent has the physical information on dynamically changing graph, it learns the optimal routing policy using Dijkstra’s algorithm. After the learning phase, the Genetic Algorithm re-routes the path using the optimal routing policy and the populational information. In experimental results, we show that the proposed algorithm achieves significantly higher scalability for large-scale networks than pure GA-based approaches in the routing problem.

more
반출 Meta View 목록