| 한글제목(Korean Title) |
Rural Postman 문제에서 근사해를 구하는 유전자 알고리즘 |
| 영문제목(English Title) |
A Genetic Algorithm for Obtaining a Near-Optimal Solution in Rural Postman Problem |
| 저자(Author) |
이영훈
강명주
한치근
Younghoon Lee
Myungju Kang
Chigeun Han
|
| 원문수록처(Citation) |
VOL 23 NO. 11 PP. 1118 ~ 1125 (1996. 11) |
한글내용
(Korean Abstract) |
본 연구에서는 무향 그래프에서의 Rural Postman Problem(RPP)을 해결하기 위한 유전자 알고리즘(Genetic Algorithm : GA)을 연구하였다. RPP는 무향 그래프 G = (V, E)가 주어지고 각 에지의 길이가 음이 아닌 수로 주어졌을 때, E의 부분집합인 E'에 속한 에지들을 한번 이상 모두 거치는 최소 거리의 경로를 구하는 문제이다. 본 연구에서는 NP-Complete 문제로 알려진 RPP를 해결하기 위한 방법으로 유전자 알고리즘을 이용하였으며, GA의 이용에 따른 유전자()의 구조를 제안하고 그에 따른 인코딩, 디코딩 방법과 여러가지 파라미터들의 결정에 대해서 연구하였다. 실험 계산에서는 본 논문에서 제안한 유전자 알고리즘을 Simulated Annealing 방법과 비교하였다. |
영문내용
(English Abstract) |
This paper process a Genetic Algorithm which can solve the Rurla Postman Problem. The Rural Postman Problem is a network routing problem in which we want to obtaina minimum cost circuit including each edge in a given subset E'⊆E at least once when a general graph G = (V, E) is given. This problem is known as an NP-Complete problem. We studied chromosome structure, encoding method, decoding method, and some operator whith are neeted when the Rural Postman Problem is solved using the proposed Genetic Algorithm. In the computational experiment, we compared the proposed GA with a Simulated Annealing method. |
| 키워드(Keyword) |
|
| 파일첨부 |
PDF 다운로드
|
