혼합 중국 우체부 문제를 위한 확장 그래프 기반 개미 시스템 메타휴리스틱
An Extended Graph-Based Ant System Metaheuristic for the Mixed Chinese Postman Problem
- 주제(키워드) 도움말 Mixed Chinese Postman Problem , Ant Colony Optimization , Metaheuristic
- 발행기관 서강대학교 일반대학원
- 지도교수 장형수
- 발행년도 2014
- 학위수여년월 2014. 8
- 학위명 석사
- 학과 및 전공 도움말 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000053994
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약 도움말
본 논문은 방향성 간선과 비방향성 간선이 함께 존재 가능한 혼합 그래프 상에서 모든 간선을 적어도 한 번씩 방문하여 최소 비용으로 출발점으로 돌아오는 혼합 중국 우체부 문제를 풀기 위해, Gutjahr 가 제안한 GBAS/tdev 에 선호도(desirability)와 시드 워크(seed walk)를 도입하여 확장한, 최적해 수렴을 보장하는 새로운 개미 시스템 메타휴리스틱을 제안한다. 그리고 실제 문제 적용 시, 전처리 과정을 통한 초기 근사해들을 이용하여 해의 질적인 면에서 유리한 위치를 선점함으로써 모든 반복(iteration)에서 3/2 근사율(approximation ratio)을 보장한다. 제안한 해법은 또한 그 초기 근사해들을 결합함으로써 각각이 갖는 장점들을 보강하여 보다 유용한 정보를 바탕으로 탐색한다. 실험을 통해 정확성과 속도 측면에서 기존 해법 알고리즘들과 비교하여 제안한 알고리즘의 효율성을 보인다.
more초록/요약 도움말
To solve the mixed Chinese postman problem visiting all the edges and arcs on a mixed graph and returning to the starting point with the minimum cost, this thesis proposes a new ant colony optimization metaheuristic extended from Gutjahr’s GBAS/tdev with desirability and seed walk and shows its convergence to optimality. In its application to the problem, 3/2-approximation over all iterations is guaranteed by taking the advantageous position for solution quality using initial approximate solutions from preprocessing. The proposed solving approach also combines the initial solutions to reinforce each strength and search for a solution of better quality based on more useful information. The experimental result shows that compared to existing algorithms, the presented algorithm is efficient in accuracy and time.
more