nlogn's log :: 천천히 달리기

 다음 [그림 1]은 유전자 알고리즘의 일반적인 수행과정을 나타낸다.

[그림 1] 유전자 알고리즘 수행과정

유전자 표현(Gene Representation)은 유전자 알고리즘을 구축하는 첫단계로 문제의 잠재해를 유전적 표현 즉, 개체로 표현하여야 한다. 이 유전적 표현은 유전자 알고리즘의  다른 절차(적합도 평가와 유전연산자 등)에 영향을 주므로 문제의 특성을 잘 반영할 수 있도록 하고, 문제에 따라 표현은 다를 수 있다. 유전자 알고리즘은 개체들로 구성된 모집단을 바탕으로 해를 찾아 나가기 때문에 초기에 모집단이 생성되어야 한다. 생성 방법은 임의생성 방법이 흔히 사용된다.

적합도(Fitness)는 유전자 개체가 갖고 있는 피부색, 저항력 등과 같은 특성을 나타내는 값으로서 이것은 환경에서 생존할 수 있는 즉, 적응할 수 있는 정도를  나타내는 값이다. 개체가 주어진 어떤 환경에서 생존하기 위해서는 최적의 적합도를 가져야 하며, 이러한 최적값은 일반적인 최적화문제의 목적함수에서와 같이 목적함수인 적합도 함수를 설정하여 이것을 최적화함으로써 얻을 수  있다. 예를 들면, 임의의 염색체(스트링)의 유전자값이 주어질 때, 이 값들을 변수로 한 적합도 함수를 설정하여 최적화시킴으로써 최적의 적합도를 구한다. 그러나 주어진 특정한 값을 갖는 염색체가 원하는 수준의 적합도를 충족시키지 못하면 유전자 변형을 통하여 염색체를 변화시켜 원하는 최적 적합도가 생성될 때까지 반복한다.

선별(Selection)은 적자생존의 자연법칙에 기초하여 환경에 대한 적합도를 평가하여 현 세대의 모집단으로부터 다음 세대를 만들 개체를 선택하는 과정이다. 모집단의 다양성과 선별압력이 조화를 이룰 수 있어야 하고, 강한 선별압력(적합도가 높은 우수개체가 열성개체보다 생존확률이 아주 높은 것)은 모집단의  개체들을 조기에 수렴시키나 해의 다양성이 떨어지며, 약한 선별압력은 해의 다양성은 유지되나 효율적으로 해를 탐색하지 못한다.

유전 연산자(Operator)는 교차(crossover)와 돌연변이(mutation) 연산자로 나누어 진다. 교차는 두 부모(parent)가 갖는 유전자를 조합하여 자손(offspring)을 생성하는 과정이다. 교차시 부모의 좋은 형질(유전자)이 가능한 파괴되지 않고 자손에 상속될 수 있어야 한다. 돌연변이는 한 개체에서 아주 작은 수의 유전자를  임의로 변화시키는 과정이며 해를 다양하게 탐색할 수 있도록 한다.

세대(Generation)는 알고리즘에서 유전연산의 횟수이며, 유전 파라미터(Parameter)로는 모집단의   크기(pop-size), 교차율, 돌연변이율, 종료조건 등이 있다. 모집단의 크기는  모집단을 이루는 개체수를 의미하며, 교차율은 각 개체가 교차될 확률, 돌연변이율은 각 유전자가 돌연변이 될 확률을 나타낸다. 알고리즘 종료조건으로는 (1) 진행된 세대수 또는 생성된 개체수, (2) 해의 개선의 이루어지지 않고   진행된 세대수 또는 생성된 개체수, (3) 계산소요시간 등이 사용된다. 다음 <표 1>과 [그림 2]는 알고리즘의 세부 절차 및 흐름도를 나타낸다.

<표 1> 유전자 알고리즘의 절차

[그림 2] 유전자 알고리즘 흐름도

 배신과 협력의 게임(1라운드의 죄수의 딜레마)

물주(게임 진행자) 한 명과 두 사람이 게임을 한다. 게임을 하는 두 사람의 손에는 '협력'과 '배신'의 카드 2장이 있으며 단 1라운드만 진행이 된다. 카드의 조합은 아래 표의 네 가지가 되며, 각각의 경우에서 이득과 손해는 아래와 같다.

가령 위의 예에서 상호 협력의 카드를 제출할 때는 상호 협력에 대한 보상으로 물주로부터 300달러를 받는 것이다. 이 때 배신에 대한 유혹료는 상호 협력의 보수보다 높아야 하고, 상호 협력의 보수는 상호 배신의 벌금보다는 좋아야 한다. 이 밖에 여러 가지 설정이 있지만 생략한다.

그럼 왜 '딜레마'일까? 누구든 낼 수 있는 카드는 '협력'과 '배신'이라는 카드 2장 밖에 없다. 만일 A가 '배신'을 냈다면 B는 최선의 카드로 '배신'을 내야 할 것이다. 만일 '협력'의 카드를 낸다면 B는 100 달러를 게임 진행자에게 줘야 한다. A가 '협력'의 카드를 냈을 경우에도 당신이 얻을 수 있는 최대의 이득은 '배신'의 카드를 내는 것이고 그 때 유혹료로 500달러를 얻을 것이다.

결론은 타인이 어느 카드를 내든 상관없이 당신의 최선 행동은 '항상' 배신이라는 것이다. 그러므로 두 사람의 이성적인 경기자가 만나면 모두 배신하여 같이 벌금 또는 운 좋으면 유혹료를 받게 될 것으로 끝난다. 두 사람 모두 만일 쌍방이 '협력'만을 낸다면 상호 협력으로 비교적 높은 보수를 받을 것을 확실히 알고 있다. 하지만 '배신'의 카드를 내는 것이 최선의 행동이라는 것이다. 쌍방이 서로 연락하거나 정보를 주고 받을 수 있다면, 서로 연락해서 '협력'의 카드를 제출하겠지만, 그렇지 않을 경우에는 '배신'을 하는 것이 합리적인 게임 진행이 될 것이다. 그러니 딜레마인 것이다.

딜레마 (dilemma) ①(논리학) ＝양도 논법(兩刀論法). 
②선택해야 하는 길은 2개뿐인데 그 어느 쪽도 바람직하지 못한 결과를 초래하는 상황.

 반복 죄수의 딜레마

'죄수'란 하나의 특별한 상징적인 예에서 유래한다. 이 경우는 돈이 아닌 죄수의 형기이다. 가령 A군과 B군이 자신들이 저지른 범죄 때문에 공범 혐의로 투옥되어 있다. 그 죄수들은 각각 독방 속에서 공범자에 대한 불리한 증언을 함으로써 동료를 배신하도록 유혹당했다. 처분은 두 사람의 죄수가 어떻게 하는가에 따라 결정되며, 어느 쪽도 상대가 어떻게 했는지 모른다. 만일 각각이 배신하면 양자 모두 죄가 인정되나 증거를 제공한 점으로 약간의 신용을 얻어 어느 정도 경감된 형기, 즉 상호 배신의 벌을 받게 된다. 만일 양자가 협력하여 증언을 거부하면 유죄가 될 충분한 증거가 없으므로 보다 경미한 죄로 짧은 형기, 즉 상호 협력의 보수를 받는다. '지불'이 돈이 아니라 형기였지만 이 게임을 기본적 특징이 보전되어 있는 것을 느낄 것이다.

1라운드의 게임에서는 상호 배신으로 끝나게 될 운명이 되고 만다. 그러나 그것이 '반복'된다면 그 때에도 '배신'을 할 것인지 생각해보자. 반복 게임은 동일한 경기자에 의해 제한없이 반복되어 행해질 뿐만 아니라 또한 두 사람은 서로 바라보고 있으며 그 사이에는 게임 진행자(판사)가 앉아 있다. 두 사람은 두 카드의 어느 한쪽을 냄으로써 승부를 내고 게임 진행자(판사)는 먼저 제시한 규칙에 따라 형기를 결정한다. 이제는 1 라운드의 게임으로 끝나는 대신에 우리는 또 다시 카드를 집어서 다음의 승부에 대비한다. ( 이와 같은 반복은 두 사람이 반복적으로 공범자로 잡힌다고 가정하면 간단히 설명된다. 단 서로의 연락은 되지 않는다.) 몇 번 승부를 계속하는 사이에 두 사람에게는 신용, 또는 불신이 쌓여 협력 또는 배신을 할 수 있는 기회가 주어진다. 제한없이 긴 게임에서 중요한 점은 서로가 손해를 볼 것 없이 쌍방이 협력의 보수를 받을 수가 있다는 것이다.

 전략

과연 위와 같은 게임을 할 경우 어떤 전략을 가진 자가 장기적으로 승리를 거둘 수 있을 것인가를 생각해보자. 몇 개의 교묘한 전략이 가능하나 승리를 거든 전략은 놀랍게도 가장 단순하고 표현적으로는 모든 것 중에서 가장 교묘함이 부족했다. 그것은 '당하면 갚는다(tit for tat)'라는 전략으로 불렸고 최초의 카드는 협력으로 시작하고 그 이후는 단순히 바로 전에 상대가 낸 카드를 흉내내는 것뿐이다. 즉, 상대가 배신을 하면 내가 배신을 하는 것이다.

다음은 '소박한 시험꾼(naive prober)'으로 '당하면 갚는다'와 같으나 10회중에 1회는 함부로 이유없이 배신하여 유혹료로서 높은 득점을 기대하는 전략이다. 그리고 '원한파'는 한번 상대방이 배신하면 끝까지 배신하는 전략이고, '항상 배신은 항상 배신만 하는 전략이다. 그 밖에 수많은 전략들이 생겨날 수 있어 이 게임의 다양성은 증가된다.

다음은 대표적 전략들을 간략히 설명한 표이다.

이러한 게임을 '액셀로드'라는 사람이 전략을 하나의 공통 프로그램 언어로 번역하여 대형 컴퓨터로 서로 대전시켰다. 각각의 전략은 다른 모든 전략과 순차적으로 짝지어져서 반복 죄수의 딜레마 게임을 하는 것이다.

액셀로드가 인정하고 있는 가장 중요한 범주는 '마음씨 좋은(nice)'이다. 마음씨 좋은 전략은 최초로 배신하는 일이 결코 없는 것으로 정의된다. '당하면 갚는다 (tit for tat)' 가 그 일례이다. 소박한 시험꾼은 때때로 배신을 하므로 간악한 전략이다. 토너먼트에 참가한 15개의 전략 중 득점이 높은 쪽부터 상위 8위까지 모두 8개의 '마음씨 좋은(nice)' 전략이 차지하고 있다는 사실이 의미 깊다고 할 수 있다.

 관용

전략이란 것은 보복하는 일은 있으나 단기의 기억밖에 없다. 그것은 오래된 나쁜 일을 바로 잊어버린다. '당하면 갚는다(tit for tat)'는 하나의 관용 전략이다. 배신자에 대해 즉시 한 때 보복으로 갚고 그 후에는 과거를 씻듯이 잊는다. 하지만 원한파는 절대로 용서하지 않는다. 그 기억은 게임의 전기간을 통해 지속된다. 한 번이라도 자기에게 배신한 적이 있는 상대에 대한 원한을 결코 잊지 않는다. 원한파와 같은 전략이 프리드만(friedman)이라는 호칭으로 대전이 되었지만 게임 성적이 별로 좋지 않다.

우리는 승리하는 전략에 두 가지 특징이 있다는 것을 상정할 수 있다. 즉 '마음씨 좋기'와 관용함이다. 다시 말해, 처음부터 배신하지 않는 전략과 단기의 기억밖에 없는 관용 전략이 그것이다. 거의 유토피아적인 경향의 이 결론은 '마음씨 좋은 사람이 성공한다' 라는 문구와 비슷한 의미를 담고 있다. 윤리가 논리로써 이끌어지는 순간이다.

위와 같은 전략은 평균적이고 반복적인 전략끼리의 대전이며, 여기가 중요한 사실은 그러한 전략의 성공은 어떤 전략이 서로 대전하는가에 달려 있다라는 것이다. 다시 말해 다른 모든 전략이 '항상 배신'이면 '마음씨 좋은' 전략이 당하기만 한다. 그러므로 '최초 구성이 어떤 전략으로 구성되었는가' 라는 요소와 전략들의 구성 비율도 각각의 전략에 대한 성공, 실패에 대한 영향을 미친다.

 ESS(Evolutionarily stable strategy, ESS)

위에서 언급한 것처럼 각 전략의 순위는 어떤 전략이 제출되었는가에 의존한다. 가령 대부분의 전략이 간악한 것이었다면 '당하는 갚는다'는 이기지 못 했을 것이다. 바꾸어 말하면 전략의 순위가 인간의 불안정하고 자의적인 것에 의존하고 있다. ( 인간이 어떤 전략을 대전시키느냐에 따라 전략의 순위가 결정될 수 있다.) 이 자의성을 어떻게 하면 줄일 수 있을 것인가? 그것은 ESS로 해결될 수 있다. ESS라는 메이나드-스미스가 제창하고 있는 중요한 개념은 '진화적으로 안정된 전략'이라는 불리는 것이며, 여기서 전략이라는 것은 미리 프로그램되어 있는 행동 방침이다. 쉽게 말하면, 정확치는 않지만 각각의 전략을 이루는 제 1세대를 만들고, 유전자 알고리즘으로 세대를 거쳐가면서 최종적으로 살아남는 전략들이 ESS가 될 수 있다.

액셀로드는 63개의 전략을 취하여 그것을 또 다시 컴퓨터에 입력해서 그것들을 제 1세대로 만들었다. 따라서 제 1세대의 풍토는 63개의 모두의 전략을 균등히 대표하는 것으로 되어 있었다. 제 1세대의 끝에 각 전략의 승자는 돈이나 득점이 아닌 그의 부모와 동일한 전략을 취하는 후손의 수로 지불된다. 세대가 진행함에 따라 어떤 전략은 수가 적어져서 최종적으로는 절멸한다. 다른 전략은 점점 수가 많아진다. 따라서 그 비율이 변함에 따라 전략들의 대전이 일어나는 풍토(전략들의 구성 비율)도 변한 것이다. 대전의 결과는 몇 개의 전략은 최초부터 절멸로 향하고 대부분은 200세대에 가서야 절멸한다. 재미난 사실은 해링턴(Harrington)이라 불리는 간악한 전략은 최초의 150세대쯤 급격하게 상승했다. 그것은 '두 발에 한발 갚기' 등의 연약한 상대가 주위에 있는 한은 그들을 착취했다. 그 후 연약한 상대가 절멸 당하게 되면 '해링턴(Harrington)'은 그들만의 포획물이 없게 되어 그들의 뒤를 쫓아 절멸하게 됐다. 싸움터는 '당하면 갚는다'처럼 마음씨 좋은 전략의 독무대로 됐다.

진화가 거듭되어 모든 간악한 전략이 절멸에 임박하게 되면 아무리 마음씨 좋은 다른(두 발에 한발 갚기) 전략도 '당하면 갚는다(tit for tat)'와 서로 상호간에 구별하는 방법이 없어지게 된다. 왜냐하면 그것들은 모두 마음씨가 좋기 때문에 서로 협력의 카드를 내놓기 때문이다. 이런 최종적인 전략들의 구성은 ESS와 닮았지만 엄밀하게는 ESS가 아니라는 것이다. 어떤 전략이 ESS가 되려면, 그것이 희소한 돌연변이의 전략에 변경되어서는 안 된다는 것을 생각해 주기 바란다.

프로그램적인 ESS는 마음씨 좋은 전략이 우세를 점하지만, 거의 무조건인 마음씨 좋은 전략( 두발에 한발 갚기, 세발에 한발 갚기 등) 이 숨어 있게 되어, 간악한 전략의 침입에 쉽게 변할 수 있기 때문에 액설로드는 다음과 같은 결론을 내린다.

"아마도 조금 간악한 전략과 마음씨 좋은 매우 관용한 전략과 
그리고 당하면 갚는다(tit for tat)와의 전략들의 혼합으로 ESS가 구성된다"

그런 전략들이 구성된 ESS는 어떤 다른 전략이 들어와도 ESS가 쉽게 변하지 않음을 알 수 있다. 다시 말해 전략들의 진화가 안정화되었다고 볼 수 있다. 최종적인 진화 상태임을 암시한다.

이것이 인간 생활에 흔한 양상을 반영하는 거울임을 알 수 있다. 즉, 어느 정도의 간악한 사람과 '당하면 갚는다(tit for tat)'와 같은 전략을 가진 사람들이 이 세상에 우세한 이유도 죄수의 딜레마라는 게임에서 유추할 수 있다.여기서 제 나름대로의 재미난 결론은 가장 이상적인 전략은 '당하면 갚는다(tit for tat)'이라는 전략이다. 한번 상대방이 배신을 하면 바로 배신을 하는 전략이 우리의 인생을 최소의 실패율을 가져다 줄 수 있는 전략이라는 것이다. 두 번을 참아서도 안 된다. 오직 한번만이 참을 뿐이다. 대신 관용을 유지해야 한다. 상대방의 잘못은 단기 기억으로 잊어버린다. 이제부터는 이것을 내 인생 전략으로 삼을까 싶다. ㅋㅋㅋ

참고자료 : 이기적 유전자, 리처드 도킨스 지음, 홍영남 옮김, 을유 문화사, 89-324-6025-6