어느날 어떤 종교의 사제(목사나 신부, 승려, 랍비 등 마음에 안드는 것을 넣으세요)와 신도가 골프를 치고 있었습니다. 그런데 그날따라 사제의 컨디션이 별로 안좋았는지 치는 족족 엉뚱한 방향으로 날아갔습니다. 그때마다 사제는 침을 뱉으며 "X발, X나 안맞네"라고 소리쳤습니다.
마침내 옆에 있던 신도가 한마디 했습니다. "아니, 신을 섬기는 분이 그런 욕을 해도 되나요? 신의 징벌이 내리면 어쩔려고..."
바로 그순간 하늘에서 벼락이 떨어져 신도에게 맞았습니다. 그리고 몇초간 소나기가 내리더니 하늘에서 이런 소리가 울려퍼졌습니다. "X발, X나 안맞네"
올해는 어떨지 모르겠지만 작년만 해도 등산중인 사람들이 벼락에 맞아 죽는 일이 종종 있었습니다. 그사람들이 정말로 벼락맞을 만큼 나쁜 사람들인지는 모르겠지만, 혹시나 하느님이 눈이 나빠져서 자꾸 겨냥이 빗나간 것은 아닐까 생각해 봤습니다.
제발 올해는 하느님의 겨냥이 빗나가지 않기를 바랍니다.
GA - 장사꾼여행문제(TSP) [5] - 실행 결과
9. 결과
앞에서 설명한 식으로 150개 도시를 여행하는 최적해를 찾아보았습니다. 이때 Tournament법에 사용하는 상수 T의 값을 0.7부터 1.0까지 바꾸어 가며 10000세대동안 돌려보았습니다.
그 결과는 다음과 같습니다.
여기서 볼 수 있듯이 T값이 1에 가까울수록 수렴속도가 빨라짐을 알 수 있습니다.
이것은 마지막 10000세대에 달성된 최적값을 모아놓은 도표입니다. T값이 약 0.85~1일 경우 거의 비슷한 값이 나타나지만* 그 이후부터는 최적값이 급격히 올라가는 것이 보입니다.**
다음은 T값이 0.99일 때와 0.975일 때 10000세대만에 나온 150개 도시여행 근사해입니다.
결과는 T값이 0.975일 때가 더 좋은 근사값임을 알 수 있습니다.*
* T값이 0.85 이상일 경우에, 10000세대에서의 최적경로가 T값에 따라 약간의 차이가 있습니다. 그뿐 아니라 같은 T값을 사용하는 경우에도 여러번 반복하면 최적경로가 달라지는 경우가 있습니다. 이것은 초기 랜덤함수의 상태(srand())에 의한 것으로 생각됩니다.(확인하고 싶지만 한번 10000세대 돌리는데 2,3시간은 족히 걸리는지라..ㅡㅡ) 그러므로 좋은 근사값을 얻기 위해서는 0.85 이상의 T값에서 여러번 돌려보고 가장 좋은 값을 사용하는 것도 방법일 수 있습니다.
** T값이 0.85 이하일 경우에도 그래프에서 보면 감소세가 확실합니다. 그러므로 시간을 충분히 주면 근사값을 발견할 가능성도 없지 않습니다(이것 역시 시간의 압박 때문에...ㅡㅡ)
앞에서 설명한 식으로 150개 도시를 여행하는 최적해를 찾아보았습니다. 이때 Tournament법에 사용하는 상수 T의 값을 0.7부터 1.0까지 바꾸어 가며 10000세대동안 돌려보았습니다.
그 결과는 다음과 같습니다.
여기서 볼 수 있듯이 T값이 1에 가까울수록 수렴속도가 빨라짐을 알 수 있습니다.
이것은 마지막 10000세대에 달성된 최적값을 모아놓은 도표입니다. T값이 약 0.85~1일 경우 거의 비슷한 값이 나타나지만* 그 이후부터는 최적값이 급격히 올라가는 것이 보입니다.**
다음은 T값이 0.99일 때와 0.975일 때 10000세대만에 나온 150개 도시여행 근사해입니다.
결과는 T값이 0.975일 때가 더 좋은 근사값임을 알 수 있습니다.*
* T값이 0.85 이상일 경우에, 10000세대에서의 최적경로가 T값에 따라 약간의 차이가 있습니다. 그뿐 아니라 같은 T값을 사용하는 경우에도 여러번 반복하면 최적경로가 달라지는 경우가 있습니다. 이것은 초기 랜덤함수의 상태(srand())에 의한 것으로 생각됩니다.(확인하고 싶지만 한번 10000세대 돌리는데 2,3시간은 족히 걸리는지라..ㅡㅡ) 그러므로 좋은 근사값을 얻기 위해서는 0.85 이상의 T값에서 여러번 돌려보고 가장 좋은 값을 사용하는 것도 방법일 수 있습니다.
** T값이 0.85 이하일 경우에도 그래프에서 보면 감소세가 확실합니다. 그러므로 시간을 충분히 주면 근사값을 발견할 가능성도 없지 않습니다(이것 역시 시간의 압박 때문에...ㅡㅡ)
창조론 이야기 - 지르콘 속에 갇힌 헬륨
창조론자들의 주장 중에 이런 것이 있습니다.
미국 뉴멕시코주 Fenton Hill이란 곳에서 시추공을 통해 지르콘을 채취했다. 그 지르콘에 함유되어 있는 헬륨 양을 계산한 결과, 동일과정설자들의 말대로 수십억년이 된 암석이라면 이미 다 날아가버려야 했을 헬륨이 상당량 남아 있었다. 그 헬륨양으로 계산한 결과, 지구의 나이는 6000±2000에 불과하다. [http://www.halos.com/reports/grl-1982-helium-in-zircons.pdf]
윗 그림은 논문에 포함되어 있던 표입니다. 보시다시피 지상부터 지하 11310m까지 파내려가서 왼쪽 그림과 같은 지르콘 시료를 채취했습니다. 지하인 만큼 온도는 상당히 높고, 그에 따라 헬륨의 확산속도는 상당히 높을 테니 암석이 수억년이 되었다면 헬륨의 농도는 상당히 낮아야 한다는 것이었죠.
그런데 상당량의 헬륨이 남아있다는 것은 그 암석의 나이 - 즉 지구의 나이 - 가 수천년밖에 안되었다는 젊은 지구론의 증거로서 제시되었습니다.
저 논문은 2005년 3월 Kevin R. Henke, Ph.D.에 의해 반박되었으며 역시 2005년 4월 D. Russell Humphreys, Ph.D.에 의한 재반박을 거쳐 다시 2005년 11월 Henke에 의한 재재반박이 계속되었습니다.
Henke에 따르면, 이 실험의 가장 큰 문제점은 압력팩터를 고려하지 않은 것입니
다. 진공상태에서의 실리콘에서의 확산속도를 측정한 후 지하 수백미터에서 채취한 이 시료에 적용한 것이죠.
지르콘 같은 실리콘 계열의 결정들은 압력에 약합니다. 압력이 없다면 오른쪽 그림의 왼쪽처럼 실리콘과 산소가 정사면체를 이루고 있습니다. 그러나 압력이 가해진다면 오른쪽 그림처럼 압력에 저항할 수 없는 결합에 비틀림이 생깁니다. 그때문에 결정격자 사이의 틈이 작아지고 헬륨의 확산속도가 느려집니다. 실제로 많은 연구자들이, 압력이 걸린 실리케이트에서의 비활성기체의 확산속도는, 같은 온도일때 진공상태에서의 확산속도의 3~6자리수 정도 감소한다고 보고하였습니다[many other researchers have already shown that the diffusion of noble gases in silicate minerals may decrease by at least 3-6 orders of magnitude at a given temperature if the studies are performed under pressure rather than in a vacuum].
또한가지 문제는, 이 Fenton Hill에서 불과 수킬로미터 떨어진 곳에 Valles Caldera라는 화산지형이 있다는 점입니다. 1980년대, 이곳 Valles Caldera에 지열측정용 굴을 팠습니다. 그때 지하 1000미터 이상의 깊이에서 채취된 지하수에서는 kg당 0.0183~0.1173cc의 헬륨 4가 검출되었습니다. 그 때문에 가까이에 있던 Fenton Hill에서 채취한 지르콘 시료의 헬륨 농도에 영향을 미칠 가능성을 생각하지 않은 것이 또하나의 잘못이었죠.
어쨋든 Henke에 의한 재재반박이 나온 이후로 Humphrey나 다른 젊은지구론자들의 재재재반박(?) 이야기는 찾을 수가 없군요. 혹시 찾게 되면 업데이트 하겠습니다.
미국 뉴멕시코주 Fenton Hill이란 곳에서 시추공을 통해 지르콘을 채취했다. 그 지르콘에 함유되어 있는 헬륨 양을 계산한 결과, 동일과정설자들의 말대로 수십억년이 된 암석이라면 이미 다 날아가버려야 했을 헬륨이 상당량 남아 있었다. 그 헬륨양으로 계산한 결과, 지구의 나이는 6000±2000에 불과하다. [http://www.halos.com/reports/grl-1982-helium-in-zircons.pdf]
윗 그림은 논문에 포함되어 있던 표입니다. 보시다시피 지상부터 지하 11310m까지 파내려가서 왼쪽 그림과 같은 지르콘 시료를 채취했습니다. 지하인 만큼 온도는 상당히 높고, 그에 따라 헬륨의 확산속도는 상당히 높을 테니 암석이 수억년이 되었다면 헬륨의 농도는 상당히 낮아야 한다는 것이었죠.그런데 상당량의 헬륨이 남아있다는 것은 그 암석의 나이 - 즉 지구의 나이 - 가 수천년밖에 안되었다는 젊은 지구론의 증거로서 제시되었습니다.
저 논문은 2005년 3월 Kevin R. Henke, Ph.D.에 의해 반박되었으며 역시 2005년 4월 D. Russell Humphreys, Ph.D.에 의한 재반박을 거쳐 다시 2005년 11월 Henke에 의한 재재반박이 계속되었습니다.
Henke에 따르면, 이 실험의 가장 큰 문제점은 압력팩터를 고려하지 않은 것입니
다. 진공상태에서의 실리콘에서의 확산속도를 측정한 후 지하 수백미터에서 채취한 이 시료에 적용한 것이죠.지르콘 같은 실리콘 계열의 결정들은 압력에 약합니다. 압력이 없다면 오른쪽 그림의 왼쪽처럼 실리콘과 산소가 정사면체를 이루고 있습니다. 그러나 압력이 가해진다면 오른쪽 그림처럼 압력에 저항할 수 없는 결합에 비틀림이 생깁니다. 그때문에 결정격자 사이의 틈이 작아지고 헬륨의 확산속도가 느려집니다. 실제로 많은 연구자들이, 압력이 걸린 실리케이트에서의 비활성기체의 확산속도는, 같은 온도일때 진공상태에서의 확산속도의 3~6자리수 정도 감소한다고 보고하였습니다[many other researchers have already shown that the diffusion of noble gases in silicate minerals may decrease by at least 3-6 orders of magnitude at a given temperature if the studies are performed under pressure rather than in a vacuum].
또한가지 문제는, 이 Fenton Hill에서 불과 수킬로미터 떨어진 곳에 Valles Caldera라는 화산지형이 있다는 점입니다. 1980년대, 이곳 Valles Caldera에 지열측정용 굴을 팠습니다. 그때 지하 1000미터 이상의 깊이에서 채취된 지하수에서는 kg당 0.0183~0.1173cc의 헬륨 4가 검출되었습니다. 그 때문에 가까이에 있던 Fenton Hill에서 채취한 지르콘 시료의 헬륨 농도에 영향을 미칠 가능성을 생각하지 않은 것이 또하나의 잘못이었죠.
어쨋든 Henke에 의한 재재반박이 나온 이후로 Humphrey나 다른 젊은지구론자들의 재재재반박(?) 이야기는 찾을 수가 없군요. 혹시 찾게 되면 업데이트 하겠습니다.
GA - 장사꾼여행문제(TSP) [4] - 돌연변이
8. 돌연변이
교차와 마찬가지로 돌연변이 역시 유전자 최소단위(비트-bit)를 임의로 바꾸는 일반적인 돌연변이를 사용할 수 없습니다. 모든 도시를 한번만 방문할 수 있다는 제한 때문이죠.
여기서 사용한 돌연변이는 두가지입니다.
만약 유전자가 7385920416이라면
㉠ 임의의 경로 뒤집기
임의의 도시와 돌연변이시킬 길이를 임의로 정합니다. 2번도시와 길이 4가 정해졌다면
먼저 2번도시를 첫머리로 옮깁니다.
2041673859
그 후에는 앞에서 4개 길이를 뒤집습니다. 즉 2->0->4->1을 1->4->0->2로 바꿉니다.
1402673859
㉡ 임의의 경로 바꾸기
임의의 도시와 돌연변이시킬 범위의 앞뒤를 임의로 정합니다. 8번도시와 3~7이 정해졌다면, 먼저 8번도시를 첫머리로 재배열합니다.
8592041673
다음에는 0~2와 3~7까지의 경로를 뒤바꿉니다.
2041859673
㉢ 돌연변이 확률
꼬마자동차의 경우처럼 일반적인 돌연변이는 비트 하나하나에 대해 돌연변이 확률을 계산합니다. 그러므로 비트 하나하나에 대한 돌연변이 확률이 작더라도 개체 하나에 대한 돌연변이는 생각보다 크게 나오는 경우가 많습니다.
이 문제의 경우에는 비트 하나하나에 대한 돌연변이가 아니라 개체 전체에 대한 돌연변이를 채택했기에 돌연변이 확률은 좀 높이는 것이 좋습니다.
procedure Mutantation(Salesman s)
.. if Random(0, 10) == 0 then // 10% 확률로 돌연변이
..... if Random(0, 2) == 0 then // 경로 뒤집기
........ startcity := Random(0, 150)
........ Rolling(s.gene, startcity)
........ startpnt := 0
........ endpnt := Random(1, 150 / 2 + 1)
........ while endpnt > startpnt do
........... // startpnt도시와 endpnt도시를 바꿈
........... tmp := s.gene[startpnt]
........... s.gene[startpnt] := s.gene[endpnt]
........... s.gene[endpnt] := tmp
........... startpnt := startpnt + 1
........... endpnt := endpnt - 1
........ end
..... else // 경로 바꾸기
........ startcity := Random(0, 150)
........ Rolling(s.gene, startcity)
........ startpnt := Random(1, 150 / 2 + 1)
........ endpnt := Random(startpnt + 1, startpnt + 150 / 3 + 1)
........ Salesman tmp
........ tmp := s // 복사본을 만들어 놓음
........ sub := 0
........ for k := startpnt, endpnt do // startpnt~endpnt까지 앞에 복사
........... s.gene[sub] := tmp.gene[k]
........... sub := sub + 1
........ end
........ for k := 0, startpnt do // 0~startpnt까지 그 뒤에 복사
........... s.gene[sub] := tmp.gene[k]
........... sub := sub + 1
........ end
..... end
.. end
end
교차와 마찬가지로 돌연변이 역시 유전자 최소단위(비트-bit)를 임의로 바꾸는 일반적인 돌연변이를 사용할 수 없습니다. 모든 도시를 한번만 방문할 수 있다는 제한 때문이죠.
여기서 사용한 돌연변이는 두가지입니다.
만약 유전자가 7385920416이라면
㉠ 임의의 경로 뒤집기
임의의 도시와 돌연변이시킬 길이를 임의로 정합니다. 2번도시와 길이 4가 정해졌다면
먼저 2번도시를 첫머리로 옮깁니다.
2041673859
그 후에는 앞에서 4개 길이를 뒤집습니다. 즉 2->0->4->1을 1->4->0->2로 바꿉니다.
1402673859
㉡ 임의의 경로 바꾸기
임의의 도시와 돌연변이시킬 범위의 앞뒤를 임의로 정합니다. 8번도시와 3~7이 정해졌다면, 먼저 8번도시를 첫머리로 재배열합니다.
8592041673
다음에는 0~2와 3~7까지의 경로를 뒤바꿉니다.
2041859673
㉢ 돌연변이 확률
꼬마자동차의 경우처럼 일반적인 돌연변이는 비트 하나하나에 대해 돌연변이 확률을 계산합니다. 그러므로 비트 하나하나에 대한 돌연변이 확률이 작더라도 개체 하나에 대한 돌연변이는 생각보다 크게 나오는 경우가 많습니다.
이 문제의 경우에는 비트 하나하나에 대한 돌연변이가 아니라 개체 전체에 대한 돌연변이를 채택했기에 돌연변이 확률은 좀 높이는 것이 좋습니다.
procedure Mutantation(Salesman s)
.. if Random(0, 10) == 0 then // 10% 확률로 돌연변이
..... if Random(0, 2) == 0 then // 경로 뒤집기
........ startcity := Random(0, 150)
........ Rolling(s.gene, startcity)
........ startpnt := 0
........ endpnt := Random(1, 150 / 2 + 1)
........ while endpnt > startpnt do
........... // startpnt도시와 endpnt도시를 바꿈
........... tmp := s.gene[startpnt]
........... s.gene[startpnt] := s.gene[endpnt]
........... s.gene[endpnt] := tmp
........... startpnt := startpnt + 1
........... endpnt := endpnt - 1
........ end
..... else // 경로 바꾸기
........ startcity := Random(0, 150)
........ Rolling(s.gene, startcity)
........ startpnt := Random(1, 150 / 2 + 1)
........ endpnt := Random(startpnt + 1, startpnt + 150 / 3 + 1)
........ Salesman tmp
........ tmp := s // 복사본을 만들어 놓음
........ sub := 0
........ for k := startpnt, endpnt do // startpnt~endpnt까지 앞에 복사
........... s.gene[sub] := tmp.gene[k]
........... sub := sub + 1
........ end
........ for k := 0, startpnt do // 0~startpnt까지 그 뒤에 복사
........... s.gene[sub] := tmp.gene[k]
........... sub := sub + 1
........ end
..... end
.. end
end
GA - 장사꾼여행문제(TSP) [3] - 교차
6. 필요한 프로시져
앞에서 말했듯 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
앞에서 말했듯 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법을 제대로 이해 못해서일 수도 있습니다만...^^ |
진화론 이야기 - 진화적 군비 경쟁
나무와 벌레들이 같이 살고 있는 조그만 숲이 있습니다. 여기서 벌레는 나무를 갉아먹습니다.
이 숲의 나무들은 벌레의 공격에 의해 두꺼운 껍질을 가진 나무가 진화적 우위를 갖습니다*.
마찬가지로 벌레들 역시 나무껍질에 의해 크고 단단한 턱을 가진 벌레가 진화적 우위를 갖습니다*.
그러므로 시간이 지날수록 그 숲의 나무들은 점점 두꺼운 껍질을, 그 숲의 벌레들은 점점 더 크고 단단한 턱을 갖게 됩니다.
그럼에도 불구하고 벌레가 나무를 먹는 상황은 변하지 않습니다. 예전에는 작은 턱으로 얇은 나무껍질을 뚫고 나무를 파먹었다면 지금은 큰 턱으로 두꺼운 나무껍질을 뚫고 나무를 파먹는다는 차이일 뿐입니다.
*위에서 '진화적 우위를 갖는다'는 말은, 두꺼운 껍질을 가진 나무/크고 단단한 턱을 가진 벌레들이 생존경쟁에 유리하게 되어 더 많은 번식기회를 갖고, 그로인해 두꺼운 껍질을 가진 나무/크고 단단한 턱을 가진 벌레들이 많아진다는 뜻입니다.
밑에 공진화 이야기가 있습니다만. 공진화에 의해 천적관계의 진화가 계속되는 현상을 진화적 군비 경쟁이라고 합니다. 사실 두꺼운 나무껍질이나 크고 단단한 턱은 그들이 번식하는데는 오히려 방해가 됩니다. 나무껍질이나 턱을 만들기 위해 자원을 쓰느라 번식에 들어가는 자원이 줄어들죠.
하지만 그렇다고 해서 어느 한쪽이 진화를 멈춘다면 그들은 전멸하게 될 것입니다. 마치 냉전시대 미소의 군비경쟁처럼 말입니다.
혹시 나무와 벌레들이 협정을 맺을 수도 있겠죠.
"우리가 아무리 두꺼운 껍질과 큰 턱을 만들어봐야 벌레가 나무를 파먹는 관계는 변하지 않는다. 그럴 바에는 우리가 최소한의 껍질과 턱을 만들고 나머지는 번식에 힘쏟자"
그렇게 되면 그들은 두꺼운 나무껍질과 큰 턱을 만들 자원을 번식에 쏟을 테니 더 많은 나무들과 벌레들이 사는 지상낙원이 될 것입니다.
가끔씩 나오는 양심적 병역거부자가 그리는 세상이 저런 세상일 것입니다. 너도 나도 총을 놓는다면 전쟁으로 죽을 사람이 없으니 인구도 늘어나겠죠. 탱크대신 자동차를, 화약대신 비료를 만들테니 생산성도 늘어나는 낙원이 될 것입니다.
그런데 저런 세상이 얼마나 오래갈 수 있을까요?
하지만 극히 일부의 벌레들이 다른 벌레들보다 약간 큰 턱을 가진다면 어떻게 될까요? 그들은 더 많은 나무를 갉아먹으며 진화적 우위를 차지할 것입니다. 결국 모든 벌레들이 조금 더 큰 턱을 가지게 되며 나무들은 생존을 위해 더 두꺼운 껍질을 가져야 할 것입니다.
반대로 극히 일부의 나무들이 조금 더 두꺼운 껍질을 가져도 마찬가지가 될 겁니다.
그렇게 해서 저 지상낙원은 다시 진화적 군비경쟁이 판치는 예전의 숲으로 되돌아갈 수밖에 없습니다.
역시 아래에 있는 죄수의 딜레마상황처럼 배신자가 더 큰 이익을 가지게 됩니다. 병역거부자들의 낙원 역시 마찬가지죠. 아무도 무력을 가지고 있지 않다면 약간의 무장만으로도 커다란 이익을 얻을 수 있습니다. 그런 유혹에 빠지지 않을 사람을 찾기가 더 힘들 걸요. 그리고 그렇게 되면 결국 모든 사람들이 다시 무장을 하는 군비경쟁의 상황으로 되돌아갈 것입니다.
그렇다면 군비경쟁의 상황으로 돌아가지 않고 전쟁없는 낙원을 만들 가능성은 없을까요?
첫째로 죄수의 딜레마에서 가장 우수한 전략, 받은대로 돌려주는 Tit-for-Tat 전략을 사용하는 것입니다. 그런데 받은만큼 돌려주기 위해서는 나도 무장을 하고 있어야겠군요. 실제로 냉전중에 긴장이 높아도 전면전이 일어나지 않은 이유가 이것입니다. 하지만 모두가 무장을 한다면 '병역거부자의 낙원'이 아니게 되겠죠.
둘째로 더 두꺼운 나무껍질, 더 큰 턱을 만들었을 때 얻을 수 있는 진화적 우위를 박탈하는 방법이 있습니다. 만약 두꺼운 나무껍질이나 큰 턱을 만드는 비용이 너무 커서 그것으로 얻을 수 있는 이익이 더 작다면(즉 죄수의 딜레마에서 배신했을때의 보상을 낮추면) 다른 노력 없이도 자연스럽게 낙원이 만들어질 수 있습니다.
그런데 아무도 무장을 안한 상태에서 약간의 무장을 한 사람들에게 손해를 줄 방법이 마땅치 않다는 점이 문제겠네요.
이래저래 병역거부자들이 원하는 낙원은 불가능한가 봅니다.
그런데, 병역거부자들의 낙원은 불가능하다 치고 위에서 예로 든 나무와 벌레들의 낙원은 정말로 불가능할까요?
만약 모든 벌레들이 지나치게 큰 턱을 가진 벌레와는 짝짓기를 하지 않는다면 어떨까요(내 자손이 큰 턱을 가지고 쉽게 번식할 수 있겠다는 이익을 포기하고 말입니다)?
마찬가지로 모든 나무들이 지나치게 두꺼운 껍질을 가진 나무와는 꽃가루를 교환하지 않는다면 어떨까요(마찬가지로 내 자손들이 두꺼운 껍질을 가지고 오래 살 수 있겠다는 이익을 포기하구요)?
만약 그렇게 한다면 큰 턱과 두꺼운 껍질을 가진 '배신자'들은, 자신은 이익일 수 있으나 자손을 만들지 못하기에 도태되어버리고 지상낙원이 유지될 수 있겠군요.
물론 이 경우에는 '내 이익을 포기하고서라도 이 지상낙원을 유지하자'는 공감대가 모든 벌레들, 그리고 모든 나무들에게 퍼져있어야겠지만 말입니다.
현실에서도 '민주주의를 유지하자'는 공감대가 전 국민들에게 퍼져 있고 전 국민들이 민주주의를 유지하기 위해 자신의 이익을 약간 포기할 수 있어야 민주주의를 유지할 수 있습니다. 투표를 하기 위해 몇시간 늦게 애인과 만난다거나 몇시간동안만 온라인게임에서의 레벨업을 멈춘다든가 하는 식으로 말입니다.
이 숲의 나무들은 벌레의 공격에 의해 두꺼운 껍질을 가진 나무가 진화적 우위를 갖습니다*.
마찬가지로 벌레들 역시 나무껍질에 의해 크고 단단한 턱을 가진 벌레가 진화적 우위를 갖습니다*.
그러므로 시간이 지날수록 그 숲의 나무들은 점점 두꺼운 껍질을, 그 숲의 벌레들은 점점 더 크고 단단한 턱을 갖게 됩니다.
그럼에도 불구하고 벌레가 나무를 먹는 상황은 변하지 않습니다. 예전에는 작은 턱으로 얇은 나무껍질을 뚫고 나무를 파먹었다면 지금은 큰 턱으로 두꺼운 나무껍질을 뚫고 나무를 파먹는다는 차이일 뿐입니다.
*위에서 '진화적 우위를 갖는다'는 말은, 두꺼운 껍질을 가진 나무/크고 단단한 턱을 가진 벌레들이 생존경쟁에 유리하게 되어 더 많은 번식기회를 갖고, 그로인해 두꺼운 껍질을 가진 나무/크고 단단한 턱을 가진 벌레들이 많아진다는 뜻입니다.
밑에 공진화 이야기가 있습니다만. 공진화에 의해 천적관계의 진화가 계속되는 현상을 진화적 군비 경쟁이라고 합니다. 사실 두꺼운 나무껍질이나 크고 단단한 턱은 그들이 번식하는데는 오히려 방해가 됩니다. 나무껍질이나 턱을 만들기 위해 자원을 쓰느라 번식에 들어가는 자원이 줄어들죠.
하지만 그렇다고 해서 어느 한쪽이 진화를 멈춘다면 그들은 전멸하게 될 것입니다. 마치 냉전시대 미소의 군비경쟁처럼 말입니다.
혹시 나무와 벌레들이 협정을 맺을 수도 있겠죠.
"우리가 아무리 두꺼운 껍질과 큰 턱을 만들어봐야 벌레가 나무를 파먹는 관계는 변하지 않는다. 그럴 바에는 우리가 최소한의 껍질과 턱을 만들고 나머지는 번식에 힘쏟자"
그렇게 되면 그들은 두꺼운 나무껍질과 큰 턱을 만들 자원을 번식에 쏟을 테니 더 많은 나무들과 벌레들이 사는 지상낙원이 될 것입니다.
가끔씩 나오는 양심적 병역거부자가 그리는 세상이 저런 세상일 것입니다. 너도 나도 총을 놓는다면 전쟁으로 죽을 사람이 없으니 인구도 늘어나겠죠. 탱크대신 자동차를, 화약대신 비료를 만들테니 생산성도 늘어나는 낙원이 될 것입니다.
그런데 저런 세상이 얼마나 오래갈 수 있을까요?
하지만 극히 일부의 벌레들이 다른 벌레들보다 약간 큰 턱을 가진다면 어떻게 될까요? 그들은 더 많은 나무를 갉아먹으며 진화적 우위를 차지할 것입니다. 결국 모든 벌레들이 조금 더 큰 턱을 가지게 되며 나무들은 생존을 위해 더 두꺼운 껍질을 가져야 할 것입니다.
반대로 극히 일부의 나무들이 조금 더 두꺼운 껍질을 가져도 마찬가지가 될 겁니다.
그렇게 해서 저 지상낙원은 다시 진화적 군비경쟁이 판치는 예전의 숲으로 되돌아갈 수밖에 없습니다.
역시 아래에 있는 죄수의 딜레마상황처럼 배신자가 더 큰 이익을 가지게 됩니다. 병역거부자들의 낙원 역시 마찬가지죠. 아무도 무력을 가지고 있지 않다면 약간의 무장만으로도 커다란 이익을 얻을 수 있습니다. 그런 유혹에 빠지지 않을 사람을 찾기가 더 힘들 걸요. 그리고 그렇게 되면 결국 모든 사람들이 다시 무장을 하는 군비경쟁의 상황으로 되돌아갈 것입니다.
그렇다면 군비경쟁의 상황으로 돌아가지 않고 전쟁없는 낙원을 만들 가능성은 없을까요?
첫째로 죄수의 딜레마에서 가장 우수한 전략, 받은대로 돌려주는 Tit-for-Tat 전략을 사용하는 것입니다. 그런데 받은만큼 돌려주기 위해서는 나도 무장을 하고 있어야겠군요. 실제로 냉전중에 긴장이 높아도 전면전이 일어나지 않은 이유가 이것입니다. 하지만 모두가 무장을 한다면 '병역거부자의 낙원'이 아니게 되겠죠.
둘째로 더 두꺼운 나무껍질, 더 큰 턱을 만들었을 때 얻을 수 있는 진화적 우위를 박탈하는 방법이 있습니다. 만약 두꺼운 나무껍질이나 큰 턱을 만드는 비용이 너무 커서 그것으로 얻을 수 있는 이익이 더 작다면(즉 죄수의 딜레마에서 배신했을때의 보상을 낮추면) 다른 노력 없이도 자연스럽게 낙원이 만들어질 수 있습니다.
그런데 아무도 무장을 안한 상태에서 약간의 무장을 한 사람들에게 손해를 줄 방법이 마땅치 않다는 점이 문제겠네요.
이래저래 병역거부자들이 원하는 낙원은 불가능한가 봅니다.
그런데, 병역거부자들의 낙원은 불가능하다 치고 위에서 예로 든 나무와 벌레들의 낙원은 정말로 불가능할까요?
만약 모든 벌레들이 지나치게 큰 턱을 가진 벌레와는 짝짓기를 하지 않는다면 어떨까요(내 자손이 큰 턱을 가지고 쉽게 번식할 수 있겠다는 이익을 포기하고 말입니다)?
마찬가지로 모든 나무들이 지나치게 두꺼운 껍질을 가진 나무와는 꽃가루를 교환하지 않는다면 어떨까요(마찬가지로 내 자손들이 두꺼운 껍질을 가지고 오래 살 수 있겠다는 이익을 포기하구요)?
만약 그렇게 한다면 큰 턱과 두꺼운 껍질을 가진 '배신자'들은, 자신은 이익일 수 있으나 자손을 만들지 못하기에 도태되어버리고 지상낙원이 유지될 수 있겠군요.
물론 이 경우에는 '내 이익을 포기하고서라도 이 지상낙원을 유지하자'는 공감대가 모든 벌레들, 그리고 모든 나무들에게 퍼져있어야겠지만 말입니다.
현실에서도 '민주주의를 유지하자'는 공감대가 전 국민들에게 퍼져 있고 전 국민들이 민주주의를 유지하기 위해 자신의 이익을 약간 포기할 수 있어야 민주주의를 유지할 수 있습니다. 투표를 하기 위해 몇시간 늦게 애인과 만난다거나 몇시간동안만 온라인게임에서의 레벨업을 멈춘다든가 하는 식으로 말입니다.
GA - 장사꾼여행문제(TSP) [2] - 유전자 초기화, 재생산
2. 유전자 초기화
일반적으로 유전자를 초기화하기 위해서는 유전자의 각 비트에 랜덤값을 넣으면 되지만, 이 경우에는 앞에서 말한 유전자의 제약 때문에 무조건 랜덤값을 넣을 수는 없습니다. 만약 도시 10개짜리 보기에서 유전자에 랜덤값을 넣어 5042852301란 유전자를 만들었다면, 이 유전자는 0번, 2번, 5번 도시는 두번씩, 6번, 7번, 9번 도시는 방문하지 않는 잘못된 유전자가 만들어집니다.
그러므로 이 경우에는 카드섞기 방법으로 초기화를 해야 합니다.
procedure InitGene(Gene gene)
.. // 0~149까지의 도시를 하나씩 넣음
.. for bit := 0, 150 do.. // 0~149까지의 도시를 하나씩 넣음
..... gene[bit] := bit
.. end
.. //배열을 뒤섞음
.. for bit := 0, 150 do
..... exchange := Random(0, 150)
..... temp := gene[bit]
..... gene[bit] := gene[exchange]
..... gene[exchange] := temp
.. end
end
이와 같이 하면 150개의 도시에 대해 중복이나 결실 없는 무작위순열을 얻을 수 있습니다.
3. 적응도테스트 및 적응도
적응도를 계산하는 자세한 알고리즘은 생략하겠습니다. 유전자에 그려진 도시순서대로 한바퀴 돌며 이동하는 도시와 도시 사이의 거리를 합산하면 됩니다.
다만, 이경우에는 도시사이의 거리와 적응도는 역관계입니다. 거리가 길수록 적응도가 낮아지기 때문입니다. 여기서는 단순하게 적응도 = -(거리의 총합)으로 정의했습니다. 이렇게 하면 모든 적응도는 음수가 되긴 합니다만, 룰렛법을 사용할 수 없다는 점 이외에는 아무런 차이가 없습니다. 혹시 음수적응도가 마음에 안든다면, 가장 긴 이동거리를 가진 도시를 찾아서 (가장 긴 이동거리) - (거리의 총합) 으로 해도 됩니다. 이렇게 하면 적응도가 가장 떨어지는 개체가 0, 나머지는 양수의 적응도를 가질 수 있습니다.
4. 재생산대상 선택
다음 단계는 각자의 적응도에 따라 재생산할 대상을 고를 차례입니다. 윗 항에서처럼 적응도가 0보다 작으니 룰렛법을 사용할 수는 없지만 앞에서 사용했던 재계산법이나 순위법을 사용할 수는 있습니다.
하지만 이 문제에서는 새로운 선택법 - Tournament법을 사용하겠습니다.
토너먼트법이란, 일단 0과 1 사이의 수 T를 정합니다.
재생산 대상을 선택하기 위해 먼저 두개의 개체를 랜덤하게 정합니다. 그 둘 중 적합도가 높은 것을 Shigh, 적합도가 낮은 것을 Slow라 합니다.
다시한번 0과 1 사이의 랜덤값 r을 발생시킵니다. 그리고 r이 T보다 작다면 Shigh를, r이 T보다 크다면 Slow를 선택하는 방법입니다.
말로 해서 복잡한데, 알고리즘은 다음과 같습니다.
function SelectParent(double T)
.. // 임의의 두 개체 선택 후 Shigh에 적합도가 높은것, Slow에 적합도가 낮은 것을 나누어 넣음
.. A := Random(0, 150)
.. B := Random(0, 150)
.. if Salesman[A].fitness > Salesman[B].fitness then
..... Shigh := A
..... Slow := B
.. else
..... Shigh := B
..... Slow := A
.. end
.. // 다시한번 랜덤값 만듦
.. r = Random(0.0, 1.0) // 0~1 사이의 실수형 랜덤값 얻음
.. if T > r then
..... return Salesman[Shigh]
.. else
..... return Salesman[Slow]
end
이때 T는 0.5 이상의 값을 선택해야 합니다. 만약 0.5 이하라면 오히려 적합도가 낮은 것이 선택될 확률이 커지죠.
일반적으로 T가 클수록 선택압이 높아져 빨리 수렴하는 대신 해의 품질이 떨어지는 경향이 있습니다. 반대로 T가 작다면 수렴속도가 느려지죠.
사실 토너먼트법은 그다지 선택압이 높은 방법이 아닙니다. 개체군의 크기(전체 개체군 수)를 N이라 한다면, 최고적합도를 가진 개체가 선택될 확률은 2(1/N * T)에 불과합니다.
5. Elitism
엘리트주의란, 최대 적합도를 가진 개체를 보호하는 알고리즘입니다. 일반적인 재생산 과정은 두 개체의 유전자를 섞어 새로운 유전자를 만드는 것이므로, 최대적합도의 유전자가 선택되더라도 그 유전자가 다음 세대에 그대로 복제되지는 않습니다. 앞에서의 꼬마자동차 보기에서와 같이, 영웅이 탄생하더라도 다음 대에서는 일단 사라졌다가 영웅의 부분유전자들이 어느정도 증식한 후에야 다시 나타납니다. 엘리티즘은 이러한 현상을 막기 위해 최대적합도를 가진 개체를 다음세대에 복제하는 것을 말합니다.
엘리티즘을 잘못 사용하면 계속 복제되는 엘리트가 계속 재생산대상으로 선택되어 다양성이 훼손되는 결과가 생길 수 있습니다. 하지만 이 TSP에서는 토너먼트법이 워낙 선택압이 낮은 관계로 엘리티즘을 추가했습니다.
한 세대의 개체수는 30001개로 정의했습니다. 그중 하나는 전세대의 가장 우수한 개체를 복제하고, 나머지 30000개는 토너먼트방식으로 교차와 돌연변이를 통해 만듦니다.
엘리티즘을 포함한다면 유전자 알고리즘의 순서도에서 다음 부분이 바뀌어야 합니다.
..... T := 0.9 // 이 값은 변화 가능..... declear Creature nextgeneration[GenerationNo] // 다음세대 creature를 만들 버퍼
..... store maxfitness to nextgeneration//전세대에서 최대적합도를 가진 개체를 그대로 넣음
..... while(not fill nextgeneration) do // nextgeneration이 채워질 동안 반복
........ Creature a, b
........ while 1 do........... a := SelectParent(T) // 적응도에 의해 재생산할 creature 선택
........... b := SelectParent(T) // a, b에 선택된 것의 복사본 만듦
........... if a != b then // 다른 Creature간의 유전자 혼합을 위해
.............. break........... end
........ end
........ call CrossOver(a, b) // a, b의 유전자를 섞음
........ call Mutantation(a) // a, b에 적당한 돌연변이 가함
........ call Mutantation(b)
........ store a, b to nextgeneration // a, b를 다음 세대 버퍼에 넣음
..... end
..... creature := nextgeneration // 새로 만들어진 creature들로 계속 실행
4. 재생산대상 선택
다음 단계는 각자의 적응도에 따라 재생산할 대상을 고를 차례입니다. 윗 항에서처럼 적응도가 0보다 작으니 룰렛법을 사용할 수는 없지만 앞에서 사용했던 재계산법이나 순위법을 사용할 수는 있습니다.
하지만 이 문제에서는 새로운 선택법 - Tournament법을 사용하겠습니다.
토너먼트법이란, 일단 0과 1 사이의 수 T를 정합니다.
재생산 대상을 선택하기 위해 먼저 두개의 개체를 랜덤하게 정합니다. 그 둘 중 적합도가 높은 것을 Shigh, 적합도가 낮은 것을 Slow라 합니다.
다시한번 0과 1 사이의 랜덤값 r을 발생시킵니다. 그리고 r이 T보다 작다면 Shigh를, r이 T보다 크다면 Slow를 선택하는 방법입니다.
말로 해서 복잡한데, 알고리즘은 다음과 같습니다.
function SelectParent(double T)
.. // 임의의 두 개체 선택 후 Shigh에 적합도가 높은것, Slow에 적합도가 낮은 것을 나누어 넣음
.. A := Random(0, 150)
.. B := Random(0, 150)
.. if Salesman[A].fitness > Salesman[B].fitness then
..... Shigh := A
..... Slow := B
.. else
..... Shigh := B
..... Slow := A
.. end
.. // 다시한번 랜덤값 만듦
.. r = Random(0.0, 1.0) // 0~1 사이의 실수형 랜덤값 얻음
.. if T > r then
..... return Salesman[Shigh]
.. else
..... return Salesman[Slow]
end
이때 T는 0.5 이상의 값을 선택해야 합니다. 만약 0.5 이하라면 오히려 적합도가 낮은 것이 선택될 확률이 커지죠.
일반적으로 T가 클수록 선택압이 높아져 빨리 수렴하는 대신 해의 품질이 떨어지는 경향이 있습니다. 반대로 T가 작다면 수렴속도가 느려지죠.
사실 토너먼트법은 그다지 선택압이 높은 방법이 아닙니다. 개체군의 크기(전체 개체군 수)를 N이라 한다면, 최고적합도를 가진 개체가 선택될 확률은 2(1/N * T)에 불과합니다.
| 여기서는 단순하게 2개의 개체를 선택했지만, 2n개의 개체를 선택한 후 토너먼트식 대결을 계속하여 최후의 승자를 선택하는 방법도 있습니다. |
5. Elitism
엘리트주의란, 최대 적합도를 가진 개체를 보호하는 알고리즘입니다. 일반적인 재생산 과정은 두 개체의 유전자를 섞어 새로운 유전자를 만드는 것이므로, 최대적합도의 유전자가 선택되더라도 그 유전자가 다음 세대에 그대로 복제되지는 않습니다. 앞에서의 꼬마자동차 보기에서와 같이, 영웅이 탄생하더라도 다음 대에서는 일단 사라졌다가 영웅의 부분유전자들이 어느정도 증식한 후에야 다시 나타납니다. 엘리티즘은 이러한 현상을 막기 위해 최대적합도를 가진 개체를 다음세대에 복제하는 것을 말합니다.
엘리티즘을 잘못 사용하면 계속 복제되는 엘리트가 계속 재생산대상으로 선택되어 다양성이 훼손되는 결과가 생길 수 있습니다. 하지만 이 TSP에서는 토너먼트법이 워낙 선택압이 낮은 관계로 엘리티즘을 추가했습니다.
한 세대의 개체수는 30001개로 정의했습니다. 그중 하나는 전세대의 가장 우수한 개체를 복제하고, 나머지 30000개는 토너먼트방식으로 교차와 돌연변이를 통해 만듦니다.
엘리티즘을 포함한다면 유전자 알고리즘의 순서도에서 다음 부분이 바뀌어야 합니다.
..... T := 0.9 // 이 값은 변화 가능..... declear Creature nextgeneration[GenerationNo] // 다음세대 creature를 만들 버퍼
..... store maxfitness to nextgeneration//전세대에서 최대적합도를 가진 개체를 그대로 넣음
..... while(not fill nextgeneration) do // nextgeneration이 채워질 동안 반복
........ Creature a, b
........ while 1 do........... a := SelectParent(T) // 적응도에 의해 재생산할 creature 선택
........... b := SelectParent(T) // a, b에 선택된 것의 복사본 만듦
........... if a != b then // 다른 Creature간의 유전자 혼합을 위해
.............. break........... end
........ end
........ call CrossOver(a, b) // a, b의 유전자를 섞음
........ call Mutantation(a) // a, b에 적당한 돌연변이 가함
........ call Mutantation(b)
........ store a, b to nextgeneration // a, b를 다음 세대 버퍼에 넣음
..... end
..... creature := nextgeneration // 새로 만들어진 creature들로 계속 실행
GA - 장사꾼여행문제(TSP) [1] - 유전자 설계
TSP(Travelling Salesman Problem)는 잘 알려진 대로, 여러개의 도시를 최단거리로 순회하는 방법을 찾는 대표적인 NP문제입니다. 쉽게 말하면 '다항식적으로 문제를 풀 수 없다' -> '무식하게 모든 경우의 수를 계산해서 풀어야 한다.'는 것이죠.
이 문제의 어려운 점은 도시가 늘어날수록 가능한 조합이 엄청난 속도로 증가한다는 것입니다. 이를테면 5개의 도시일 경우 5! = 120가지 조합을 계산해서 최소값을 찾으면 되지만, 10개의 도시라면 10! = 3628800가지 조합, 20개라면 20! = 2432902008176640000가지 조합을 따져야 합니다. 100개의 도시라면? 9로 시작하는 158자리 길이의 숫자만큼의 조합을 계산해야 합니다. 그야말로 '빅뱅부터 우주의 종말까지' 계산해도 끝나지 않을 계산량이죠.
그래서 이런 문제는, '최소값'을 찾는 것은 포기하고 '근사값'을 찾는 여러가지 알고리즘이 개발되어 있습니다.
여기서는 장사꾼이 최소 이동거리로 150개 도시를 지나는 문제를 유전자 알고리즘을 사용해서 근사값을 찾는 방법을 알아보겠습니다.
1. 유전자 설계
TSP를 위한 가장 간단한 유전자는 돌아다닐 도시를 차례로 나열하는 것입니다. 만약 0~9까지 10개의 도시를 이동한다면, 유전자 9421850637은 9->4->2->1->8->5->0->6->3->7->9번 도시의 순서로 돌아다닌다는 의미입니다. 그러므로 1850637942나 0637942185, 3794218506 등도 동일한 유전자라고 할 수 있습니다. 또한 반대로 도는 2497360581 역시도 동일한 유전자입니다
이렇게 만드는 유전자의 경우에는 한가지 제약이 생깁니다. 같은 도시가 둘 이상 나와서는 안된다는 것이죠. 이를테면 9421850137과 같은 유전자는 6번도시는 빠뜨리고 1번도시는 두번 방문하게 되므로 제대로된 유전자가 아닙니다.
그러므로 최초 유전자를 초기화할 때라든지 교차, 돌연변이 등 유전자에 조작을 가할 경우에는 위와 같은 제약을 어기지 않도록 조심해야 할 필요가 있습니다.
이 문제의 어려운 점은 도시가 늘어날수록 가능한 조합이 엄청난 속도로 증가한다는 것입니다. 이를테면 5개의 도시일 경우 5! = 120가지 조합을 계산해서 최소값을 찾으면 되지만, 10개의 도시라면 10! = 3628800가지 조합, 20개라면 20! = 2432902008176640000가지 조합을 따져야 합니다. 100개의 도시라면? 9로 시작하는 158자리 길이의 숫자만큼의 조합을 계산해야 합니다. 그야말로 '빅뱅부터 우주의 종말까지' 계산해도 끝나지 않을 계산량이죠.
그래서 이런 문제는, '최소값'을 찾는 것은 포기하고 '근사값'을 찾는 여러가지 알고리즘이 개발되어 있습니다.
여기서는 장사꾼이 최소 이동거리로 150개 도시를 지나는 문제를 유전자 알고리즘을 사용해서 근사값을 찾는 방법을 알아보겠습니다.
| 만약 '무식한 방법'으로 최선의 경로를 찾기 위해서는 150!개 경우의 수를 다 계산해야 합니다. 150!의 값은 다음과 같은 263자리 숫자입니다. 5713383956445854590478932865261054003189553578601126418254 83758331798291248453983931265744886753111453771078787468542 0416266625019868450446635594919592206657494259209573577892 9325357290444962472405416790722118445437122269675520000000 000000000000000000000000000000 |
1. 유전자 설계
TSP를 위한 가장 간단한 유전자는 돌아다닐 도시를 차례로 나열하는 것입니다. 만약 0~9까지 10개의 도시를 이동한다면, 유전자 9421850637은 9->4->2->1->8->5->0->6->3->7->9번 도시의 순서로 돌아다닌다는 의미입니다. 그러므로 1850637942나 0637942185, 3794218506 등도 동일한 유전자라고 할 수 있습니다. 또한 반대로 도는 2497360581 역시도 동일한 유전자입니다
| 역순유전자를 동일한 것으로 처리하기 위해서는, 모든 도시에 대해 A->B 이동시의 비용과 B->A 이동시의 비용이 동일해야 합니다. 만약 역방향으로 이동할 때의 비용이 차이난다면(바람이나 해류가 존재할 때 등) 역방향유전자를 동일한 것으로 처리할 수 없습니다. |
이렇게 만드는 유전자의 경우에는 한가지 제약이 생깁니다. 같은 도시가 둘 이상 나와서는 안된다는 것이죠. 이를테면 9421850137과 같은 유전자는 6번도시는 빠뜨리고 1번도시는 두번 방문하게 되므로 제대로된 유전자가 아닙니다.
그러므로 최초 유전자를 초기화할 때라든지 교차, 돌연변이 등 유전자에 조작을 가할 경우에는 위와 같은 제약을 어기지 않도록 조심해야 할 필요가 있습니다.
창조론 이야기 - 인구증가곡선
"현재 인구증가율의 1/4만으로 계산해도 노아시대 남은 8명이 현재의 60억으로 늘어날 수 있다. 반대로 진화론자들의 주장처럼 인간이 생긴지 2백만년이 되었다면 지금쯤 인구는 태양계를 다 채우고도 모자랄 것이다."
창조론자들의 주장입니다. 사람들이 태양계를 가득 채우지 못한 것으로 봐서 인간은 200만년전 오스트랄로피테쿠스로부터 진화된 것이 아니라 노아의 홍수 후 남은 8명이 번성한 것이라는 주장이죠. 그런데 정말로 인간이 200만년 전에 생겼다면 태양계를 가득 채워야 할까요?
일반적으로 생물의 개체변화곡선은 다음과 같습니다.
초반에는 (창조론자들의 주장대로) 지수형태로 늘어나지만 결국은 환경영향(천적, 먹이부족, 공간부족, 질병 등)에 의해 증가가 정체되는 S자곡선을 형성하죠.
여기에는 인간도 예외가 아닙니다. 다만 인간의 경우에는 여러번에 걸쳐 저 자연의 한계라는 제한을 넘어선 적이 있습니다. 하지만 곧 새로운 자연의 한계에 부딫쳐 정체상태에 들어가는 것은 마찬가지죠. 말하자면 인구의 증가곡선은 다음과 같습니다.
(그림이 좀... 클릭해서 보세요^^)
초기부터 일정한 증가율로 인구가 증가한 것이 아니라, 긴 정체구간 - 문명발달로 한계넘음 - 새로운 한계 봉착 - 긴 정체구간의 반복입니다. 지금은 과학기술의 발달로 한계가 엄청나게 높아졌기에 상당한 인구증가율을 보이는 것이죠(지금의 과학기술 속도라면 거의 한계가 없어졌다고 보는 편이 나을수도 있겠네요).
어쨋든 실제 인구증가곡선 역시 이렇습니다.
창조론자들의 주장입니다. 사람들이 태양계를 가득 채우지 못한 것으로 봐서 인간은 200만년전 오스트랄로피테쿠스로부터 진화된 것이 아니라 노아의 홍수 후 남은 8명이 번성한 것이라는 주장이죠. 그런데 정말로 인간이 200만년 전에 생겼다면 태양계를 가득 채워야 할까요?
일반적으로 생물의 개체변화곡선은 다음과 같습니다.
초반에는 (창조론자들의 주장대로) 지수형태로 늘어나지만 결국은 환경영향(천적, 먹이부족, 공간부족, 질병 등)에 의해 증가가 정체되는 S자곡선을 형성하죠.여기에는 인간도 예외가 아닙니다. 다만 인간의 경우에는 여러번에 걸쳐 저 자연의 한계라는 제한을 넘어선 적이 있습니다. 하지만 곧 새로운 자연의 한계에 부딫쳐 정체상태에 들어가는 것은 마찬가지죠. 말하자면 인구의 증가곡선은 다음과 같습니다.
(그림이 좀... 클릭해서 보세요^^)초기부터 일정한 증가율로 인구가 증가한 것이 아니라, 긴 정체구간 - 문명발달로 한계넘음 - 새로운 한계 봉착 - 긴 정체구간의 반복입니다. 지금은 과학기술의 발달로 한계가 엄청나게 높아졌기에 상당한 인구증가율을 보이는 것이죠(지금의 과학기술 속도라면 거의 한계가 없어졌다고 보는 편이 나을수도 있겠네요).
어쨋든 실제 인구증가곡선 역시 이렇습니다.
참고로 통계에 따르면 서기 1년을 전후한 세계의 인구는 2억5천만이었습니다. 그것이 5억이 된 것은 16세기에 들어서였죠.
이것으로 인구증가율을 계산해보면
최소한 성경시대(AD 1세기 전후)의 인구증가율은 0.04%였습니다. 더구나 이것은 1세기~16세기의 평균증가율이었으므로 성경시대의 인구증가율은 0.04%보다 훨씬 적다고 봐야 하겠죠.
참고
이것으로 인구증가율을 계산해보면
2.5억*(1+x)1600 = 5억 (x=인구증가율)
(1+x)1600 = 5억 / 2.5억 = 2
(1+x) = 2(1/1600) ≒ 1.0004
x = 0.0004 = 0.04%
(1+x)1600 = 5억 / 2.5억 = 2
(1+x) = 2(1/1600) ≒ 1.0004
x = 0.0004 = 0.04%
최소한 성경시대(AD 1세기 전후)의 인구증가율은 0.04%였습니다. 더구나 이것은 1세기~16세기의 평균증가율이었으므로 성경시대의 인구증가율은 0.04%보다 훨씬 적다고 봐야 하겠죠.
참고
노아의 방주 이후 남녀 네 쌍을 시작기준으로 인구증가율을 매년 0.5%로 가정하면 N년이 흐른 후...왜, 0.5%라고 하나면, 대홍수 리셋 후의 인구증가가 현재와 같으려면 그 수치밖에 없음(기독교측 주장임) 기자피라미드는 기원전 2490년에 건설되었다. -> 성서적 해석으로 당시 전세계 인구 13명 // 기원전 1446년 모세가 60만 장정을 이끌고 탈출 -> 성서적 해석으로 당시 전세계 인구 726명이 됨..
창조론 이야기 - 엔트로피(Entropy)
창조론자들의 주장들 중 하나가 '진화는 열역학 제 2 법칙에 위배된다'는 것이죠. 모든 것은 무질서한 방향으로 진행되는데, 진화는 질서가 생기는 현상이라는 것입니다.
하지만 창조론자들이 말하는 열역학 제 2 법칙의 정확한 정의는 '고립계(isolated system)의 전체 엔트로피는 증가한다'는 것입니다. 심지어 고립계라고 해도 그 안에서 국소적인 엔트로피감소는 충분히 일어날 수 있습니다. 오른쪽 그림 전체가 고립계라고 해도 A부분은 B부분과 물질 및 에너지를 교환하고 있는 열린계(opened system)이기 때문이죠. 그 때문에 A와 B를 포함한 전체의 엔트로피는 증가하겠지만 A만의 엔트로피는 감소할 수 있습니다.
지구는 닫힌계가 아닙니다. 태양으로부터 계속 에너지를 받고, 우주먼지라는 형태로 물질도 받아들이고 있습니다. 바로 옆에 '태양'이라고 불리는, 엄청나게 우주의 엔트로피를 증가시키는 존재가 있는 이상 지구에서는 엔트로피의 감소가 일어나는 것은 충분히 가능합니다. 그러므로 지구에서 일어나는 진화가 에너지 제 2 법칙을 위반하는 것은 아닙니다.
그렇다면 정말로 지구에서 엔트로피가 감소하는 현상이 일어날까요? 물론입니다.
매년 내리는 눈송이를 본다면, 무질서하던 수증기들이 6각형의 질서있는 결정을 만듧니다. 다이아몬드도 무질서하던 탄소원자들이 정사면체의 결정을 만듦니다. 소금이나 염화칼슘 모든 결정들이 엔트로피가 감소하는 증거입니다.
하지만 창조론자들이 말하는 열역학 제 2 법칙의 정확한 정의는 '고립계(isolated system)의 전체 엔트로피는 증가한다'는 것입니다. 심지어 고립계라고 해도 그 안에서 국소적인 엔트로피감소는 충분히 일어날 수 있습니다. 오른쪽 그림 전체가 고립계라고 해도 A부분은 B부분과 물질 및 에너지를 교환하고 있는 열린계(opened system)이기 때문이죠. 그 때문에 A와 B를 포함한 전체의 엔트로피는 증가하겠지만 A만의 엔트로피는 감소할 수 있습니다.
지구는 닫힌계가 아닙니다. 태양으로부터 계속 에너지를 받고, 우주먼지라는 형태로 물질도 받아들이고 있습니다. 바로 옆에 '태양'이라고 불리는, 엄청나게 우주의 엔트로피를 증가시키는 존재가 있는 이상 지구에서는 엔트로피의 감소가 일어나는 것은 충분히 가능합니다. 그러므로 지구에서 일어나는 진화가 에너지 제 2 법칙을 위반하는 것은 아닙니다.
그렇다면 정말로 지구에서 엔트로피가 감소하는 현상이 일어날까요? 물론입니다.
매년 내리는 눈송이를 본다면, 무질서하던 수증기들이 6각형의 질서있는 결정을 만듧니다. 다이아몬드도 무질서하던 탄소원자들이 정사면체의 결정을 만듦니다. 소금이나 염화칼슘 모든 결정들이 엔트로피가 감소하는 증거입니다.
피드 구독하기:
글 (Atom)