https://dawninthemoon.tistory.com/79


디씨 html이 병신이기도 하고 플러그인도 없어서 수식이 다 깨져가지고 링크 걸어놓음 좀 더 자세한 설명 보고 싶은 사람은 저기서 보삼


프로그래밍 하는 인붕이들은 다 아는 문제겠지만, NP-Hard 문제중에 외판원 문제라고 유명한 문제가 있음

왜 유명하냐 하면 DFS로 정직하게 풀 경우 O(N!)이라는 극악의 시간복잡도가 나와서 그럼


도시 a에서 출발해서 n-1개의 도시를 거쳐 다시 a로 돌아오는 최단 거리(경로)를 구하는 건데 도시가 15개만 되어도 1억 3천만개의 경우를 탐색해야 해서 아마 인류가 멸망할 때까지 답이 안 나올거임


근데 어제 이 문제를 유전 알고리즘으로 푸는 재미있는 접근을 봐서 나도 한 번 해봐야지 하고 만들어 봤음


테스트 환경:

도시의 수: 15개

출발 지점: 0번

위치의 범위: 100 ≤ x, y ≤ 100

종료 조건: 가장 큰 적합도를 가진 유전자가 100세대가 넘을 동안 변화가 없을 경우

변이 확률: 3% (동적 변이 - 후반으로 갈수록 변이 확률 감소)

거리 제한: 없음(모든 노드가 연결됨)

선택: 룰렛 휠 선택

교배: 일점 교배

집단 수: 15


결과



viewimage.php?id=2abcdd23dad63db0&no=24b0d769e1d32ca73cec86fa11d0283110260b998d7cfa8997b92765228e1b7279f9654fb5d203aec1ac11dc731b65338efbc0ffebdc9dae304c8fcf30cadf501472b1


viewimage.php?id=2abcdd23dad63db0&no=24b0d769e1d32ca73cec86fa11d0283110260b998d7cfa8997b92765228e1b7279f9654fb5d203aec1ac11dc731b65338efbc0ffebdc9df968498aca30918950548d18




정적 변이냐 동적 변이냐, 변이 확률이 몇이냐에 따라 결과가 천차만별임


정적 변이로 하고 변이 확률을 0.1%로 했을 때는 2000세대까지 가기도 했는데

동적 변이로 하고 변이 확률을 3%로 하니까 보통 200세대 정도에서 값이 수렴함


수정)

값이 재미없을 땐 집단이나 유전자 수를 늘려보자