염색체의 유전자가 고유하지 않은 경우 GA에서 주문 교차를 적용하는 방법은 무엇입니까?

Question

유전 알고리즘 (GA)에서 주문 교차 (OX)는 일반적으로 고유 유전자가있는 염색체에 적용됩니다. 이 paper 따르면, OX이처럼 염색체인가된다 {3, 1, 2, 1, 1}이 지침 :

(a) Randomly choose two cut-off points in the string. 

(b) Copy the elements of the first parent that are found between the two 
    cutoff points in the first offspring. 

(c) Copy the elements that still have not been included in the first offspring 
    as follows: 

    (c.1) Start from the second cutoff point of the second parent. 

    (c.2) Copy the elements not included in the first offspring, respecting 
      the order in which the elements appear in the second parent. 

    (c.3) Once the list of the second parent is finished, continue with the 
      first elements (as in a circular arrangement). 

(d) The second offspring is created in a similar way (steps b and c), inverting 
    the role of the parents. 

이 문서에서 설명하는 문제가 트리 문제 걸친 일반화 최소 (인 GMSTP)에서 그래프는 정점의 클러스터로 나뉘며 MST는 각 클러스터의 단 하나의 정점만으로 구성되어야합니다. 논문에서 염색체의 각 요소는 클러스터를 나타내며 요소의 각 값은 GMST를 구성하기 위해 클러스터의 선택된 노드입니다.

OX는 부모 2에서 유전자의 순서를 보존한다. GA를 사용하여 여행 판매원 문제 (TSP)를 해결할 때 염색체의 각 값이 노드 (도시)를 나타내는 경우. 그러나 GMSTP의 경우 클러스터의 순서가 항상 동일하기 때문에 모호합니다. OX에

[편집]

예 : 이제

Parent1 = { 1 2 3 4 5 6 7 8 9 } 
Parent2 = { 3 2 8 1 4 9 6 5 7 } 

after 2 random cut-off points 

Parent1: { 1 2 | 3 4 5 6 | 7 8 9 } 
Parent2: { 3 2 | 8 1 4 9 | 6 5 7 } 

Copy genes between the two cut-off points of the 1st parent 
Child1: { x x | 3 4 5 6 | x x x } 

Copy the rest of genes of the 2nd parent starting from the 2nd cut-off point, 
excluding genes already in the child as well as preserving order 
Child1: { 1 9 | 3 4 5 6 | 7 2 8 } 

(Do the same for Child2 swapping the parents) 

, 유전자의 세트에 OX를 적용하려고 : 같은 염색체에 OX을 구현하는

Parent1: { 3 1 2 1 1 } 
Parent2: { 3 2 2 1 4 } 

I do not see a way of doing that, however, researchers said they used OX here. 

Answer 1

한 가지 방법이다 정상적으로 진행하고 누락 된 요소가 발견되면 원래 요소 (제 질문에 대한 제 1 저자의 답변)를 복사하십시오. 나는 완전히 당신이 실제로 여기 요구하는지 이해가 안

Parent1 = { 3 1 2 1 1 } 
Parent2 = { 3 2 2 1 4 } 

after 2 random cut-off points 

Parent1: { 3 | 1 2 | 1 1 } 
Parent2: { 3 | 2 2 | 1 4 } 

Copy genes between the two cut-off points of the 1st parent 
Child1: { x | 1 2 | x x } 

Copy the rest of genes of the 2nd parent starting from the 2nd cut-off point, 
excluding genes already in the child as well as preserving order 
Child1: { x | 1 2 | 4 3 } 

Copy original values to the missing elements 
child1: { 3 | 1 2 | 4 3 } 

The same for Child2 swapping the rules of the parents 
child2: { 3 | 2 2 | 1 3 }