서 론

유전자 알고리즘 : Zbigniew Michalewicz 저서, 공성곤.김인택.박대희.박주영.신요안 공역, 도서출판 그린 (원서 : Genetic Algorithm + Data Structure = Evolution Programs, 1996), Page 8~18

지난 30 년 도안 진화 및 유전원리에 기초한 문제해결 시스템에 대한 관심이 증가하고 있는데, 이러한 시스템들은 해가 될 가능성이 있는 개체집단을 유지하고, 개체의 적합도와 몇 가지 "유전" 연산자에 기초한 선택과정을 가지고 있다. 이들 시스템의 한 형태는 진화전략 (Evolution Strategies) 의 부류로, 매개변수 최적화문제에 대하여 자연의 진화원리를 흉내낸 알고리즘이다 [239], [263] (Rechenberg, Schwefel). Fogel 의 진화 프로그래밍 (Evolutionary Programming) [93] 은 소규모의 유한-상태 기계들의 공간을 탐색하는 기법이다. Glover 의 스캐터탐색 (Scatter Search) 기법 [105] 의 기준점의 집단을 유지하고 가중된 선형결합에 의해 자손세대를 만들어 낸다. 또다른 형태의 진화기반 시스템은 Holland 의 유전자 알고리즘 (GA ; Genetic Algorithm) [142] 이다. 1990 년에 Koza [172] 는 진화기반 시스템인 유전자 프로그래밍 (Genetic Programming) 을 제안하여 어떤 문제를 해결하기 위한 적합한 컴퓨터 프로그램을 찾아내었다.

이러한 모든 진화기반 시스템에 대해 (위에서 설명한 시스템들을 포함하여) 진화 프로그램 (EP ; Evolution Program) 이라는 공통용어를 사용한다. 그림 0.1 은 진화 프로그램의 구조를 나타낸다.

그림 1  진화 프로그램의 구조

진화 프로그램은 순환 t 에서 개체집단 를 유지하는 확률적인 알고리즘이다. 각 개체는 직접적으로 주어진 문제의 해가 될 가능성이 있는 것을 나타내며, 모든 진화 프로그램에서 (때로 복잡한) 데이터 구조 S 로 구현된다. 각 해  는 평가 되어 "적합도" 의 기준을 제공한다. 그러면 더 적합한 개체들을 선택하여 (선택단계) 새로운 개체집단이 형성된다 (순화 t+1). 새로운 개체집단의 어떤 회원은 "유전" 연산자에 의해 변환되어 (변천단계) 새로운 해를 형성한다. 작은 변화에 의한 한 개체로부터 새로운 개체를 생성하는 단일변환 (돌연변이 형태) 와 , 여러개의 (둘 또는 그 이상의) 개체들로부터 부분들을 결합하여 새로운 개체를 생성하는 고차변환 (교배 형태) 가 존재한다 (). 적당한 수의 세대 이후에 프로그램은 수렴하고, 이때 가장 좋은 개체가 근사 최적인 (적합한) 최적해를 나타내는 것으로 기대된다.

일반적인 예를 살펴보자. 어떤 요구사항들을 만족하는 그래프를 찾고 있다고 (이를 테면 메시지를 보내는데 소요되는 비용, 신뢰성 등과 같은 기준에 따라 통신 네트웍의 최적구조를 찾는다고) 가정하자. 진화 프로그램의 각 개체는 문제의 해가 될 가능성이 있는 것, 즉 하나의 그래프를 나타낸다. 그래프들의 초기집단 P(0) 는 (임의로 생성되었든 아니든 어떤 경험적인 과정의 결과로서 생성되었든) 진화 프로그램의 시작점 (t=0) 이다. 보통 평가함수가 도입되어 문제의 요구사항을 반복시킨다. 평가함수는 각 그래프의 적합도를 계산하여 더 좋은 개체와 나쁜 개체간의 차이를 구별한다. 여러가지 돌연변이 연산자들이 하나의 그래프를 변환하도록 고안될 수 있다. 어떤 교배 연산자는 두개의 (또는 그 이상의) 그래프의 구조를 하나로 결합하는 것으로 고려할 수 있다. 보통 이들 연산자는 문제고유의 지식을 반영시킨다. 예를 들어 만일 찾고자 하는 그래프가 연결되어 있고 비주기적이면 (나무구조이면) 가능한 돌연변이 연산자가 그래프로부터 에지를 제거하고 새로운 에지를 추가하여 두개의 구별된 부 그래프들을 연결시킨다. 다른 가능성은 주어진 문제와 관계없는 돌연변이를 설계하고 이 요구사항을 나무구조가 아닌 그래프에 벌점을 부과하는 평가함수에 반영시킨다.

주어진 문제에 대해 많은 진화 프로그램들이 체계화될 수 있다. 이들 프로그램은 여러가지 면에서 다를 수 있는데, 어떤 개체와 그것을 변환하는 "유전" 연산자, 초기 개체집단을 생성하는 방법, 문제의 구속조건을 취급하는 방법, 그리고 매개변수들 (개체집단의 크기, 여러 연산자들의 적용확률, 등) 을 구현하기 위하여 다른 데이터 구조를 사용할 수 있다. 그러나 개체집단은 어떤 변환과정을 겪으며, 진화과정동안 개체는 생존을 위하여 투쟁한다는 공통원리를 가지고 있다.

진화 프로그래밍의 아이디어는 새로운 것이 아니고 적어도 30 년 동안이나 우리 주위에 존재하여 왔다 [93], [113], [263]. 그러나 진화 프로그램에 대한 개념은 이전에 제안되었던 것과는 다르며 유전자 알고리즘 [142] 의 아이디어에 전적으로 기초하고 있다. 차이점은 (염색체 표현에 대하여) 확장된 유전 연산자들과 함께 보다 풍부한 데이터 구조들을 사용하고 있으나, 고전적 유전자 알고리즘은 개체에 대하여 일정한 길이의 이진 스트링 (염색체로서 데이터 구조 S) 과 이진 돌연변이와 이진 교배라는 두 연산자를 사용하고 있다는 것이다. 다시 말하여 유전자 알고리즘의 구조는 진화 프로그램의 구조 (그림 1) 와 동일하고, 차이점은 하위레벨에 숨겨져 있다. EP 에서는 염색체가 반드시 비트 스트링에 의해 표현되어야 할 필요는 없고 변천과정은 주어진 구조와 문제에 적합한 다른 "유전" 연산자를 포함하고 있다.

이것은 비교적 새로운 방향이다. 1985 년에 De Jong 만이 다음과 같이 기술하였다 [64] :

"탐색될 공간의 원소들이 행렬, 나무, 이중자 등과 같이 보다 복잡한 데이터 구조에 의하여 가장 자연스럽게 표현될 때 어떻게 할 것인가? 그들을 스트링 표현으로 재정의하는 방법들이 있어야 한다. 나는 이 분야의 어떠한 발전에도 주의를 기울이지 않는다."

위에서 언급된 바와 같이, 유전자 알고리즘은 일정한 길이의 이진 스트링과 단지 두 개의 기본적인 유전 연산자들을 사용한다. 유전자 알고리즘에 관한 두 개의 주된 (초기의) 연구 [142], [62] 는 그러한 GA 의 이론과 구현을 설명하고 있다. [114] 에서 언급된 바와 같이 :

"이 연구 [62] 가 기여한 바는 무자비한 축약과 단순화이다. De Jong 은 그의 단순화 때문에 무엇엔가 도달하였다. [중략] Holland 의 책 [142] 은 유전자적인 탐색에 있어서 유사성 부분집합 (스키마타), 최소 연산자 붕괴, 그리고 재생산적 선택의 결합된 역할을 수학적으로 인식함으로써 De Jong 과 그 이후의 모든 GA 연구에 대한 이론적인 토대를 마련하엿다. [중략] 그 이후의 연구자들은 [142] 의 이론적인 제안을 상당히 문자그대로 받아들이는 경향이 있었고 그래서 De Jong 의 깔끔한 코딩과 연산자의 구현성공을 보강해 주었다."

그러나 다음 문단에서 Goldberg [114] 는 다음과 같이 말하였다 :

"아무도 그의 연구가 그렇게 문자그대로 받아들여지기를 의도하지 않았다는 것은 아이러니컬하지 않다면, 흥미있는 일이다. 비록 De Jong 의 구현이 Holland 의 이론적인 단순화에 부합하여 사용가능한 기법을 개발하였지만, 이후의 연구자들은 두가지 업적을 모두 신성한 복음으로 취급하는 경향이 있었다."

주어진 문제의 해가 될 가능성이 있는 것들의 "자연스러운" 표현과 적용 가능한 여러 가지 "유전" 연산자들의 결합은 많은 문제들의 해의 근사화에서 상당히 유익할 수 있으며, 이러한 자연을 모델링하는 접근방식 (진화 프로그래밍) 은 일반적으로 문제해결에 대한 바람직한 방향인 것처럼 보인다. 이미 몇몇 연구자들은 배열된 목록 (상자포장에 대하여), 내재된 목록 (공장 스케줄링문제에 대하여), 변수-요소 목록 (반도체 레이아웃에 대해서) 과 같은 다른 표현방법을 탐구해왔다. 최근 10 년동안 여러 가지 응용에 적합하도록 변경된 유전자 알고리즘방법들이 보고되었다 [53], [126], [130], [131], [209], [277], [278], [300]. 이러한 변경된 방법들은 가변길이 스트링 (원소가 if-then-else 규칙들인 스트링 [277] 을 포함하여), 이진 스트링보다 더 풍부한 구조 (예를 들어 행렬 [300]), 그리고 특정한 응용의 필요를 충족시키기 위하여 변경된 유전 연산자에 대한 실험들을 포함한다 [203]. [216] 에서는 신경회로망 문제영역에 적합하도록 만들어진 돌연변이와 교배와 함께, 연산자로서 백프로파게이션 (신경회로망의 한 학습기법) 을 사용하는 유전자 알고리즘에 관한 설명이 있다. Davis 와 Coombs [48], [56] 는 패킷-스위칭 통신망을 설계하는 과정에서 하나의 단계를 수행하는 유전자 알고리즘을 설명하였는데, 사용된 표현은 이진이 아니고 다섯 개의 "유전" 연산자들 (지식기반, 통계적, 수치적) 이 사용되었다. 이 연산자들은 이진 돌연변이 및 교배와는 상당히 다르다. 다른 연구자들은 개별공정일정문제 [14] 를 해결하기 위한 연구에서 다음과 같이 기술하였다 :

"알고리즘의 성능을 향상시키고 탐색공간을 확장시키기 위하여 문제고유의 정보를 저장하는 염색체 표현이 고안되었다. 추가정보의 잇점을 이용하기 위하여 문제고유의 재조합 연산자들 역시 개발되었다."

이와 유사한 인용문들은 얼마든지 있다. 대부분의 연구들은 스트링이 아닌 염색체 표현에 의해, 또는 해결하려고 하는 문제를 포용하는 문제고유의 특정한 유전 연산자들을 설계하여 유전자 알고리즘의 구현을 "변경시키는" 것처럼 보인다. [169] 에서 Koza 는 다음과 같이 관찰하였다 :

"표현방법은 유전자 알고리즘 연구에서 주된 관심사인데, 그 이유는 표현이 시스템이 스스로 세계를 관찰하는 창문을 아주 제한할 수 있기 때문이다. 그러나 Davis 와 Steenstrup [54] 는 'Holland 의 모든 연구와 많은 그의 학생들의 연구에 있어서 염색체들은 비트 스트링이다' 라고 지적하였다. 스트링에 기초한 표현기법들은 많은 문제들에 대해서 어렵고 부자연스러우며 보다 강력한 표현기법에 대한 필요가 한동안 인식되어 왔다 [64], [65], [66]."

여러 가지 비표준적인 구현이 특정한 문제에 대해 창조되었는데, 단순히 고전적인 GA 는 문제에 직접 적용하기가 어려웠고 염색체구조의 변경이 약간 필요하였다. 이 책에서는 비트 스트링을 사용하는 고전적 유전자 알고리즘으로부터 의식적으로 벗어나서 더욱 풍부한 데이터 구조와 다양한 문제들의 구조에 적용시킬 수 있는 "유전" 연산자들을 탐색하였다. 그러한 구조와 연산자에 대한 실험에 의하여, 더 이상 유전자 알고리즘, 최소한 고전적인 GA 가 아닌 시스템을 얻었다. 여러 보고서의 제목은 다음과 같이 시작한다 : "수정된 유전자 알고리즘..." [204], "특별한 유전자 알고리즘..." [153], "비표준 유전자 알고리즘..."[209]. 또한 "유전자 알고리즘" 이라는 이름이 개발된 시스템에 관련되어 상당히 오해를 불러일으킬 수 있다는 느낌이 있다. Davis 는 많은 문제고유의 연산자들을 가지는 여러 비표준 시스템들을 개발하였는데, [57] 에서 다음과 같이 관찰하였다 :

"나는 유전자 알고리즘 분야에서 다른 연구자들의 시스템에 관하여 약간의 부정적인 시각을 가지고 있으며 [중략] 우리가 구축한 시스템이 유전자 알고리즘이라는 데에 솔직히 불신하고 있다. (왜냐하면 우리는 이진표현, 이진 교배, 그리고 이진 돌연변이를 사용하지 않았기 때문이다.)"

예를 들어 추가적으로 진화전략이 유전자 알고리즘인지 물어볼 수 있다. 이 반대도 사실인가? 진화 시스템들의 분류와 관련된 모든 문제들을 피하기 위하여, 이들을 단순히 "진화 프로그램 (EP)" 이라고 부른다.

왜 유전자 알고리즘으로부터 벗어나서 보다 융통성있는 진화 프로그램을 향하여 진행하는가? 아주 잘 이론체계가 잡혀졌다고 해도 GA 는 많은 분야에서 성공적인 응용을 제공하지 못했다. 이러한 실패의 뒤에 있는 주된 요인은 그들의 성공에 기여한 것, 즉 문제영역과 무관하기 때문인 것처럼 보인다.

GA 의 깔끔한 결과로 (문제영역과 무관함의 관점에서) 복잡한 구속조건을 다룰 수 없다. 앞서 언급했던 대로 유전자 알고리즘의 대부분의 연구에서 염색체는 비트 스트링 (0 과 1 의 열) 이었다. 문제에 대한 해답의 염색체 표현을 설계하는 데 있어서 고려되어야 할 중요한 물음은 문제에 대한 구속조건 (문제고유의 지식) 의 구현이다. [54] 에서 언급된 것처럼 :

"위반될 수 없는 구속조건은 그것을 위반하는 개체에 대해 큰 벌점을 부과하고, 적절한 벌점을 부과하거나, 구속조건을 위반하는 개체가 생성되지 않도록 하는 표현의 해독기를 만들어 내어서 구현될 수 있다. 이러한 해들은 각각 장점과 단점을 가지고 있다. 만일 평가과정에 높은 벌점을 부과하고 그 문제영역이 구속조건을 위반하는 개체를 생산하는 경향이 있다면, 유전자 알고리즘이 부적합한 개체를 평가하는 데 대부분의 시간을 소모할 위험이 있다. 게다가 부적합한 개체가 발견되었을 때 다른 것들을 몰아내고 개체집단이 더 좋은 개체를 탐색하지 않고 그 개체에 수렴하는 경우가 발생할 수 있는데, 그 이유는 다른 적절한 개체에 대한 가능한 경로를 위해서 부적절한 개체가 중간구조로서 생성되어야 할 필요가 있는데, 구속조건을 위반하는 데에 대한 벌점은 그러한 중간구조가 생성되기 어렵게 하기 때문이다. 만일 적절한 벌점을 부과한다면 평가함수의 나머지 부분이 적당한 구속조건의 벌점을 피하기보다 받아들임으로써 더욱 잘 만족될 수 있기 때문에 그 시스템은 구속조건을 위반하는 개체로 진화할 수도 있지만 위반하지 않는 것들보다 더 좋게 평가될 수도 있다. 만일 염색체로부터 부적절한 개체를 구축하는 것을 지능적으로 피하는 "해독기" 를 평가과정에 구축한다면 그 결과로 계산량이 크게 증가할 것이다. 더욱이 모든 구속조건이 이러한 식으로 용이하게 구현될 수 있는 것도 아니다."

(여러가지 벌점함수와 함께 해독기와 복구 알고리즘의 예가 배낭문제가 고려된 4.5 절에 주어져 있다.)

진화 프로그래밍에서 구속조건의 만족문제는 다른 경향을 가지고 있다. 어떤 벌점을 가지고 있는 평가함수를 선택하는 것이 문제가 아니라, 문제에 의해 부과된 모든 구속조건들을 만족하기 위한 의미있는 유전 연산자와 함께 "가장 좋은" 염색표현을 선택하는 것이다. 어떠한 유전 연산자도 부모로부터 자손세대로 어떤 특징구조를 전달해야만 한다. 그래서 표현 구조는 유전연산자를 정의하는데 있어서 중요한 역할을 한다. 게다가 다른 표현구조는 문제를 더욱 복잡하게 하는 구속조건의 표현에 대하여 다른 적합한 특징들을 가지고 있다. 이러한 두 개의 요소 (표현과 연산자) 는 서로간에 영향을 준다 어떠한 문제도 의미있는 유전 연산자가 존재하도록 적절한 표현을 만들어내는 주의깊은 해석을 필요로 할 것이다.

Glover 는 복잡한 키보드 배열문제의 해결에 대한 자신의 연구 [104] 에서 다음과 같이 기술하였다 :

"비록 GA 탐색기법의 강인한 특성이 키보드 배열문제의 요구에 아주 적합하지만, 비트 스트링 표현과 이상적인 연산자는 [중략] 요구되는 구속조건에 적절하게 맞지 않는다. 예를 들어 만일 세 개의 비트가 단지 40 개의 요소로 되어있는 단순한 키보드의 각 요소를 표현하는 데 사용되었다면, 모든 1016 개의 임의로 선택된 120 비트의 구조들 중에서 단 하나가 적절한 배열 맵 구조를 표현한다는 것을 쉽게 보일 수 있다."

그 밖의 인용구는 순회판매원문제가 간략하게 논의된 De Jong 의 연구 [70] 로부터 나온 것이다 :

"표준교배와 돌연변이 연산자를 사용하여 GA 는 사실상 고나심있는 모든 순열의 공간, 즉 도시들의 모든 조합의 공간을 전역탐색할 것이다. 명백히 N [여행하는 도시의 수] 이 증가함에 따라, 순열공간은 조합공간의 아주 작은 부분집합이고, 강력한 GA 의 표본화 휴리스틱은 표현을 잘못 선택하여 무능하게 되어 왔다."

AI 의 초기단계에서 복잡한 문제에 접근하는 일반적인 도구로서 일반적인 문제해결기 (GPS) 가 설계되었다. 그러나 실제로 나타난 바와 같이, 이들 시스템의 감당할 수 없는 복잡도 때문에 문제에 따른 지식을 포함시킬 필요가 있었다. 이제 역사는 스스로 반복되었다. 최근까지 유전자 알고리즘은 많은 어려운 문제들의 최적화에 유용한 일반적인 도구로서 인식되었다. 그러나 유전자 알고리즘에 문제고유의 지식을 포함시킬 필요성이 한동안 연구논문들 [7], [94], [97], [129], [282] 에서 인식되어 왔다. (GPS 로서) GA 는 너무나 문제영역과 무관하여 많은 응용분야에서 유용하지 못했다. 그래서 염색체의 데이터구조와 특정한 "유전" 연산자에서 문제고유의 지식을 포함시킨 진화 프로그램들이 훨씬 더 잘 수행된다는 것은 놀랄 일이 아니다.

고전적인 유전자 알고리즘과 진화 프로그램사이의 기본적인 개념의 차이가 그림 6-2 와 6-3 에 제시되었다. 고전적 유전자 알고리즘은 이진 스트링을 사용하는데, 원래의 문제를 적절한 (GA 에 적합한) 형태로 변경할 필요가 있다. 이것은 해가 될 가능성이 있는 것과 이진표현사이의 매핑, 해독기 또는 복구 알고리즘의 고려등을 포함하는데, 그리 쉬운 작업은 아니다.

그림 2  유전자 알고리즘의 접근방식

그림 3  진화 프로그램의 접근방식

반면에 진화 프로그램은 ("자연스러운" 데이터 구조를 사용하여) 해가 될 가능성이 있는 것의 염색체 표현을 변경하고, 적절한 "유전" 연산자를 적용하여 문제를 변경되지 않은 상태로 남겨둔다.

다시 말하면, 진화 프로그램을 사용하여 복잡한 문제를 해결하기 위하여, 그 문제를 유전자 알고리즘에 적합한 형태로 변환하거나 (그림 2), 또는 유전자 알고리즘을 그 문제에 맞게 변환할 수 있다 (그림 3). 분명히 고전 GA 는 전자의 접근방식, EP 는 후자의 접근방식을 취한다. 그래서 진화 프로그램의 배후의 아이디어는 아주 단순하고, 다음 표어에 기초하고 있다 :

"만일 산이 모하메드에게로 오지 않으면, 모하메드가 산으로 갈 것이다."

이것은 아주 새로운 아이디어는 아니다. [57] 에서 Davis 는 다음과 같이 기술하였다 :

"당분간은 이진 교배와 이진 돌연변이만으로 구성된 연산자들의 집합과 이진표현을 가지고 대부분의 실세계 문제들을 다룰 수 없는 사실인 것 같다. 이에 대한 한 이유는 거의 모든 실세계 영역이 그 문제영역의 해의 변환을 고려할 때 사용되는 문제영역 지식을 연관시키고 있다는 것이다. [중략] 나는 유전자 알고리즘이 아주 많은 실세계 응용에서 사용되기에 적절한 알고리즘이라고 믿는다. 나는 또한 실세계 지식을 해독기에 추가하거나 연산자 집합을 확장시킴으로써 실세계 지식을 알고리즘에 포함시켜야 한다고 믿는다."

그러한 변형된 유전자 알고리즘을 "진화 프로그램" 이라고 부른다.

유전자 알고리즘과 진화 프로그램 사이에 선을 긋는 것은 꽤 어렵다. 진화 프로그램이 유전자 알고리즘이 되기 위해 요구되는 것은 무엇인가? 해가 될 가능성이 있는 개체집단을 유지하는 것인가? 해가 될 가능성이 있는 것의 이진표현인가? 개체의 적합도에 근거한 선택과정인가? 재조합 연산자인가? 스키마정리의 존재인가? 구성부 가설인가? 이러한 모든 것들인가? 정수벡터 표현과 PMX 연산자를 가진 순회판매원문제에 대한 진화 프로그램 (10장) 이 유전자 알고리즘인가? 행렬표현과 산술교배 연산자를 가진 운송문제에 대한 진화 프로그램이 유전자 알고리즘인가? 이 책에서는 이러한 질문에 대한 대답을 제시하지는 않을 것이다. 그 대신 다양한 문제에 대해 진화 프로그래밍 기법을 사용한 몇 가지 흥미있는 결과를 제시할 것이다.

앞서 언급한 대로 여러 연구자들이 다양한 변경의 뒤에 숨어있는 잠재력을 인식하였다. [58] 에서 Davis 는 다음과 같이 기술하였다.

"사용자와 대화할 때 나는 내 계획이 다음과 같은 세 가지 원리들을 도입하여 유전자 알고리즘기법과 현재의 알고리즘을 혼합하는 것이라고 설명한다.

• 현재의 코딩의 사용. 혼합 알고리즘에서 현재 알고리즘의 코딩기법을 사용한다.
• 가능한 곳의 혼합. 혼합 알고리즘에 현재 알고리즘의 긍정적인 특징을 포함시킨다.
• 유전 연산자의 적응. 비트 스트링 교배와 돌연변이 연산자와의 유사성에 의해 새로운 형태의 코딩을 위한 교배와 돌연변이 연산자를 창조한다. 연산자와 마찬가지로 문제 영역에 기초한 휴리스틱을 포함시킨다.

[중략] 나는 이러한 세 가지 원리를 적용하여 창조한 알고리즘에 대해 혼합 유전자 알고리즘이라는 용어를 사용한다."

혼합 유전자 알고리즘과 진화 프로그램은 공통의 아이디어를 가지고 있는 것으로 보이는데, 그것은 고전적인 비트-스트링 유전자 알고리즘으로부터 벗어나서 적절한 데이터 구조 (현재의 코딩의 사용) 와 적절한 유전 연산자 (유전 연산자의 적응) 를 포함하는 보다 복잡한 시스템으로의 접근이다. 반면에 Davis 는 문제영역에서 얻을 수 있는 하나 또는 그 이상의 현재의 (전통적인) 알고리즘의 존재를 가정하였는데, 그러한 알고리즘의 기초 위에서 혼합 유전자 알고리즘의 구축이 논의되고 있다. 진화 프로그래밍에 대한 접근에서 이러한 종류의 가정을 전혀 하지 않는데, 앞으로 이 책에서 논의될 모든 진화 시스템은 백지로부터 구축된 것이다.

진화 프로그래밍의 강점과 약점은 무엇인가? EP 기법의 주된 강점은 광범위한 적용 가능성인 것 같다. 이 책에서는 다양한 문제들을 설명하고 각각에 대한 진화 프로그램의 구축을 논의하려고 한다. 결과는 아주 우수한 경우가 많은데, 그들 시스템은 상용 소프트웨어보다 훨씬 더 성능이 우수하다. 진화 프로그램과 연관된 또다른 강점은 본질적으로 병렬적이라는 것이다. [113] 에서 언급된 대로 :

"보통 수많은 트릭과 왜곡을 통하여 직렬 알고리즘이 병렬적으로 되는 세계에서, (아주 병렬적인) 유전자 알고리즘이 마찬가지로 부자연스러운 트릭과 반전에 의해 직렬적으로 되는 것은 커다란 아이러니이다."

물론 이것은 어떠한 (개체집단에 기초한) 진화 프로그램에 대해서도 사실이다. 반면에 진화 프로그램의 불충분한 이론적인 기초를 인정해야 한다. 다른 데이터 구조에 대한 실험과 교배와 돌연변이의 변경에 대해 주의깊게 해석해야 하는데, 그것은 적당한 성능을 보장할 것이다. 그러나 아직 이루어지지는 않았다.

그렇지만 몇몇 진화 프로그램들은 이론적 기초를 가지고 있는데, 정규문제에 적용된 진화전략 (8장) 에서는 수렴특성을 보일 수 있다. 유전자 알고리즘이 왜 동작하는가를 설명해주는 스키마정리 (3장) 가 있다. 그밖의 진화 프로그램에 대해서는 흥미있는 결과만을 가지고 있을 뿐이다.

일반적으로, AI 의 문제해결 전략은 "강한" 방법과 "약한" 방법으로 분류된다. 약한 방법은 문제영역에 대하여 거의 가정을 가지 않는데, 그 결과 광범위한 적용가능성을 보여준다. 반면에 대규모 문제로 규모를 증가시켰을 때 해의 비용이 조합적, 폭발적으로 증가할 수 있다 [68]. 이것은 문제영역에 대하여 강한 가정을 하고, 결과적으로 문제 해결 방법에서 이러한 가정을 이용함으로써 피할 수 있다. 그러나 이와같은 강한 방법의 단점은 제한된 적용가능성인데, 심지어는 관계된 문제에 적용할 때조차 상당한 재설계가 필요한 경우가 흔히 있다.

진화 프로그램은 약한 방법과 강한 방법사이의 어딘가에 위치한다. (유전자 알고리즘 같은) 어떤 진화 프로그램은 문제영역에 관하여 전혀 가정을 하지 않는 상당히 약한 방법이다. 몇몇 다른 프로그램들 (GENOCOP, GAFOC, GENETIC-2) 은 문제에 대한 종속정도가 변하는 보다 문제에 따라 좌우되는 방법들이다. 예를 들어 GENOCOP (7장) 은 모든 진화 전략들처럼 (8장) 매개변수 최적화 문제를 해결하기 위하여 구축되었다. 이 시스템은 몇몇 집합의 선형 구속조건들을 가지고 있는 어떠한 목적함수도 취급할 수 있다. GAFOC (7장) 과 GENETIC-2 (9장) 는 각각 최적제어 문제와 운송문제에 대해 동작한다. 다른 시스템들은 (스케줄링문제 및 순회판매원문제와 같은) 조합최적화 문제 (10장), 또는 그래프 작성문제 (11 장) 들에 적합하다. 결정규칙의 유도학습을 위한 진화프로그램의 흥미로운 응용이 12 장에서 논의되었다.

유전자 알고리즘이 약한 방법으로 인지되고 있다는 것은 약간 아이러니하다. 그러나 복잡한 구속조건이 존재하면 급속히 강한 방법으로 변화한다. 벌점함수, 해독기, 또는 복구 알고리즘을 고려하든 아니든, 이들은 특정한 응용에 맞게 고쳐져야 한다. 반면에 (훨씬 강하고, 문제고유의 방법으로 인지되고 있는) 진화 프로그램들은 갑자기 훨씬 약하게 보인다 (이 문제는 결론에서 좀더 논의할 것이다). 이것은 진화 프로그래밍 접근방식의 배후에 존재하는 거대한 잠재력을 보여준다.

모든 이러한 관찰은 비트 스트링보다 더욱 풍부한 구조위에서 정의된 다른 유전 연산자의 성질을 살펴보려는 흥미를 유발하였고, 더욱이 이 연구는 새로운 프로그래밍 방법론을 창조해 냈다 ([208] 에서 제안된 프로그래밍 방법론은 EVA (EVolution progr-Amming) 라고 불렸다). 개괄적으로 말하여 그러한 환경에서 프로그래머는 평가함수를 선택하고 개체집단을 초기화하는 것은 물론 주어진 문제에 대한 적절한 유전 연산자를 갖는 데이터 구조를 선택할 것이다 (그 밖의 다른 매개변수들은 다른 유전자 과정에 의해 조정된다).

그러나 그와같은 프로그래밍 환경의 기본구성을 제안할 수 있기 전에 많은 연구가 이루어져야 한다. 이 책은 많으 ㄴ문제들에 대해 진화 프로그램을 구축하는 다른 구조들과 유전 연산자를 조사하여 이 목표를 향한 첫걸음을 제공할 뿐이다.

이 책의 결론에서는 새로운 프로그래밍 환경의 아이디어로 돌아갈 것이다.