유전자 알고리즘 : 개관

(Genetic Algorithms : An Overview)

유전자 알고리즘 입문 : Melanie Mitchell 저서, 공성곤.김인택.박대희.박주영.신요안 공역, 진영사, 1997 (원서 : An Introduction to Genetic Algorithms, 1996)

1.1 진화연산의 간략한 역사

1.2 진화의 매력

1.3 생물학 용어

1.4 탐색공간과 적합도 지형

1.5 유전자 알고리즘의 요소

1.6 단순 유전자 알고리즘

1.7 유전자 알고리즘과 전통적인 탐색방법

1.8 유전자 알고리즘의 응용

1.9 두 가지 간단한 예

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

과학은 세계를 이해하고 통제하고자 하는 인간의 욕구로부터 발생한다. 지금까지의 역사의 과정동안, 우리 인간들은 날씨, 행성의 운동, 일식과 월식, 질병의 과정, 경제성장의 상승과 하강, 어린이들에 있어서의 언어발달의 단계, 그리고 광범위한 그 밖의 자연적, 사회적, 그리고 문화적 현상들을 어느 정도 예측할 수 있는 장엄한 지식체계를 점진적으로 구축해왔다. 최근에 이르러서야 우리는 우리의 예측능력에 대한 몇몇 근본적인 한계를 이해하기 시작했다. 오랜 세월에 걸쳐 우리는 우리의 삶과 자연과의 상호작용의 많은 관점들을 제어하기 위한 아주 복잡한 수단들을 개발해 왔으며, 때로 어려운 방식으로 다른 관점들을 통제할 수 없는 한도를 학습하였다.

전자식 컴퓨터의 도래는 과학기술의 역사상 가장 혁명적인 발전임에 틀림없다. 이러한 계속적인 혁명은 반세기전만 해도 거의 인식되지 못했던 방식으로 자연을 예측하고 제어할 수 있는 우리의 능력을 상당히 향상시키고 있다. 무엇보다도 이 혁명의 훌륭한 업적은 지능적인 개체와 새로운 형태의 생명의 (컴퓨터 프로그램의 형태의) 창조일 것이다.

인공지능과 인공생명을 창조하려는 목표는 컴퓨터 시대의 시작으로 거슬러 올라갈 수 있다. Alan Turing, John von Neumann, Norbert Wiener 등과 같은 초기의 컴퓨터 과학자들은 지능, 스스로 복제할 수 있는 생명과 같은 능력, 그리고 주위환경을 학습하고 제어할 수 있는 적응능력을 가진 컴퓨터 프로그램에 관한 미래상을 가지고 열심히 연구하였다. 이들 컴퓨터과학의 초기 선구자들은 전자공학만큼 생물학과 심리학에 많은 흥미를 가지고 있었고 그들의 미래상을 성취하기 위한 방법을 인도하는 은유로써 자연체계를 연구하였다. 따라서 초창기부터 컴퓨터들이 미사일의 탄도를 계산하고 군사암호를 해독하는데 뿐만 아니라 두뇌를 모델링하고 인간의 학습과정을 흉내내고, 생물의 진화를 시뮬레이션하는데 적용되었다는 것은 놀랄 만한 일이 아니다. 이러한 생물학적으로 동기를 가진 계산활동들은 여러해 동안 활발하였다가 쇠퇴하였지만, 1980 년대초 이후부터는 컴퓨터 연구학계에서 모두 부활하게 되었다. 첫 번째는 신경망 분야, 두 번째는 기계학습 분야, 그리고 세 번째는 현재 유전자 알고리즘으로 대표되는 "진화연산 (evolutionary computation)" 이라고 불리고 있는 분야로 성장하였다.

1.1 진화연산의 간략한 역사

    (A Brief History of Evolutionary Computation)

1950 년대와 1960 년대에 여러 컴퓨터 과학자들은 진화가 공학문제들을 위한 최적화도구로 사용될 수 있다는 아이디어를 가지고 독립적으로 진화 시스템들을 연구하였다. 이러한 모든 시스템들에서 아이디어는 자연의 유전적 변이와 자연 선택에 의해 고무된 연산자들을 사용하여 주어진 문제에 대한 후보해의 집단을 진화시켜 나가는 것이었다.

1960 년대에 Rechenberg (1965, 1973) 는 "진화전략 (evolution strategies)" 을 소개했는데, 이것은 그가 비행기날개와 같은 장치의 실수값 파라미터를 최적화 하는데 사용한 방법이었다. 이 아이디어는 Schwefel (1975, 1977) 에 의해 더욱 발전되었다. 진화전략 분야는 활발한 연구영역으로 자리잡았고, (비록 최근에 두 분야가 서로 교류하기 시작했지만) 유전자 알고리즘 분야와는 거의 독립적으로 발전되었다. (진화전략에 관한 간략한 개관은 Bäck, Hoffmeister, Schwefel (1991) 을 참고하라.) Fogel, Owens, Walsh (1966) 는 "진화 프로그래밍 (evolutionary programming)" 을 발전시켰는 데, 이것은 주어진 문제에 대한 후보해들을 유한상태의 기계로 표현하고, 그들의 상태천이 도표를 랜덤하게 변이시키고 가장 적합한 것을 선택함으로써 진화하는 기법이다. 진화 프로그래밍의 약간 광범위한 구성 역시 활발한 연구분야가 되었다 (예를 들어 Fogel, Atmar 1993) 을 참고하라). 진화전략, 진화 프로그래밍, 그리고 유전자 알고리즘은 모두 진화연산 분야의 근간을 이루고 있다.

1950 년대와 1960 년대에 연구하고 있었던 다른 여러 연구자들은 최적화와 기계학습을 위해 진화에서 영감을 얻은 알고리즘들을 개발하였다. 비록 그들의 연구가 진화전략, 진화 프로그래밍, 유전자 알고리즘처럼 주목받거나 연구가 계속되지는 못하였지만, Box (1957), Friedman (1959), Bledsoe (1961), Bremermann (1962), 그리고 Reed, Toombs, Baricelli (1967) 는 모두 이 분야에서 연구하였다. 게다가 많은 진화 생물학자들은 억제된 실험을 하기 위한 목적으로 컴퓨터를 사용하여 진화를 시뮬레이션 하였다 (예를 들어 Baricelli 1957, 1962 ; Fraser 1957a, b; Martin, Cockerham 1960 를 참조하라). 진화연산은 전자식 컴퓨터가 형성되는 시대에 분명히 널리 퍼져있었다.

유전자 알고리즘은 1960 년대에 John Holland 에 의해 창안되었고 Holland 와 학생, 동료들에 의해 1960 년대와 1970 년대에 미시간 대학에서 발전되었다. 진화전략과 진화 프로그래밍과는 대조적으로 Holland 의 원래 목적은 특정한 문제를 해결하기 위한 알고리즘을 고안하는 것이 아니었고, 자연에서 발생하는 적응의 현상을 체계적으로 연구하고 자연의 적응능력 메카니즘을 컴퓨터 시스템에 이식하는 방법을 개발하기 위한 것이었다. Holland 의 1975 년도 저서인 『자연과 인공 시스템에서의 적응 (Adaptation in Natural and Artificial Systems)』는 유전자 알고리즘을 생물학적 진화의 추상적 개념으로써 진술했고 GA 하에서 적응의 이론적인 토대를 제시하였다. Holland 의 GA 는 교배 (crossover), 돌연변이 (mutation), 그리고 역치 (inversion) 와 같이 유전학에 의해 고안된 연산자들과 함께 일종의 "자연의 선택" 을 사용하여 "염색체" (예를 들어 비트, 즉 1 과 0 의 문자열) 의 한 개체집단에서 새로운 집단으로 이동시키는 방법이다. 각 염색체는 "유전인자 (gene)" (예를 들어 비트) 들로 이루어져 있고, 각 유전인자는 특별한 "대립 유전자 (allele)" (예를 들어 0 또는 1) 의 한 예이다. 선택 연산자 (selection operator) 는 개체집단에서 재생산하도록 허용할 염색체들을 선택하고, 적합한 염색체들은 적합하지 않은 염색체들보다 평균적으로 더 많은 자손들을 생산한다. 교배는 개략적으로 두 개의 단수 염색체 유기체들간의 생물학적 재결합을 흉내내어 두 염색체들의 일부분을 교환하고, 돌연변이는 염색체내의 어떤 위치의 대립유전자 값을 랜덤하게 변화시킨다. 그리고 역치는 염색체의 인접한 부분의 순서를 역전시켜서 유전인자들이 배열되어 있는 순서를 재배열한다. (여기서 대부분의 GA 문헌에서처럼 "교배 (crossover)" 와 "재결합 (recombination)" 같은 것을 의미한다.)

교배, 역치, 그리고 돌연변이를 가지는 개체집단에 기초한 알고리즘에 대한 Holland 의 소개는 주된 혁신이었다. (Rechenburg 의 진화전략은, 하나의 부모와 하나의 자손인 두 개체의 "개체 집단 (population)" 으로 출발하는데, 자손은 부모의 돌연변이된 형태이고 많은 개체의 집단과 교배는 최근에 비로소 도입되었다. Fogel, Owens, Walsh 의 진화 프로그래밍도 마찬가지로 변종을 만들어내기 위하여 돌연변이만 사용하였다.) 게다가 Holland 는 컴퓨터를 이용한 진화를 확고한 이론적인 토대위에 올려놓은 최초의 사람이었다 (Holland 1975). 최근까지 "스키마 (schema)" 의 개념에 기초한 이 이론적인 토대가 그 이후의 거의 모든 유전자 알고리즘들의 이론적인 업적의 기초가 되었다.

최근 몇 년동안 다양한 진화연산 방법들을 연구하는 연구자들 사이에 교류가 활발하게 이루어지고 있고, GA, 진화전략, 진화 프로그래밍, 그리고 다른 진화적 접근방법들 사이의 경계가 어느정도 무너지게 되었다. 오늘날, 연구자들은 Holland 의 원래 개념과 상당히 다른 어떤 것을 나타내는데 "유전자 알고리즘" 이라는 용어를 종종 사용한다. 이 책에서 필자는 이 융통성을 받아들이기로 하였다. 여기서 설명하는 대부분의 프로젝트들은 원래의 창시자에 의하여 GA 로 칭해졌다. 몇몇은 아니지만 충분한 "과 유사성 (family resemblance)" 을 가지고 있으므로 유전자 알고리즘이라는 제명하에 모두 포함하였다.

1.2 진화의 매력

    (The Appeal of Evolution)

컴퓨터 계산문제들을 해결하기 위한 착상으로 왜 진화를 사용하는가? 진화 연산 연구자들에게는 진화의 메카니즘이 많은 분야에서 몇몇 가장 까다로운 계산 문제들에 적합하다고 생각된다. 많은 계산문제들은 굉장히 많은 수의 가능한 해들을 탐색하여야 하는 것을 필요로 한다. 이러한 예 중 하나는 계산 단백질공학의 문제인데, 이 문제에서는 규정된 성질들을 가지는 단백질을 위한 엄청난 수의 가능한 아미노산의 배열들을 탐색하는 알고리즘을 찾아야 한다. 또 다른 예는 외환시장과 같은 재정시장의 상승과 하강을 예측하는 일련의 규칙들이나 방정식들을 탐색하는 것이다. 그러한 탐색 문제는 병렬처리를 효과적으로 사용하여 도움을 받을 수 있는데, 많은 다른 가능성들이 효과적인 방법으로 동시에 탐색된다. 예를 들어 규정된 성질을 가지고 있는 단백질을 탐색하는데 있어서, 한번에 하나의 아미노산 배열을 평가하는 대신에 많은 것들을 동시에 평가하는 것이 훨씬 빠를 것이다. 필요한 것은 계산의 병렬처리 (즉, 여러 개의 배열들을 동시에 평가하는 많은 프로세서들) 와 다음에 어떤 배열을 평가할 것인지 선택하는 지능적인 전략이다.

많은 계산문제들은 변화하는 환경에 계속해서 잘 대처하기 위해서 적응적인 컴퓨터 프로그램을 필요로 한다. 이러한 대표적인 경우가 어떤 로봇이 변화하는 환경 하에서 작업을 수행하여야 하는 로봇제어 문제와, 다양한 사용자들의 개성에 적응하여야 하는 컴퓨터 인터페이스 문제이다. 다른 문제들은 혁신적인 컴퓨터 프로그램, 다시 말하여 계산작업이나 새로운 과학 발견을 수행하기 위한 새로운 알고리즘같이 진정으로 새롭고 독창적인 것을 구축할 수 있는 컴퓨터 프로그램을 필요로 한다. 끝으로, 많은 계산 문제들은 복잡한 해를 필요로 하므로 손으로 프로그램하는 것이 어렵다. 주목할 만한 예는 인공지능을 창조하는 문제이다. 일찍이 AI 종사자들은 프로그램에 지능을 부여하는 규칙을 직접 얻을 수 있다고 믿었는데, 전문가 시스템은 이러한 초기 낙관의 한 결과였다. 오늘날 많은 AI 연구자들이 지능을 표현하기 위한 "규칙 (rules)" 들이 너무 복잡하여 과학자들은 "위에서 아래로 (top-down)" 의 형식으로 손으로 프로그램하는 것이 어렵다고 믿고 있다. 대신 인공지능에 이르는 가장 좋은 방법은 사람이 아주 단순한 규칙만을 제공하고 지능과 같은 복잡한 행동은 이들 단순한 규칙들의 대규모 병렬적용과 상호작용으로부터 발현하는 "아래에서 위로 (bottom-up)" 의 형식을 통하는 것이라고 믿는다. 연결주의 (connectionism, 신경망 시스템으로 고취된 컴퓨터 프로그램의 연구) 는 이 철학의 한 예이고 (Smolensky 1988), 진화연산은 또 다른 예이다. 연결주의에서 규칙들은 전형적으로 단순한 "신경망적 (neural)" 발단, 활성 전파, 연결의 강화 또는 약화이고, 기대되는 창발적 행동은 복잡한 패턴 인식과 학습이다. 진화연산에서 규칙들은 전형적으로 교배와 돌연변이에 기인한 변화를 가진 "자연 선택" 이고, 기대되는 창발적 행동은 어려운 문제에 대한 좋은 해를 설계하는 것과 변화하는 환경에 대처하여 이들 해를 적응시키는 능력이다.

생물학적 진화는 이러한 문제들에 접근하는 호소력있는 착상의 원천이다. 실제로 진화는 "해 (solutions)" 가 될 수 있는 굉장히 많은 수의 가능성들 중에서 탐색하는 방법이다. 생물학에서 많은 수의 가능성들은 가능한 유전적 배열의 집합이고, 원하는 "해" 는 아주 적합한 유기체 (주어진 환경에서 잘 생존하고 재생산할 수 있는 유기체) 이다. 또한 진화는 복잡한 문제들에 대한 혁신적인 해를 얻기 위한 방법으로 볼 수 있다. 예를 들어 포유류의 면역체계는 신체를 침범하는 세균의 문제에 대하여 아주 잘 진화된 예이다. 이러한 관점에서 보면 진화의 메커니즘은 계산상의 탐색방법에 아이디어를 제공할 수 있다. 물론 생물학적 유기체의 적합도는 많은 요인, 예를 들어 환경의 물리적 특징에 잘 대처해 나갈 수 있는가 그리고 주위에 있는 다른 유기체들과 얼마나 잘 경쟁하거나 협력할 수 있는가와 같은 요인들에 따라 좌우된다. 유기체가 진화함에 따라 적합도 기준은 계속적으로 변화하므로 진화도 지속적으로 변화하는 가능성들의 집합을 탐색하고 있다. 변화하는 조건에 직면하여 해를 탐색하는 것은 바로 적응적인 컴퓨터 프로그램들에게 필요한 것이다. 게다가 진화는 대규모 병렬탐색 방법인데, 진화는 한 번에 하나의 종에 대해서만이 아니라 수백만의 종을 병렬적으로 테스트하고 변화시킨다. 끝으로 높은 수준에서 보면 진화의 "규칙 (rules)" 들은 굉장히 간단하다. 종들은 랜덤한 변화 (돌연변이, 재결합, 그리고 다른 연산자) 에 의해서 진화하고, 자연 선택에 의하여 가장 적합한 개체가 살아남고 재생산하게 되며, 그들의 유전물질이 이후의 세대에 전파된다. 그럼에도 불구하고 이와 같은 간단한 규칙들이 우리가 생물계에서 직면하는 매우 특이한 다양성과 복잡성에 상당히 영향을 주었다고 생각된다.

1.3 생물학 용어

    (Biological Terminology)

이 시점에서 이 책에서 사용될 몇 가지 생물학 용어들은 공식적으로 소개하는 것이 도움이 될 것이다. 유전자 알고리즘의 문맥에서 이들 용어들이 가리키는 실체가 실제 생물학적인 것보다 훨씬 단순한 것이지만, 실제 생물학과의 유사성을 나타내기 위하여 사용된다.

모든 살아있는 유기체는 세포들로 구성되어 있고, 각 세포는 그 유기체에 대한 "청사진 (blueprint)" 으로 작용하는 하나 이상의 염색체 (DNA 의 문자열) 의 같은 집합을 포함하고 있다. 염색체는 개념적으로 DNA 의 기능적 블록인 유전인자들로 나누어질 수 있는데, 각 유전인자는 특별한 단백질을 나타내고 있다. 개략적으로 말하여 어떤 유전인자는 눈동자의 색깔과 같은 어떤 속성 (trait) 특징을 나타내고 있다고 생각할 수 있다. 어떤 특징에 대한 여러 가지 다른 가능한 "설정 (settings)" (예를 들어 파랑, 갈색, 엷은 갈색) 들을 대립유전자라고 부른다. 각 유전인자는 염색체위의 특별한 위치 (locus) 에 위치하고 있다.

많은 유기체들은 각 세포에 복수개의 염색체들을 가지고 있다. 유전 물질의 완전한 집합 (모든 염색체들) 을 그 유기체의 게놈 (genome) 이라고 부른다. 유전자형 (genotype) 이라는 용어는 게놈에 포함되어 있는 특정한 유전인자들의 집합을 의미한다. 동일한 게놈을 가지고 있는 두 개체는 동일한 유전형을 가지고 있다고 말한다. 유전형은 태아 그리고 이후의 성장과정에서 유기체의 표현형 (phenotype) 을 생성하는데, 표현형이란 눈 색깔, 키, 두노의 크기, 지능과 같은 유전형의 물리적 및 정신적인 특징을 말한다.

염색체들이 쌍으로 배열되어 있는 유기체들을 배수 염색체 (diploid) 라고 하고, 염색체가 쌍을 이루고 있지 못한 유기체를 반수 염색체 (haploid) 라고 한다. 인간을 포함하여 자연에서 유성 생식에 의해 재생산하는 대부분의 종들은 배수 염색체인데, 인간은 신체내 각 체강의 세포는 각각 23 쌍의 염색체들을 가지고 있다. 유성 생식에 의한 재생산에서는 재결합 (또는 교배) 이 일어나는데, 이 과정은 각각의 부모에서 염색체의 쌍 사이에 유전인자들이 교환되어 배우자 (하나의 염색체) 를 구성하고, 두 부모들로부터의 배우자들이 쌍을 이루어 하나의 완전한 배수 염색체를 구성한다. 반수 염색체 유성 생식에서는 두 부모들간에 유전인자들이 교환되어 한 가닥 (one strand) 염색체가 된다. 자손들은 돌연변이를 겪는데, 이것은 하나의 핵산 (DNA 의 기본 비트) 이 부모에서 자손으로 전수될 때 변화되는 것이며, 이 변화는 때때로 복제 에러로부터 나오기도 한다. 유기체의 적합도는 전형적으로 그 유기체가 살아남아 재생산하는 확률 (viability), 또는 그 유기체가 가지게 되는 자손의 수의 함수 (fertility) 로 정의된다.

유전자 알고리즘에서 염색체라는 용어는 전형적으로 어떤 문제에 대한 후보 해를 의미하며, 보통 비트 문자열로 부호화된다. "유전인자" 는 후보해의 특정한 원소 (예를 들어 다변수 함수 최적화의 관점에서는 특정한 매개변수를 표현하는 비트들이 유전인자로 고려될 수 있다.) 를 부호화하는 하나의 비트 또는 인접한 비트들의 짧은 블록이다. 어떤 비트 문자열에서 대립유전자는 0 또는 1 인데, 기호가 둘 이상일 경우에는 각 위치 (locus) 에 많은 대립유전자들이 있을 수 있다. 교배는 전형적으로 두 개의 단수 염색체 부모들간에 유전물질들을 교환하는 것으로 구성되어 있다. 돌연변이는 임의로 선택된 위치에 있는 비트를 역전시키는 것으로 구성된다 (기호가 둘 이상일 경우에는 임의로 선택된 위치에 있는 기호를 임의로 선택된 새로운 기호로 교체한다).

대부분의 유전자 알고리즘 응용에서는 단수 개체, 특히 하나의 염색체를 가진 개체를 사용한다. 비트 문자열을 사용하는 GA 에서의 각 개체의 유전형은 단순히 그 개체의 염색체에서의 비트의 구성이다. 비록 최근에 많은 연구자들이 유전형 레벨과 표현형 레벨이 둘 다 존재하는 (예를 들어 신경망을 나타내는 비트 문자열 부호화와 신경망 그 자체) GA 에 관하여 실험하고 있지만, GA 의 문맥에서는 흔히 "표현형" 의 개념이 존재하지 않는다.

1.4 탐색공간과 적합도 지형

    (Search Spaces and Fitness Landscapes)

후보해 집합에서 탐색하여 원하는 해를 얻는 아이디어는 컴퓨터 과학에서 아주 보편적이어서 "탐색공간 (search space)" 에서의 탐색이라는 고유의 이름을 가지고 있다. 여기서 "탐색공간" 이라는 용어는 어떤 문제에 대한 후보해들의 집합에 해당하며 후보해들 간의 "거리 (distance)" 의 개념을 가지고 있다. 계산 생물공학에서 가장 중요한 문제들 중 하나인 앞에서 언급한 컴퓨터에 의한 단백질 설계의 문제를 예로 들어보자. 아미노산의 배열이 접혀져서 특정한 3 차원 형태를 가짐으로써 이를테면 특정한 바이러스에 대항하도록 사용될 수 있는 단백질을 컴퓨터를 이용하여 찾아 내기를 원한다고 하자. 탐색공간은 모든 가능한 단백질 배열의 집합인데, 가능성의 수는 무한대이다. 이것에 제약조건을 가하기 위하여 길이 100 이하인 가능한 배열만을 찾는다고 하더라도, 배열의 각 위치마다 20 개의 가능한 아미노산이 있으므로 여전히 굉장히 큰 탐색공간일 것이다. (얼마나 많은 수의 가능한 배열이 존재하는가?) 만일 우리가 20 개의 아미노산들을 알파벳 문자로 표현한다면, 후보해들은 다음과 같이 표현될 것이다.

A    G    G    M    C    G    B    L    ㆍㆍㆍ

우리는 두 배열간의 거리를 대응되는 위치의 문자가 다른 위치의 개수로 정의할 것이다. 예를 들어 AGGMCGBL 과 MGGMCGBL 의 거리는 1 이고, AGGMCGBL 과 LBMPAFGA 와의 거리는 9 이다. 이 공간을 탐색하는 알고리즘은 탐색의 단계마다 어떤 후보해들을 테스트할 것인가를 결정하는 방법이다. 대부분의 경우에서 테스트될 다음 후보해는 이전 배열들의 테스트 결과에 의해 좌우된다. 대부분의 유용한 알고리즘들은 탐색공간에서 가까이 있는 "인접한 (neighboring)" 후보해들의 질에 대한 어떤 상관관계가 존재한다고 가정한다. 유전자 알고리즘은 다른 지역으로부터의 좋은 "부모 (prent)" 후보해들이 교배에 의하여 결합되어 좋은 "자손 (coffspring)" 후보해들을 생성해 낼 수 있다고 가정한다.

또다른 중요한 개념은 "적합도 지형 (fitness landscape)" 에 관한 것이다. 본래 생물학자인 Sewell Wright (1931) 이 집단 유전학의 관점에서 정의한 것인데, 적합도 지형은 적합도와 관련하여 모든 가능한 유전형들의 공간의 표현이다.

간단히 설명하기 위하여 각 유전형이 길이가 ℓ 인 비트 문자열이고 두 유전형들 간의 거리는 "해밍거리 (Hamming distance)" 즉 해당하는 비트가 다른 위치의 개수이고, 각 유전형에는 실수값을 갖는 적합도를 부여한다고 가정하자. 각 유전형은 ℓ 차원 공간의 한 점이고 그것의 적합도는 (ℓ + 1) 번째 축을 따라 도시되므로 적합도 지형은 (ℓ + 1) 차원의 그림으로 표현될 수 있다. ℓ = 2 인 경우의 간단한 적합도 지형을 그림 1 에 나타냈다. 이러한 그림을 지형 (landscape) 이라고 부르는데, 그 이유는 적합도 값의 그림이 "언덕 (hills)" "봉우리 (peaks)" "계곡 (valleys)" 그리고 그 밖의 물리적인 지형과 비슷한 특징들로 구성되어 있기 때문이다. Wright 의 이론에 의하면 진화는 특정한 방법으로 개체집단이 지형을 따라 이동하도록 하고, "적응 (adaptation)" 은 지역 봉우리를 향한 이동으로 볼 수 있다. ("지역 봉우리 (local peak)" 또는 "지역 최적값 (local optimum)" 은 반드시 그 지형에서 가장 높은 점은 아니지만 그곳으로부터 약간만 이동해도 적합도 값이 내려가는 점을 의미한다.) 마찬가지로 GA 에서 교배와 돌연변이 연산자들은 적합도 함수에 의해 정의된 지형 위를 따라 개체집단을 이동시키는 방법이라고 볼 수 있다.

                               그림 1.1  ℓ = 2 인 경우의 간단한 적합도 지형.
                                         여기서 f(00) = 0.7, f(01) = 1.0, f(10) = 0.1, 그리고 f(11) = 0.0 이다.

변화하지 않는 지형에서 개체집단을 이동시키는 진화의 아이디어는 여러가지 이유에 의해 생물학적으로 현실적이지 못하다. 특히 어떤 유기체도 자신의 환경에 있는 다른 유기체와 무관한 적합도 값을 가질 수 없다. 그래서 개체집단이 변화함에 따라 특정한 유전형의 적합도도 마찬가지로 변화한다. 다시 말하여 실세계에서 "지형" 은 그곳에 거주하고 있는 유기체들과 분리될 수 없다. 이러한 경고에도 불구하고 적합도 지형의 개념은 유전자 알고리즘의 연구에서 중심적인 부분이 되었고, 이 책에서 여러 가지 다른 형태로 나타나게 될 것이다.

1.5 유전자 알고리즘의 요소

    (Elements of Genetic Algorithms)

진화연산 학계에서 모든 사람들에 의해 받아들여지며 GA 를 다른 진화연산 방법들과 구분하는 "유전자 알고리즘" 의 확고한 정의가 없다. 그러나 GA 라고 불리고 있는 대부분의 방법들은 최소한 다음의 요소들을 공통으로 가지고 있다고 말할 수 있는데, 그것은 염색체의 개체집단, 적합도에 따른 선택과정, 새로운 자손을 생성하기 위한 교배, 그리고 새로운 자손을 위한 랜덤한 돌연변이이다. GA 에 관한 Holland 의 네 번째 요소인 역치는 오늘날의 구현에서는 거의 사용되지 않으며, 장점들이 설사 있다하더라도 잘 정립되어 있지 않다. (역치는 유전자 알고리즘의 구현에서 자세히 논의될 것이다.)

GA 의 개체집단에서 염색체들은 전형적으로 비트 문자열의 형태를 취한다. 염색체에서의 각 위치는 두 가지 가능한 대립유전자인 0 과 1 을 가진다. 각 염색체는 후보해들의 탐색공간에서 하나의 점으로 고려될 수 있다. GA 는 하나의 염색체 집단을 다른 집단으로 계속적으로 교체하면서 염색체의 집단을 처리한다. GA 는 현재의 개체집단에서 각 염색체에 대해 점수 (적합도) 를 부여하는 적합도 함수를 가장 많이 필요로 한다. 어떤 염색체의 적합도는 그 염색체가 주어진 문제를 얼마나 직접 잘 해결하는가에 의해 좌우된다.

적합도 함수의 예 (Examples of Fitness Functions)

가장 흔한 GA 의 응용분야는 함수 최적화인데, 그 목표는 이를테면 복잡한 다변수 함수를 최대화하는 매개변수 값들의 집합을 찾아내는 것이다. 간단한 예로서 실수값을 갖는 1 차원 함수

f (y) = y + |sin (32y)|, 0 ≤ y < π

를 최대화하고자 한다고 하자 (Riolo 1992). 여기서 후보해는 y 의 값인데, 실수를 표현하는 비트 문자열으로 부호화될 수 있다. 적합도 계산은 주어진 비트 문자열 x 를 실수 y 로 변환하고 그 값에서의 함수를 계산한다. 어떤 문자열의 적합도는 그 점에서의 함수값이다.

수치적이 아닌 예로서 원하는 3 차원 단백질 구조로 접혀지는 50 개의 아미노산의 배열을 찾는 문제를 고려해보자. GA 는 각 후보해들이 다음과 같은 50 개 문자 문자열들에 의해 부호화되는 후보해들의 집단을 탐색함으로써 이 문제에 적용될 수 있다.

IHCCVASASDMIKPVFTVASYLKNWTKAKGPNFEICISGRTPYWDNFPGI

여기서 각 문자는 20 개의 가능한 아미노산들 중 하나를 나타낸다. 후보 배열의 적합도를 정의하는 한 방법은 원하는 구조에 관하여 배열의 위치에너지 (potential energy) 의 음수를 취하는 것이다. 위치에너지는 그 배열이 원하는 구조로 접혀지게 되었을 때 얼마나 큰 물리적 저항을 가지게 되는가에 관한 척도이다 - 위치에너지가 낮을수록 접합도는 더 높아진다 - 이것은 불가능하지는 않다 하더라도 매우 어려운 일이다. 그 대신 어떤 배열과 원하는 구조가 주어졌다면 (그리고 관련된 생물 물리학 (biophysics) 지식을 가지고 있다면), 각 아미노산에 작용하는 몇몇 힘 (force) 들을 계산함으로써 위치에너지를 예측할 수 있으며, 따라서 전체 적합도는 계산에 의해 구할 수 있다.

이러한 예들은 어떤 문제에 대한 후보해들이 기호의 문자열으로 부호화되고, 그 결과로 주어지는 문자열의 공간에서 정의되는 적합도 함수를 갖는 추상적인 염색체들로 부호화될 수 있다는 두 개의 다른 관계를 보여준다. 유전자 알고리즘은 아주 적합한 문자열에 대한 적합도 지형을 탐색하는 방법이다.

GA 연산자 (GA Operators)

가장 단순한 형태의 유전자 알고리즘은 선택, 교배, 그리고 돌연변이의 세 연산자들을 포함하고 있다.

선택 (Selection) : 이 연산자는 재생산을 위하여 개체집단에서 염색체들을 선택한다. 더 적합한 염색체일수록 더 많이 선택되어 재생산되는 경향이 있다.
 

교배 (Crossover) : 이 연산자는 랜덤하게 어떤 위치를 선택하고, 두 염색체들 사이에 그 이전과 이후의 배열의 일부분을 교환하여 두 개의 자손을 생성한다. 예를 들어 문자열 10000100 과 11111111 은 각각 세 번째 위치 이후에서 교배되어 두 자손 10011111 과 11100100 을 생성할 수 있다. 교배 연산자는 개략적으로 두 개의 반수 염색체 유기체간의 생물학적 재결합을 흉내낸 것이다.
 

돌연변이 (Mutation) : 이 연산자는 염색체내의 어떤 비트들을 랜덤하게 역전시키는 것이다. 예를 들어 문자열 00000100 은 두 번째 위치에서 돌연변이되어 01000100 이 될 수 있다. 돌연변이는 보통 매우 작은 확률 (예를 들어 0.001) 을 가지고 각 비트위치에서 발생할 수 있다.

1.6 단순 유전자 알고리즘

    (A Simple Genetic Algorithm)

해결하려고 하는 분명히 정의된 문제와 후보해들에 대한 기호 문자열 표현이 주어졌을 때 간단한 유전자 알고리즘은 다음과 같이 동작한다 :

1. 랜덤하게 생성된 n 개의 ℓ - 비트 염색체들의 개체집단 (문제에 대한 후보해들) 을 가지고 시작한다.

2. 개체집단에서 각 염색체 x 의 적합도 f(x) 를 계산한다.

3. n 개의 자손이 생성될 때까지 다음 단계를 반복한다 :

a. 현재 개체집단으로부터 한 쌍의 부모 염색체를 선택하고 선택확률이 적합도 함수를 증가시키도록 한다. 선택은 교체로 끝나는데, 이것은 염색체가 한번이상 선택되어 부모가 되었다는 것을 의미한다.

b. 확률 ("교배확률" 또는 "교배율") 을 가지고 랜덤하게 선택된 (균일한 확률을 가지고 선택된) 점에서 그 쌍을 교배하여 두 개의 자손을 형성한다. 만일 교배가 이루어지지 않았다면 그대로 부모를 복제한 두 자손을 형성한다. (여기서 교배율은 두 부모가 한 점에서 교배되는 확률로 정의된다는 것을 주목하라. 한 쌍의 부모에 대한 교배율이 교배가 일어나는 점들의 수인 "다점 교배" 버전의 GA 도 또한 존재한다.)

c. 확률 (돌연변이 확률 또는 돌연변이율) 으로 각 위치에서 두 자손을 돌연변이 시키고 얻어진 염색체를 새로운 개체집단에 포함시킨다. 만일 n 이 홀수이면 한 개의 새로운 개체는 임의로 버릴 수 있다.

d. 현재 개체집단을 새로운 개체집단으로 교체한다.

e. 단계 2. 로 간다.

이 과정에서 각 반복을 세대 (generation) 라고 한다. GA 는 50 에서 500 또는 그 이상의 세대만큼 반복되는 것이 보통이다. 모든 세대들의 전체집합을 실행 (run) 이라고 한다. 한 실행이 끝나면 보통 개체집단에서 하나 이상의 아주 적합한 염색체가 존재한다. 각 실행에서 임의성이 매우 중요한 역할을 하기 때문에 다른 난수값을 갖는 초기값을 가지고 두 번 실행하면 일반적으로 다른 세부적인 행동이 생긴다. GA 연구자들은 같은 문제에 대해 다른 조건을 가지고 GA 를 많이 실행시키고 이것을 평균한 통계값 (한 실행에서 발견되는 가장 높은 적합도와 가장 높은 적합도를 가진 개체가 발견되는 세대 등) 을 보고하기도 한다.

위에서 설명한 간단한 과정은 GA 의 대부분의 응용에 대한 기초이다. 개체집단의 크기와 교배 및 돌연변이 확률과 같이 충족시켜야 할 많은 세부사항들이 존재하고, 알고리즘의 성공은 이러한 세부사항에 크게 좌우되기도 한다. 또한 더욱 복잡한 버전의 GA (예를 들어 문자열이 아닌 다른 표현에서 작용하는 GA 또는 다른 형태의 교배와 돌연변이 연산자들을 갖는 GA) 들이 존재한다. 많은 그러한 예들을 이후의 장에서 설명할 것이다.

간단한  GA 의 보다 상세한 예로서 ℓ (문자열 길이) 이 8, f(x) 가 비트 문자열 x 에서 1 들의 수 (여기서 예를 들기 위해 사용한 아주 간단한 적합도 함수), n (개체집단의 크기) 은 4, = 0.7, =0.001 이라고 가정하자. (적합도함수처럼 이들 ℓ 과 n 의 값들도 간단히 선택되었다. 보다 전형적인 ℓ 과 n 의 값은 50-1000 의 범위내에 있다. 와 의 값은 상당히 전형적인 값이다.)

(랜덤하게 발생된) 초기 개체집단은 다음과 같다 :

GA 에서 흔한 선택방법은 적합도 비례 선택 (fitness-proportionate selection) 인데, 여기서 어떤 개체가 재생산된다고 기대되는 횟수는 그 적합도를 개체집단의 평균 적합도로 나눈 것과 같다. (이것은 생물학자들이 "생존력 선택 (viability selection)" 이라고 부르는 것과 동일하다.)

적합도 비례 선택을 구현하는 간단한 방법 중 하나는 "룰렛휠 표본 추출 (roulette-wheel sampling)" (Goldberg 1989a) 인데, 이것은 개념적으로 면적이 각 개체의 적합도에 비례하도록 각 개체에게 순환성의 룰렛휠의 한 조각을 부여하는 것과 동일하다. 룰렛휠이 돌려지면, 구슬이 쐐기 형태의 조각에 정지하게 되고, 그에 해당하는 개체가 선택된다. 앞의 n = 4 인 예에서 룰렛휠이 4 번 돌려졌다고 했을 때 첫 번째 두 회전에서는 염색체 B 와 C 가 부모로 선택되고 두 번째 두 회전에서는 염색체 B 와 C 가 부모로 선택될 수 있다. (A 가 선택되지 않을 수 있다는 사실은 단지 운에 따른다. 만일 룰렛휠이 여러 번 회전된다면, 평균 결과는 기대값에 가까워질 것이다.)

일단 한 쌍의 부모가 선택되면, 확률 로 교배되어 두 자손을 구성한다. 만일 교배되지 않으면, 자손은 각 부모의 그대로의 복제이다. 위의 예에서 부모 B 와 D 가 첫 번째 비트 위치이후에서 교배되어 자손 E = 10110100 과 F = 01101110 을 형성하였고, 부모 B 와 C 는 교배되지 않아서 B 와 C 의 그대로의 복제인 자손들을 형성하였다고 가정하자. 다음에 각 자손은 확률 으로 각 로커스에서 돌연변이 된다. 예를 들어 자손 E 가 여섯 번째 위치에서 돌연변이 되어 E' = 10110000 을 만들어내었고 자손 F 와 C 는 돌연변이 되지 않았고, 자손 B 는 첫 번째 위치에서 돌연변이 되어 B' = 01101110 을 형성하였다고 가정하자. 새로운 개체집단은 다음과 같을 것이다 :

새로운 개체집단에서 가장 좋은 문자열 (적합도 값이 6 인 개체) 을 잃어버렸지만, 평균 적합도는 12/4 에서 14/4 로 올라갔다는 것을 주목하라. 이 과정을 반복하면 궁극적으로 모두 1 인 문자열을 얻게 될 것이다.

1.8 유전자 알고리즘의 응용

    (Some Applications of Genetic Algorithms)

앞에서 설명한 유전자 알고리즘의 형태는 매우 간단하지만, 이 기본적인 형태의 변형들이 많은 과학 및 공학문제와 모델들에 있어서 사용되어 왔다. 그중 몇몇 예는 다음과 같다.

최적화 (Optimization) : GA 는 수치최적화와 회로의 레이아웃이나 직무분배계획과 같은 조합 최적화 문제를 포함한 다양한 최적화 문제들에 사용되어 왔다.
 

자동 프로그래밍 (Automatic programming) : GA 는 특정한 문제에 대한 컴퓨터 프로그램을 진화시키고, 셀룰러 오토마타 (cellular automata) 와 정렬망 (sorting network) 과 같은 다른 계산구조를 설계하는데 사용되어 왔다.

 

기계학습 (Machine learning) : GA 는 날씨나 단백질구조의 예측과 같은 분류와 예측과제를 포함한 많은 기계학습 응용에 사용되어 왔다. 또한 GA 는 신경망의 가중치, 분류 시스템이나 기호생성 시스템을 위한 학습규칙, 그리고 로봇의 센서등과 같은 특정한 기계학습 시스템의 형태를 진화시키는데 사용되어 왔다.
 

경제학 (Economica) : GA 는 기술혁신, 입찰전략의 발전, 그리고 경제시장의 발현과정을 모델하는데 사용되어 왔다.
 

면역체계 (Immune systems) : GA 는 개체의 일생동안의 신체 면역과 진화기간 동안의 다유전인자 과들의 발견을 포함한 자연적인 면역체계의 여러 관점을 모델하는데 사용되어 왔다.
 

생태학 (Ecology) : GA 는 생물학적 무기경쟁, 숙주-기생체의 공진화, 공생, 그리고 자원의 흐름과 같은 생태학적 현상을 모형화하는데 사용되어 왔다.
 

집단 유전학 (Population genetics) : GA 는 "어떤 조건하에서 재결합을 위한 유전인자가 진화적으로 생존할 수 있는가?" 와 같은 집단 유전학에서의 문제들을 연구하는데 사용되어 왔다.
 

진화와 학습 (Evolution and learning) : GA 는 개체의 학습과 종의 진화가 서로 어떻게 영향을 주는지 연구하는데 사용되어 왔다.
 

사회 시스템 (Social systems) : GA 는 곤충집단에서 사회적인 행동의 진화, 그리고 보다 일반적으로 다개체 시스템에서의 협조와 통신의 진화와 같은 사회 시스템의 진화적인 관점을 연구하는데 사용되어 왔다.

이상은 유전자 알고리즘의 응용분야를 결코 총망라한 것은 아니지만 GA 가 문제해결에 있어서 그리고 과학의 관점에서 어떤 종류의 대상에 사용되어 왔는지를 알 수 있게 해준다. 이들 그리고 다른 분야에 있어서의 성공 때문에 GA 에 대한 관심이 많은 분야의 연구자들 사이에 최근 여러해동안 빠르게 증가하고 있다. GA 의 분야는 학술회의, 학술논문지, 그리고 과학계에서 컴퓨터과학의 한 학문분야로 자리잡았다.