가장 가까운 이웃 또는 유전자 알고리즘은 TSP 문제에서 더 짧은 투어를 생성하는 방법은 무엇입니까?

Question

지난 며칠 동안 나는 몇 가지를 언급했습니다. 편물 사이트 유전자 알고리즘을 사용하여 TS 솔루션을 입증했습니다.

접근법은 TSP 문제에서 더 짧은 투어를 생성합니다. 가장 가까운 이웃 또는 유전자 알고리즘은 무엇입니까?

Answer 1

어느 기술도 최적의 솔루션을 보장하기 때문에 마일리지는 다릅니다. 약간의 운이 좋으면 어느 기술도 다른 기술을 능가 할 수 있습니다. 두 기술 모두 장단점이 있습니다.

가장 가까운 이웃 : +빠른, +단순, -일반적으로 최적이 아님

유전자 알고리즘 : -셀워, -더 복잡한, +솔루션 트렌드는 시간이 지남에 따라 최적으로 향합니다.

가장 큰 차이점은 무작위 알고리즘과 같은 것입니다 시뮬레이션 어닐링 그리고 유전자 알고리즘은 시간이 지남에 따라 계속 향상 될 수 있습니다. 더 오래 실행할수록 최적의 솔루션에 대한 기회가 더 많아집니다 (보장은 없지만).

NN이 빠르기 때문에 기술을 결합하는 것을 막는 것은 없습니다. NN을 실행하여 랜덤보다 시작된 솔루션을 찾으십시오. 그런 다음 해당 솔루션을 유전자 알고리즘에 공급하고 적절하다고 생각하는 한 실행하십시오.

최적의 솔루션에 관심이 있으시면 Lin-Kernighan 휴리스틱 그리고 선형 프로그래밍. 둘 다 큰 투어를위한 최적의 솔루션을 찾는 데 사용되었습니다. 이 솔루션 a 85,900 시티 투어 그리고 a 24,978시 스웨덴 투어.

그만큼 조지아 기술 TSP 사이트 훌륭한 자원입니다.