강건(强健) 최소 비용 신장트리 문제를 해결하기 위한 개미 집단 최적화 알고리즘
An Ant Colony Optimization Algorithm for Robust Minimum Spanning Tree Problems
- 주제(키워드) ACO , Robust Minimum Spanning Tree Problem
- 발행기관 서강대학교 일반대학원
- 지도교수 장형수
- 발행년도 2010
- 학위수여년월 2010. 2
- 학위명 석사
- 학과 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000045937
- 본문언어 한국어
- 저작권 서강대학교의 논문은 저작권에 의해 보호받습니다
초록/요약
일반적인 그래프 문제는 간선에 고정된 비용이 부여된 그래프를 입력으로 한다. 그러나 본 논문에서는 주어진 그래프의 각 간선의 값이 고정되지 않고, 구간(interval)사이의 값을 가지되 구간 사이값의 확률 분포가 주어져 있지 않은 그래프를 기반으로 하는 문제들 중 대표적인 RMST(Robust Minimum Spanning Tree)문제를 개미 알고리즘을 통해서 해결하고자 한다. 선형 프로그래밍(linear programing)으로 표현된 구간을 가진 RMST문제는 NP-hard임이 증명되었다[3][7]. 따라서 입력으로 주어지는 그래프의 정점(vertex)의 수나 간선(edge)의 수가 증가한, 크기가 큰 그래프가 입력으로 주어지면 프로그램의 실행시간도 기하급수적으로(exponentially) 증가하게 된다. 이로 인해 최적해를 찾기 위해서 exponential time을 할애하는 알고리즘들은 빠른 프로그램 실행시간을 필요로 하는 실제 응용(application) 환경에서는 실용성의 한계를 지니게 된다. 이를 보완하기 위해서 최적이 아닌 최적해에 가까운 근사해(good solution)를 최적해를 찾는 알고리즘 보다 빠른 실행시간으로 찾는 휴리스틱 알고리즘들이 제안되고 있다. RMST문제를 해결하는 새로운 휴리스틱 알고리즘으로 ACO(Ant Colony Optimization)알고리즘을 기반으로 한 ACO-RO (Ant Colony Optimization Algorithm for solving Robust Optimization problem) 알고리즘을 제안한다. ACO-RO 알고리즘은 기존에 제안된 휴리스틱(heuristic)알고리즘의 실행속도에 뒤지지 않으면서 더 좋은 근사해를 얻는 알고리즘이다. 이러한 알고리즘의 성능 향상을 위해서 RMST문제의 관찰을 통해 효과적인 휴리스틱을 제안하고, 수렴성의 증진을 위해서 엘리트전략(Elitism)[5][6]을 사용하며, 국부최적에 빠지는 것을 방지하기 위해 탐험방법을 추가하였다. ACO-RO알고리즘이 RMST문제를 해결함에 있어 기존에 제안된 휴리스틱 알고리즘인 SA보다 빠른 시간에 최적해에 가까운 근사해를 얻어냄을 실험을 통해 증명하도록 한다.
more