유전자 알고리즘 : 정환묵

유전자 알고리즘

유전자 알고리즘 은 생물의 유전과 진화 메카니즘을 공학적으로 모델화하여 문제 해결이나 시스템의 학습 등에 응용하려고 한 것이다. 여기서는 공학적인 유전자 알고리즘을 근본적으로 이해하기 위해서 생물의 유전과 진화를 설명하고 예를 통하여 유전자 알고리즘의 원리를 습득한다.

진화적 연산

유전자 알고리즘 또는 진화적 알고리즘은 자연세계의 진화현상에 기반한 계산 모델이다. 진화알고리즘은 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 생성한다. 각각의 가능한 해를 하나의 유기체(organism) 또는 개체(indivisual)로 보며 이들의 집합을 개체군(population)이라 한다. 하나의 개체는 보통 한 개 또는 여러 개의 염색체(chromosomes)로 구성되며 염색체를 변형하는 연산자들을 유전연산자라 한다. 진화알고리즘은 탐색, 최적화 및 기계학습을 도구로 많이 사용한다. 진화적 연산(evolutionary computation)은 주로 다음의 문제해결 전략에 의해 특징 지울 수 있다([표 1참조]).

◈ 유전자 알고리즘(유전자 알고리즘 : GA)

◈ 유전자 프로그래밍(Genetic Programming : GP)

◈ 진화적 프로그래밍(Evolutionary Programming : EP)

◈ 진화적 전략(Evolutionary Strategy : ES)

이상의 기원은 19세기의 Charles Darwin의 진화론에 의한 것으로 자연선택과 적자생존(natural selection and survival of fittest)을 기초로 한 생물학적 관찰 제안이다. 따라서, 현재 이와같은 알고리즘을 진화적 알고리즘(evolutinary algorithm : EA)이라 부른다. 진화적 연산중에는 개체의 집단에 관한 유전의 변화의 모델에 기초한 다수의 방법론과 기술이 포함되어 있다. 현재 인공생명이나 생물학등의 분야에 있어서 GA, GP, EP, ES라는 진화적 접근(approch)이 다수 사용되고 있다.

[표 1] 진화 알고리즘의 종류
이 름	문제 표현 방식			주연산자	기 원	주 응용분야
유전자 알고리즘(GA)	0/1	스트링	길이고정	crossover	Holland, J.H.(1975)	문자열, 벡터열탐색
진화전략(ES)	실수	벡터	길이고정	mutation	Rechenberg, I.(1963)	실수치 탐색
진화 프로그래밍(EP)	이산치	그래프	크기고정	mutation	Fogel, L.J.	오토마톤 합성
유전자 프로그래밍(GP)	기본함수	트리	크기가변	crossover	Koza, J.(1990)	프로그램 합성

진화적 연산에 있어서 중심으로 되는 것은 거의 Darwinian이론의 단순화된 메카니즘의 응용이다. 특히 대부분의 응용은 다음 3가지의 기본적인 구성요소를 갖고 있다.

◈ 적응도(fitness) : 개체가 장래의 세대에 영향을 주는 범위를 결정한다.

◈ 생식 오퍼레이타(reprodution operator) : 개체가 다음세대에 자손을 생성한다.

◈ 유전자 오퍼레이타(genetic operator) : 부모의 유전자 정보로부터 자손의 유전자

정보를 결정한다.

진화적 연산은 컴퓨터를 사용한 문제해결시스템의 설계와 실행에 진화적 프로세스를 사용한다. 현재까지 여러 가지 진화적 프로세스의 연산모델이 제안되어 있다. 이들은 주로 3가지의 진화적 프로세스 즉, 선택(selection), 돌연변이(mutation), 생식(reproduction)을 사용한다.

■ 진화적 알고리즘과 종래의 최적화벙법의 차이점

진화적 알고리즘은 포인트로부터 포인트로의 해를 구하는 국소 탐색법이 아니고 개체군으로 해를 구하는 최적해 탐색법이다.

◈ 진화적 알고리즘은 목적함수의 연속성과 미분가능성에 관계없이 적용한다.

◈ 진화적 알고리즘은 결정법칙이 아닌 확률적으로 변화하는 법칙을 사용한다.

■ 진화적 전략(evolutionary strategy)

진화적 전략은 무성생식에서 유기체의 발달을 simulation 한 것이다. 유전자 알고리즘이 교배방법에 의한 해의 재결합인 것에 대하여 진화적 전략은 돌연변이와 선택방법만을 사용한다.

ES는 GA와 다른 실 파라미터를 사용한다. 여기서 ES에 관하여 보다 깊게 이해하기 위하여 Schwefel에 의해 제안된 -ES에 대하여 설명한다.

단계 1

초기화 : 부모벡터의 초기화된 개체집단 X_i(i=1, …, μ)는 실행범위로부터 랜덤하게 선택된다.

단계 2

돌연변이 : 자손벡터 X_i(j=1, …, μ)는 각각의 X_i의 구성에 대한 Gaussian의 랜덤인 변화를 기하는 것에 의해 각각의 부모 X_i로부터 만들어진다.

단계 3

평가 : X_i와 X_j의 적응도를 평가한다.

단계 4

선택 : 다음세대의 새로운 부모를 그들의 적응도로 기초한 개체집단으로부터 선택한다.

단계 3

(단계2)로부터 (단계4)까지를 해가 수렴할 때까지 반복한다.

■ 진화적 프로그래밍(evolutionary programming)

진화적 프로그램은 -ES와 유사하다. 그러나 확률적인 토너멘트를 사용한 해의 변화를 강조하고 있다. 확률적인 토너멘트에서는 개체가 서로 다음 세대에 선택된 과정을 직접 연산한다. 따라서 하나의 낮은 적응도를 가진 개체는 만일 상대방 개체의 적응도가 낮으면 선택될 가능성이 높게 된다. 진화적 프로그램을 사용한 최적해를 얻는 방법은 다음과 같다.

단계 1

초기화 : 부모벡터의 초기화된 개체집단 X_i(i=1, …, μ)는 실행범위로부터 랜덤하게 선택된다.

단계 2

돌연변이 : 자손벡터 X_i(j=1, …, μ)는 각각의 X_i의 구성에 대한 Gaussian의 랜덤인 변화를 기하는 것에 의해 각각의 부모 X_i로부터 만들어진다.

단계 3

평가 : X_i와 X_j의 적응도를 평가한다.

단계 4

경합 : q개의 경합자를 X_i와 X_j중에서 랜덤하게 선택한다. 그 다음에 각 개체의 적응도와 경쟁 상대방을 비교하여 무게 계수 W_i(j=1,…, μ)를 계산한다.

단계 5

선택 : 그들의 무게에 의해 다음 세대의 새로운 부모가 선택된다.

단계 6

(단계2)로 부터 (단계5)까지를 해가 수렴할 때까지 반복한다.

생물의 유전과 진화의 원리

유전자 알고리즘 (GA) 이란 자연계에 있어서 생물의 유전과 진화의 메카니즘을 공학적으로 모델화하는 것에 의해 생물이 갖는 환경에서 적응능력을 취급하는 것이고, 1970년대 초기에 John Holland(당시 Michigan대학교수)에 의해 제안된 자연도태의 원리를 기초로한 최적화 방법이다. 즉, 유전자 알고리즘은 자연계의 진화현상을 기반으로 만들어진 계산모델로써 풀고자하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 생성하게 된다. 유전자 알고리즘은 탐색 및 최적화, 기계학습의 도구로 많이 사용되고 있다. 그러므로 공학적인 유전자 알고리즘을 근본적으로 이해하기 위해서 우선 생물의 유전과 진화에 대해서 설명한다.

일반적으로 생물은 환경에 잘 적응할 수 있다면 생명의 존속과 증식이 가능하다. 증식을 할 때에는 자기자신이 가지고 있는 생물로서의 설계 정보를 몇 가지의 형태로 자손들에게 전수해야만 한다. 이러한 설계 정보는 유전자에 써넣는다.

단세포 생물과 같은 하등생물에 있어서는 증식은 체세포 분열에 의해 행해진다. 이 경우, 유전자는 복사되어 후손에게 전달된다. 하등생물은 후천적으로 획득된 것이 매우 적기 때문에 자손은 원리적으로 아주 같은 성질을 가진다. 그 결과, 많은 세대를 거쳐도 거의 변화하지 않은 생물이 만들어져 간다.

고등생물에서는 증식은 적자생존에 의해서 행해지기 때문에 아버지와 어머니쪽의 유전자가 혼합이 되게 된다. 따라서 똑같은 개체는 생성되지 않고, 조금씩 다른 개체가 생성되므로 이 세대에 자신과 똑같은 인간은 만들어지지 않는 것이다(일란성 쌍둥이는 유전적으로는 똑같지만 후천적인 개체 형성의 과정에 있어서 차례로 개체 사이에 차이가 생긴다. 그러나, 유전자 알고리즘의 원리를 학습하는 것이 목적이기 때문에 더 이상의 논의는 생략한다).

고등생물은 [표 2]에 나타낸 바와 같이 개체 기능의 종합적 제어를 수행하는 뇌신경계로부터 내분비계, 효소계, 면역계 등의 우수한 제어 기구를 가지고 있다. 특히 뇌신경계는 후천적인 경험이나 학습에 의해 크게 발달한다.

[표 2] 고등생물의 제어 기구
제 어 계	제어 내용
뇌신경계	개체 기능의 종합적 제어
내분비계	호르몬에 의한 제어
효 소 계	생체 반응의 제어
면 역 계	외부로 부터의 방어

그러나 경험이나 학습을 받아들이는 기구는 태어날 때부터 구비되어 있다. 즉 고등 생물은 선천적인 유전자에 의한 정보 전달과 후천적인 경험이나 학습, 적응 등의 2가지 요소에 의해 형성되는 것이다. 그 때문에 같은 종류의 생물도 각각 미묘하게 다르고, 보다 우수한 개체가 생성될 가능성이 높다.

또한 고등생물, 하등생물에 관계없이 유전자의 복사를 수행할 때에는 미묘한 오류(error)가 생길 가능성이 있다. 이것에 대해 돌연변이(Mutation)가 생기고, 생물의 다양성이 확대된다.

이상을 정리하면, 우선 부모로 부터 유전자에 의해 생물로서의 정보 전달이 행해진다. 다음세대에는 각 개체 중에서도 보다 우수한 즉, 환경에 적응도가 높은 개체의 유전 정보가 우선적으로 전해진다. 적응도가 낮은 개체는 수명이 짧고, 증식할 수 없게 되기 때문이다. 동시에 적응도가 낮은 종족도 자연 도태되어 간다. 이러한 원리에 기초하여 세대를 거듭해 가면 차례로 환경에 적응도가 높은 개체가 많아진다. 이것이 유전과 진화의 기본적인 원리이다.

실제의 유전자

여기서는 알고리즘의 이해에 도움이 되는 생물학적인 배경에 대해 설명한다. 생물은 세포로 구성되고, 그 세포에는 핵이 있으며 그 핵 중에는 염색체(chromosome)라는 것이 있다. 사람의 체세포의 경우에는 46개의 염색체가 있고, 염색체는 주로 DNA로 구성되어 있다.

이 DNA는 4종류의 염기라고 부르는 화학 물질이 중요한 구성 요소며, DNA가 가지는 정보는 이들 4종류의 염기의 구성 방법에 있다. DNA는 2중 나선구조로 되어 있으며, 이들이 복잡하게 겹쳐져서 염색체를 구성하고 있다.
[그림 1]에 나타낸 바와 같이 유전자(gene)란 유전정보를 담당하는 DNA를 말한다. 특정의 유전자는 염색체의 특정 위치에 존재하고, 그 장소를 그 유전자의 자리(locus)라고 부르는 일종의 좌표에 의해 규정되며 유전자가 취하게 되는 유전자의 후보를 대립유전자(형질 : allele)라고 한다.

[그림 1] 염색체, 유전자, 유전자 자리

결국 유전정보는 염색체상에서의 위치(유전자 위치)와 염기의 배열에 의해 표현되는 것이다. 하나의 유전자 위치에 관한 유전자의 조합을 유전자형(genotype)이라고 한다. 또한 어느 형질이 어떤 유전자에 의해서 대개 결정될 때, 그 형질을 유전자의 표현형(phenotype)이라고 한다. 표현형은 실제로는 다른 유전자나 환경 등에서 어느 정도 변하는 것도 있다. 유전자 알고리즘에서는 염색체를 1차원으로 간단화한다. 결국 기호(symbol)나 수치를 1차원으로 나열하고, 그것을 염색체로 취급한다. 그리고 1차원 상에서의 위치를 유전자의 자리로서 취급한다. 표현형을 유전형으로 바꾸는 것은 코드화(coding), 그 역을 디코드화(decoding)라고 한다.

최근 유전자 공학의 진보에 의해 인간의 염색체의 해명이 이루어지고는 있지만, 염색체가 가지는 정보량은 매우 많기 때문에 전체로 보면 아직 많은 발전이 있어야 할 것이다.

[표 3] 생물학과 유전자 알고리즘의 용어 비교
생 물 학	유전자 알고리즘
염색체(chromosome)	문자열(string)
유전자(gene)	특성(feature), 형질(character)
대립 유전자(allele)	특성치(feature value)
유전자 자리(locus)	문자열의 위치(string position)
유전형(genotype)	구조체(structure)
표현형(phenotype)	파라메터 집합(parameter set)
	대체해(alternative solution) 디코드화를 위한 구조체(a decoded structure)

인간의 3가지 기억 시스템

지구상에서 가장 고도로 진화한 생물인 인간은 다음의 3가지 기억 시스템을 가진다고 말 할 수 있다.

① 유전에 의한 기억
② 뇌에 의한 기억
③ 외부 기억에 의한 기억(문자의 이용)

이들 중에서 문자를 이용한 기억은 유전이나 뇌에 의한 기억과는 다르고, 인간의 개체외에 존재하는 인류 특유의 기억 방법이다. 문자는 인류 최대의 발명이고, 이것에 의해 문화나 기술을 넓히고, 후세에 남기는 것이 용이하게 되었다. 결국 공간적, 시간적으로 쉽게 넓힐 수 있게 되었다. 이와같이 인류는 문자에 의해 과학과 의학, 사회 시스템, 다양한 기술 등을 발달 시킬 수가 있고, 환경으로의 적응도를 높인다고 말할 수 있다. 최근에는 멀티미디어의 보급에 의해 화상정보나 음성정보도 마찬가지 역할을 담당하고 있다.

유전에 의한 기억과 뇌에 의한 기억

유전자 알고리즘은 유전자 공학과는 달리 실제 생물을 취급하는 것이 아니며 유전자에 어떤 조작을 첨가하여도 위험하지 않다. 예를들면 내력이 좋지 않은 개체를 바로 도태시키거나 돌연변이를 많이 행해도 관계는 없다.

그런데 실제 자연계에서 과격한 돌연변이를 수행하는 것은 매우 위험하다. 모처럼 우수한 종이 생겨도 머지 않아 멸종되고 만다. 사람의 경우에도 돌연변이에서 우수한 개체가 발생하는 것 보다도 염색체 이상에 의한 병에 약한 개체가 될 수 있는 가능성이 높다. 따라서 자연계에서 유전자의 돌연변이의 비율은 작아진다.

그러나 돌연변이의 비율이 작아져도 유전자 전체의 양이 많아진다면 어떻게 될까? 돌연변이를 하는 유전자의 수는 많게 되고, 그 종류의 존속이 위험하게 된다.

사람의 뇌는 성장과 함께 신경세포(뉴런)끼리의 결합이 증가해 가고, 많은 것은 하나의 신경 세포가 20만개의 결합을 가지고 있다고 한다. 이러한 결합 정보를 모두 유전자로서 전하도록 하면 어떻게 될까? 유전자 전체의 정보량은 매우 많게 되고, 돌연변이를 하는 유전자의 수도 그것에 따라서 매우 많아지고 만다. 그 결과 신경 세포의 결합부의 많은 오류가 생겨 버리고 회복 불가능하게 된다. 이것에 의해 많은 개체는 멸종하게 된다. 신경세포끼리의 결합은 후천적인 학습에 의해 행해지도록 된 것이다. 이것을 "뇌의 가소성"이라 한다.

유전자 알고리즘 의 프로세스

유전자 알고리즘을 처음 공부하는 사람을 위하여 유전자 알고리즘에 대하여 간단히 정리하면 다음과 같다. 유전자 알고리즘 은 어떤 범위 내에서 정의되어 있는 변수 x에 대한 함수 f(x)의 최대치 혹은 최소치를 준 x의 값을 고속으로 구하기 위한 최적화 탐색 알고리즘의 일종이다. GA는 생물의 진화과정에 힌트를 얻은 비교적 단순한 기본 원리를 기초로 하여 거의 대부분의 최적화 탐색 문제에 적용 가능한 알고리즘이다.

GA는 유전자를 갖는 가상적인 생물의 집단을 컴퓨터 내에 설정하여 미리 정해진 환경에 적응하고 있는 개체가 자손을 남길 확률이 높게 되도록 세대교체 시뮬레이션을 실시하여 유전자 및 생물집단을 "진화" 시킨다. 유전자 알고리즘의 기본적인 조작에는 다음의 3가지가 있다. 유전자 알고리즘이란 진화와 그것을 구성하고 있는 유전조직의 정보처리 모델이다.

◈ 선택(selection) : 집단 중에서 적응도의 분포에 따라서 다음의 단계로 교배를 행하는 개체의 생존 분포를 결정한다. 적응도의 분포에 기초하고 있기 때문에 적응도가 높은 개체일수록 보다 많은 자손을 남기기 쉽게 된다.

◈ 교배(crossover) : 2개의 염색체 사이에서 유전자를 바꾸어 넣어 새로운 개체를 발생시킨다.

◈ 돌연변이(mutation) : 유전자의 어떤 부분의 값을 강제적으로 변화시킨다.

실제로는 [그림 2]와 같은 흐름으로 처리가 수행된다.

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

단계 1

유전자형의 결정

유전자 알고리즘에서 유전자 요소는 DNA가 아니라 기호열이다. 따라서 우선대상으로 하는 문제를 유전자형으로 표현해야만 한다. 유전자의 어디에 어떤 수치, 문자를 배당하여 가는가를 결정하는 것이다. 역시 "대상으로 하는 문제"로부터 "기호열"이라고 하는 변환을 수행하는 것이다. 이것을 코딩이라고 한다. 유감스럽게도 이 일반적 방법은 아직 확립되어 있지 않고, 설계자의 숙달이나 경험에 달려있다.(GA의 과제로 되는 사상의 모델화)

단계 2

초기 유전자 집단의 결정

유전자 알고리즘의 큰 특징으로 많은 개체에 의한 상호적인 처리를 들 수 있다. 우선 단계 1에서 결정된 유전자형에서 요소가 다른 다양한 개체를 발생 시킨다. 개체의 수는 문제의 난이도나 성질에 의존하지만 일반적으로 수십개 이상 발생시킨다. 너무 적으면 병렬적 처리를 특징으로 하는 유전자 알고리즘의 장점이 발휘되지 않는다. 반대로 너무 많으면 한세대 당 연산량이 많아지기 때문에 낭비가 많아진다. 이것도 설계자의 숙달과 경험에 달려있다.(결정한 유전자형을 중심으로한 일정범위내에서의 변화를 인정한 복수의 생물개체의 생성처리)

단계 3

각 개체의 적응도의 평가

지금부터 유전자 알고리즘의 핵심적인 내용에 관하여 설명한다. 유전자 알고리즘에서는 "적응도"가 매우 중요한 요소가 된다. 여기서는 각 개체의 적응도를 미리 결정한 방법으로 연산한다. 집단중에 미리 결정한 기준을 만족하는 개체의 유무를 체크하고 있으면 종료하고, 그렇지 않으면 다음 단계로 간다.(적응환경에 관한 적응도의 산정처리)

단계 4

선 택

단계 3에서 결정한 적응도에 기초하여 다음 단계에서 교배를 수행하는 개체의 생존 분포를 결정한다. 단계 4는 "도태처리"와 "중식처리" 단계로 생각할 수 있다.
? 도태처리 : 각 개체의 평가에 기초하여 각 개체마다의 삭제처리
? 증식처리 : 도태처리에 의해 감소한 집단수를 랜덤샘풀링에 의해 개체를 증식시켜 집단 수를 증가하는 처리

단계 5

교배처리

2개의 염색체 사이에서 유전자를 바꾸어 넣어 새로운 개체를 발생시킨다.(유전자형으로서 정의되어 있는 정보를 개체사이에 바꾸어 넣는 처리)

단계 6

돌연변이 처리

유전자의 어떤 부분의 값을 강제적으로 바꾸고, 유전자 집단으로서의 다양성, 결국 흩어짐을 크게 한다. 이렇게 함으로써 보다 좋은 해를 가지는 개체의 발생을 기대하는 것이다. 물론 이 돌연변이의 비율을 너무 크게 하면 나쁜 방향으로 변이의 확률도 크게 되고, 해를 좀처럼 구할 수 없게 된다.(유전자형으로서 정의되어 있는 유전자정보의 기호열을 특정의 확률(변이율)로 변화시키는 처리)

단계 7

반 복

단계 3으로 되돌아 가고, 각 개체의 적응도를 평가한다.

여러가지 선택법

1.4에서 서술했듯이 유전자 알고리즘에는 선택, 교배, 돌연변이 3가지의 기본적인 조작이 있다. 여기에서는 선택에 대해 자세히 설명한다. 선택은 집단 중에서 적응도의 분포에 따라 다음 단계로 교배를 수행하는 개체의 생존 분포를 결정하는 것이다. 기본적인 선택 방법은 다음과 같으며, 이들이 조합되어 사용되는 것도 있다.

(1) 적응도 비례 방식
선택 중에서도 가장 기본적인 방식으로, 각 개체의 자손은 그 적응도에 비례한 확률로 선택될 수 있다. 따라서 적응도가 큰 개체일수록 선택되기 쉽고, 다음 단계의 교배에 참가할 수 있는 가능성이 높아진다.

(2) 에리트 보존 방식 (elitism)
에리트 보존 방식은 개체 중에서 가장 적응도가 높은 개체는 그대로 다음 세대에 남는 방법이다. 어떤 세대에서의 개체는 교배나 돌연변이에 의한 변형을 받지 않고 다음 세대에 전달된다. 그러나 경우에 따라서 원래는 아주 질이 좋지 않은 유전자가 집단 중에 널리 퍼져 버릴 위험성이 있다. 그 때문에 다른 방식, 예를 들면 다음에 설명하는 기대치 방식 등과 조합하여 사용할 수 있다.

(3) 기대치 방식
(1)의 적응도 비례 방식은 적응도로 부터 구해진 확률에 기초하는 선택 방식이었다. 이 경우 만일 개체수가 적으면 선택된 개체 분포가 원하는 분포로부터 크게 멀어져 버릴 가능성이 있다. 예를 들면 주사위를 6회 던져 보다도 1부터 6까지의 눈금이 모두 1회씩 나온다는 것은 좀처럼 발생하지 않을 것이다. 기대치 방식에서는 적응도의 분포에 기초하여 각 개체가 선택될 기대치(개수)를 계산한다. 그리고 어떤 개체가 선택될 때에 그 개체의 기대치를 작게하여 가는 것이다. 이렇게 하는 것에 의해 선택된 개체는 선택되기 어렵고, 적응도 비례 방식에서의 확률에 의한 오차를 가능한한 작게 할 수 있다.

(4) 순위(Rank) 방식
순위 방식에서는 미리 순위와 선택할 개체수와의 관계를 결정해 둔다. 그리고 각 개체를 적응도 순으로 나열하고, 선택할 개체를 결정해 가는 것이다. 적응도의 대소관계만이 고려되기 때문에 적응도 그 자체의 값은 무시된다.

(5) 토너먼트 방식
토너먼트 방식은 집단 중에 결정된 수(실제로는 2개인 경우가 많다)의 개체를 무작위로 선택한다. 그들 중에서 가장 적응도가 높은 개체를 선택하는 것으로 이러한 조작을 필요한 횟수만큼 반복한다.

스케일링

앞절에서 설명한 선택은 교배를 행할 때의 생존 분포를 집단 중에서 적응도의 분포에 따라 결정하는 것이었다. 그런데 특히 초기 세대에 있어서 해에 어느 정도 가깝다면 해로서는 아직 불충분한 적응도를 가지는 유전자가 집단중에 퍼져 버리게 되는 경우가 있다. 마치 "우물안의 개구리"와 같은 것이 집단 중에서 일어나고 있는 상태이다. 이렇게 되면 보다 적응도가 높은 유전자를 탐색하는 것이 어려워져 간다. 이러한 현상을 방지하기 위해서 고안된 것이 스케일링(Scaling)이다. 스케일링은 적응도의 값을 선택에 직접 반영시키는 것이 아니라 함수를 이용하여 변환한 후에 선택에 반영시키려고 하는 것이다. 따라서 적응도의 차이가 확대 혹은 축소되게 된다.

스케일링에 이용되는 함수로서 [표 3]과 같은 함수가 지금까지 제안되었다. [표 3]에서 f는 스케일링 전에 적응도의 값을, f'는 스케일링 후의 적응도의 값을 보여주고 있다. 시그마 절단에서 이용되는 는 집단의 표준 편차이다. 선형 스케일링은 1차 함수가 사용되고 멱승 스케일링에서는 지수 함수가 사용되고 있다.

[표 3] 스케일링에 이용되는 함수
스케일링	함 수
선형 스케일링	f' = af + b
멱승 스케일링	f' = f^k
시그마 절단	f' = f-(f' - c × )

선형 스케일링을 사용할 경우 스케일링 후의 적응도의 값이 음수가 되지 않도록 주의 해야한다. 멱승 스케일링의 경우는 적응도 값이 음수가 될 수 없다는 것은 수학적으로도 증명되어 있다. 시그마 절단으로 스케일링 후의 적응도의 값이 음수가 될 경우는 강제적으로 0으로 한다.

유전 연산자(genetic operator)

기본적인 연산자로 교배(crossover)와 돌연변이(mutation)가 있으며 문제에 따라 역위(inversion), 치환(displacement), 중복(duplication), 추가(addition), 제거(deletion) 등의 연산자를 사용하는 경우도 있다.

교 배

교배(crossover)는 2개의 염색체 사이에서 유전자를 바꾸어 넣어 새로운 개체를 발생시키는 것이다. 여기서 교배에 대해 좀 더 자세히 설명한다.

앞의 예제에서는 가장 간단한 교배법을 이용했다. 교배하는 위치를 임의로 결정하여 그들의 위치를 경계로 2개의 염색체 사이에서 유전자를 교환하였다. 그 외에는 다음과 같은 교배법이 있다.

(1) 단순교배(simple crossover)
다음과 같이 부모 1, 2가 있고 교배점(crossover site)을 3으로 했을 때 생성되는 자식은 자식 1, 2와 같이 된다.

[그림 3] 단순교배

(2) 복수점 교배
지금까지의 교배법에서는 교배 위치는 한군데였지만 복수점 교배에서는 [그림 4]과 같이 교배 위치가 복수개이고, 그들의 위치를 경계로 유전자의 교환이 행해진다.

교배점이 복수 개(이 경우는 2군데)가 있고 그들의 위치를 경계로 유전자를 교환한다.

[그림 4] 복수점 교배

(3) 일양 교배(uniform crossover)
일양 교배는 복수점 교배의 일종으로 생각할 수 있다. 우선 [그림 5]와 같은 마스크(교배 위치를 정한 표)를 준비해 둔다. 그리고 자식 1에 대해 마스크의 값이 0인 부분에는 부모 1의 값을 복사하고, 마스크의 값이 1인 부분에는 부모 2의 값을 복사한다. 그리고 자식 2에 대해서는 그 반대이다. 즉 마스크의 값이 0인 부분에는 부모 2의 값을 복사하고, 마스크의 값이 1인 부분에는 부모 1의 값을 복사하는 것이다.

자식 1에 있어서는 마스크가 0인 부분은 부모 1을, 마스크가 1인 부분은 부모 2의 유전자를 복사한다. 자식 2에 있어서는 역으로 한다.

[그림 5] 일양 교배

(4) 부분일치 교배(partially matched crossover)
보통 TSP 문제에서 아래와 같이 A와 B의 두 개의 염색체(즉, 도시의 방문순서)를 교배할 경우 2개의 교배점을 잡고 그 사이의 중간부분을 일치시켜 교환한 후 나머지 부분의 그 결과에 따라 중복되는 부분을 피하여 조정한다.

A = 9 8 4 | 5 6 7 | 1 3 2 10 → A' = 9 8 4 | 2 3 1 0 | 1 6 5 7
B = 8 7 1 | 2 3 10 | 9 5 4 6 → B' = 8 10 1 | 5 6 7 | 9 2 4 3

(5) 순서 교배(ordered crossover : OX)
TSP 문제에서 순서 교배의 예는 다음과 같다.

A = 9 8 4 | 5 6 7 | 1 3 2 10
B - 8 7 1 | 2 3 10 | 9 5 4 6
→ B = 8 H 1 | 2 3 10 | 9 H 4 H
→ B = 2 3 10 | H H H | 9 4 8 1
A' = 5 6 7 | 2 3 10 | 1 9 8 4
B' = 2 3 10 | 5 6 7 | 9 4 8 1

기타 연산자

교배 연산자 이외의 기타 연산자는 다음과 같다.

(1) 돌연변이(mutation)
개체의 각 유전자좌의 유전자에 대하여 일정한 돌연변이 확률(p_m)을 적용하여 대립 유전자의 값으로 바꾸는 것이다. 개체에 근접한 새로운 개체를 생성하는 국소적인 랜덤 탐색의 일종이다. 또한 집단에서 잃어 버린 유전형질을 복구하여 다양성을 유지하기 위한 수단으로도 사용된다. 이때 전형적인 돌연변이 확률은 0.05 이하이다.
다음은 돌연변이의 적용예이다. 세 번째 비트인 a₃가 A₃로 바뀌었다.

부모 a₁a₂a₃a₄a₅a₆a₇a₈자식 a₁a₂a₄a₅a₆a₇a₈

(2) 치 환(displacement)
염색체의 일부분을 다른 염색체의 일부분으로 대치하는 방법

  (3) 역 위(inversion)
  부모 1 0 0 1 0 0 1 0        자식 1 0 0 0 1 0 1 0
             ↑                 ↑

(4) 중 복(duplication)
염색체상의 코드의 일부분을 중복시킨다.

(5) 추 가(addition)
염색체상에 어떤 길이의 부분 문자열을 삽입시킨다. 이 결과 염색체의 길이가 길어지게 된다.

(6) 제 거(deletion)
염색체상에 어떤 길이의 부분 문자열을 제거시킨다. 이 결과 염색체의 길이가 짧아지게 된다.

유전자 알고리즘 을 이해하기 위한 응용 예

간단한 예제를 이용하여 유전자 알고리즘의 원리를 이해하도록 한다. 염색체의 길이는 10비트로 한다. 적응도를 앞의 5비트에 대해서는 0의 요소 수, 나머지 5비트에 대해서는 1의 요소 수의 합으로 한다. 예를 들면 10101 11011인 유전자에서는 전반 5비트에 0이 2개, 나머지 5비트에는 1이 4개이기 때문에 적응도는 2+4로 6이 된다. 문제는 가능한한 적응도가 큰 염색체를 발견하는 것이다. 이 예는 매우 간단하기 때문에 적응도의 연산법으로부터 해를 즉시 구할 수 있다. 유전자가 0000011111이면 적응도가 10으로 최대가 된다. 그러나 먼저 해는 미지수로 하여 유전자 알고리즘에 의해 해를 발견하게 된다. 이것으로 일단 유전자형이 결정되고, (단계 1)이 끝난다.

다음에 초기 유전자 집단의 결정(단계 2)이다. 여기서는 유전자 집단 수를 6으로 한다. 각 유전자의 각 요소는 임의로 결정된다.

(단계 3)에서는 각 개체의 적응도를 구한다. [그림 6(a)]에 적응도가 높은 순서로 나열한 유전자를 나타낸다. 한편 순위는 적응도가 같은 경우에 위쪽을 높은 순서로서 번호를 붙인다.

(단계 4)는 선택 단계이다. 여기서는 간단하기 때문에 에리트 보존 선택법을 단순화시킨 것을 이용하기로 한다. 에리트 보존 선택법이란 적응도가 제일 낮은 개체를 적응도가 제일 높은 개체로 치환하는 것이다. 이 조작을 수행하여 적응도가 큰 순서로 나열하면 [그림 6(b)]와 같이 된다.

(단계 5)의 교배에서는 2개의 유전자를 한 조로 하여 [그림 6(c)]에 나타낸 바와같이 교배위치를 임의로 결정한다. 그것을 경계로 유전자의 요소를 상호 교환하는 것이다. 여기서 순위 1의 유전자와 순위 6의 유전자, 순위 2의 유전자와 순위 5의 유전자, 순위 3의 유전자와 순위 4의 유전자를 각각 한 조로 하여 교배를 행하기로 한다.

(단계 6)의 돌연변이에 대해서 우선 여기에서는 생략한다.

그런데 여기에서 [그림 6(d)]에 보여주는 것과 같은 제 2세대 유전자가 6개 갖추어져 있다. 제 1세대 유전자 집단은 [그림 6(a)]에 보여주는 것과 같이 평균 적응도가 5.0으로 최대값이 6이 되는데 비해 제 2세대에서는 [그림 6(d)]에 의해 평균 적응도가 5.3으로 최대값은 7로 각각 향상되는 것을 알 수 있다.

유전자 알고리즘은 이러한 세대 교대의 조작을 반복해 간다. [그림 7]에 다음 세대에서의 반복을 나타낸다. 교배위치는 매회 임의로 선택하기 때문에 [그림 6]의 경우와 다르다.

(a) 도태(제1세대) 평균 적응도 5.0 (b) 증식(제1세대) 평균 적응도 5.3

(c) 교배(제1세대) (d) 유전자 집단(제2세대) 평균 적응도 5.3

[그림 6] 유전자 알고리즘 예

[그림 6(d)]에 의해 제 3세대 유전자 집단에서는 최대값은 7로써 제 2세대와 같지만, 평균 적응도는 5.8로 향상된 것을 알 수 있다.
이러한 조작을 반복하면 적응도는 향상되어 가고, 최대값을 얻을 수 있다(불가능한 경우도 있다)

(a) 도태(제2세대) 평균 적응도 5.3 (b) 증식(제2세대) 평균 적응도 5.8

(c) 교배(제2세대) (d) 유전자 집단(제3세대) 평균 적응도 5.8

[그림 7] 유전자 알고리즘 예([그림 5.6]의 계속)

유전자 알고리즘 의 장점과 단점

여기서는 유전자 알고리즘의 장점과 단점을 정리해 보기로 하자. 우선 유전자 알고리즘의 장점으로서 다음과 같은 점을 들 수 있다.

■ 복수 개의 개체 사이의 상호 협력에 의한 해의 탐색
유전자 알고리즘은 복수의 개체 사이에서 선택이나 교배 등의 유전적 조작에 의해서 상호 협력적으로 해의 탐색을 수행하고 있다. 따라서, 단순한 병렬적 해의 탐색과 비교하여 보다 좋은 해를 발견하기 쉽다.

■ 번거로운 미분 연산 등이 불필요
뉴럴 네트워크, 특히 백프로파게이션 알고리즘 등에서는 평가 함수의 미분값을 필요로 하였다. 유전자 알고리즘에서는 현재 적응도를 분별할 수 있으면 되기 때문에 알고리즘이 단순하고, 평가 함수가 불연속인 경우에도 적용이 가능하다.

한편 다음과 같은 문제점이 있다.

■ 대상으로 하는 문제를 유전자 알고리즘으로 해결하기 위한 일반적인 방법이 없다. 특히문제의 유전자형으로의 표현(코딩)은 설계자의 숙달로 되어 있다.

■ 개체수, 선택 방법이나 교배법의 결정, 돌연변이의 비율 등 파라미터의 수가 많다.