개요 ( What are Genetic Algorithms? ) 유전자 알고리즘(Genetic Algorithm, GA)은 적자 생존과 유전의 메카니즘을 바탕으로 하는 탐색 알고리즘이다. 다시 말해 주어진 환경에 잘 적응하는 유전자만을 선택(selection)하고 교배(crossover)하고 때에 따라서는 돌연변이(mutation)도 하며 다음 세대에 우수한 유전 형질이 전달(reproduction)되게 된다. 따라서 진화(evolution)가 거듭될수록 주어진 환경에 더 적합한 유전자들만이 남아있게 될 것이다.
[출처 : http://zzpark.egloos.com/5508970]
유전자 알고리즘은 미시간대학의 홀랜드(John Holland)에 의해 탄생하였으며. 당시 연구원들의 연구 목표는
[1] 자연시스템의 적응적 과정을 추상화시키며 철저하게 분석하여,
[2] 그러한 시스템을 소프트웨어적으로 디자인하는 것이었다.
[2] 그러한 시스템을 소프트웨어적으로 디자인하는 것이었다.
유전자 알고리즘(GA)은 그러한 배경에서 만들어졌으며, 근본적으로 다른 탐색이나 최적화 알고리즘과는 세 가지 정도가 다르다.
[1] GA는 하나의 개체(변수 등)가 아닌 개체들의 군(pool) 단위로 탐색한다.
[2] GA는 적합성 함수(fitness function)를 사용한다.
[3] GA는 확률적인 변이 규칙을 사용한다.
[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
11000
01000
10011
위의 네 개체가 오손도손(^_^) 살고 있는 군(집단)에서 과연 f(x) = x2이라는 환경에서 누가 더 잘 적응할 것으로 생각되는가? 위의 이진수를 십진수로 바꾸어 생각하면 쉽게 알 수 있다. 위의 예에서 01000은 살기 어렵고, 11000은 그나마 가장 잘 적응할 것이다. 그러므로 다음 세대에서는 01000은 도태를 하고, 11000은 자손을 생산하게 된다. 이와 같은 과정을 거친 먼 훗날의 개체는 바로 11111이라는 개체가 탄생할 것이고, 이 넘(^_^)이 바로 주어진 환경을 지배할 것이다.
11111
11111
11111
11111
11111
11111
11111
군(pool)이 위와 같은 개체(gene)로 구성되었을 때 '환경에 적응하였다'라고 말한다. 또는 '해를 찾았다'라고 말하기도 한다. 이와 같이 유전자 알고리즘은 자연의 적자 생존 원칙에 기반을 하고 있는 탐색 알고리즘이다. 다음 내용에서는 유전자 알고리즘의 단계별 과정들인 재생산(reproduction), 교배(crossover), 돌연변이(mutation)들을 알아보겠다
----------------
이번에는 유전자 알고리즘(GA; Genetic Algorithm)에 대해서 하겠습
니다.랜덤을 사용하는 알고리즘중에 제가 젤 좋아하는 알고리즘입니다
.(잘은 사용 하지만...^^)
그럼 강좌 시작하겠습니다.
찰스 다윈은 "종의 기원"에서 종이 어떻게 진화하는가를 적자 생존
의 원칙으로 명하였습니다. 그리고 멘델은 완두콩에 대한 실험으로 자
손의 형질은 원소로서 유전되며, 두 부모로 부터 각각 한개씩 받는다
고 설명하였습니다.
유전자 알고리즘은 적자 생존의 원칙과 교배, 돌연변이를 사용하여
탐색하는 기법으로 국소 탐색이나 시뮬레이티드 어닐링이 한개의 해
를 가지고 운영하는데 비해 유전자 알고리즘은 여러개의 해를 가지고
운영합니다.
유전자 알고리즘의 기본적인 구조는 다음과 같습니다.
Procedure GenetcAlgorithm;
begin
t := 0;
P(t)의 초기화(초기모집단 생성)
P(t)의 적응도 평가
while(종료조건이 만족되지 않으면) do
begin
t := t + 1;
P(t-1)로부터 P(t)를 선별
P(t)의 유전연산(교차와 돌연변이)
P(t)의 적응도 평가
end;
end;
P(t)는 t세대에서의 모집단을 나타냄니다. 간단한 문제를 가지고 예
를 들어 설명하겠습니다.
문제) f(x) = | 10*x-100 | 이고, 0 <= x <= 31 일때 함수 f(x)를
최대로 하는 x
를 찾아라. 단 x는 정수이다.
위 문제는 국소탐색을 할때 사용한 문제죠... 숫자만 약간 바꿨습니
다. 우선 해의 표현 방법을 정해야 겠죠. (유전 알고리즘에서 해는 보
통 유전자라고 부름니다. 이것 말고도 많은 용어들이 생물학에서 사용
되는 용어를 많이 사용합니다.) 0 ~ 31까지 나타내기 위해서는 5비트
가 필요 합니다. 유전자는 2진백터로 표현 합니다. 즉, (10101) = 21,
(11111) = 31, (01100) = 12 가 됩니다.
그러면 0세대 부터 시작 합니다. 처음에는 초기 집단을 생성 합니다.
초기 집단은 랜덤하게 만듭니다. 20개의 염색체로, 초기 집단이 다음
과 같이 만들어 졌다고 합시다.
v[1]: (01101)
v[2]: (01111)
v[3]: (10100)
v[4]: (01101)
v[5]: (10101)
v[6]: (01011)
v[7]: (10111)
v[8]: (10000)
v[9]: (01101)
v[10]: (01011)
평가 단계에서 각 염색체를 해독하고, 해독된 값으로 부터 적합도
함수값을 계산 한 결과 다음과 같은 결과를 얻었습니다.
eval(v[1]) = f(13) = 30
eval(v[2]) = f(15) = 50
eval(v[3]) = f(20) = 100
eval(v[4]) = f(13) = 30
eval(v[5]) = f(21) = 110
eval(v[6]) = f(11) = 10
eval(v[7]) = f(24) = 130
eval(v[8]) = f(16) = 60
eval(v[9]) = f(13) = 30
eval(v[10]) = f(11) = 10
이제 이중에서 몇개의 염색체를 선택해야 합니다. 선택하는 방법은
여러가지가 있는데 여기에서는 룰렛선택을 합니다. 룰렛선택은 적합도
에 비례해서 선택될 확률이 높아짐니다. 룰렛선택은 다음과 같이 합니
다.
------------------------------------------------------------------------------
1) 개체집단의 총 적합도를 계산한다.
F = eval(v[1]) + eval(v[2]) + .... + eval(v[10])
2) 각 염색체에 대한 선택 확률 p[i]를 계산한다.
p[i] = eval(v[i])/F
3) 각 염색체에 대한 누적 확률 q[i]를 계산한다.
q[i] = p[1] + p[2] + ... p[i]
선택과정은 유전자의 개수만큼 다음 방법으로 새로운 개체집단을 위
한 하나의 염색체를 선택합니다.
범위 0..1사이의 난수 r를 발생시킨다.
q[i-1]< r <=q[i] 인 i번째 염색체를 선택한다.
------------------------------------------------------------------------------
그럼 위와 같은 방법으로 룰렛 선택을 합니다. 개체집단의 총 적합도는
F = eval(v[1]) eval(v[2]) +...+ eval(v[10]) = 560
입니다. 각 염색체가 선택될 확률 p[i]는 다음과 같습니다.
p[1] = eval(v[1])/F = 0.0535714286
p[2] = eval(v[2])/F = 0.0892857143
p[3] = eval(v[3])/F = 0.1785714286
p[4] = eval(v[4])/F = 0.0535714286
p[5] = eval(v[5])/F = 0.1964285714
p[6] = eval(v[6])/F = 0.0178571429
p[7] = eval(v[7])/F = 0.2321428571
p[8] = eval(v[8])/F = 0.1071428571
p[9] = eval(v[9])/F = 0.0535714286
p[10] = eval(v[10])/F = 0.0178571429
그러면 각 염색체의 누적 확률 q[i]는 다음과 같습니다.
q[1] = 0.0535714286
q[2] = 0.1428571429
q[3] = 0.3214285714
q[4] = 0.3750000000
q[5] = 0.5714285714
q[6] = 0.5892857143
q[7] = 0.8214285714
q[8] = 0.9285714286
q[9] = 0.9821428571
q[10] = 1.0000000000
이제 0부터 1사이의 난수를 10(유전자의 개수)개 발생시켜 유전자를선택합니다.
만약 난수가 0.45772737743 이라면 q[4] < 0.45772737743 <= q[5] 를 만족하기 때
문에 유전자v[5] 를 선택합니다. 난수가 다음과 같이 발생 되었습니다.
0.4572273774 0.6205325316 0.2902582685 0.3707185990
0.6674934615 0.5626070339 0.7364188557 0.9917080770
0.6376504887 0.9917636998
그러면 선택된 개체들은 최종적으로 다음과 같습니다.
v'[1] = (10101)
v'[2] = (10111)
v'[3] = (10100)
v'[4] = (01101)
v'[5] = (10111)
v'[6] = (10101)
v'[7] = (10111)
v'[8] = (01011)
v'[9] = (10111)
v'[10] = (01011)
그러면 이제 유전 연산을 하면 됩니다. 유전 연산은 교배과 돌연변
이가 있는데 우선 교배부터 합니다. 교배하는 방법은 우선 교배 확률
에 의해 교배시킬 염색체를 선택합니다. 교배 확률은 0.25로 하겠습니
다. 다음과 같은 난수를 10개 발생시켜서 다음과 같은 수를 얻었습니
다.
0.5725024704 0.0490196129 0.8726333449 0.3486277370
0.3863749911 0.8044754410 0.8187371953 0.5160406448
0.0951179727 0.6477678808
결과 선택된 것은 v'[2]와 v'[9]가 선택되었습니다. 운좋게 짝수개
가 선택되어서 모두 교배시킬수 있습니다. 만약에 홀수개가 선택되었
다면 하나를 빼든가 추가해야 됩니다. 교배하는 방법은 다음과 같이
합니다.
------------------------------------------------------------------------------
염색체 x = (x1 x2 x3 x4 x5)와 염색체 y = (y1 y2 y3 y4 y5)가 있
다으면 우선 1 ~ 4(5-1) 사이의 수 중 난수 r를 발생 시킨다. 만약
r이 3이라면
x' = (x1 x2 x3 | y4 y5)
y' = (y1 y2 y3 | x4 x5)
로 r번째 다음에 있는 유전인자들을 바꿔주어서 새로운 유전자를 만
듭니다.
------------------------------------------------------------------------------
v'[2] = (10111) 와 v'[9] = (10111) 를 교배시키기 위해 난수 r를
발생 시킴니다. r은 1이 발생 되었습니다. 다음과 같이 됩니다.
v'[2] = (1 | 0111)
v'[9] = (1 | 0111)
v'[2]와 v'[9] 서로 같아서 아무런 변화가 없습니다. (예제가 나쁘
죠...프로그램을 실행시키면서 쓰는 것이라서 다른 걸로 바꿀수가...^^),
그리고 여기에서는 2개의 유전자가 선택 되었는데 만약 4개 또는 6개 이
상이 선택 되었다면은 임의로 2개씩 짝지어서 교배 시켜야 됩니다. 교배
이후에 개체집단은 다음과 같습니다.
v'[1] = (10101)
v'[2] = (10111)
v'[3] = (10100)
v'[4] = (01101)
v'[5] = (10111)
v'[6] = (10101)
v'[7] = (10111)
v'[8] = (01011)
v'[9] = (10111)
v'[10] = (01011)
이제 돌연변이를 시켜 줍니다. 돌연 변이 확률은 0.1로 하겠습니다.
돌연 변이는 각 염색체에 대해서 난수를 발생시켜 (돌연 변이 확률)<(
난수) 이면은 유전인자를 바꾸어 줍니다. 즉, 1이면 0으로 0이면 1로
바꿉니다. 돌연 변이를 시킨 다음에 개체집단은 다음고 같습니다. 바
뀐 염색체는 위에 '_' 표시를 했습니다.
_
v'[1] = (11001)
_
v'[2] = (00111)
_
v'[3] = (10101)
_
v'[4] = (00101)
v'[5] = (10111)
_
v'[6] = (10111)
v'[7] = (10111)
v'[8] = (01011)
v'[9] = (10111)
_
v'[10] = (00011)
그러면 v'에서 '표시를 지우고 다시 고쳐쓰면 다음고 같습니다.
v[1] = (11001)
v[2] = (00111)
v[3] = (10101)
v[4] = (00101)
v[5] = (10111)
v[6] = (10111)
v[7] = (10111)
v[8] = (01011)
v[9] = (10111)
v[10] = (00011)
이 개체의 적합도를 계산 하면 다음과 같습니다.
eval(v[1]) = f(25) = 150
eval(v[2]) = f(7) = 30
eval(v[3]) = f(21) = 110
eval(v[4]) = f(5) = 50
eval(v[5]) = f(23) = 130
eval(v[6]) = f(23) = 130
eval(v[7]) = f(23) = 130
eval(v[8]) = f(11) = 10
eval(v[9]) = f(23) = 130
eval(v[10]) = f(3) = 70
대체적으로 이전세대 보다 더 좋은 값을 갖는 개체집단이 생겼습니
다. 이런 방법을 반복하면은 꽤 좋은 해를 찾을수 있습니다. 10세대
까지 진행 시킨 결과는 다음과 같습니다.
v[1] = (11111)
v[2] = (11011)
v[3] = (11011)
v[4] = (11100)
v[5] = (10111)
v[6] = (11100)
v[7] = (11111)
v[8] = (11111)
v[9] = (11100)
v[10] = (11111)
이것을 평가하면 다음과 값을 얻을수 있습니다.
eval[2] = f(27) = 170
eval[3] = f(27) = 170
eval[4] = f(28) = 180
eval[5] = f(23) = 130
eval[6] = f(28) = 180
eval[7] = f(31) = 210
eval[8] = f(31) = 210
eval[9] = f(28) = 180
eval[10] = f(31) = 210
여기에서는 운좋게 마지막 세대에서 최적값 210을 얻을수 있었습니
다. 하지만 마지막 세대에 최적값을 못얻는 경우가 생길수 있으므로
여태까지 출현했는 염색체중에서 가장 좋은 평가값을 갖는 염색체를
따로 저장해 둡니다.
----
니다.랜덤을 사용하는 알고리즘중에 제가 젤 좋아하는 알고리즘입니다
.(잘은 사용 하지만...^^)
그럼 강좌 시작하겠습니다.
찰스 다윈은 "종의 기원"에서 종이 어떻게 진화하는가를 적자 생존
의 원칙으로 명하였습니다. 그리고 멘델은 완두콩에 대한 실험으로 자
손의 형질은 원소로서 유전되며, 두 부모로 부터 각각 한개씩 받는다
고 설명하였습니다.
유전자 알고리즘은 적자 생존의 원칙과 교배, 돌연변이를 사용하여
탐색하는 기법으로 국소 탐색이나 시뮬레이티드 어닐링이 한개의 해
를 가지고 운영하는데 비해 유전자 알고리즘은 여러개의 해를 가지고
운영합니다.
유전자 알고리즘의 기본적인 구조는 다음과 같습니다.
Procedure GenetcAlgorithm;
begin
t := 0;
P(t)의 초기화(초기모집단 생성)
P(t)의 적응도 평가
while(종료조건이 만족되지 않으면) do
begin
t := t + 1;
P(t-1)로부터 P(t)를 선별
P(t)의 유전연산(교차와 돌연변이)
P(t)의 적응도 평가
end;
end;
P(t)는 t세대에서의 모집단을 나타냄니다. 간단한 문제를 가지고 예
를 들어 설명하겠습니다.
문제) f(x) = | 10*x-100 | 이고, 0 <= x <= 31 일때 함수 f(x)를
최대로 하는 x
를 찾아라. 단 x는 정수이다.
위 문제는 국소탐색을 할때 사용한 문제죠... 숫자만 약간 바꿨습니
다. 우선 해의 표현 방법을 정해야 겠죠. (유전 알고리즘에서 해는 보
통 유전자라고 부름니다. 이것 말고도 많은 용어들이 생물학에서 사용
되는 용어를 많이 사용합니다.) 0 ~ 31까지 나타내기 위해서는 5비트
가 필요 합니다. 유전자는 2진백터로 표현 합니다. 즉, (10101) = 21,
(11111) = 31, (01100) = 12 가 됩니다.
그러면 0세대 부터 시작 합니다. 처음에는 초기 집단을 생성 합니다.
초기 집단은 랜덤하게 만듭니다. 20개의 염색체로, 초기 집단이 다음
과 같이 만들어 졌다고 합시다.
v[1]: (01101)
v[2]: (01111)
v[3]: (10100)
v[4]: (01101)
v[5]: (10101)
v[6]: (01011)
v[7]: (10111)
v[8]: (10000)
v[9]: (01101)
v[10]: (01011)
평가 단계에서 각 염색체를 해독하고, 해독된 값으로 부터 적합도
함수값을 계산 한 결과 다음과 같은 결과를 얻었습니다.
eval(v[1]) = f(13) = 30
eval(v[2]) = f(15) = 50
eval(v[3]) = f(20) = 100
eval(v[4]) = f(13) = 30
eval(v[5]) = f(21) = 110
eval(v[6]) = f(11) = 10
eval(v[7]) = f(24) = 130
eval(v[8]) = f(16) = 60
eval(v[9]) = f(13) = 30
eval(v[10]) = f(11) = 10
이제 이중에서 몇개의 염색체를 선택해야 합니다. 선택하는 방법은
여러가지가 있는데 여기에서는 룰렛선택을 합니다. 룰렛선택은 적합도
에 비례해서 선택될 확률이 높아짐니다. 룰렛선택은 다음과 같이 합니
다.
------------------------------------------------------------------------------
1) 개체집단의 총 적합도를 계산한다.
F = eval(v[1]) + eval(v[2]) + .... + eval(v[10])
2) 각 염색체에 대한 선택 확률 p[i]를 계산한다.
p[i] = eval(v[i])/F
3) 각 염색체에 대한 누적 확률 q[i]를 계산한다.
q[i] = p[1] + p[2] + ... p[i]
선택과정은 유전자의 개수만큼 다음 방법으로 새로운 개체집단을 위
한 하나의 염색체를 선택합니다.
범위 0..1사이의 난수 r를 발생시킨다.
q[i-1]< r <=q[i] 인 i번째 염색체를 선택한다.
------------------------------------------------------------------------------
그럼 위와 같은 방법으로 룰렛 선택을 합니다. 개체집단의 총 적합도는
F = eval(v[1]) eval(v[2]) +...+ eval(v[10]) = 560
입니다. 각 염색체가 선택될 확률 p[i]는 다음과 같습니다.
p[1] = eval(v[1])/F = 0.0535714286
p[2] = eval(v[2])/F = 0.0892857143
p[3] = eval(v[3])/F = 0.1785714286
p[4] = eval(v[4])/F = 0.0535714286
p[5] = eval(v[5])/F = 0.1964285714
p[6] = eval(v[6])/F = 0.0178571429
p[7] = eval(v[7])/F = 0.2321428571
p[8] = eval(v[8])/F = 0.1071428571
p[9] = eval(v[9])/F = 0.0535714286
p[10] = eval(v[10])/F = 0.0178571429
그러면 각 염색체의 누적 확률 q[i]는 다음과 같습니다.
q[1] = 0.0535714286
q[2] = 0.1428571429
q[3] = 0.3214285714
q[4] = 0.3750000000
q[5] = 0.5714285714
q[6] = 0.5892857143
q[7] = 0.8214285714
q[8] = 0.9285714286
q[9] = 0.9821428571
q[10] = 1.0000000000
이제 0부터 1사이의 난수를 10(유전자의 개수)개 발생시켜 유전자를선택합니다.
만약 난수가 0.45772737743 이라면 q[4] < 0.45772737743 <= q[5] 를 만족하기 때
문에 유전자v[5] 를 선택합니다. 난수가 다음과 같이 발생 되었습니다.
0.4572273774 0.6205325316 0.2902582685 0.3707185990
0.6674934615 0.5626070339 0.7364188557 0.9917080770
0.6376504887 0.9917636998
그러면 선택된 개체들은 최종적으로 다음과 같습니다.
v'[1] = (10101)
v'[2] = (10111)
v'[3] = (10100)
v'[4] = (01101)
v'[5] = (10111)
v'[6] = (10101)
v'[7] = (10111)
v'[8] = (01011)
v'[9] = (10111)
v'[10] = (01011)
그러면 이제 유전 연산을 하면 됩니다. 유전 연산은 교배과 돌연변
이가 있는데 우선 교배부터 합니다. 교배하는 방법은 우선 교배 확률
에 의해 교배시킬 염색체를 선택합니다. 교배 확률은 0.25로 하겠습니
다. 다음과 같은 난수를 10개 발생시켜서 다음과 같은 수를 얻었습니
다.
0.5725024704 0.0490196129 0.8726333449 0.3486277370
0.3863749911 0.8044754410 0.8187371953 0.5160406448
0.0951179727 0.6477678808
결과 선택된 것은 v'[2]와 v'[9]가 선택되었습니다. 운좋게 짝수개
가 선택되어서 모두 교배시킬수 있습니다. 만약에 홀수개가 선택되었
다면 하나를 빼든가 추가해야 됩니다. 교배하는 방법은 다음과 같이
합니다.
------------------------------------------------------------------------------
염색체 x = (x1 x2 x3 x4 x5)와 염색체 y = (y1 y2 y3 y4 y5)가 있
다으면 우선 1 ~ 4(5-1) 사이의 수 중 난수 r를 발생 시킨다. 만약
r이 3이라면
x' = (x1 x2 x3 | y4 y5)
y' = (y1 y2 y3 | x4 x5)
로 r번째 다음에 있는 유전인자들을 바꿔주어서 새로운 유전자를 만
듭니다.
------------------------------------------------------------------------------
v'[2] = (10111) 와 v'[9] = (10111) 를 교배시키기 위해 난수 r를
발생 시킴니다. r은 1이 발생 되었습니다. 다음과 같이 됩니다.
v'[2] = (1 | 0111)
v'[9] = (1 | 0111)
v'[2]와 v'[9] 서로 같아서 아무런 변화가 없습니다. (예제가 나쁘
죠...프로그램을 실행시키면서 쓰는 것이라서 다른 걸로 바꿀수가...^^),
그리고 여기에서는 2개의 유전자가 선택 되었는데 만약 4개 또는 6개 이
상이 선택 되었다면은 임의로 2개씩 짝지어서 교배 시켜야 됩니다. 교배
이후에 개체집단은 다음과 같습니다.
v'[1] = (10101)
v'[2] = (10111)
v'[3] = (10100)
v'[4] = (01101)
v'[5] = (10111)
v'[6] = (10101)
v'[7] = (10111)
v'[8] = (01011)
v'[9] = (10111)
v'[10] = (01011)
이제 돌연변이를 시켜 줍니다. 돌연 변이 확률은 0.1로 하겠습니다.
돌연 변이는 각 염색체에 대해서 난수를 발생시켜 (돌연 변이 확률)<(
난수) 이면은 유전인자를 바꾸어 줍니다. 즉, 1이면 0으로 0이면 1로
바꿉니다. 돌연 변이를 시킨 다음에 개체집단은 다음고 같습니다. 바
뀐 염색체는 위에 '_' 표시를 했습니다.
_
v'[1] = (11001)
_
v'[2] = (00111)
_
v'[3] = (10101)
_
v'[4] = (00101)
v'[5] = (10111)
_
v'[6] = (10111)
v'[7] = (10111)
v'[8] = (01011)
v'[9] = (10111)
_
v'[10] = (00011)
그러면 v'에서 '표시를 지우고 다시 고쳐쓰면 다음고 같습니다.
v[1] = (11001)
v[2] = (00111)
v[3] = (10101)
v[4] = (00101)
v[5] = (10111)
v[6] = (10111)
v[7] = (10111)
v[8] = (01011)
v[9] = (10111)
v[10] = (00011)
이 개체의 적합도를 계산 하면 다음과 같습니다.
eval(v[1]) = f(25) = 150
eval(v[2]) = f(7) = 30
eval(v[3]) = f(21) = 110
eval(v[4]) = f(5) = 50
eval(v[5]) = f(23) = 130
eval(v[6]) = f(23) = 130
eval(v[7]) = f(23) = 130
eval(v[8]) = f(11) = 10
eval(v[9]) = f(23) = 130
eval(v[10]) = f(3) = 70
대체적으로 이전세대 보다 더 좋은 값을 갖는 개체집단이 생겼습니
다. 이런 방법을 반복하면은 꽤 좋은 해를 찾을수 있습니다. 10세대
까지 진행 시킨 결과는 다음과 같습니다.
v[1] = (11111)
v[2] = (11011)
v[3] = (11011)
v[4] = (11100)
v[5] = (10111)
v[6] = (11100)
v[7] = (11111)
v[8] = (11111)
v[9] = (11100)
v[10] = (11111)
이것을 평가하면 다음과 값을 얻을수 있습니다.
eval[2] = f(27) = 170
eval[3] = f(27) = 170
eval[4] = f(28) = 180
eval[5] = f(23) = 130
eval[6] = f(28) = 180
eval[7] = f(31) = 210
eval[8] = f(31) = 210
eval[9] = f(28) = 180
eval[10] = f(31) = 210
여기에서는 운좋게 마지막 세대에서 최적값 210을 얻을수 있었습니
다. 하지만 마지막 세대에 최적값을 못얻는 경우가 생길수 있으므로
여태까지 출현했는 염색체중에서 가장 좋은 평가값을 갖는 염색체를
따로 저장해 둡니다.
----
이번에는 죄수의 딜레마 라는 단순한 게임에 대한 전략을 학습하
기 위하여 어떻게사용될 수 있는지 설명하겠습니다.
------------------------------------------------------------------------------
죄수의 딜레마 - 두 명의 죄수가 독립된 방에 수감되어 있어서 서
로 통신할 수가 없는 상태에 놓여 있습니다. 죄수들은 각각 상대방
을 이탈하고 배신(죄를 시인하는 것이라 생각하면 됩니다)을 하도록
요구됩니다.
┌───────────┬──────────┬──────────┐
│ 나 ＼ 상대방 │협력 │ 배신 │
├───────────┼──────────┼──────────┤
│ 협력 │ 각각 2년형 │ 나만 5년형 │
├───────────┼──────────┼──────────┤
│ 배신 │ 상대방만 5년형 │ 각각 4년형 │
└───────────┴──────────┴──────────┘
위표와 같이 징역을 살게 됩니다. 그러면 이기적인 선택은 상대방
이 어떠한 선택을 하든 상관없이 협력하는 것보다는 더 나은 보상을
가져다 주게 됩니다(상대방이 협력 했을 경우에 내가 협력하면 2년형
을 살지만 배신하면 5년형이고, 상대방이 배신했을 때도 협력하면
5년형을 살지만 배신하면 4년형을 살게 되기 때문입니다) 하지만 둘
다 배신하면 둘다 협력했을 때보다 결과가 나쁘게 됩니다. 죄수의 딜
레마는 협력할 것인가 배신할 것인가를 선택하는 문제입니다.
------------------------------------------------------------------------------
만약 단, 한번의 기회만 주어진다면 어떤 선택을 해야 될까요?? 이
것을 여러번 시행하게 만들면 다음과 같이 점수를 주면 됩니다.
┌────────┬────────┬────────┬────────┐
│ Player1 │ Player2 │ Player1의 점수 │ Player2의 점수 │
├────────┼────────┼────────┼────────┤
│ 배신 │ 배신 │ 1 │ 1 │
├────────┼────────┼────────┼────────┤
│ 배신 │ 협조 │ 5 │ 0 │
├────────┼────────┼────────┼────────┤
│ 협조 │ 배신 │ 0 │ 5 │
├────────┼────────┼────────┼────────┤
│ 협조 │ 협조 │ 3 │ 3 │
└────────┴────────┴────────┴────────┘
위 표대로 점수를 주면서 게임을 합니다. 예를 들어 게임이 (협조,
협조),(협조,배신),(협조,배신)이 되었다면 Player1은 3+0+0=3점을 얻
게 되고, Player2는 3+5+5 = 13점을얻게 됩니다. 그러면 이것을 유전
자 알고리즘으로 점근해 보겠습니다.
1) 전략의 표현 - 전략은 최근에 했던 3게임을 가지고 현재의 행동을
선택합니다. 예를 들어 최근에 했던 게임이 (배신,배신),(배신,협조),
(협조,배신) 였고, 염색체 내의 이것에 해당되는 유전인자가 협조였다
면 그 염색체의 다음 행동은 협조가 됩니다. 이런 방법으로 표현하면
은 한 게임에 대해 4개의 가능한 결과가 존재하므로 4*4*4=64개의 서
로 다른 이전 행동들이 존재합니다.
64개의 서로 다른 행동에 대한 다음 행동이 협조냐 배신이냐에 따라
2가지 경우가 존재 하므로 비트 또는 D와 C로 표현할수 있습니다. 그리
고 게임시작 이전의 세 가설적인 행동에 관한 초기 가정을 규정할 필요
가 있으므로 추가로 6개의 유전인자가 필요하게 되빈다. 총 70개의 유
전인자가 하나의 염색체를 표현하게 됩니다.
2) 유전자 알고리즘의 윤곽
죄수의 딜레마에 대한 전략을 학습하기 위한 Axelrod의 유전자 알고
리즘은 다음과 같은 네 가지 과정으로 이루어집니다.
------------------------------------------------------------------------------
1. 초기 개체집단을 선택한다. 각 플레이어는 위에서 언급된 것처럼 하
나의 전략을 나타내는 70비트의 임의의 스트링에 할당된다.
2. 각 플레이어를 테스트하여 유효성을 결정한다. 각 플레이어는 자신의
염색체에 의해 정의된 전략을 사용하여 다른 플레이어와 게임한다. 그
플레이어의 점수는 그가 하는 모든 게임에 있어서의 평균이다.
3. 증식시킬 플레이어를 선택한다. 평균점수를 가진 플레이어에 한번의
증식 기회를 부여한다. 평균점수보다 하나의 표준편차 이상의 점수를 가
진 플레이어에는 두번의 증식기회를 부여한다. 평균점수보다 하나의 표
준편차 이하의 점수를 가진 플레이어는 증식기회를 갖지 못한다.
4. 성공적인 플레이어는 임의로 짝을 지어 교배당 두명의 자손을 만들어
낸다. 각 자손의 전략은 그의 부모의 전략으로부터 결정된다. 이것은 두
개의 유전 연산자인 교배와 돌연벼이에 의해 이루어진다.
------------------------------------------------------------------------------
3) 실험 결과
- 위와 같이 프로그램을 실행하고 나서 Axelrod가 얻은 결과는 놀랄
만한 결과를 얻었다고 합니다. 그 중 일부를 적으면 다음과 같습니다.
------------------------------------------------------------------------------
C는 협력, D는 배신;
1. 배를 흔들지 말라: 세번의 상호협력 이후에는 계속 협력한다
((CC)(CC)(CC) 이후에 C).
2. 화를 내라: 다른 플레이어가 배신하였을 때는 같이 배신하라
((CC)(CC)(CD) 이후에 D)
3. 사과를 받아들이라: 협력관계가 다시 정립되었을 때 계속 협력하라
((CD)(DC)(CC) 이후에 C)
4. 잊어버리라: 배신 후에 협력관계가 재정립되었을 때 협력하라
((DC)(CC)(CC) 이후에 C)
5. 관례를 받아들이라: 세번의 상호 배신 이후에 배신하라
((DD)(DD)(DD) 이후에 D)
------------------------------------------------------------------------------
------------------------------------------------------------------------------
제가 해본 결과는 신기하게도 ((CC)(CC)(CC) 이후에 D)로 진화하
는 개체가 되는군요...^^;; 아마도 어딘가 잘못한듯 싶은데... 혹시
시간 있으신 분은 한번 위 프로그램을 짜보세요...그래서 결과를 올
려 주시면 감사...(제가 한번 보고 싶어서여...^^;;)
-------------
기 위하여 어떻게사용될 수 있는지 설명하겠습니다.
------------------------------------------------------------------------------
죄수의 딜레마 - 두 명의 죄수가 독립된 방에 수감되어 있어서 서
로 통신할 수가 없는 상태에 놓여 있습니다. 죄수들은 각각 상대방
을 이탈하고 배신(죄를 시인하는 것이라 생각하면 됩니다)을 하도록
요구됩니다.
┌───────────┬──────────┬──────────┐
│ 나 ＼ 상대방 │협력 │ 배신 │
├───────────┼──────────┼──────────┤
│ 협력 │ 각각 2년형 │ 나만 5년형 │
├───────────┼──────────┼──────────┤
│ 배신 │ 상대방만 5년형 │ 각각 4년형 │
└───────────┴──────────┴──────────┘
위표와 같이 징역을 살게 됩니다. 그러면 이기적인 선택은 상대방
이 어떠한 선택을 하든 상관없이 협력하는 것보다는 더 나은 보상을
가져다 주게 됩니다(상대방이 협력 했을 경우에 내가 협력하면 2년형
을 살지만 배신하면 5년형이고, 상대방이 배신했을 때도 협력하면
5년형을 살지만 배신하면 4년형을 살게 되기 때문입니다) 하지만 둘
다 배신하면 둘다 협력했을 때보다 결과가 나쁘게 됩니다. 죄수의 딜
레마는 협력할 것인가 배신할 것인가를 선택하는 문제입니다.
------------------------------------------------------------------------------
만약 단, 한번의 기회만 주어진다면 어떤 선택을 해야 될까요?? 이
것을 여러번 시행하게 만들면 다음과 같이 점수를 주면 됩니다.
┌────────┬────────┬────────┬────────┐
│ Player1 │ Player2 │ Player1의 점수 │ Player2의 점수 │
├────────┼────────┼────────┼────────┤
│ 배신 │ 배신 │ 1 │ 1 │
├────────┼────────┼────────┼────────┤
│ 배신 │ 협조 │ 5 │ 0 │
├────────┼────────┼────────┼────────┤
│ 협조 │ 배신 │ 0 │ 5 │
├────────┼────────┼────────┼────────┤
│ 협조 │ 협조 │ 3 │ 3 │
└────────┴────────┴────────┴────────┘
위 표대로 점수를 주면서 게임을 합니다. 예를 들어 게임이 (협조,
협조),(협조,배신),(협조,배신)이 되었다면 Player1은 3+0+0=3점을 얻
게 되고, Player2는 3+5+5 = 13점을얻게 됩니다. 그러면 이것을 유전
자 알고리즘으로 점근해 보겠습니다.
1) 전략의 표현 - 전략은 최근에 했던 3게임을 가지고 현재의 행동을
선택합니다. 예를 들어 최근에 했던 게임이 (배신,배신),(배신,협조),
(협조,배신) 였고, 염색체 내의 이것에 해당되는 유전인자가 협조였다
면 그 염색체의 다음 행동은 협조가 됩니다. 이런 방법으로 표현하면
은 한 게임에 대해 4개의 가능한 결과가 존재하므로 4*4*4=64개의 서
로 다른 이전 행동들이 존재합니다.
64개의 서로 다른 행동에 대한 다음 행동이 협조냐 배신이냐에 따라
2가지 경우가 존재 하므로 비트 또는 D와 C로 표현할수 있습니다. 그리
고 게임시작 이전의 세 가설적인 행동에 관한 초기 가정을 규정할 필요
가 있으므로 추가로 6개의 유전인자가 필요하게 되빈다. 총 70개의 유
전인자가 하나의 염색체를 표현하게 됩니다.
2) 유전자 알고리즘의 윤곽
죄수의 딜레마에 대한 전략을 학습하기 위한 Axelrod의 유전자 알고
리즘은 다음과 같은 네 가지 과정으로 이루어집니다.
------------------------------------------------------------------------------
1. 초기 개체집단을 선택한다. 각 플레이어는 위에서 언급된 것처럼 하
나의 전략을 나타내는 70비트의 임의의 스트링에 할당된다.
2. 각 플레이어를 테스트하여 유효성을 결정한다. 각 플레이어는 자신의
염색체에 의해 정의된 전략을 사용하여 다른 플레이어와 게임한다. 그
플레이어의 점수는 그가 하는 모든 게임에 있어서의 평균이다.
3. 증식시킬 플레이어를 선택한다. 평균점수를 가진 플레이어에 한번의
증식 기회를 부여한다. 평균점수보다 하나의 표준편차 이상의 점수를 가
진 플레이어에는 두번의 증식기회를 부여한다. 평균점수보다 하나의 표
준편차 이하의 점수를 가진 플레이어는 증식기회를 갖지 못한다.
4. 성공적인 플레이어는 임의로 짝을 지어 교배당 두명의 자손을 만들어
낸다. 각 자손의 전략은 그의 부모의 전략으로부터 결정된다. 이것은 두
개의 유전 연산자인 교배와 돌연벼이에 의해 이루어진다.
------------------------------------------------------------------------------
3) 실험 결과
- 위와 같이 프로그램을 실행하고 나서 Axelrod가 얻은 결과는 놀랄
만한 결과를 얻었다고 합니다. 그 중 일부를 적으면 다음과 같습니다.
------------------------------------------------------------------------------
C는 협력, D는 배신;
1. 배를 흔들지 말라: 세번의 상호협력 이후에는 계속 협력한다
((CC)(CC)(CC) 이후에 C).
2. 화를 내라: 다른 플레이어가 배신하였을 때는 같이 배신하라
((CC)(CC)(CD) 이후에 D)
3. 사과를 받아들이라: 협력관계가 다시 정립되었을 때 계속 협력하라
((CD)(DC)(CC) 이후에 C)
4. 잊어버리라: 배신 후에 협력관계가 재정립되었을 때 협력하라
((DC)(CC)(CC) 이후에 C)
5. 관례를 받아들이라: 세번의 상호 배신 이후에 배신하라
((DD)(DD)(DD) 이후에 D)
------------------------------------------------------------------------------
------------------------------------------------------------------------------
제가 해본 결과는 신기하게도 ((CC)(CC)(CC) 이후에 D)로 진화하
는 개체가 되는군요...^^;; 아마도 어딘가 잘못한듯 싶은데... 혹시
시간 있으신 분은 한번 위 프로그램을 짜보세요...그래서 결과를 올
려 주시면 감사...(제가 한번 보고 싶어서여...^^;;)
-------------
이번에는 유전자 알고리즘의 동작 원리에 대해서 하겠습니다.
우선 스키마란 개념을 알 필요가 있습니다. 스키마란 염색체들 사이의
유사성을 나타낼 수 있는 하나의 전형 입니다. 이것은 '*'기호를 사용해
서 나타내는데 '*'기호에는 어떠한 유전인자와도 대응된다는 표시 입니
다. 예를 들어 (*10101101)은 다음 두개의 염색체와 일치 합니다.
(010101101), (110101101)
다른 스키마 (*101*01010*)은 다음 염색체와 일치 합니다.
(01010010100), (01010010101), (01011010100) (01011010101)
(11010010100), (11010010101), (11011010100) (11011010101)
스키마에서 '*'기호의 갯수가 k개이면 이것에 대응되는 염색체의 갯수
는 2^k개가 됩니다.
그러면은 유전 알고리즘은 #1에서 논의한 대로 선택, 교배연산, 돌연변
이연산을 거치게 됩니다. 우선 선택 연산만 생각하고 어떤 스키마 S가 살
아 남을 확률을 계산해 보겠습니다.
만약 어떤 염색체의 적합도가 상당히 높다면은 그 염색체는 다음세대에
여러개가 생길것이라고 예측할수 있습니다. 예를 들어 염색체가 다음과 같
이 있고, (강좌 #1에서의 문제 입니다)
v[1]: (01101)
v[2]: (01111)
v[3]: (10100)
v[4]: (01101)
v[5]: (10101)
v[6]: (01011)
v[7]: (10111)
v[8]: (10000)
v[9]: (01101)
v[10]: (01011)
각 염색체의 적합도는 다음과 같습니다.
eval(v[1]) = f(13) = 30
eval(v[2]) = f(15) = 50
eval(v[3]) = f(20) = 100
eval(v[4]) = f(13) = 30
eval(v[5]) = f(21) = 110
eval(v[6]) = f(11) = 10
eval(v[7]) = f(24) = 130
eval(v[8]) = f(16) = 60
eval(v[9]) = f(13) = 30
eval(v[10]) = f(11) = 10
위 개체의 총 적합도는 560이고, 평균 적합도는 56이 됩니다. 염색체
v[7]같은 경우에는 평균 적합도의 약 2배정도 됩니다. 이것은 다음 세대
에 염색체 v[7]이 약 2개정도 있을거라고 짐작할수 있습니다. 다음 세대
에서도 v[7]의 적합도가 높다면은 2개에서 4개로 늘어날수 있고, 그 다
음에 8개라는 식으로(실제로는 평균 적합도가 높아져서 이렇게 되기 힘
들겠지만) 될 것이라 생각할수 있습니다. 즉, 어떤 염색체가 평균 적합
도보다 높으면 그것은 다음 세대에서 기하 급수적으로 늘어날 것을 예상
할수 있습니다. 같은 방법으로 염색체가 평균 적합도보다 낮다면은 그것
은 다음 세대에서 기하 급수적으로 줄어 들게 되고, 평균이라면은 같은
수의 염색체들이 다음세대에 살아 있을거라 예상 할수 있습니다.
그러면 스키마 S와 일치하는 염색체들의 적합도의 평균을 구합니다.
이것을 스키마 S의 적합도라 부르겠습니다.
그러면 만약 스키마 S의 적합도가 평균 적합도 보다 크다면 다음 세대
에 스키마 S와 일치하는 염색체는 기하 급수적으로 늘어날 것이고, 평균
이라면 같은수의 염색체가 존재할 것이고, 평균 이하라면은 기하 급수적
으로 줄어들것이라고 예측할수 있습니다.
그러면 선택된 스키마가 교배나 돌연변이 연산에 의해서 파괴될수도
있습니다. 교배연산에서 다음과 같은 스키마가 선택되었다고 합시다.
(***111*****), (111*****01*)
그러면은 교배연산은 각 유전인자의 위치에 대해 골고루 선택될 확률이
높으므로 첫번째 스키마가 파괴될 확률은 두번째 스키마가 파괴될 확률보
다 낮습니다. 엄밀하게 계산하면 첫번째 스키마가 파괴될 확률은 3/11이
고, 두번재 스키마가 파괴될 확률은 10/11이 됩니다.
그리고 또 돌연변이 연산을 하게 됩니다. 돌연 변이할때는 고정된 유전
인자의 개수가 적을수록 스키마가 파괴될 확률이 적어지게 됩니다.(고정된
유전인자의 개수를 차수라고 합니다 : (101*1****)의 차수는 4가 됩니다),
위에 있는 염색체에서 첫번째 스키마의 차수는 3이 되고, 돌연변이 연산에
의해 파괴될 확률은 {1-(돌연변이 확률)}^3이 되고, 두번째 스키마가 돌연
변이에 의해 파괴될 확률은 {1-(돌연변이 확률)}^5가 됩니다.
즉, 이것을을 정리하면
선택 - 평균 이상이면 지수합수적으로 증가한다.
교배및 돌연변이 연산 - 짧고, 낮은 차수의 스키마는 생존율이 높다.
이것으로 부터 다음과 같은 스키마 정리와 구설부 가설이 생기게 됩니다.
------------------------------------------------------------------------------
스키마 정리 - 짧고, 낮은 차수의, 평균 이상의 스키마는 유전자 알고리
즘의 이후 세대에서 지수함수적으로 증가하는 시도를 받는다.
즉, GA는 짧고 낮은 차수의 스키마에 의해서 공간을 탐색한다는 것입니다.
구설부 가설 - 유전자 알고리즘은 구설부라고 불리는 짧고, 낮은 차수의,
고성능 스키마타의 병렬을 통하여 근사 최적 성능을 추구한다.
------------------------------------------------------------------------------
------------------------------------------------------------------------------
수학적인 식들은 다 제거해버리고 썼습니다.
우선 스키마란 개념을 알 필요가 있습니다. 스키마란 염색체들 사이의
유사성을 나타낼 수 있는 하나의 전형 입니다. 이것은 '*'기호를 사용해
서 나타내는데 '*'기호에는 어떠한 유전인자와도 대응된다는 표시 입니
다. 예를 들어 (*10101101)은 다음 두개의 염색체와 일치 합니다.
(010101101), (110101101)
다른 스키마 (*101*01010*)은 다음 염색체와 일치 합니다.
(01010010100), (01010010101), (01011010100) (01011010101)
(11010010100), (11010010101), (11011010100) (11011010101)
스키마에서 '*'기호의 갯수가 k개이면 이것에 대응되는 염색체의 갯수
는 2^k개가 됩니다.
그러면은 유전 알고리즘은 #1에서 논의한 대로 선택, 교배연산, 돌연변
이연산을 거치게 됩니다. 우선 선택 연산만 생각하고 어떤 스키마 S가 살
아 남을 확률을 계산해 보겠습니다.
만약 어떤 염색체의 적합도가 상당히 높다면은 그 염색체는 다음세대에
여러개가 생길것이라고 예측할수 있습니다. 예를 들어 염색체가 다음과 같
이 있고, (강좌 #1에서의 문제 입니다)
v[1]: (01101)
v[2]: (01111)
v[3]: (10100)
v[4]: (01101)
v[5]: (10101)
v[6]: (01011)
v[7]: (10111)
v[8]: (10000)
v[9]: (01101)
v[10]: (01011)
각 염색체의 적합도는 다음과 같습니다.
eval(v[1]) = f(13) = 30
eval(v[2]) = f(15) = 50
eval(v[3]) = f(20) = 100
eval(v[4]) = f(13) = 30
eval(v[5]) = f(21) = 110
eval(v[6]) = f(11) = 10
eval(v[7]) = f(24) = 130
eval(v[8]) = f(16) = 60
eval(v[9]) = f(13) = 30
eval(v[10]) = f(11) = 10
위 개체의 총 적합도는 560이고, 평균 적합도는 56이 됩니다. 염색체
v[7]같은 경우에는 평균 적합도의 약 2배정도 됩니다. 이것은 다음 세대
에 염색체 v[7]이 약 2개정도 있을거라고 짐작할수 있습니다. 다음 세대
에서도 v[7]의 적합도가 높다면은 2개에서 4개로 늘어날수 있고, 그 다
음에 8개라는 식으로(실제로는 평균 적합도가 높아져서 이렇게 되기 힘
들겠지만) 될 것이라 생각할수 있습니다. 즉, 어떤 염색체가 평균 적합
도보다 높으면 그것은 다음 세대에서 기하 급수적으로 늘어날 것을 예상
할수 있습니다. 같은 방법으로 염색체가 평균 적합도보다 낮다면은 그것
은 다음 세대에서 기하 급수적으로 줄어 들게 되고, 평균이라면은 같은
수의 염색체들이 다음세대에 살아 있을거라 예상 할수 있습니다.
그러면 스키마 S와 일치하는 염색체들의 적합도의 평균을 구합니다.
이것을 스키마 S의 적합도라 부르겠습니다.
그러면 만약 스키마 S의 적합도가 평균 적합도 보다 크다면 다음 세대
에 스키마 S와 일치하는 염색체는 기하 급수적으로 늘어날 것이고, 평균
이라면 같은수의 염색체가 존재할 것이고, 평균 이하라면은 기하 급수적
으로 줄어들것이라고 예측할수 있습니다.
그러면 선택된 스키마가 교배나 돌연변이 연산에 의해서 파괴될수도
있습니다. 교배연산에서 다음과 같은 스키마가 선택되었다고 합시다.
(***111*****), (111*****01*)
그러면은 교배연산은 각 유전인자의 위치에 대해 골고루 선택될 확률이
높으므로 첫번째 스키마가 파괴될 확률은 두번째 스키마가 파괴될 확률보
다 낮습니다. 엄밀하게 계산하면 첫번째 스키마가 파괴될 확률은 3/11이
고, 두번재 스키마가 파괴될 확률은 10/11이 됩니다.
그리고 또 돌연변이 연산을 하게 됩니다. 돌연 변이할때는 고정된 유전
인자의 개수가 적을수록 스키마가 파괴될 확률이 적어지게 됩니다.(고정된
유전인자의 개수를 차수라고 합니다 : (101*1****)의 차수는 4가 됩니다),
위에 있는 염색체에서 첫번째 스키마의 차수는 3이 되고, 돌연변이 연산에
의해 파괴될 확률은 {1-(돌연변이 확률)}^3이 되고, 두번째 스키마가 돌연
변이에 의해 파괴될 확률은 {1-(돌연변이 확률)}^5가 됩니다.
즉, 이것을을 정리하면
선택 - 평균 이상이면 지수합수적으로 증가한다.
교배및 돌연변이 연산 - 짧고, 낮은 차수의 스키마는 생존율이 높다.
이것으로 부터 다음과 같은 스키마 정리와 구설부 가설이 생기게 됩니다.
------------------------------------------------------------------------------
스키마 정리 - 짧고, 낮은 차수의, 평균 이상의 스키마는 유전자 알고리
즘의 이후 세대에서 지수함수적으로 증가하는 시도를 받는다.
즉, GA는 짧고 낮은 차수의 스키마에 의해서 공간을 탐색한다는 것입니다.
구설부 가설 - 유전자 알고리즘은 구설부라고 불리는 짧고, 낮은 차수의,
고성능 스키마타의 병렬을 통하여 근사 최적 성능을 추구한다.
------------------------------------------------------------------------------
------------------------------------------------------------------------------
수학적인 식들은 다 제거해버리고 썼습니다.
[출처 : http://zzpark.egloos.com/5508970]