Gurugail

개요

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

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

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

것이었다.

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

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

간단한 예를 들어보자. f(x) = x²[0 ≤ x ≤ 31] 이라는 환경이 있다고 한다면, 그리고 주어진 f(x) 환경에 잘 적응하는 정도가 바로 함수값으로 정의된다고 하자. 그러면 x = 0 에서 31까지의 개체들이 이 환경에서 살고 있는 셈이다. 그리고 x = 4라는 개체가 f(x) = x²[0 ≤ x ≤ 4]라는 환경에서 최적으로 잘 적응하는 셈인 것이다.

환경

 f(x) = x2[0 ≤ x ≤ 31]

적합성(fitness)

 f(x) = x2

개체

 0 ≤ x ≤ 31
 Ex.
 01101 
 11000 
 01000 
 10011 

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

 11111 
 11111 
 11111 
 11111 

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

재생산(reproduction)

유전자 알고리즘에서 재생산(reproduction)이란 적합함수(fitness function)에 따라서 개체들을 복사하는 과정이다. 쉽게 말해서 개체들이 속해 있는 군에서 잘난 넘(nom?)은 다음 세대를 더 많이 생산할 수 있는 기회를 주고, 물론 못난 놈은 자기와 닮은 개체를 생산할 수가 없어 그 형질이 다음 세대에 전달되지 않도록 하는 것이다.

그렇다면 과연, 우수 형질의 개체는 어느 정도(만큼) 개체를 생산할 수 있고, 열등 형질의 개체는 무조건 없어져야 하는가? 그렇지만은 않다. 왜냐면 열등 형질도 부분적으로는 우수 형질의 기질을 가지고 있기 때문이다. 따라서 유전자 알고리즘에서는 어떤 개체에게 어느 정도의 우수성을 부여하고 어떤 방식으로 재생산이 행해지느냐는 중요한 요소이다. 무작정 우수 형질의 개체를 재생산하다보면 전체 해(global point)를 찾지 못할 가능성도 커진다.

결론적으로 우수 형질의 개체 생산과 열등 형질의 개체 생산비율을 적절히 설정할 필요가 있다. 이를 실현하는 데 있어 유전자 알고리즘에서 기본적으로 roulette wheel이라는 확률 개념을 사용한다. 지금은 많이 사라졌지만, roulette wheel을 돌려서 뽑기하는 장사를 기억할 것이다. 원판(roulette wheel을 원판이라 번역, ^_^)에서 할당된 영역이 넓으면 그만큼 걸릴 확률이 많은 것이다. 우수 형질은 그만큼 원판에서의 면적 할당이 넓게 함으로써 다음 세대의 개체 생산의 가능성을 크게 하는 것이다. 아래 그림을 보면 이해가 될 것이다. 군(pool)에 개체들이 있고, 그 개체들은 우수 정도에 따라 영역을 할당받는다. 우수 개체는 아래 그림에서 (2) 영역을 할당받을 것이고, 열등 형질은 (1) 영역을 할당받을 것이다. 이제 재생산의 남은 과정은 원판을 돌리고 화살만 쏘면 되는 것이다. 걸리면 살아남는 개체가 되는 것이다. 냉혹함이 숨겨져 있는 알고리즘이다.

그림. 유전자 알고리즘에서의 재생산(Reproduction)

예제(example)

f(x) = x²이라는 환경에서 살아가는 개체가 시간 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) = x²에서의 개체와 적합함수(fitness function)

원판위에 적합함수(fitness function)에 따라 다음 세대에서의 생존 가능성을 그리면 앞의 원판 그림이다. No. 2라는 개체가 f(x) = x²이라는 환경에서는 가장 잘 적응되고 원판에서도 가장 넓은 영역을 차지하고 있다. 따라서 다음 세대를 재생산(reproduction) 하기 위해 화살을 네 번 쏜다면, No. 2라는 개체는 살아남아서 다음 단계인 교배(crossover)를 할 가능성이 가장 높다.

이상으로 roulette wheel이라는 확률 기반의 재생산(reporduction) 방법에 대해 알아보았다. 다음은 교배(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) 이론 이해 참고

유전자 알고리즘의 세 연산자(operator)인 재생산(reproduction), 교배(crossover), 돌연변이(mutation)은 너무나 간단하다. 결국 n개의 문자열(strings, 개체)로 구성되어 있는 개체군(population)에서 적합 함수(fitness function)에 따라 몇 개의 개체를 선택하고, 몇 개의 부분 문자열을 바꿈으로써 교배를 시키고, 확률에 따라서 돌연변이를 발생함으로써 환경에 진화하는 것이다. 간단하지만 수학적 근거가 없었다면 끝났다면, 아마도 유전자 알고리즘이 이처럼 유용한 알고리즘이 되지는 못하였을 것이다. 위의 방법론은 누구나가 제시할 수 있지만, 수학적 근거를 제시하기는 쉽지만은 않다. 이런 점에서 스키마 이론은 유전자 알고리즘의 수학적 배경을 제시한다는 점에서 유전자 알고리즘의 근본되는 이론이라 할 수 있다. 원서(참조)에서는 스키마 이론을 The fundamental theorem이라고 말하고 있다. 먼저 스키마가 무엇인지를 언급하고, 그 스키마가 환경에 적응하는 정도를 제시함으로써, 그 스키마에 속하는 개체들의 적응력(?)도 그 스키마의 적응력과 결국 같은 것이기 때문에, 유전자 알고리즘이 무작위 탐색과는 다르다라는 것을 말하고자 한다.

스키마타(schemata)

f(x) = x²이라는 환경에서 아래와 같은 개체군이 존재한다고 가정하자.

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)을 정리해 보면, 주어진 환경에 적응하는 스키마는 기하급수적으로 증가하며, length가 짧을수록, order가 작을수록 더 빠르게 증가한다.라는 것을 말한다. 물론 적응하지 못하는 스키마는 기하급수적으로 감소한다라는 것도 뜻한다. 쉽게 말하면, 유전자 알고리즘의 탐색 능력은 단순한 무작위 탐색과는 비교가 안된다라는 것을 수학적으로 증명한 이론이 스키마 이론(schema theorem)이다.

유전자 알고리즘에 의한 분류기 (classifier system)

유전자 알고리즘을 응용한 시스템으로 대표적으로 분류기가 있다. 기능적으로는 유전자와 규칙 기반 시스템과의 융합 버전이라고도 할 수 있다. 보통 규칙 시스템의 규칙 정의는 다음과 같다.

 if <condition> then <action>

위 식에서 <condition> 이 만족되며 <action>이 발현되는 식이다. 그렇다면 유전자 알고리즘과는 어떤 식으로 결합될까? 이해를 위해서는 classifier 라는 단어를 우선 알아야 하는데 classifier 의 구성은 다음과 같다.

 classifier := <condition>:<message>
 ex. classifier1 = 100#:010

#의 기호는 위 스키마타와 같은 기능이다. 가령 1001의 유전자도 위 classifier에 만족되어 010이라는 메시지를 생성할 것이다.

분류기의 동작 원리

분류기를 설명하기 전 환경에 대한 구성을 알아보자. Holland의 처음 분류기 모델에 의하면 위 classifier system의 주변에 해당하는 환경 구성은 외부 환경 정보를 검출할 수 있는 detector, 그리고 외부 환경에 액션을 취할 수 있는 effector, 그리고 환경의 detector와 effector를 연결시켜주는 분류 시스템으로 구성되어 있다. 우선 동작 원리를 이해하기 위해서 알아야 낼 사항이 있다. 분류 시스템은 내부적으로 1개 이상의 classifier set 이 있다는 것이다.

#	classifier
1	01##:0000
2	00#0:1100
3	11##:1000
4	##00:0001

가령 위와 같이 classifier들로 구성되어 있는 분류기라 생각해보자. 외부에서 0100 이 검출되면 위 1번과 4번의 classifier가 활성화될 수 있다. 따라서 액션들에 대한 최종 액션을 결정하기 위해서 classifier 의 세기(strength) 정보가 할당되어 있다. 다시 말하면 classifier마다 시스템에 대해서 제대로 반응하는 정도를 나타내는 신뢰 정도를 기준으로 환경으로 최종 액션을 내보낼 주체(classifier)를 가리게 되는 것이다. 그리고 classifier 자체도 유전자 알고리즘으로 점차 학습하게 되어 분류기 시스템 전체가 환경에 적응하도록 진화되는 것이다.

분류기 구성 요소

분류기를 구성하는 요소들은 detector, effector, classifier set, message list, apportionment of credit 들로 구성되어 있다.

• detector : 외부 환경을 감지하는 요소이며 classifier 가 이해할 수 있는 수준으로 encoding 하는 기능을 제공한다.
• effector : 외부 환경에 대해 반응(액션)하는 모듈
• classifier set : 분류기는 여러 개의 classifier들이 사용된다. 유전자 알고리즘으로 해당 classifier가 진화되면서 학습되어 지는 것이다.
• message list : classifier 에 의해 액션들에 해당하는 메시지들이 생성되면 message list라는 곳에 저장된다. 규칙 시스템 기반에서의 Working Memory와 같은 역할을 한다.
• apportionment of credit : detector에 의해서 감지된 메시지에 대하여 활성화될 수 있는 classifier 가 여러 개 가능할 것이다. 이들 여러 개체들간의 우선 순위를 할당하는 기능을 수행한다.

LCS (Learning Classifier System)의 파생

Holland 가 최초 제안을 하였지만 분류기에는 유형이 몇 가지 있다.

• Pittsburgh approach : 개체 하나 하나가 시스템에 있어 그 자체로의 완성된 규칙
• Michigan approach : 개체 하나는 전체 시스템에 있어 하나의 규칙에 불과, 여러 개의 규칙들이 학습되어 전체 시스템을 이루어감
• Iterative Rule Learning approach

참고

• http://www.exa.unicen.edu.ar/escuelapav/cursos/bio/l7.pdf
• Genetic Algorithms in Search, Optimization & Machine Learning / David E. Goldburg / Addison Wesley / ISBN 0-201-15767-5

\\