구간 데이터를 가진 강건(强健) 최단 경로 문제들을 해결하기 위한 확장 Biased Random-key 유전 알고리즘
An Extended Biased Random-key Genetic Algorithm for Robust Shortest Path Problems with Interval Data
- 주제(키워드) 유전 알고리즘 , 강건 최단 경로 , 강건 최적화 , 메타휴리스틱 , 최단 경로 , Biased Random-key 유전 알고리즘 , genetic algorithm , robust shortest path , robust optimization , metaheuristic , shortest path , biased random-key genetic algorithm
- 발행기관 서강대학교 일반대학원
- 지도교수 장형수
- 발행년도 2018
- 학위수여년월 2018. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000062905
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권보호를 받습니다.
초록/요약
본 논문은 NP-난해 문제로 알려진 구간 그래프(interval graph)에서 강건 최단 경로 문제(robust shortest path problem)를 해결하기 위한 알고리즘을 제안한다. 이 알고리즘은 조합 최적화 문제를 풀기 위한 근사 알고리즘(approximation algorithm) 중 하나인 biased random-key 유전 알고리즘 [2]의 프레임워크에 활성 함수(active function)를 추가하여 확장한 알고리즘이며, 이것을 강건 최단 경로 문제에 적용하는 방법을 제안한다. 이때 활성 함수는 구간 그래프의 특성을 이용하여 각각의 간선에 선호도를 정의함으로써 간선의 활성 여부를 결정한다. 실험을 통해 본 연구가 제안한 알고리즘이 기존 알고리즘보다 최적해에 더 가까운 해를 찾는 것을 보여준다.
more초록/요약
This study proposes a new algorithm to solve the robust shortest path problem with interval data, which is known as NP-hard problem. It also suggests how the proposed algorithm which is an extension to the framework of biased random-key genetic algorithm [2], one of the approximation algorithms for solving combinatorial optimization problems, by adding an active function applies to the problem. At this time, the active function determines whether an edge is active or not by defining the preference of each edge, using the characteristic of interval data. The experimental results show that in reaching the optimal solution, the presented algorithm is performing better than existing algorithms.
more