진화알고리즘으로 외판원문제 해결하기

소개글

진화알고리즘을 이용하여 경영과학의 주요문제인 외판원문제(tsp)를 java 프로그래밍하여 gui로 구현하였습니다.

TSP(Traveling Salesman Problem)가 주어지고, 각각의 돌연변이-교차조합으로 최적의 조합을 찾는 식으로 문제를 해결하였습니다.

## 첨부된 폴더중 txt파일을 기본으로 만들어진 것이므로 txt파일을 훼손하지 마시기 바랍니다. 7열까지를 skip한채로 연산하였으므로 8열부터 값이 시작되어야 합니다.


아래 문제에 따라서 프로그래밍하였습니다.


1. 데이터 파일로 주어진 외판원문제에서 도시 1에서 출발하여 다시 1로 돌아온다고 가정할 때, 가장 가까운 도시부터 차례로 방문하는 방법을 사용한다면 이 때 총 거리와 도시 경로를 구하라.

※. 위의 외판원문제를 진화알고리즘으로 구현하고자 한다. 조건은 다음과 같다.

-. 해의 표현방법: 경로표현
-. 모집단 크기: 500
-. 세대 수: 500
-. 선택방법: 토너먼트 선별(토너먼트 크기: 2)
-. 교차방법(교차율-0.7): 순서교차, 순서기반교차, 부분사상교차
-. 돌연변이방법(돌연변순이율-0.3): 교환, 역순, 전위

2. 각각의 교차-돌연변이 방법의 조합을 이용하여 진화알고리즘을 구현하라. 각각의 경우, 최소 거리와 도시 경로를 구하고 가장 좋은 교차-돌연변이 조합을 찾아라.

3. 문제 2에서 가장 좋은 성능을 보인 교차-돌연변이 조합에서 각 세대별 best, worst, average해를 찾고 이를 그래프로 표현하라.

4. 진화알고리즘을 이용한 외판원문제의 해와 문제 1의 해와 비교하라. 어떤 차이점이 존재하는가?

나름의 해답도 정리되어 있습니다.

컴파일 실행환경

eclipse v3.4

압축파일 내 파일목록

SOLUTION/박정민.doc
SOURCE/Console.java
SOURCE/main.java
SOURCE/TSP.java
TSP-data.txt
과제-2-TSP.doc

참고 자료

없음