경로 찾기를위한 유전 알고리즘 - 크로스 오버 및 돌연변이

Question

무차별 그래프 내에서 최단 경로를 찾는 유전 알고리즘을 사용하고 싶습니다. 나는 이것에 관해서 Crossover와 Mutation에 관해 두 가지 질문을한다. 나는 이것과 비슷한 상황에서 크로스 오버가 어떻게 수행 될 수 있는지 연구 해왔고, 가장 대중적인 알고리즘은 PMX 인 것 같다. 내 이해는 부분적인 경로가 2 개의 부모 염색체 사이에서 스왑되어 자손을 만든다. 내가 가지고있는이 문제는 거의 모든 자손이 무효화 될 수있는 막대한 범위가 있다는 것인가? 네가 나를 위해 이걸 확인할 수 있는지 궁금해서. 내가 틀렸다면, 나를 바로 잡고 설명해.

별도의 관련 메모에; 나는 이것을하는 방법에 대한 아이디어를 가지고 있었지만 좋은 생각인지 모르겠다. 두 부모를 선택했다. 경로에서 동일한 노드를 공유하고 그 지점에서 크로스 오버를하면, 모든 자식이 유효하다.

두 번째 문제점은 Mutation입니다. 나는 이것이 어떻게 행해질 수 있는지에 대한 일반적인 생각을 가지고있다; 하나의 노드를 선택하여 제거하고 다른 방법으로 경로를 다시 링크하는 것이 현명합니까?

감사합니다 :)!

Answer 1

우선, 당신은 효율적인 부모를 잃어 버릴지도 모른다고 말했기 때문에 교차 알고리즘과 돌연변이에 대해 공부하지만 유전 알고리즘에서는 "엘리트주의"개념을 사용합니다. 제안 된 크로스 오버 방법으로 극복해야한다는 것입니다. 왜냐하면 그 자체로 십자가에서 우리는 할 수있는 방법이 있기 때문에, 나는 두 번째 변종 교차 주문을 할 것을 제안합니다. 이것은 머피의 법칙이 아니므로 성취하려고 노력하십시오.