유전자 알고리즘은 어떻게 동작하는가?

(How Do Genetic Algorithms Work?)

 

유전자 알고리즘은 설명하고 프로그램하기 간단하지만, 그 행동이 복잡해질 수 있으며,  어떻게 동작하는가 그리고 어떠한 종류의 문제에 가장 적합한 것인지에 관한 많은 문제가 미해결 상태로 남아 있다. GA 에 관한 이론적인 기초에 많은 연구가 행해졌다. (Holland 1975; Goldberg 1989a; Rawlins 1991; Whitley 1993b; Whitley and Vose 1995). 4 장에서는 몇 가지 이들 연구를 자세히 소개한다. 여기서는 몇 가지 근본적인 개념들을 간단히 살펴보기로 한다.

GA 의 전통적인 이론 (Holland 1975 에서 처음으로 공식화된) 은 아주 일반적인 수준의 설명에서 GA 가 아주 병렬적인 형태로 해의 좋은 "구성부 (building blocks)" 들을 찾아내고, 강조하고, 그리고 재결합함으로써 동작한다고 가정하였다. 여기서의 아이디어는 좋은 해는 구성부 - 이것들이 포함되어 있는 문자열이 높은 적합도를 가지도록 하는 비트 값들의 조합 - 들로 구성되는 경향이 있다는 것이다.

Holland (1975) 는 비공식적인 개념인 "구성부" 를 공식화하기 위하여 스키마 (또는 스키마타 (schemata)) 의 개념을 소개하였다. 스키마는 1 과 0, 그리고 "상관없음 (don't cares)" 을 나타내는 별표 (*) 로 구성되는 형태로 표현될 수 있는 비트 문자열들의 집합이다. 예를 들어 스키마 H = 1****1 은 1 로 시작하고 1 로 끝나는 모든 6 비트 문자열들을 나타낸다. (이 절에서는 Goldberg (1989a) 의 표현을 사용하는데, H 는 "초평면 (hyperplane)" 을 나타낸다. 스키마는 ℓ 비트 문자열의 ℓ 차원 공간에서의 초평면들 (여러 차원의 평면들) 을 나타내므로 H 는 스키마를 나타내는데 사용된다.) 이 형태에 적합한 문자열들 (예를 들어 100111 과 110011) 은 H 의 실례 (instances) 라고 한다. 스키마 H 에는 두 개의 정의된 비트 (별표가 아닌 비트) 가 있다고 하고, 또는 다른 표현으로 차수가 2 라고 한다. 정의길이 (defining length) (맨 바깥쪽에 정의된 비트사이의 거리) 는 5 이다. 여기서 "스키마" 라는 용어는 그 형태 자신과 그 형태에 의해 표현되는 문자열의 부분집합을 모두 가리키고 있다. 이후에서 이 용어의 의미는 문맥에서 분명해질 것이다.

길이 ℓ 비트 문자열의 모든 가능한 부분집합이 스키마를 나타낼 수 있는 것은 아니라는 것을 주의해야 한다. 사실 굉장히 많은 것들이 나타낼 수 없다. 길이 ℓ 의 모든 가능한 개의 비트 문자열들이 있고 따라서  개의 가능한 문자열들의 부분집합이 있지만 단지 개만이 가능한 스키마가 된다. 그러나 전통적인 GA 이론의 중심 이론에서 스키마는 암시적으로 GA 가 선택, 돌연변이, 그리고 일점 교배의 연산자들을 가지고 효과적으로 처리하는 구성부들을 의미한다.

GA 가 어떻게 스키마를 처리하는가? 주어진 길이  ℓ 의 비트 문자열은  가지 다른 스키마들 중 하나이다. 예를 들어 문자열 11 은 **(길이 2 의 모든 4 가지 가능한 비트 문자열들), *1, 1*, 그리고 11 (단 하나의 문자열을 포함하고 있는 스키마) 의 한 실례이다. 그래서 주어진 집단의 n 개의 문자열은  개와 개의 다른 스키마들 사이의 실례들을 포함한다. 만일 모든 문자열들이 동일하다면 정확히  개의 다른 스키마들이 실례가 존재한다, 그렇지 않으면 그 수는 보다 작거나 같다. 이것은 주어진 세대에서 GA 가 그 집단에서 n 개의 문자열의 적합도를 분명하게 평가하는 동안 훨씬 많은 수의 스키마들의 평균 적합도를 암시적으로 예측하는 것이며, 스키마의 평균 적합도는 그 스키마의 모든 가능한 보기의 평균 적합도로 정의된다. 예를 들어 랜덤하게 생성된 n 개 문자열의 개체집단에서 평균적으로 절반의 문자열은 1***...* 의 실례일 것이고, 절반은 0***...* 의 실례일 것이다. 1***...* 의 실례들인 약 n/2 문자열들의 평가는 그 스키마의 평균 적합도의 예측값을 제공한다. (전형적인 크기의 개체집단에서 평가되는 실례들은 단지 모든 가능한 보기들의 작은 표본에 불과하므로 이것은 예측이다.) GA 에 의해서 스키마들이 분명하게 표현되거나 평가되지 않는 것처럼, 스키마의 평균 적합도의 예측값도 GA 에 의해서 분명하게 계산되거나 저장되지 않는다. 그러나 이후에서 볼 수 있듯이, GA 의 행동은 개체집단에서 주어진 스키마의 많은 실례들의 개수의 증가와 감소에 의해서 이들 평균값들을 실제로 계산하고 저장하는 것처럼 설명될 수 있다.

우리는 스키마 보기들의 증가와 감소의 대략적인 동력학을 다음과 같이 계산할 수 있다. H 를 주어진 시간 t 에서 개체집단에 존재하는 적어도 하나의 문자열이라고 하자. m (H, t) 를 시간 t 에서 H 의 실례들의 수, 그리고 û(H, t) 를 시간 t 에서의 H 의 관측된 평균 적합도 (즉 시간 t 에서 개체집단에서 H 의 보기의 평균 적합도) 라고 하자. 우리는 시간 t + 1 에서의 H 의 실례들의 기대수인 E(m(H, t+1)) 을 계산하고자 한다. 앞에서 설명한대로 선택되었다고 가정하자. 문자열 x 의 자손의 기대수는 인데, 여기서 는 x 의 적합도이고 는 시간 t 에서 개체집단의 평균 적합도이다. x 가 시간 t 에서 개체집단내에 존재, 즉 x ∈ H 가 "x 가 H 의 실례이다" 를 의미한다고 하고, 우선 교배와 돌연변이의 영향을 무시하면, 시간 t 에서 개체집단내의 x 에 대해 이므로, 정의에 의해서

이다. 그래서 GA 가 를 명확하게 계산하지 않는다고 하더라도 개체집단에서 스키마 실례의 증가 또는 감소는 이 양에 따라 좌우된다.

교배와 돌연변이는 H 의 실례들을 모두 없애거나 만들어낼 수 있다. 우선 교배와 돌연변이의 파괴적인 영향들 - H 의 보기의 수를 감소시키는 것들만을 포함시키자. 이 효과들을 포함하여, 우리는 식 (1.1) 의 우변을 수정하여 의 하한을 구한다. 한 문자열에 일점 교배가 행해지는 확률을 라고 하고, 스키마 H 의 한 실례가 부모로 선택되었다고 가정하자. 만일 한 자손이 또한 스키마 H 의 실례이면 스키마 H 는 일점 교배하에서 "생존 (survive)" 하였다고 한다. 우리는 H 가 1 점 교배에서 생존하는 확률 의 하한을 구할 수 있다.

여기서 는 H 의 정의길이이고 ℓ 은 탐색공간에서의 비트 문자열의 길이이다. 즉, H 의 정의길이 내에서 일어나는 교배는 H 를 파괴시킬 수 있다. (즉, H 의 보기가 아닌 자손을 만들어 낼 수 있다.) 따라서 우리는 H 가 가지고 있는 문자열의 일부분을 교배확률과 곱하여 그것이 파괴될 확률의 상한을 얻는다. (만일 두 개의 동일한 문자열들이 서로 교배되면 스키마의 정의된 위치 내에서의 교배는 그것을 파괴하지 않으므로 이 값이 상한이다.) 이 값을 1 에서 빼면 생존확률 의 하한이 된다. 간략히 말하여 교배하에서의 생존확률은 짧은 스키마에서 더 높다.

돌연변이의 파괴적인 효과는 다음과 같이 정량화될 수 있다. 을 어떤 비트가 돌연변이될 확률이라고 하자. 그러면 스키마 H 가 자신의 실례의 돌연변이 하에서 생존할 확률 는 와 같다. 여기서 는 H 는 차수이다. (즉 H 에서 정의된 비트의 수) 즉 각 비트에 대해서 그 비트가 돌연변이 되지 않을 확률은 이다. 그래서 스키마 H 의 정의된 비트가 돌연변이 되지 않을 확률은 자신을 o(H) 번 곱한 양이다. 간략히 말하여 돌연변이 하에서 생존할 확률은 낮은 차수 스키마에 대해서 더 높다.

이러한 파괴적인 효과는 식 (1.1) 을 수정하는데 사용될 수 있다.

이것은 스키마 정리 (Schema Theorem) 로 알려져 있다 (Holland 1975, Gold-berg 1989a). 이것은 한 세대에서 다음세대로의 스키마의 성장을 설명한다. 스키마 정리는 평균 적합도가 평균값 이상인 짧고 낮은 차수의 스키마들이 시간에 따라 지수적으로 증가하는 표본의 수를 받는다는 것을 암시한다고 흔히 해석된다. 그 이유는 적합도에 있어 평균이상인 그들 스키마의 표본의 수가 매 세대마다 에 비례하여 증가하기 때문이다. (이 해석에 대한 몇몇 경고가 있는데, 그것들은 4 장에서 논의될 것이다.)

식 (1.2) 에서 언급된 스키마 정리는 교배와 돌연변이의 파괴적인 효과만을 취급하고 있으므로 이것은 하한이다. 그러나 교배는 좋은 스키마의 보기들을 재결합하여 동등하거나 더 좋은 고차 스키마의 예들을 구성하는 능력을 가지고 있으며 GA 의 능력의 주된 원천이라고 믿어지고 있다. 이것이 GA 가 작동하는 과정이라는 가정이 "구성부 가설 (Building Block Hypothesis)" 로 알려져 있다. (Goldberg 1989a) (이러한 교배의 "건설적인 (constructive)" 능력을 정량화하는 연구에 대해서 Holland 1975, Thierens 와 Goldberg 1993, 그리고 Spears 1993 을 참조하라.)

n 문자열의 개체집단을 평가하는데 있어서 GA 는 이 개체집단에 존재하는 모든 스키마들의 평균 적합도를 함축적으로 예측하고 있고, 스키마 정리에 의하여 그들의 표현을 증가시키거나 감소시킨다. n 문자열의 개체집단에서 많은 수의 스키마들을 동시에 함축적으로 평가하는 것을 함축적 병렬성 (implicit paralleism) 이라고 한다 (Holland 1975). 선택의 영향은 점차적으로 적합도가 평균이상인 스키마의 실례를 위한 표본추출 과정에 치우치게 된다. GA 는 그러한 스키마의 실례를 점점 더 많이 표본추출하므로 시간이 지날수록 한 스키마의 평균 적합도의 예측값은 원리적으로 점점 더 정확해 진다. (정확성이 증가하는 개념에 대한 몇몇 반례들이 4 장에서 논의될 것이다.)

스키마 정리와 구성부 가설은 GA 에서 선택과 교배의 역할을 주로 취급한다. 무엇이 돌연변이의 역할인가? Holland (1975) 는 돌연변이가 주어진 비트 위치에서 다양성의 상실을 방지하는 것으로 제안하였다. 예를 들어 돌연변이가 없다면 개체집단에서 모든 문자열이 첫 번째 비트 위치에서 1 을 갖게 될 것이고 0 으로 시작하는 문자열을 얻는 방법이 없게 될 것이다. 돌연변이는 그러한 고착화에 대한 "보험증권 (insurance poticy)" 을 제공한다.

식 (1.1) 에서 주어진 스키마 정리는 단지 스키마뿐만 아니라 탐색공간내의 어떠한 문자열의 부분집합에도 적용된다. 특별히 스키마에만 집중하는 이유는 특히 짧고 높은 평균 적합도를 가진 스키마들이 일접 교배에 의해 효과적으로 결합되는 구성부의 형태에 대한 좋은 설명이다. 이와 같은 GA 의 공식화는 스키마가 좋은 해를 위한 적절한 구성부의 좋은 결합이 될 것이라고 믿는 것이다. GA 연구자들은 다른 형태의 구성부를 다루는 여러 형태의 교배 연산자들을 정의하였고, 주어진 교배 연산자들이 효과적으로 다룰 수 있는 일반화된 "스키마" 를 해석하였다  (Radcliffe 1991; Vose 1991).

스키마 정리와 GA 의 행동에 대해 알려져 있는 몇몇 함축적 의미들은 최근 GA 학계에서 아주 중요한 논쟁의 주제가 되어왔다. 이러한 비평과 그들에 비해 착상된 GA 이론에 대한 새로운 접근방식들은 4 장에서 논의될 것이다.