GA - 장사꾼여행문제(TSP) [5] - 실행 결과

9. 결과

앞에서 설명한 식으로 150개 도시를 여행하는 최적해를 찾아보았습니다. 이때 Tournament법에 사용하는 상수 T의 값을 0.7부터 1.0까지 바꾸어 가며 10000세대동안 돌려보았습니다.
그 결과는 다음과 같습니다.



여기서 볼 수 있듯이 T값이 1에 가까울수록 수렴속도가 빨라짐을 알 수 있습니다.



이것은 마지막 10000세대에 달성된 최적값을 모아놓은 도표입니다. T값이 약 0.85~1일 경우 거의 비슷한 값이 나타나지만* 그 이후부터는 최적값이 급격히 올라가는 것이 보입니다.**

다음은 T값이 0.99일 때와 0.975일 때 10000세대만에 나온 150개 도시여행 근사해입니다.



결과는 T값이 0.975일 때가 더 좋은 근사값임을 알 수 있습니다.*

* T값이 0.85 이상일 경우에, 10000세대에서의 최적경로가 T값에 따라 약간의 차이가 있습니다. 그뿐 아니라 같은 T값을 사용하는 경우에도 여러번 반복하면 최적경로가 달라지는 경우가 있습니다. 이것은 초기 랜덤함수의 상태(srand())에 의한 것으로 생각됩니다.(확인하고 싶지만 한번 10000세대 돌리는데 2,3시간은 족히 걸리는지라..ㅡㅡ) 그러므로 좋은 근사값을 얻기 위해서는 0.85 이상의 T값에서 여러번 돌려보고 가장 좋은 값을 사용하는 것도 방법일 수 있습니다.
** T값이 0.85 이하일 경우에도 그래프에서 보면 감소세가 확실합니다. 그러므로 시간을 충분히 주면 근사값을 발견할 가능성도 없지 않습니다(이것 역시 시간의 압박 때문에...ㅡㅡ)