TSP 알고리즘 구현 20114514 서왕덕
Index 작년 TSP 프로젝트 소개 구현했던 알고리즘 소개 프로젝트를 진행하면서 느꼈던 점
작년 프로젝트 설명 각 팀은 TSP 문제를 풀기 위한 알고리즘 1개씩 준비 1분 안에 지도에 대한 텍스트 파일을 입력 받아서 경로 출력 도시의 개수는 최대 1000개 이하 모든 도시는 연결 되어있으며 가는 거리와 오는 거리가 같음
작년 프로젝트 설명 입력 출력
구현한 알고리즘 Greedy Simulated Annealing Search Genetic Algorithm Nearest Neighbor Algorithm K-Opt Search Simulated Annealing Search Genetic Algorithm
Nearest Neighbor Algorithm 출발 도시로부터 방문하지 않은 도시 중 가장 거리가 짧은 도시 를 선택. 각 노드에서 위와 같은 방법 반복 Baseline Performance로 사용
Nearest Neighbor Algorithm Code 사족을 달자면 왜 안좋은지
K-opt Search 전체 완성된 경로 중 k개의 점을 기준으로 그 사이 경로들을 역 순으로 나열 Example(2-opt Search) 0 – 1 – 2 – 3 – 4 – 0 의 경우 2번째 index와 4번째 index를 선 택할 경우 0 – 3 – 2 – 1 – 4 – 0 으로 바뀜 간단하며 반복할 경우 좋은 경로를 찾기 쉽다. 간단한 예시 설명
2-opt Search – Design Issue 처음에 시작하는 경로는 어떻게 할 것인가? (Random하게 시작? Nearest Neighbor 등으로 초기화 후 시작?) 경로를 바꿀 2개의 지점은 어떻게 정할 것인가? (Random하게 선택? 기준에 따라 선택?) 알고리즘을 언제 종료할 것인가? 디자인 이슈 설명 후에 내가 선택한 알고리즘 말하기
2-opt Search Code
2-opt Search Code
2-opt Search Code
Simulated Annealing – Design Issue 초기 파라미터는 어떻게 정할것인가? 온도는 어떻게, 얼마나 온도를 낮출 것인지 2-opt와 마찬가지로 초기 경로는 어떻게 시작할 것인지 프로그램 안에서 어떻게 경로를 바꿀 것인가? 초기경로를 어떻게 설정했는지 설명하기
SA Code 𝑒 − 𝑡𝑟𝑖𝑎𝑙𝑆𝑐𝑜𝑟𝑒 − 𝑏𝑒𝑠𝑡𝑆𝑐𝑜𝑟𝑒 𝑡𝑒𝑚𝑝𝑒𝑟𝑎𝑡𝑢𝑟𝑒
SA Code
SA Code
SA Code
SA Code
Genetic Algorithm – Design Issue 초기 파라미터는 어떻게 설정할 것인가? 인구 수, 세대는 얼마나?(어떻게 종료할 것인가?) 내부의 알고리즘은 어떤 것을 사용 할 것인가? 어떻게 첫 세대를 초기화 할 것인가? 인구 선택은 어떻게 할 것인가? 교배는 어떻게 할 것인가? 돌연변이는 어떻게 할 것인가? 도시 리스트는 어떻게 표현 할 것인가? (Permutation Encoding)
GA Process 1. Population 초기화 (Initialization) 2. 교배할 해들을 선택 (Selection) 3. 선택된 해들을 교배 (Crossover) 4. 일부 해들에게 돌연변이 적용 (Mutation) 5. 2 ~ 4의 과정을 반복
GA Process 1. Population 초기화 (Initialization) (Random or SA) 2. 교배할 해들을 선택 (Selection) (Pseudo Tournament Selection) 3. 선택된 해들을 교배 (Crossover) (PMX) 4. 일부 해들에게 돌연변이 적용 (Mutation) (Swap Mutation) 5. 2 ~ 4의 과정을 반복
GA Code
GA Code
GA Code
GA Code
GA Code
(Pseudo) Tournament Selection
PMX (Partially Mapped Crossover)
PMX Code
PMX Code
PMX Code
Mutation – Swap Mutation 랜덤한 2지점 선택해서 교환
Swap Mutation Code
GA 참고자료 Youtube에 Noureddin Sadawi 검색
Project Demo 쓰인 데이터 설명하기
Q & A
휴대폰 번호 010 – 3481 – 4704 E-mail 주소 seowangduk@gmail.com