TSP 문제에 대해 GA 운영자에게 제안 하시겠습니까?

Question

나는 여행 세일즈맨 문제를 해결하기 위해 유전자 알고리즘을 만들고 있습니다. 불행히도, 나는 1000 대 이상을 유지할 수있는 봉우리를 치고 돌연변이를 일으키고 더 나은 결과를 얻습니다. 이 경우 교차 및 돌연변이 연산자가 일반적으로 잘하는 것은 무엇입니까?

Answer 1

당신은

는 "불행하게도, 내가 더 나은 결과를 그들 에서 돌연변이 및 도착하기 전에 이상 만 세대에 견딜 수있는 피크에 충돌"명확히 주시겠습니까?

교차 연산자를 확인하면 자식 염색체에 반복 노드가 없는지 확인할 수 있습니다. 이러한 교차 연산자 중 몇 가지는 Order Crossover (OX)와 Edge Crossover 연산자입니다.

단일 염색체에서 두 위치를 바꾸는 것만 큼 간단하게 변이를 만들 수 있습니다.

"비단뱀"이라고 태그를 지정 했으므로 Pyevolve을 살펴보면 TSP 예제도 있습니다.

Answer 2

정렬 돌연변이 및 규칙적인 교차 (this article 참조). 표준 돌연변이 및 교차 교차 작업은 일반적으로 유효하지 않은 솔루션 (즉, 경로의 중복 및/또는 누락 된 도시)을 초래합니다.

최근에 similar question이 발생했습니다.

구현 성능을 비교하고 싶다면 a Java applet that implements the TSP using ordered cross-over and mutation입니다.

Answer 3

문제가 천이 넘는 세대 동안 남아 있다면 문제는 크로스 오버 및 돌연변이 연산자가 아닐 수도 있습니다. 당신은 인구를 충분히 도입하거나 유지하지 않을 수도 있습니다. 한 세대에서 다음 세대로의 교차, 돌연변이 및 생존자의 비율을 조사하고 돌연변이의 비율을 높일 수 있습니다.