인공지능) Pathfinding2

최적화 문제 (Optimazation Problem)

--> TSP (Traveling Salesman Problem) 을 예로 설명

--> 여러 대학을 모두 방문하는데 최단 거리는? (한번만 방문한다고 가정)

○ 최적화에서 고려할 점

- 목적 함수 : 차량으로 이동한 거리의 합

- 해를 어떻게 표현할 것인가? : 방문한 대학 순서

- 어떻게 최적화 할 것인가?

○ 방법

- 전수 조사

- 랜덤 탐색

- Greedy 탐색

- Hill Climbing

- Genetic Algorithm

--> 전수 조사, 랜덤 탐색, Greedy 탐색은 생략 (기본적인 내용이므로)

○ Hill-climbing

- 초기에 랜덤값을 줌

--> 경사를 이동하며 탐색

--> 지역적으로는 최적화된 값을 찾을 수 있다.

--> 하지만 전역적으로 최적화된 값을 찾는다는 보장은 없다.

--> 문제를 해결하려면 단순히 많이 돌리는 방법밖에 없다. (랜덤값이 다양하게 분포되도록)

○ Genetic Algorithm

- Hill climbing이 점을 하나로 이용한다면, Genetic Algorithm은 점을 여러개 사용

- 병렬화가 가능하다

- 결과가 좋았던 값들이 보편적으로 좋은 결과를 이끌어냄

--> 이 값들 근처의 값들을 뽑음

--> 만약을 위해 mutation

- 기본 동작 구성

1. Selection (100%에 가까운 확률로 발생)    : 좋은 결과 근처의 값을 많이 뽑음

2. Cross-Over (50~80%)   : 두개를 섞음 (솔루션의 일부를 교환)

3. Mutation (10% 이내) : 값을 랜덤하게 바꿈

○ Genetic Algorithm 실험 링크