TSP 알고리즘 구현 20114514 서왕덕.

Presentation on theme: "TSP 알고리즘 구현 20114514 서왕덕."— Presentation transcript:

1 TSP 알고리즘 구현 서왕덕

2 Index 작년 TSP 프로젝트 소개 구현했던 알고리즘 소개 프로젝트를 진행하면서 느꼈던 점

3 작년 프로젝트 설명 각 팀은 TSP 문제를 풀기 위한 알고리즘 1개씩 준비
1분 안에 지도에 대한 텍스트 파일을 입력 받아서 경로 출력 도시의 개수는 최대 1000개 이하 모든 도시는 연결 되어있으며 가는 거리와 오는 거리가 같음

4 작년 프로젝트 설명 입력 출력

5 구현한 알고리즘 Greedy Simulated Annealing Search Genetic Algorithm
Nearest Neighbor Algorithm K-Opt Search Simulated Annealing Search Genetic Algorithm

6 Nearest Neighbor Algorithm
출발 도시로부터 방문하지 않은 도시 중 가장 거리가 짧은 도시 를 선택. 각 노드에서 위와 같은 방법 반복 Baseline Performance로 사용

7 Nearest Neighbor Algorithm Code
사족을 달자면 왜 안좋은지

8 K-opt Search 전체 완성된 경로 중 k개의 점을 기준으로 그 사이 경로들을 역 순으로 나열
Example(2-opt Search) 0 – 1 – 2 – 3 – 4 – 0 의 경우 2번째 index와 4번째 index를 선 택할 경우 0 – 3 – 2 – 1 – 4 – 0 으로 바뀜 간단하며 반복할 경우 좋은 경로를 찾기 쉽다. 간단한 예시 설명

9 2-opt Search – Design Issue
처음에 시작하는 경로는 어떻게 할 것인가? (Random하게 시작? Nearest Neighbor 등으로 초기화 후 시작?) 경로를 바꿀 2개의 지점은 어떻게 정할 것인가? (Random하게 선택? 기준에 따라 선택?) 알고리즘을 언제 종료할 것인가? 디자인 이슈 설명 후에 내가 선택한 알고리즘 말하기

10 2-opt Search Code

11 2-opt Search Code

12 2-opt Search Code

13 Simulated Annealing – Design Issue
초기 파라미터는 어떻게 정할것인가? 온도는 어떻게, 얼마나 온도를 낮출 것인지 2-opt와 마찬가지로 초기 경로는 어떻게 시작할 것인지 프로그램 안에서 어떻게 경로를 바꿀 것인가? 초기경로를 어떻게 설정했는지 설명하기

14 SA Code 𝑒 − 𝑡𝑟𝑖𝑎𝑙𝑆𝑐𝑜𝑟𝑒 − 𝑏𝑒𝑠𝑡𝑆𝑐𝑜𝑟𝑒 𝑡𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒

15 SA Code

16 SA Code

17 SA Code

18 SA Code

19 Genetic Algorithm – Design Issue
초기 파라미터는 어떻게 설정할 것인가? 인구 수, 세대는 얼마나?(어떻게 종료할 것인가?) 내부의 알고리즘은 어떤 것을 사용 할 것인가? 어떻게 첫 세대를 초기화 할 것인가? 인구 선택은 어떻게 할 것인가? 교배는 어떻게 할 것인가? 돌연변이는 어떻게 할 것인가? 도시 리스트는 어떻게 표현 할 것인가? (Permutation Encoding)

20 GA Process 1. Population 초기화 (Initialization)
2. 교배할 해들을 선택 (Selection) 3. 선택된 해들을 교배 (Crossover) 4. 일부 해들에게 돌연변이 적용 (Mutation) 5. 2 ~ 4의 과정을 반복

21 GA Process 1. Population 초기화 (Initialization) (Random or SA)
2. 교배할 해들을 선택 (Selection) (Pseudo Tournament Selection) 3. 선택된 해들을 교배 (Crossover) (PMX) 4. 일부 해들에게 돌연변이 적용 (Mutation) (Swap Mutation) 5. 2 ~ 4의 과정을 반복

22 GA Code

23 GA Code

24 GA Code

25 GA Code

26 GA Code

27 (Pseudo) Tournament Selection

28 PMX (Partially Mapped Crossover)

29 PMX Code

30 PMX Code

31 PMX Code

32 Mutation – Swap Mutation
랜덤한 2지점 선택해서 교환

33 Swap Mutation Code

34 GA 참고자료 Youtube에 Noureddin Sadawi 검색

35 Project Demo 쓰인 데이터 설명하기

36 Q & A

37 휴대폰 번호 – 3481 – 4704 주소