유전 프로그래밍

진화계산 및 진화디자인 : 황희수, 내하출판사, 2002, Page 95~113

유전프로그래밍은 컴퓨터 과학 분야에서 아서 사무엘 (Arthur Samuel) 에 의해 제기된 의문 가운데 하나인 "문제해결 방법을 명확하게 지시 받지 않은 컴퓨터가 스스로 문제해결 방법을 학습할 수 있는 방법이 없을까" 를 다루고자 하는 시도이다. 다시 말해, 유전프로그래밍은 컴퓨터가 인간에 의해 프로그램 되지 않은 상태에서 스스로 문제해결을 위한 프로그램을 자동으로 생성할 수 있도록 하는 연구인 것이다. 유전프로그래밍은 두 가지 접근법을 통해 발전해왓다. 하나는 코자 (Koza) 가 제안한 리습 S - 표현에 기초한 방법으로 그는 자신의 책에서 문제에 독립적인 방법을 통해 다양한 분야의 문제를 자동으로 해결할 수 있는 컴퓨터 프로그램을 진화시킬 수 있다는 놀라운 결과를 보여주었다. 다른 하나는 페르키스 (Perkis) 가 제안한 스택 기반의 표현방식이다. 이 장에서는 일반적으로 널리 쓰이는 코자의 방법을 설명하기로 한다.

유전프로그래밍은 유전알고리즘에 그 근본을 두고 있으며 이 둘 사이의 가장 큰 차이는 유전프로그래밍이 프로그램으로 해석되는 동적인 트리 구조를 진화시키는데 있다. 즉, 유전알고리즘의 출력이 정량적인데 비해 유전프로그래밍의 출력은 컴퓨터 프로그램이다. 유전프로그래밍은 스스로 프로그램 할 수 있는 컴퓨터 프로그램의 시초라 할 수 있다. 유전프로그래밍은 특히 이상적인 해가 없는 문제에서 그 우수성을 발휘한다. 그 예로 자동차를 운전하는 프로그램을 생각해보자. 차를 운전하는 방식에 대한 해는 존재하지 않는다. 일부 해는 시간이 좀 더 걸리지만 안전 운행을 중시할 수 있고, 다른 해는 위험이 따르지만 빨리 운전하려 할 수 있다. 따라서, 차를 운전하는 것은 안전과 속도뿐만 아니라 다른 관련 변수들을 포함해서 절충점을 찾는 것이다. 이 경우에 유전프로그래밍은 많은 변수를 고려한 후 절충을 통해 가장 효율적인 해를 찾을 수 있다. 잘 정리된 콘크리트 고속도로를 주행할 때와 비포장인 거친 도로를 주행할 때 운전 방식이 완전히 다른 것처럼 변수가 계속 변화하는 동적인 상황에서도 유전프로그래밍은 유용한 해를 찾을 수 있다.

유전프로그래밍을 정의하기 위해서는 먼저 프로그램을 구성할 원시함수와 터미널 집합을 정의해야 한다. 트리 구조에서 잎사귀 노드는 터미널에 대한 심볼을 포함하며 내부 노드는 함수에 다한 심볼을 포함한다. 프로그램 트리의 전체 구조는 함수 노드와 함수 노드에 대한 입력 파라메타의 수에 의해 결정된다. 가령, 하나의 함수가 3 개의 인수 파라메타를 갖는다면 자신의 함수 노드 아래에 3 개의 관련 하위 트리를 갖게 된다. 유전프로그래밍에서 자식 개체를 발생하기 위한 주요 메커니즘은 이들 하위 트리를 서로 교환하는 하위 트리 교배 연산이고, 교배를 통해 발생된 자식 개체는 부모와 다른 구조를 갖게 된다. 유전알고리즘에서 돌연변이는 주로 배경 연사자로 사용되지만 유전프로그래밍에서는 주요 연산자로 사용된다. 개체 프로그램의 적합도를 평가하고 선택을 통해서 목표한 해가 얻어질 수 있도록 진화를 유도한다. 프로그램의 가장 기본적인 구조는 모듈화된 특성을 갖도록 하는 것이다. 모듈 구조를 갖는 프로그램을 진화시키기는 위해서 프로그램 트리가 계층 구조를 가져야 하고 이를 구현하는 방법으로 자동정의 함수, 적응 표현체계 및 유전 라이브러리 등이 있다. 여기서는 가장 많이 쓰이는 자동정의 함수와 구조 변경 연산자를 5.2 절에 소개하고 모든 진화알고리즘의 특징인 병렬처리를 5.3 절에서 다룬다.

1. 단순 유전프로그래밍

(1) 개체의 데이터 표현 체계 및 평가

유전프로그래밍은 유전학적 학습 모델 (유전알고리즘) 을 프로그램공간으로 확장한 것으로 유전프로그래밍의 개체 (해) 는 컴퓨터 프로그램을 나타낸다. 따라서 유전프로그래밍에서 개체는 유전알고리즘에서와 같은 비트 문자열이 아닌 트리 구조에 의해 표현된다. 보다 정확히 말하면, 이는 프로그램 언어인 리습 (Lisp) 에서 사용되는 것과 같은 서로 연계된 데이터 구조이다. 많은 유전프로그래밍 사용자가 프로그래밍 언어로 리습을 사용하는 이유도 여기에 있다. 그러나 유전프로그래밍을 리습이 아닌 다른 프로그램 환경에서도 구현할 수 있기 때문에, 리습 언어를 반드시 사용해야 하는 것은 아니다. 프로그램은 터미널 및 함수 집합의 원소로 구성되므로 터미널과 함수 집합이 프로그램을 구성할 문장이라 할 수 있다. 이들 집합은 문제를 풀기에 적합하도록 선택된 기호 집합으로 통상 고정되어 있다. 터미널 집합은 프로그램의 변수와 상수로 구성되고, 함수 집합은 프로그램의 기능을 구현하는 것으로 표준적인 산술 연산, 수학 연산, 논리 연산 또는 문제에 따른 특수 함수를 가질 수 있다. 함수 집합은 인수를 갖는 프로그램으로 작용하기 때문에 트리의 내부 노드로 표시되며, 터미널은 인수를 갖지 않는 프로그램으로 작용하기 때문에 트리의 말단 노드로 표현된다.

유전프로그래밍에서 가장 구현하기 어렵고 중요한 개념이 적합도 함수이다. 적합도 함수는 프로그램이 문제를 얼마나 잘 해결할 수 있는지를 평가하며 문제에 따라 달라진다. 보통 유전프로그래밍에서는 개체 컴퓨터 프로그램이 다수의 적합도 평가 사례에 대해 실행되기 때문에 프로그램의 최종 적합도는 대표적 사례에 대한 적합도를 모두 합하거나 이들을 평균한 것으로 계산된다. 적합도 계산을 위한 대표적 사례에는 흔히 독립변수가 다른 값을 갖거나 시스템이 다른 초기값으로 시작하는 경우를 포함하지만, 무작위 또는 특정한 방식 (일정한 간격이나 규칙적인 격자점) 에 의해 선택되기도 한다.

이해를 돕기 위해 사격 및 미로 찾기 문제에 유전프로그래밍이 어떻게 적용될 수 있는지 알아보자. 움직이는 표적을 총으로 맞히는 프로그램을 만든다고 생각해 보자. 적합도 값은 탄환이 표적에서 벗어난 거리일 것이다. 풍속, 사용된 총의 종류, 표적과의 거리, 표적의 높이, 표적의 속도와 가속도 등 고려해야 할 변수가 많다. 많은 변수를 갖고 있지만 간단한 적합도 함수를 사용할 수 있는 이런 문제는 유전프로그래밍이 가장 잘 풀 수 있는 형태이다. 여기서 터미널 집합은 탄환, 총 및 표적의 속도와 가속도 등과 같은 변수이며, 함수 집합은 덧셈, 뺄셈, 곱셈, 나눗셈과 다른 복잡한 연산을 포함한다. 미로의 탈출구를 찾는 프로그램을 만들고 싶으면 우선 몇 개의 알려진 미로 문제를 가지고 프로그램을 학습시켜야 할 것이다. 출발점에서 미로의 탈출구까지 가장 이상적인 해를 점의 경로로 표시한다면 다음 선택한 경로에 대한 적합도는 프로그램이 찾아낸 점의 숫자를 통해 계산할 수 있다 (점의 수가 많으면 적합도는 높음). 프로그램이 미로에서 영원히 방황하는 것을 방지하기 위하여 적합도에 시간제한을 도입할 수 있다. 이 경우 터미널 집합은 '직진', '우측' 과 '좌측' 이라는 3 개의 명령어를 포함할 것이고 함수 집합은 '만약 "점" 이면 실행 X, 아니면 실행 Y' 와 같은 문장을 포함한다.

(2) 재결합 (교배)

교배는 유전프로그래밍에서 가장 중요한 연산자로 두 개의 개체를 교배하여 두 개의 새로운 자식 개체를 발생한다. 부모 개체는 통상 서로 다른 크기와 형태를 갖으며, 교배 후 자식 개체도 부모 개체와 다른 형태와 크기를 갖게 된다. 교배에 의한 자식 개체 1 은 부모 개체 1 의 교배 부분을 제거하고 부모 개체 2 의 교배 부분을 삽입함으로써 생성된다. 자식 개체 2 는 자식 개체 1 과 대칭적으로 구성된다. 예제 1 과 예제 2 를 살펴보자. 부모 개체 가운데 그림에서 굵은 선으로 표시된 부분 (식에서는 밑줄 그어진 부분) 이 자식 개체 생성을 위한 교배에서 교환될 부분이다. 교배 과정에서 하위 트리 전체가 교환되기 때문에 선택된 교배 지점에 상관없이 자식 개체로 문법적으로나 의미론적으로 항상 유효한 프로그램이 생성된다. 이 예제에서 유전프로그래밍의 이점 하나를 발견할 수 있다. 유전프로그래밍에서는 동일한 부모 개체가 교배해서 서로 다른 자식 개체를 발생할 수 있지만, 유전알고리즘에서는 그럴 수 없다. 다시 말해, 유전알고리즘은 동일한 해로부터 새로운 해를 만들 수 없기 때문에 개체의 다양성 측면에서 보면 유전프로그래밍이 유리하다.

예제 1  부모 개체가 다른 경우의 교배

예제 2  부모 개체가 동일한 경우의 교배

(3) 돌연변이

돌연변이에는 함수간의 교체, 터미널간의 교체와 하위 트리간의 교체가 있다. 예제 3 에 이들 돌연변이의 예가 보여진다. 터미널 돌연변이에 의해 그림 (가) 의 '2' 가 (나) 의 왼편 그림에서 'a' 로 교체되었다. 함수 돌연변이에 의해 그림 (가) 의 '-' 가 (나) 의 왼편 그림에서 '+' 로 교체되었다. 하위 트리 교체 돌연변이에 의해 그림 (가) 의 하위 트리가 (나) 의 오른편 그림과 같이 다른 트리로 대체되었다.

예제 3  단일 터미널의 돌연변이

(4) 선택 및 진화

집단에서 부모 개체를 선택할 때 다음 3 가지 선택 방법 가운데 하나를 사용한다.

    ■ 비례선택

개체의 적합도에 기초하는 확률을 사용하는 방법으로, 개체 가 다음 세대로 복제될 확률은 식 (1) 에 의해 계산된다.

                                           (1)

는 개체 의 적합도, 는 집단에 속한 개체의 적합도 합.

    ■ 승자승 선택

임의로 두개의 개체를 선택하고 적합도가 높은 개체를 선택한다. 이 방법은 동일한 성을 갖는 두 개체가 이성인 제 3 의 개체와 교배하기 위해 경쟁하는 생물학적 교배 양상을 묘사한 것이다.

    ■ 랭크기반 선택

개체의 적합도에 대한 랭크에서 기초해서 선택한다.

이상에서 설명한 단순 유전프로그래밍의 계산 과정을 가상 코드 형태로 정리하면 그림 1 과 같다.

그림 1  단순 유전프로그래밍의 일반적 계산 과정

2. 발전된 유전프로그래밍

자동화된 프로그램이 복잡한 문제를 해결할 수 있도록 하기 위해서는 프로그램이 문제 환경에 따라 재사용, 파라메타화, 규칙성, 패턴 및 모듈성 등을 이용할 수 있는 계층 구조를 가져야 한다. 따라서 주 프로그램과 하나 이상의 하위 프로그램 (재사용 가능하며 계층적으로 호출됨) 을 갖는 프로그램을 진화시킬 수 있어야 하기 때문에 이를 해결하기 위한 수단으로 자동 정의 함수와 구조 변경 연산자가 도입된다. 이 절에서는 자동 정의 함수와 구조 변경 연산자의 개념만을 간략히 소개하기로 한다.

(1) 자동 정의 함수

자동 정의 함수는 유전프로그래밍에게 하위 단위 함수를 자동으로 찾을 수 있는 능력을 제공해서, 어렵고 복잡한 문제를 해결할 수 있게 해준다. 유전프로그래밍이 자동 정의 함수를 갖고 있으면, 갖지 않는 경우에 비해 계산 요구량이 줄고 평균적으로 해의 크기가 작아진다. 자동 정의 함수를 유전프로그래밍에 도입하기 위해서는 초기 집단 개체가 특정하게 배열된 가지 구조와 같은 제한된 문법 구조를 가져야 한다. 자동 정의 함수는 현재 진화중인 호출 프로그램이 호출할 수 있으며, 유전프로그래밍 실행되는 동안에 동적으로 진화된다. 자동 정의 함수가 사용될 때, 집단의 개체 프로그램은 주요 결과 - 생성 가지와 함께 하나 이상의 재사용 가능한 함수 - 정의 가지 (자동 정의 함수) 로 구성된 계층 구조를 갖는다. 유전프로그래밍의 개체는 계층적 형태로 된 프로그램으로 유전알고리즘에서와 같은 해독 과정 없이 현재 상태에서 바로 실행될 수 있는 구조를 갖는다.

두 숫자의 지수화 계산을 포함하는 프로그램을 작성한다면 아마도 공통의 계산을 위한 서브루틴 (하위 프로그램, 절차 또는 정의된 함수) 을 먼저 작성하고, 주 프로그램에서 이 서브루틴을 두 번 호출하도록 할 것이다. 예제 5 에서 을 계산하기 위한 6 줄의 코드가 보여진다. 이 코드는 한 줄의 주 리습 프로그램과 지수 함수에 대한 근사값을 계산하기 위한 3 줄의 자동 정의 함수 (exp-approx) 로 구성된다. 1 행과 3 행은 주석이고 2 행은 exp-approx 함수를 두 번 호출한 후 이 둘의 차이를 계산하는 주 프로그램이다. 다음의 4 가지 사항을 처리한다. 첫째, 4 행의 defun 은 함수 이름 exp-approx 를 자동 정의 함수에 할당하고, 이 이름을 통해 주 프로그램이 정의된 함수를 참조할 수 있도록 한다. 둘째, 정의된 함수의 인수 목록 (4행) 을 찾는다. 이 예제에서 인수 목록은 (arg0) 이다. 셋째, 함수의 기능을 수행하는 몸체 (5 와 6 행) 는 를 테일러 급수로 전개한 것 중 첫 3 항을 합하는 계산을 한다. 넷째, 함수에 의해 복귀될 값을 찾는다. 여기서 사용된 defun 은 단지 하나의 지역 변수를 갖으며, 하나의 값을 복귀하고 하나의 명목 변수만을 참조한다. 그러나, 일반적으로 정의된 함수는 다수의 인수를 가지거나 아예 갖지 않을 수도 있으며, 다수의 값을 복귀시키거나 하나도 복귀시키지 않을 수도 있다. 또한, 문제의 실제 (전역) 변수를 명확하게 참조하거나 하지 않을 수도 있다.

예제 4   을 계산하기 위한 유전프로그래밍 코드

예제 5 에서 그림은 각각 하나의 함수-정의 가지와 주요 결과-생성가지로 구성된 프로그램의 전체적인 구조를 보여준다. 결과-생성 가지는 보통 하나 이상의 자동 정의 함수를 호출할 수 있다. 함수-정의 가지는 다른 자동 정의 기능 (심지어 자기 자신까지) 을 계층적으로 참조할 수도 있다. 결과-생성 가지가 단지 하나의 값만을 복귀할 때 이를 값-복귀 가지라 부르기도 한다. 이 그림의 왼편에 있는 것이 함수-정의 가지이고 오른편에 있는 것은 결과-생성 가지이다. 전체 프로그램에는 8개의 서로 다른 형태의 점이 있는데 그림에서 점선 위에 위치한 첫 6 개는 그 형태가 변하지 않는다. 전체 프로그램이 평가될 때 PROGN 은 두 가지를 순차적으로 평가한다. PROGN 은 첫 가지인 함수-정의 가지를 먼저 평가한다. 함수-정의 가지는 단지 자동 정의 함수인 ADF0 만을 정의한다. PROGN 은 두 번째 가지인 결과-생성 가지를 평가하고, 이 가지의 몸체는 자동 정의 함수인 ADF0 를 참조할 수 있다. 전체 프로그램에 의해 복귀된 값은 결과-생성 가지와 관련된 VALUES 기능에 의해 복귀된 값으로 구성된다. 이런 구성에서 자동 정의 함수에 대한 참조는 동일한 개체 프로그램 내에 존재하는 자동 정의 함수에 국한된다.

예제 5  각기 하나의 함수-정의 가지와 결과-생성 가지로 구성된 컴퓨터 프로그램

유전프로그래밍은 함수-정의 가지와 결과-생성 가지에서 자동 정의 함수로 구성된 프로그램 개체 집단을 진화시킨다. 함수-정의 가지와 결과-생성 가지의 구조는 적합도에 따른 선택 압력과 교배 및 돌연변이 연산에 의해 세대를 거치면서 진화한다. 결과-생성 가지는 함수-정의 가지에 의해 정의된 함수를 사용할 수 있지만, 정의된 함수가 실제 호출되는지의 여부는 사전에 알 수 없으며, 진화 과정에 의해 결정된다. 위의 예제에서 개체 프로그램은 각기 하나의 함수-정의 가지와 결과-생성 가지로 구성되므로 임의로 발생된 초기 집단의 개체도 반드시 이와 동일한 문법 구조를 갖도록 제한된다. 초기의 모든 개체 프로그램은 형태 ① 에서 ⑥ 까지의 6 점에 의해 표현된 고정된 구조를 가져야 한다. 함수-정의 가지에서 각 함수와 터미널은 ⑦ 번 형태이다. 함수-정의 가지는 함수 집합에 속한 함수와 터미널 집합에 속한 터미널의 임의적 결합에 의해 구성된다. 터미널 집합은 보통 지역 변수 (예 : ARG0) 를 포함한다. 결과-생성 가지에서 각 함수와 터미널은 ⑧ 번 형태이다. 결과-생성 가지는 터미널 집합에 속한 터미널과 함수 집합에 속한 함수의 임의적 결합에 의해 구성된다. 통상 결과-생성 가지에서 함수 집합은 보통 이용 가능한 함수 (예, ADF0) 를 포함하지만 정의 함수의 명목상 변수는 포함하지 않는다. 결과-생성 가지는 문제의 실제 변수를 포함하며 이 실제 변수가 함수-정의 가지에 나타날 수도 있지만 대개는 나타나지 않는다. 교배 후에도 자식 개체에서 제한된 문법 구조가 보존되어야 한다. 개별 프로그램은 형태 ① 에서 ⑥ 까지의 6 점에 의해 고정된 구조를 가져야 하기 때문에, 교배 점은 형태 ⑦ 과 ⑧ 의 점에 국한된다. 첫 부모 개체에서 교배 점으로 형태 ⑦ 이나 ⑧ 이 선택되도록 하고, 교배 점이 선택되면 두 번째 부모 개체의 교배 점도 같은 형태 (형태 ⑦ 또는 ⑧) 를 취한다.  이것은 교배를 통해 부모 개체 함수-정의 가지의 하위 트리를 서로 교환하거나 부모 개체 결과-생성 가지의 하위 트리를 서로 교환하도록 한다. 부모 개체의 교배 점 선택에 의한 이런 제한은 이후 발생하는 모든 자식 개체에서 초기 집단에서 만들어진 제한된 문법 구조를 그대로 유지할 수 있도록 해준다. 이렇게 고정된 점은 교배나 돌연변이에 의해 변경되지 않기 때문에 불변 점이라 불린다. 그러나 다음에서 논의되는 구조 변경 연산자가 도입되면 불변 점은 더 이상 쓸모가 없어진다.

(2) 구조의 진화

단일-가지로 된 프로그램의 경우에 유전프로그래밍은 해 (프로그램 트리) 의 크기와 형태를 자동으로 결정하지만, 다수-가지로 된 프로그램이 자동 정의 함수와 함께 사용되면 진화될 프로그램의 구조를 결정하는 방법이 필요하게 돈다. 다수-가지로 된 프로그램의 구조는 함수-정의 가지 (자동 정의 함수) 와 각 함수-정의 가지가 소유한 인수의 숫자로 구성된다. 전체 프로그램의 구조를 만드는 한 가지 방법은 유전프로그래밍의 실행 과정에서 동적인 구조를 선택하는 것으로 진화 선택이라 부른다. 진화 선택은 구조적으로 다양한 초기 집단에서 시작해서 진화가 진행됨에 따라 특정 구조를 갖는 개체가 문제를 해결하는데 적합함이 드러나면 그 개체를 번성시키고 최종적으로 살아남도록 하는 방법이다. 이는 유전프로그래밍에서 구조적으로 다양한 초기 집단을 발생할 수 있도록 해준다. 그러나 이 방법은 구조적으로 다른 부모 개체로부터 문법 및 의미론적으로 유효한 자식 개체를 발생할 수 있도록 하는 구조-보존 교배를 필요로 한다.

전체 프로그램의 구조를 진화시키기 위한 또 다른 방법으로 구조 변경 연산자를 사용한다. 구조 변경 연산자는 유전프로그래밍이 실행되는 동안 다수-가지로 구성된 컴퓨터 프로그램이 문제를 해결할 수 있는 순차와 구조를 갖도록 해준다. 구조 변경 연산은 자동 정의 함수와 함께 다음의 3 가지 역할을 수행함으로써 자동으로 문제를 해결할 수 있도록 해준다. 첫째, 전체 프로그램의 구조를 결정할 수 있는 수단을 제공하며 둘째, 문제 표현 체계를 동적이고 자동으로 변경할 수 있도록 해주며 셋째, 문제를 다수의 하위 문제로 분해하고 해당 하위공간 (전체 프로그램보다 차원이 낮지만 유용함) 의 탐색을 통해 하위 문제의 해를 찾은 후 이를 전체 문제의 해로 조합한다. 구조 변경 연산자에는 가지 복제, 인수 복제, 가지 제거, 인수 제거, 가지 생성 및 인수 생성의 6 가지가 있다.

    ■ 가지 복제

이 연산은 프로그램의 가지 가운데 하나를 복사하는 것으로 다음과 같은 과정을 통해 이루어진다. 첫째, 이 연산자를 적용할 개체 프로그램을 선택한다. 둘째, 선택된 개체 프로그램의 함수-정의 가지 가운데 하나를 복사 대상으로 선정한다. 셋째, 선택된 프로그램에 고유한 이름을 갖는 새로운 함수-정의 가지를 더해서 함수-정의 가지 숫자를 하나 증가시킨다. 새로운 함수-정의 가지는 본래 가지와 동일한 몸체와 인수 목록을 갖는다. 넷째, 프로그램에서 복사 대상 가지의 호출은 새로 복제된 함수-정의 가지를 호출하도록 변경하거나 그대로 둔다. 구조 변경 연산의 적용 대상 프로그램을 선정하는 것은 적합도에 기초해서 확률적으로 이루어지기 때문에 더 적합한 개체가 구조 변경에 참여할 확률이 높다. 예제 6 의 그림 (나) 는 그림 (가) 에 가지 복제 연산을 적용한 결과이다. 현재는 동일한 그림 (나) 의 두 가지가 유전연산을 거치면 변화하게 될 것이다. 이 가지 복제 연산은 항상 문법적으로 유효한 프로그램을 발생한다.

예제 6  가지 복제 연산의 적용

    ■ 인수 복제

이 연산은 프로그램의 자동 정의 함수 가운데 하나로부터 명목 인수 하나를 복제하는 것으로 다음과 같은 과정을 거친다. 첫째, 이 연산자를 적용할 대상 개체 프로그램을 선택한다. 둘째, 선택된 개체 프로그램의 함수-정의 가지 인수 중 하나를 복제 대상 인수로 지정한다. 넷째, 복제 대상 인수에 고유한 이름을 붙이고 그 이름을 선택된 함수-정의 가지의 인수 목록에 추가하여 인수의 숫자를 하나 증가시킨다. 다섯째, 선택된 함수-정의 가지의 몸체에서 복제 대상 인수를 호출하는 경우에 대해 이를 그대로 두던지 새로 복제된 인수로 변경된 인수로 변경하던지 임으로 선택한다. 여섯째, 선택된 함수-정의 가지를 호출하는 경우 복제 대상 인수에 대응하는 인수 하위 트리를 찾아내고 호출시에 이 인수 하위 트리를 복제함으로써 호출시 인수의 숫자를 하나 증가시킨다. 복제된 인수를 포함하고 있는 함수-정의 가지가 이전에 존재하는 인수를 그대로 복제한 후 호출되기 때문에 이 연산으로 인해 전체 프로그램의 복귀 값이 변하지 않는다.

    ■ 가지 제거

이 연산은 프로그램의 자동 정의 함수 가운데 하나를 제거하는 것으로 다음과 같은 과정을 거친다. 첫째, 이 연산자를 적용할 대상 개체 프로그램을 선택한다. 둘째, 선택된 개체 프로그램의 함수-정의 가지 가운데 하나를 선정한다. 셋째, 선택된 프로그램으로부터 삭제 대상인 가지를 제거해서 가지 숫자를 하나 줄인다. 넷째, 선택된 프로그램 내에서 삭제 대상 가지를 호출하는 경우 이를 남아 있는 가지를 호출하는 것으로 변경한다. 이 변경에는 첫째, 대신하기에 적합한 함수-정의 가지를 찾아 이것으로 대체하는 방식 둘째, 삭제 대상 가지를 호출하는 대신에 이용 가능한 함수와 터미널로 구성된 새로운 하위 트리를 임으로 발생하도록 하는 방식과 셋째, 삭제 대상 가지의 호출시 대상 가지의 몸체 전부를 삽입하는 방식이 있다.

    ■ 인수 제거

이 연산은 프로그램에서 자동 정의 함수의 인수 가운데 하나를 삭제하는 것으로 다음과 같은 과정을 거쳐 이루어진다. 첫째, 이 연산자를 적용할 대상 개체 프로그램을 선택한다. 둘째, 선택된 개체 프로그램의 함수-정의 가지 가운데 하나늘 선택한다. 셋째, 선정된 함수-정의 가지의 인수 가운데 하나를 삭제 대상으로 지정한다. 넷째, 삭제 대상 인수를 선정된 함수-정의 가지의 인수 목록에서 제거한다. 다섯째, 선택된 프로그램에서 선정된 함수-정의 가지를 호출할 때 그 호출에서 삭제 대상인수에 대응하는 인수 하위 트리를 제거한다. 여섯째, 선정된 함수-정의 가지의 몸체에서 삭제 대상 인수를 호출할 때 이 인수를 기존에 남아 있는 인수로 대체한다. 인수가 삭제될 때 이 인수에 대한 참조도 변경되어야 하며, 그 방법은 가지 제거 연산에서와 유사하다.

    ■ 가지 생성

이 연산은 하나의 새로운 자동 정의 함수를 다음과 같은 과정을 통해 만든다. 첫째, 이 연산자를 적용할 대상 개체 프로그램을 선택한다. 둘째, 선택된 개체 프로그램의 함수-정의 가지나 결과-생성 가지의 몸체에서 한 점을 선택한다. 이 점은 생성될 가지의 몸체 부분에서 가장 상위의 점이 된다. 셋째, 선택된 점에서 그 아래로 깊이에 우선하면서 하위 트리를 횡으로 이동한다. 넷째, 횡으로 이동하면서 만나는 모든 점에 대해 그 점을 생성될 가지를 위한 인수 하위 트리의 최상위 점으로 지정할 것인지를 결정한다. 지정이 되면 그 점 아래에 있는 하위 트리에 대해 더 이상 횡으로 이동하지 않는다. 깊이 우선의 횡 이동은 계속되고, 이 네 번째 과정은 횡 이동 동안 접하게 되는 각 점에 대해 반복된다. 선택된 점 아래의 하위 트리의 횡 이동이 완료 되었을 때는 지정된 점이 하나도 없을 수도 있고 하나 이상이 있을 수도 있다. 다섯째, 새로 생성된 함수-정의 가지에 고유한 이름을 붙인다. 새 가지의 인수 목록은 깊이 우선의 횡 이동 동안 지정된 점의 수와 동일한 수만큼의 연속적인 번호를 부여 받은 명목 변수로 구성된다. 새 가지의 몸체는 선택된 점에서 시작하는 하위 트리의 수정된 복사본을 구성한다. 복사본의 수정은 다음과 같이 이루어진다. 본래 하위 트리의 횡 이동 동안 지정된 점에 대응하는 복사본에서의 점을 고유한 명목 변수로 대체한다. 새로운 함수-정의 가지의 인수 목록에 있는 명목 변수의 수와 동일한 수의 명목 변수 (고유 이름을 가짐) 를 포함하는 새 함수-정의 가지의 몸체가 생긴다. 여섯째, 프로그램의 선택 점을 새 함수-정의 가지로 대체한다. 선택 점 밑에 위치한 점이 횡 이동 중 지정되지 않았다면 가지 생성 연산은 종료된다. 일곱째, 횡 이동 중 선택 점 밑에 있는 점이 하나 이상 지정되었다면 이제 막 삽입된 이름의 새 함수-정의 가지 밑에 있는 하위 트리는 새 함수-정의 가지에 있는 명목 인수의 수와 동일한 수의 인수 하위트리를 받게 된다.

    ■ 인수 생성

이 연산은 함수-정의 가지에 새로운 명목 인수를 다음과 같은 과정을 거쳐 생성한다. 첫째, 이 연산자를 적용할 대상 개체 프로그램을 선택한다. 둘째, 선택된 개체 프로그램의 함수-정의 가지 가운데 하나를 선정한다. 셋째, 생성될 인수를 정의하기 위해 선정된 함수-정의 가지의 인수 목록에 고유한 이름을 붙인 새 인수를 추가한다. 넷째, 선택된 함수-정의 가지에서 선정된 점과 그 밑의 전체 하위 트리를 새로운 인수 이름으로 대체한다. 다섯째, 프로그램에서 인수 생성을 위해 선택된 함수-정의 가지를 호출하는 경우 부가적인 인수 하위 트리를 해당 호출에 추가한다.

구조 변경 연산은 초기 집단의 생성 및 교배에서 유전프로그래밍의 구현에 영향을 미친다. 이와 관련된 상세한 내용은 참고문헌을 참고하기 바란다. 구조 변경 연산자를 도입하면, 그림 1 의 유전프로그래밍 계산 과정은 그림 2 와 같이 변경된다.

그림 2  구조 변경 연산을 포함한 유전프로그래밍의 계산 과정

3. 병렬 유전프로그래밍

모든 다른 진화알고리즘의 병렬처리에서와 같이 대부분의 노력은 부모를 선택하고 자식을 발생하는 메커니즘을 병렬처리 하는데 집중된다. 개체에 대한 평가를 병렬처리 하는 것은 쉬우며 모든 병렬처리는 개체 수준에서 병렬처리와 하위 집단상에서 병렬처리로 구분될 수 있다. 앙드레 (Andre) 와 코자 (Koza) 는 유전프로그래밍의 병렬처리구현을 위한 시스템 기준으로 2500 점까지 포함할 수 있는 다수 가지로 구성되는 프로그램을 선택했다. 점당 한 바이트의 기억용량을 사용하기 때문에 한 점은 함수, 터미널과 임의의 상수를 합하여 총 256 개를 나타낼 수 있다. 집단의 크기가 1000점당 한 바이트를 사용하고, 2500 점을 갖는 개체 프로그램 집단을 생각하면 2.5 메가바이트의 기억용량이 필요하다. 개체의 구조가 다양하다면 실제 기억용량은 3 메가바이트에 달할 것이다. 개체 하나의 적합도를 평가하는데 1 초가 걸린다면 집단에 대한 적합도 평가에는 1000 초가 걸리고 이를 100 세대 진화시킨다면 그 처리에 하루 정도가 걸린다. 따라서 유전프로그래밍을 병렬 처리해야 할 필요성을 느낄 수 있다. 이들은 트랜스퓨터를 사용하여 병렬 유전프로그래밍을 구현하였다. 고정된 길이의 문자열을 사용하는 유전알고리즘을 트랜스퓨터 네트워크상에서 병렬처리한 사례는 많이 있다. 병렬처리를 위해 트랜스퓨터를 사용한 이유는 트랜스퓨터가 충분한 통신 능력을 갖고 있기 때문이다. 병렬 처리 원리는 기본적으로 유전알고리즘의 경우와 차이가 없다.

4. 활용 분야

코자는 그의 논문에서 유전프로그래밍이 인간의 경험과 지식에 의한 결과보다 우수하고 성공적인 컴퓨터 프로그램을 자동으로 생성할 수 있는 대표적인 14 가지 사례를 그 선정 기준과 함께 제시하였다. 이들 사례는 증폭기 설계, 필터 설계, 로봇 제어회로 설계, 계산회로 설계, 온도 감지회로 설계, 항목 분류 네트워크 생성, 외부 세포질과 세포막 단백질의 분류 등을 자동으로 할 수 있는 컴퓨터 프로그램을 다루고 있다. 유전프로그래밍은 계량경제 분야에도 사용된다. 경험적으로 관측된 경제변수 사이의 관계를 표현하는 계량경제 모델을 찾는 문제는 독립변수 값이 입력으로 주어질 때 출력인 종속변수 값을 발생하는 컴퓨터 프로그램을 찾는 문제로 볼 수 있다. 보통 이런 문제는 가장 잘 맞는 모델 형태를 먼저 결정하고 나서 선정된 모델의 최적 수치 계수를 구사는 것으로 해결된다. 유전프로그래밍을 사용하면 최적의 함수 형태에 대한 사전 지식이 없어도 최적의 함수 형태와 수치 계수를 동시에 찾을 수 있다. 이는 주어진 입력하에 목표 출력을 생성할 수 있는 컴퓨터 프로그램을 탐색하는 것이다. 입출력 데이터로부터 입출력 관계를 정의하는 모델 형태와 모델의 계수를 찾아내는 것은 적용 분야와 사용 목적에 따라 차이는 있겠지만, 보통 모델링 (modeling), 예측 (prediction 이나 forcasting), 데이터 발굴 (data mining) 또는 기호 회귀 (symbolic regression) 라 불리며 유전프로그래밍 뿐만 아니라 다른 진화알고리즘도 이 분야에 대한 적용 사례가 많이 있다.