TSPTW 유전자 알고리즘 내가 81 개 도시와 유전자 알고리즘과 TSPTW (시간 창 여행 세일즈맨)을 구현하고

Question

, 나는 다음과 같이 적용과 :

mutation prob=0.03 
population size=100 
-Generate random population according to the value of population size intialized 
-Sort the generated population 
-Looping for populations and determine two parents by roulette selection, apply crossover on the parents, get child and add it to children list 
-I am saving the best solution over the algorithm 
-Sort the Children, replace worst tour in populations with best one of children 
until no good children is existing is better than worst solution in populations 
-loop (1 to population size)in all populations and Apply mutation of each worst solution with solution i , if the mutated solution is better than the worst solution of children. I insert it in populations in its place according to its fitness function and remove the worst one. 

내가 좋은 결과를 찾을 수 없습니다, 나는 실행을 그것은 특정 시간에,하지만 때로는 해결책으로 붙어 더 나은 결과를 얻을 수 없습니다 발견. 는 내가

매개 변수를 변경 (인구 규모 = 20000, 1000,100, 돌연변이 확률 = 0.03,0.02, ..)

나는 또한 사이클 크로스 오버로 테스트했습니다 및 정렬 크로스 오버

내가 알고 싶은 것은, 나의 발길은 맞습니까? 어떻게 인구 크기와 돌연변이 확률을 정확하게 지정할 수 있습니까?

Answer 1

알고리즘이 너무 엘리트입니다. 그것은 당신의 인구를 입력하는 더 나은 솔루션을 허용합니다. 어떤 시점에서 모든 유사한 개인으로 구성 될 것이라고 가정합니다. 다양성이 남아 있지 않고 엘리트 주의적 대체물이 없기 때문에 적은 양의 돌연변이 만이 새로운 유전 물질을 도입 할 수 있습니다.

이전 세대의 최고의 개인 만 생존 할 수 있다는 점에서 elitism을 사용하는 것이 좋습니다. 나머지 개인은 모두 새로운 세대로 대체되어야합니다.

또는 우리가 발명 한 자손 선택 방식을 사용할 수 있습니다. 생존 할 수있는 각 어린이는 부모보다 나은 부모가되어야합니다. 그렇지 않으면 그들은 버려지고 새 부모를 낳아 새로운 아이를 낳습니다. 새로운 인구를 채우기에 충분할 때까지 새로운 아이들을 생산하도록 반복합니다. 그런 다음 인구를 대체하고 새롭게 시작하십시오. 자손 선택 유전 알고리즘은 일반적으로 달성 할 수있는 품질 측면에서 유전 알고리즘보다 우수합니다. HeuristicLab에 구현되었습니다. VRPTW를 열고 하나의 차량 만 허용하는 경우 TSPTW를 모델링 할 수 있어야합니다.

또 다른 옵션은 궤도 기반 알고리즘으로 진행하는 것입니다. 통합 된 금기 검색과 같은 금기 검색에 기초하여 제약 조건 완화는 아마도 시간 창 솔루션 (time windowed solution)과 서로 다른 지역 최적 값 (local optima)으로 인해 필요하다.