여행 세일즈맨을위한 경험적 방법

Question

나는 진화론적인 최적화 작업을하고 있으며,이 프로젝트에서는 여행 세일즈맨 문제에 대해 휴리스틱이 필요합니다. 이 문맥에서 유전 알고리즘, 우리는 작은 돌연변이를 적용하고 어딘가에 길 희망 상황이 나아질 것을 바랍니다. 그래서, 잠재적으로 개선으로 이어질 수있는 솔루션을 변형하기위한 간단한 경험적 방법을 찾고 있습니다. .

내가 추천하고 싶은

Answer 1

나는 당신이 여행 향상을위한 경험적 방법을 찾고 있다고 생각하며, Lin-Kernighan 알고리즘을 제안 할 수 있습니다. 그러나이 알고리즘은 당신에게 너무 어려울 수 있습니다. 그래서 대신 2-opt 또는 3-opt 알고리즘을 조사 할 수 있습니다.

Answer 2

하나의 참조가 R's TSP package 어떤 제안을 주셔서 감사합니다. (R을 사용하지 않더라도 조사해보십시오.) Their vignette on TSP은 우수하며 GA 구현을 향상시킬 수있는 동적 프로그래밍 기반 트릭이 많이 있습니다. 당신이 통합 할 수 투어 건설 휴리스틱 특히 회담 네트의

2.4. 그에서 인용 :

가장 가까운 이웃 알고리즘 : 매우 간단한 욕심 절차는 다음과 같습니다 알고리즘은 투어가 임의로 이 선택한 도시를 포함하는 시작하고 항상 순회 가까운하지의 마지막 도시에 추가 아직 방문한 도시. 모든 도시가 둘러보기에 일 때 알고리즘이 중지됩니다.

이 알고리즘을 확장하면 각 도시마다 출발점으로 반복 한 다음 가장 좋은 둘러보기를 반환합니다. 이 추론은 반복적으로 가장 가까운 이웃이라고하는 입니다.

삽입 알고리즘.은 임의의 도시로 구성된 둘러보기로 시작한 다음 각 단계에서 아직 둘러 보지 않은 도시를 선택합니다. 이 도시는 삽입 비용 (즉, 투어의 길이의 증가)이 최소화되도록 두 개의 연속적인 도시 i 및 j 사이의 기존 투어에 삽입됩니다. 둘러보기에있는 모든 도시가 일 때 알고리즘이 중지됩니다.

가장 가까운 삽입 도시 k는 투어에서 도시와 가장 가까운 도시로 각 단계에서 선택됩니다.

가장 멀리 삽입 도시 k는 각 단계에서 둘러보기에있는 도시 중 가장 멀리 떨어져있는 도시로 선택됩니다.

가장 저렴한 삽입 도시 k는 새로운 도시를 삽입하는 데 드는 비용이 최소화되도록 각 단계에서 선택됩니다.

vignette에 언급 된 많은 세부 사항 및 기타 기술을 찾을 수 있습니다.