외판원문제에 대한 유전알고리즘 성능평가

목차

1. 서론

2. 문제기술

3. TSP를 위한 유전 알고리즘 설계

4. Ⅳ. 수치실험 및 결과

5. 결론

6. 참고문헌

본문내용

Ⅰ. 서 론

외판원문제(Traveling Salesman Problem: TSP)는 전형적인 조합최적화 문제로 폭 넓은 응용 분야를 가진 문제로서 공학, 생물학, 물리학 분야 등의 문제들에도 많이 이용되고 있는 중요한 문제이다. 그 예로는 차량경로문제(Vehicle Routing Problem: VRP), X-ray 결정학실험문제, 직접회로 삽입(IC Insertion)문제, 항공기 노즐의 유도날개문제 등과 같이 다양한 분야에서 적용되고 있다. 1859년 Hamilton[1]이 처음으로 이 문제를 제시한 이후 수리계획법의 주된 관심 대상으로서 많은 연구가 되어져 왔다. 외판원문제는, n개의 모든 지점을 오직 한 번씩만 방문하는 순회경로를 결정하는 과정에서 순회비용 또는 순회거리를 최소화하는 문제이다. 따라서 종래의 NP-hard문제에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다루고 있다. 지난 수년간 많은 연구자들에 의해서 새로운 모델과 기법들이 제안되고 있다.
최근에 보편적이면서도 널리 실세계에 적용되는 최적화 문제들을 푸는데 많은 메타휴리스틱 방법들이 제안되고 있다. 이러한 메타휴리스틱 방법들 중에는 진화 연산법, 유전적 프로그래밍, 진화 전략 혹은 타부 검색(Tabu Search), 시뮬레이티드 어닐링(Simulated Annealing)등과 같은 방법들이 있다. 이들 가운데 유전 알고리즘은 매우 주목받는 최적화 방법들 중에 하나이다. 유전 알고리즘은 생물의 유전현상을 모방한 해 탐색 방법을 이용하고 있다

참고 자료

[1] S. Kabadi, A. P. Punnen(2003). "Weighted graphs with all Hamiltonian cycles of the same length", Discrete Mathematics, Vol. 271, Issues 1-3, pp. 129-139.
[2] M. Gen and R. W. Cheng (2000). Genetic Algorithm and Engineering Optimization, John Wiley and Sons, New York.[3] I. Kara, T. Bektas (2006). "Integer linear programming formulations of multiple salesman problems and its variations", European Journal of Operational Research, Vol. 174, Issue 3, pp.1449-1458.
[4] G. Syswerda(1991). Schedule Optimization Using Genetic Algorithms, Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 332-349.
[5] M. Gen, and R. Cheng (1997). Genetic Algorithms and Engineering Design, John Wiley and Sons, New York.
[6] M. Gen and R. Cheng and L. Lin (2008). Network Models and Optimization: Multiobjective Genetic Algorithm Approach, Springer Verlag.