순수 유전 알고리즘을 이용한 외판원순회문제 (TSP) 실험

소개글

TSP 해결을 위한 유전 알고리즘 코드 및 보고서입니다.
룰렛휠선택알고리즘, PMX, ERX 등이 구현되어 있습니다.
C언어로 작성되었으며, makefile도 동봉합니다.
성격상 주석을 코드보다 많이 쓰기 때문에,
C언어 잘 모르시는 분들도 코드 이해하시는데 전혀 어려움이 없을 것으로 생각됩니다.
기본적으로 GCC로 돌아가지만,
Visual Studio나 기타 등등 아무 개발 환경에서 코드를 복사해 사용해도 무방합니다.

목차

1. 실험 목적

2. 실험 내용 및 방법
- 문제 표현
- 선택 연산
- 교차 연산
- 변이 연산
- 대치 연산

3. 실험 결과
- 실험 환경
- 입력 데이터
- 실험 결과

4. 논의 및 결론

본문내용

Travel Salesman Problem(TSP)은 거리가 주어진 각 도시들에서 그들을 모두 연결하는 가장 짧은 경로를 찾는 문제이며, 계산 시간이 도시수의 지수로 증가하는 전형적인 NP-hard 문제이다. 적당한 시간 내에 근사 최적해(near-optimal solution)를 구하기 위한 많은 연구들 중 자연 도태와 자연적 염색체의 진화 원리에 기초하여 동작하는 탐색 및 최적화 기법인 유전알고리즘(genetic algorithm, GA)은 TSP를 해결하기 위한 많은 유전적 교차 연산자가 제안되면서 성공적인 실험결과들을 제시하였다.
본 보고서에서는 지역 최적화(local optimization) 과정을 포함하지 않는 순수 GA의 범위 내에서 TSP를 해결하기 위한 최적의 방법을 찾는 것을 목적으로 하여, 순수한 형태의 GA가 갖는 한계를 실험 결과에 근거하여 기술한다.

참고 자료

문병로 저, 쉽게 배우는 유전 알고리즘, 한빛미디어

압축파일 내 파일목록

code.zip
순수 유전알고리즘을 이용한 외판원문제 실험.docx