앞에서 말했듯 1234567890과 4567890123, 5432109876 같은 유전자들은 모두 동일한 유전자입니다. 이렇게 유전자를 변형시키는 프로시저가 필요합니다. 자세한 알고리즘은 생략하겠습니다.
㉠ Rolling(Gene gene, CityID city)
gene에서 도시들의 순서는 변화시키지 않고 특정 도시를 가장 앞으로 끌어오는 프로시져입니다.
즉 gene이 0123456789일때 Rolling(gene, 7)을 하면 gene이 7890123456으로 바뀝니다.
㉡ Flip(Gene gene)
gene에서 첫째 도시는 건드리지 않고 전체 도시 순서를 역순으로 바꿉니다. 즉 gene이 7890123456일때 을 Flip(gene)하면 gene은 7654321098이 됩니다.
7. 교차
잘 아시다시피 교차는 특정한 유전자를 교환하는 작업입니다. 그런데 이 문제에서와 같이 유전자에 제약이 있는 경우에는 함부로 유전자를 교환할 수 없습니다.
한가지 보기로 다음과 같은 두 유전자가 있습니다.
A : 0219746835
B : 7150382946
이 유전자를 1점교배로 교환하면
A : 0219382946
B : 7150746835
이런 유전자가 생깁니다. A는 2, 9번 도시를 두번씩, B는 7, 5번 도시를 두번씩 방문하는군요. 즉 일반적인 교차를 사용하면 제약을 만족하는 유전자를 얻을 수가 없습니다. 그러므로 이 문제에서는 다음과 같은 방식으로 교차를 시킵니다.
㉠ 먼저 교차영역을 정해야 합니다. 임의의 도시를 정해 양쪽 모두 Rolling프로시저를 호출합니다. 만약 4번도시가 선택되었다면
A : 4683502197
B : 4671503829
와 같이 변환시킵니다.
이후에는 앞쪽부터 살펴가면서 경로가 나뉘어졌다가 다시 합류하는 부분을 찾습니다.
A : 4683502197
B : 4671503829
두 유전자의 경로는 6번 도시 이후부터 나뉘기 시작하고 5번 도시에서 다시 일치합니다. 그러므로 이 경우에는 4번도시부터 5번도시까지의 경로를 교차영역으로 삼습니다.
만약 교차영역을 찾을 수가 없다면 이 두 유전자는 교차를 포기하게 됩니다.
㉡ A'와 B'를 만들어 일단 상대방의 교차영역을 복사합니다.
A' : 46715
B' : 46835
㉢ 다음에는 유전자의 나머지 영역을 완성할 차례입니다.
A와 B는 교차영역의 끝(5)을 첫머리로 돌립니다.
A : 5021974683
B : 5038294671
다음에는 A'와 B'에 A와 B를 연결하는데, A'와 B'에 이미 들어가 있는 도시는 제외하면서 연결합니다.
A' : 4671502983
B' : 4683502971
procedure CrossOver(Salesman A, Salesman B)
.. if Random(0, 100) > 50 then // 일정확률로 유전자 하나를 뒤집음
..... Flip(A.gene)
.. end
.. crosspoint := Random(0, 150) // 교차 시작할 도시 정해서 첫머리로
.. Rolling(A.gene, crosspoint)
.. Rolling(B.gene, crosspoint)
.. // 달라지기 시작하는 위치 찾기
.. sub := 0
.. while A.gene[sub] == B.gene[sub] do
..... sub := sub + 1
.. end
.. if sub >= 150 then // 두 유전자가 동일한 유전자
..... return // 교차 포기
.. end
.. // 교차 끝날 위치 찾기
.. while A.gene[sub] == B.gene[sub] do
..... sub := sub + 1
.. end
.. if sub >= 150 then // 두 유전자가 전혀 다른 유전자
..... return // 교차 포기
.. end
.. crossend := sub
.. Salesman AA, BB // 새로운 유전자를 만들 틀
.. // 상대방의 앞쪽부분을 복사
.. for sub := 0, crossend do
..... AA.gene[sub] := b.gene[sub]
..... BB.gene[sub] := a.gene[sub]
.. end
.. // 나머지 부분을 정리하기 위해
.. Rolling(A.gene, A.gene[crossend]) // 교차의 끝부분을 첫째도시로 재설정
.. // AA에 A를 추가
.. insertloc := crossend
.. for sub := 0, 150 do
..... // A.gene[sub]가 AA.gene에 포함되어 있는지를 확인하기 위해
..... for ct := 0, insertloc do
........ if AA.gene[ct] == A.gene[sub] then
........... break for loop
........ end
..... end
..... if ct >= insertloc then // 정상적 루프 탈출 - 중복되는 것이 없었음
........ AA.gene[insertloc] := A.gene[sub]
........ insertloc := insertloc + 1
..... end
.. end
.. // BB에 B를 추가
.. // 생략.. AA건과 동일
.. A := AA
.. B := BB
end
| TSP 문제를 해결하기 위한 유전자 설계법이 여러가지인 것처럼, 여기서 사용한 경로표현법 유전자를 교차하는 방법도 여러가지입니다. 여기서 사용한 교차법은 OX법(어떤 말의 약자인지는 모르겠습니다. Order Xover가 아닐까 추측할 뿐입니다)을 약간 수정한 것입니다. OX법은 원리는 같지만, 교차 시작점과 끝점을 찾는 것이 아니라 그냥 랜덤하게 결정해서 교차시키는 방법입니다. 하지만 제가 테스트한 결과로는 전혀 수렴이 안되더군요. 물론 제가 OX법을 제대로 이해 못해서일 수도 있습니다만...^^ |
댓글 없음:
댓글 쓰기