유전자 알고리즘

유전자 알고리즘 - Genetic Algorithms

 

 개요 ( What are Genetic Algorithms? )

유전자 알고리즘(Genetic Algorithm, GA)은 적자 생존과 유전의 메카니즘을 바탕으로 하는 탐색 알고리즘이다. 다시 말해 주어진 환경에 잘 적응하는 유전자만을 selection)하고 교배(crossover)하고 때에 따라서는 돌연변이(mutation)도 하며 다음 세대에 우수한 유전 형질이 전달(reproduction)되게 된다. 따라서 진화(evolution)가 거듭될수록 주어진 환경에 더 적합한 유전자들만이 남아있게 될 것이다.

유전자 알고리즘은 미시간대학의 홀랜드(John Holland)에 의해 탄생하였으며. 당시 연구원들의 연구 목표는

[1] 자연시스템의 적응적 과정을 추상화시키며 철저하게 분석하여,
[2] 그러한 시스템을 소프트웨어적으로 디자인하는 것이었다.

유전자 알고리즘(GA)은 그러한 배경에서 만들어졌으며, 근본적으로 다른 탐색이나 최적화 알고리즘과는 세 가지 정도가 다르다.

[1] GA는 하나의 개체(변수 등)가 아닌 개체들의 군(pool) 단위로 탐색한다.
[2] GA는 적합성 함수(fitness function)를 사용한다.
[3] GA는 확률적인 변이 규칙을 사용한다.

간단한 예를 들어보자. f(x) = x2[0 ≤ x ≤ 31] 이라는 환경이 있으며, 환경에 살아가는 개체(유전자)가 x인 셈이다. 그리고 환경에 잘 적응하는 정도를 함수값으로 정의하자. 그러므로 x = 0이라는 개체보다 x = 4라는 개체가 f(x) = x2[0 ≤ x ≤ 4]라는 환경에서 더 잘 적응하는 것이다.

환경	: f(x) = x2[0 ≤ x ≤ 31]
개체	: 0 ≤ x ≤ 31
적합성(fitness)	: f(x)

01101
11000
01000
10011

위의 네 개체가 오손도손(^_^) 살고 있는 군(집단)에서 과연 f(x) = x2이라는 환경에서 누가 더 잘 적응할 것으로 생각되는가? 위의 이진수를 십진수로 바꾸어 생각하면 쉽게 알 수 있다. 위의 예에서 01000은 살기 어렵고, 11000은 그나마 가장 잘 적응할 것이다. 그러므로 다음 세대에서는 01000은 도태를 하고, 11000은 자손을 생산하게 된다. 이와 같은 과정을 거친 먼 훗날의 개체는 바로 11111이라는 개체가 탄생할 것이고, 이 넘(^_^)이 바로 주어진 환경을 지배할 것이다.

11111
11111
11111
11111

군(pool)이 위와 같은 개체(gene)로 구성되었을 때 '환경에 적응하였다'라고 말한다. 또는 '해를 찾았다'라고 말하기도 한다. 이와 같이 유전자 알고리즘은 자연의 적자 생존 원칙에 기반을 하고 있는 탐색 알고리즘이다. 다음 내용에서는 유전자 알고리즘의 단계별 과정들인 재생산(reproduction), 교배(crossover), 돌연변이(mutation)들을 알아보겠다.
--------------------

유전자 알고리즘에서의 개체 재생산

유전자 알고리즘은 기본적으로 세 가지의 연산자(operator)로 구성된다. [1] 재생산(reproduction) [2] 교배(Crossover) [3] 돌연변이(Mutation) 이번 내용에서는 재생산이라는 연산자(operator)에 대해 알아보자. 근데 operator를 연산자라고 번역하니까 좀 이상하군요.(^_^)  개요 유전자 알고리즘에서 재생산(reproduction)이란 적합함수(fitness function)에 따라서 개체들을 복사하는 과정이다. 쉽게 말해서 개체들이 속해 있는 군에서 잘난 넘(nom?)은 다음 세대를 더 많이 생산할 수 있는 기회를 주고, 물론 못난 놈은 자기와 닮은 개체를 생산할 수가 없어 그 형질이 다음 세대에 전달되지 않는다. 그렇다면 과연, 우수 형질의 개체를 어느 정도 개체를 생산할 수 있고, 열등 형질은 무조건 없어져야 하는가? 그렇지만은 않다. 왜냐면 열등 형질도 부분적으로는 우수 형질의 기질을 가지고 있기 때문이다. 따라서 유전자 알고리즘에서는 어떤 개체에게 어느 정도의 우수성을 부여하고 어떤 방식으로 재생산이 행해지느냐는 중요한 요소이다. 무작정 우수 형질의 개체를 재생산하다보면 전체 해(global point)를 찾지 못할 가능성도 커진다. 결론적으로 우수 형질의 개체 생산과 열등 형질의 개체 생산비율을 적절히 설정할 필요가 있다. 이를 실현하는 데 있어 유전자 알고리즘에서 기본적으로 roulette wheel이라는 확률개념을 사용한다. 지금은 많이 사라졌지만, roulette wheel을 돌려서 뽑기하는 장사를 기억할 것이다. 원판(roulette wheel을 원판이라 번역, ^_^)에서 할당된 영역이 넓으면 그만큼 걸릴 확률이 많은 것이다. 우수 형질은 그만큼 원판에서의 면적 할당이 넓게 함으로써 다음 세대의 개체 생산의 가능성을 크게 하는 것이다. 아래 그림을 보면 이해가 될 것이다. 군(pool)에 개체들이 있고, 그 개체들은 우수 정도에 따라 영역을 할당받는다. 우수 개체는 아래 그림에서 (2) 영역을 할당받을 것이고, 열등 형질은 (1) 영역을 할당받을 것이다. 이제 재생산의 남은 과정은 원판을 돌리고 화살만 쏘면 되는 것이다. 걸리면 살아남는 개체가 되는 것이다. 냉혹함이 숨겨져 있는 알고리즘이다. 그림. 유전자 알고리즘에서의 재생산(Reproduction)  예제(example) f(x) = x2이라는 환경에서 살아가는 개체가 시간 t일 때 01101 11000 01000 10011 와 같이 네 개체만이 있다면 개체들의 적합도(fitness)와 전체에 대한 우수성의 비율을 아래 표에 나타내었다. No. 개체 Fitness % of Total 1 01101 169 14.4 2 11000 576 49.2 3 01000 64 5.5 4 10011 361 30.9 Total   1170 100.0 표. f(x) = x2에서의 개체와 적합함수(fitness function) 원판위에 적합함수(fitness function)에 따라 다음 세대에서의 생존 가능성을 그리면 앞의 원판 그림이다. No. 2라는 개체가 f(x) = x2이라는 환경에서는 가장 잘 적응되고 원판에서도 가장 넓은 영역을 차지하고 있다. 따라서 다음 세대를 재생산(reproduction) 하기 위해 화살을 네 번 쏜다면, No. 2라는 개체는 살아남아서 다음 단계인 교배(crossover)를 할 가능성이 가장 높다. 이상으로 roulette wheel이라는 확률 기반의 재생산(reporduction) 방법에 대해 알아보았다. 다음은 교배(crossover)에 대해 알아볼 차례다. 교배는 실제 재생산된 개체들끼리의 연산으로 좀 더 나은 개체를 발생시키고자 하는 데 목적이 있다. 유전자 알고리즘은 재생산(reproduction), 교배(crossover), 돌연변이(mutation)에 대해서 확실히 알면 그 다음은 그것들의 응용이다. -------------------------------------------------- 교배와 돌연변이    교배(crossover) 개체의 진화는 물론 돌연변이에 의해, 확률적으로 적지만, 발생할 수도 있지만, 주로 개체들끼리의 교배(crossover)에 의해 발생한다. 교배(crossover) 연산자는 개체들끼리 유전자 배열을 섞는 과정이다. 자연 환경에 대한 인간들의 적응도 근본적으로는 교배, 즉 성 관계를 통하여 이루어졌다. 유전자 알고리즘(GA)에서 교배는 두 단계로 구성된다. [1] 교배대상의 개체(들)를 선택한다. ( 하나 혹은 2개 이상의 개체 ) [2] 유전자 배열 중의 임의의 위치 k를 선택하고, 개체들간의 유전자 배열을 바꾼다.(swap) 아래 그림은 두 개체(01101, 11001)간의 교배를 나타낸 것이다. 너무나도 간단하다! 하지만 교배 연산을 통해 개체군(pool)이 세대가 지날수록 환경에 적응하는 개체들이 늘어나게 된다. 그림. 교배(crossover) 과정  돌연변이(mutation) 교배는 개체군 내에서의 개체 진화에 한계가 존재한다. 다시 말해, 주어진 환경에 어느 한계까지는 진화하여 적응할 수 있지만, 개체군내의 개체의 유전자 schema를 극복할 수 없다. 예를 들어 11110 11100 두 개체가 아무리 교배를 한다하더라도 11111이라는 개체는 생길 수가 없다. 이를 보완하기 위해 돌연변이(mutation) 연산자를 사용한다. 돌연변이(mutation)은 유전자 배열 중의 유전자(gene)를 바꾸는 연산자이다. 하지만 돌연변이가 발생하는 확률을 너무 높게 설정하면 무작위 탐색이 될 수 있기에, 적절한 돌연변이의 발생이 요구된다. ( 일반적으로, 돌연변이 발생 확률 = 0.01 ) 그림. 돌연변이(mutation) 이상으로 유전자 알고리즘의 기본적인 연산자에 대하여 알아보았다. 재생산(reproduction), 교배(crossover), 돌연변이(mutation)이라는 기본적인 연산자를 이용하여 개체군 내에서의 개체를 변화시켜며, 또 적응해가도록 하며, 그러한 연산자는 다윈의 자연 선택(natural selection)의 원칙을 그 모델로 삼고 있다. 유전자 알고리즘에서의 스키마(schema) 이론 이해    스키마 이론(schema theorem) 유전자 알고리즘의 세 연산자(operator)인 재생산(reproduction), 교배(crossover), 돌연변이(mutation)은 너무나 간단하다. 결국 n개의 문자열(strings, 개체)로 구성되어 있는 개체군(population)에서 적합 함수(fitness function)에 따라 몇 개의 개체를 선택하고, 몇 개의 부분 문자열을 바꿈으로써 교배를 시키고, 확률에 따라서 돌연변이를 발생함으로써 환경에 진화하는 것이다. 간단하지만 수학적 근거가 없었다면 끝났다면, 아마도 유전자 알고리즘이 이처럼 유용한 알고리즘이 되지는 못하였을 것이다. 위의 방법론은 누구나가 제시할 수 있지만, 수학적 근거를 제시하기는 쉽지만은 않다. 이런 점에서 스키마 이론은 유전자 알고리즘의 수학적 배경을 제시한다는 점에서 유전자 알고리즘의 근본되는 이론이라 할 수 있다. 원서(참조)에서는 스키마 이론을 'The fundamental theorem'이라고 말하고 있다. 먼저 스키마가 무엇인지를 언급하고, 그 스키마가 환경에 적응하는 정도를 제시함으로써, 그 스키마에 속하는 개체들의 적응력(?)도 그 스키마의 적응력과 결국 같은 것이기 때문에, 유전자 알고리즘이 무작위 탐색과는 다르다라는 것을 말하고자 한다.  스키마타(schemata) f(x) = x2이라는 환경에서 아래와 같은 개체군이 존재한다고 가정하자. 01101 11000 01000 10011 이 예제에서는 0**** 보다는 1**** (* = 0 or 1)의 형태를 띠는 개체들이 더 높은 적합 함수값을 가진다. 일반적으로 환경을 모르더라도 개체들의 유전자 구성에 따른 일정한 법칙이나 배열규칙에 따라 적합 함수값이 비슷한 값들을 알 수 있다. 다시 말해, 개체의 특정한 유전자 배열 규칙이 개체의 우수성을 지니게 하는 하는 것이다. 스키마는 0****, 또는 1****처럼 표현한 것을 말하고 스키마의 복수가 스키마타이다. 0**** = 01101, 01000 1**** = 11000, 10011 을 각각 표현하는 것이다. 예제처럼개체군내에서 부분 개체 집단의 일반적 적합성을 표현하는 데 있어 *(0 or 1) 이란 기호를 사용하여 스키마타(schemata)를 사용한다. 스키마타의 적합 함수값은 그 스키마타로 표현되는 개체들의 평균 적합함수값으로 표현된다. 개체군에 대단히 많은 개체들이 존재한다고 가정하자. 각각의 개체들은 유전자 알고리즘의 연산자에 따라 선택되고, 교배되고, 돌연변이 하면서 적응을 하겠지만, 겉으로 드러나지 않은 어떤 법칙에 따라 유전자 배열이 주어진 개체들만이 적응을 하게 되고, 그 드러나지 않는 공통적 법칙이 스키마타로 표현이 될지도 모른다. 스키마타는 개체들의 부분군을 대표하며, 또한 개체들의 병렬적 처리라고 생각하면 된다. 이해가 되었으리라 생각되지만 또 하나의 인간군을 예를 들어보자. 스키마타는 집단의 대표자라고 할 수 있다. 집단의 대표자는 그 집단의 평균적 우수성을 지니고 있다고 가정하자. 집단 A와 집단 B가 있을 경우, 집단 A의 대표자가 집단 B의 대표자보다 우수하면 집단 A는 적응하고, 집단 B는 도퇴하는 것이다. 각각의 개체 각각의 적합성보다는 집단 대표자의 적합성을 보고 그 개체들의 적합성을 추측하는 것이다. 그만큼 처리속도(적응하는 데 소요되는 시간)가 빨라 질 수 있다. 스키마타를 이용한 환경에 대한 개체 적응은 [1] 처리 속도를 올릴 수 있지만 [2] 반면, 열등 부분 집합에 속해있는 우수 개체를 도퇴시킬 수 있다는 부작용(side effect)도 존재한다.  Order, Length의 개념 먼저 정의부터 확인해보자. order라는 것을 우리말로 번역하면 이상할 것 같아 원어 그대로 사용한다. 스키마 H에 대하여 order와 definig length의 정의는 아래와 같다. 정의 표기 설명 order ο(H) H의 유전자 구성에서 고정된 위치의 갯수 length δ(H) H의 고정된 위치에서 처음과 끝의 거리 예를 들어, 스키마 H = 011*1** 인 경우 ο(H) = 4, δ(H)= 5-1 = 4이다. 위와 같은 order와 length는 스키마에서 어떤 의미를 지니고 있는 것인가? 우선 '스키마타가 생존한다'라는 의미부터 정확히 알아야 될 것 같다. 특정 스키마 H가 교배나 돌연변이를 하여도 그 스키마가 생존한다는 의미는 소속집단(?)이 바뀌지 않는다는 말로 이해하면 될 것이다. 아래 그림을 보자. 그림. 스키마(schema) 생존의 의미 그림에서 스키마 H1과 H2 가 개체 A와 교배(crossover)를 하였다고 가정하면, 교배의 결과 스키마 H1C는 H1의 배열 규칙을 벗어나게 되고 H2C는 H2의 규칙에서 벗어나지 않고 다만 좀 더 한정적인 스키마가 될 뿐이다. 생존의 의미는 바로 규칙에서 벗어나지 않음을 의미한다. 그럼 스키마가 생존할 확률(survival probability, SP)은 어떻게 표현될 수 있을까? 바로 order와 length가 밀접한 관계가 있다. length가 짧을수록 그만큼 교배후에도 스키마가 생존할 확률이 크고, order가 작을수록 돌연변이 이후에도 스키마가 생존할 확률이 크다. 즉, SP(H) ∝ (1 - c1 * ο(H) - c2 * δ(H)) 단, c1 = f(pc, t) , c2 = f(pm), pc : prob. of crossover, pm : prob. of mutation, t : total length of schema (ex. 0**011 = 6) 위의 개념을 바탕으로 스키마 이론(schema theorem)을 적어보면 - Schema theorem is fundamental theorem 와 같다. 위의 식을 풀어쓰면, '주어진 환경에 적응하는 스키마는 기하급수적으로 증가하며, length가 짧을수록, order가 작을수록 더 빠르게 증가한다.' 라는 것을 말한다. 물론 적응하지 못하는 스키마는 기하급수적으로 감소한다라는 것도 뜻한다. 쉽게 말하면, 유전자 알고리즘의 탐색 능력은 단순한 무작위 탐색과는 비교가 안된다라는 것을 수학적으로 증명한 이론이 스키마 이론(schema theorem)이다.

죄수의 딜레마(prisoner's dilemma)

배신과 협력의 게임(1라운드의 죄수의 딜레마) 물주(게임 진행자) 한 명과 두 사람이 게임을 한다. 게임을 하는 두 사람의 손에는 '협력'과 '배신'의 카드 2장이 있으며 단 1라운드만 진행이 된다. 카드의 조합은 아래 표의 네 가지가 되며, 각각의 경우에서 이득과 손해는 아래와 같다.   A가 선택한 카드 B가 선택한 카드   협력 배신 협력 보수 (상호 협력에 대한) 예) 300달러 매우 나쁨 매우 나쁨 예) 100달러 징수 배신 매우 좋음 유혹료 (배신으로) 예) 500 달러 꽤 나쁨 벌금 (상호 배신에 대한) 예) 10 달러 징수 표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) 최초의 카드는 협력으로 시작, 상대가 배신을 하면 내가 배신 원한파 최초 협력, 상대가 한번 배신하면 계속 배신 간악 항상 배신 항상 배신 소박한 시험꾼 (naive prober) 최초 협력, 가끔 배신 표2. 죄수의 딜레마에서 대표적인 전략 이러한 게임을 '액셀로드'라는 사람이 전략을 하나의 공통 프로그램 언어로 번역하여 대형 컴퓨터로 서로 대전시켰다. 각각의 전략은 다른 모든 전략과 순차적으로 짝지어져서 반복 죄수의 딜레마 게임을 하는 것이다. 액셀로드가 인정하고 있는 가장 중요한 범주는 '마음씨 좋은(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)'이라는 전략이다. 한번 상대방이 배신을 하면 바로 배신을 하는 전략이 우리의 인생을 최소의 실패율을 가져다 줄 수 있는 전략이라는 것이다. 두 번을 참아서도 안 된다. 오직 한번만이 참을 뿐이다. 대신 관용을 유지해야 한다. 상대방의 잘못은 단기 기억으로 잊어버린다. 이제부터는 이것을 내 인생 전략으로 삼을까 싶다. ㅋㅋㅋ

유전자 알고리즘의 개요

2. GA의 구조및 요소 위에서 설명한 GA의 절차를 정리하면 다음과 같다. t : 세대 P(t) : t 세대의 모집단 GeneticAlgorithm { t = 0; initialize P(t); // 모집단 생성및 초기화 evaluate P(t); // 평가 while(종료조건이 만족되지 않으면) { t = t + 1; select P(t) from P(t-1); // 새로운 새대 선별 alter P(t); // 유전연산(교차,돌연변이) evaluate P(t); // 적응도 평가 } } 특정 문제를 해결하기 위한 GA를 구현하기 위해서는 다음 5가지의 요소가 결정되어야 한다. 1) 표현(representation) : 문제의 해를 개체로 표현하는 방법, 2) 초기모집단(initial population) : 초기모집단을 형성하는 방법, 3) 평가함수(evaluation function) : 개체의 적응도(fitness)를 평가하는 함수, 4) 유전연산자(genetic operators) : 자손 개체를 생산하기 위한 유전연산자, 5) 유전파라미터(genectic parameters) : 모집단의 크기, 각 유전연산의 적용확률 등). 3. 빌딩블럭 가설(building block hypothesis) GA의 가장 중요한 개념이며, 알고리즘 구현의 핵심인 빌딩블럭 가설에 대해 살펴보자. A genetic algorithm seeks near-optimal performance through the juxtaposition of short, low-order, high performance schemata, called the building blocks.[1] GA는 빌딩블럭의 병렬적 결합을 통하여 해를 탐색한다. 빌딩블럭은 짧고 고정인자 갯수가 적은 우수한 스키마(정현철님의 글 참조)를 말한다. 스키마는 개체의 특성을 결정하는 유전 형질로 볼 수 있다. 짧고 고정인자 수가 적은 스키마는 유전연산에 의해 잘 파괴되지 않고 계속 다음 세대의 개체로 유전될 수 있으며, 우수한 스키마를 가진 개체는 살아 남아 다음 세대의 생산에 참여하게 된다. GA는 우수한 개체(해)를 탐색하는 알고리즘이 아니다. GA는 다양한 형질들을 만들어내고, 여러 세대의 재생산과 유전연산을 통하여 개체의 특성을 결정하는 우수한 형질들을 자연스럽게(?) 추출하고, 이들의 병렬적인 결합을 시도해 보는 알고리즘이다. 따라서 GA의 구현에 있어서, 가장 먼저 고려해야 할 것은 개체의 특성을 결정짓는 유전 형질을 어떻게 표현할 것인가 하는 것이다. 해의 정보라고 할 수 있는 유전 형질의 추출이 용이한 표현 방법을 선택해야 한다. 또한 다양한 형질들을 만들어 낼 수 있고, 유전 형질을 크게 파괴하지 않는 유전연산자가 만들어져야 한다. 전통적인 GA에서는 2진 형태로 개체를 표현하기 때문에 short, low-order schemata가 빌딩블럭의 조건을 만족하였지만, 많은 문제에서 2진 형태로 해를 표현하기 어렵다. 2진 형태의 표현이 아니라면, 그에 맞는 빌딩블럭이 정의되어야 할 것이다. 이것이 GA의 구현에 있어서 핵심이라고 할 수 있다. 1. 유전알고리즘(Genetic Algorithm :GA) GA는 생태계의 진화과정, 즉 자연선별(natural selection)과 유전법칙을 모방한 확률적 최적해 탐색 기법이다. GA는 1975년 J. Holland의 논문 "Adaptation in Natural and Artificial Systems" 에서 처음 소개되었다. GA에서는 해결하고자 하는 문제의 해가 DNA형태의 개체(individual, string, chromosome, genome)로 표현(representation)된다. GA에서는 여러 개체로 이루어진 모집단(population)을 운용하여 최적해를 탐색한다. 매 세대마다 모집단의 각 개체들의 적응도(fitness)가 평가(evaluation)되고, 이를 기준으로 운 좋은 개체들은 자연 선별(natural selection)되고, 다음 세대를 생산할 행운(?)을 획득한 개체들은 서로 결합하여 서로의 유전형질이 교차(crossover)된 새로운 자손 개체(offspring)을 생산한다. 또한 주어진 확률로 개체의 특정 인자(gene)에 돌연변이(mutation)가 발생되어 유전형질에 변화가 일어난다. 이러한 과정 속에서 세대교체(replacement)가 이루어지고 새롭게 탄생한 개체들은 다시 평가된다. 이러한 과정이 특정 조건이 만족될 때가지 계속되어 모집단의 개체들은 진화한다.

이 글은 스프링노트에서 작성되었습니다.