유전자 프로그래밍 : 정환묵

유전자 프로그래밍

Genetic Programming (GP) 은 Genetic Algorithm (GA) 의 유전자형을 구조적인 표현이 취급될 수 있도록 확장하여 프로그램의 생성과 학습, 추론, 개념형성 등에 적용하는 것을 목적으로 한다. GP의 기본적인 생각은 스텐포드 대학의 J. Koza로부터 제안되었다. 현재 Koza의 연구실에는 다수의 GP 연구자가 모여 GP는 GA에 있어서 한 분야를 확립하고 있다.
GP의 수법을 AI에 적용하여, 학습, 추론, 문제 해결을 실현하는 방식을 진화론적 학습(evolutionary learning)이라 부른다. 이것은 표현되는 지식을 변환하여, 선택 도태에 의하여 보다 적절한 해를 남기려고 하는 적합적인 학습방법이다. 진화론적 학습은 분류자 시스템(classifier system)등으로 대표적인 GBML (Genetic-Based Machine Learning, GA와 같은 기계학습)과도 많은 공통점을 가진다. GP에는 그래프구조(특히 나무구조)를 취급할 수 있도록 GA의 방법을 확장한다. 따라서 알고리즘의 기본적인 실행 방법은 GA와 동일하고 염색체의 구조만 다른다. 여기서 일반적으로 LISP의 S-식(Symbolic Expression)은 나무구조로서 표현 가능하기 때문에 GP에서는 유전자로서 LISP의 프로그램을 취급하는 경우가 많다.

유전 연산자

프로그램 진화를 위한 기본적인 유전 연산자로 다음의 세 가지가 있으며 그 외에도 문제에 따라 여러 가지를 사용한다(단, 그림의 ○은 노드를 ∧는 가지를 나타낸다.)

(1) 돌연변이
임의의 노드를 선택하여 임의적으로 변경한다.

(OR(AND (D0 D1)D0))
→(OR (AND ((NOTD1) D1)D0)

(2) 교 배
두 개의 나무(tree, 프로그램)를 선택해서 각각의 나무의 일부분을 서로 교환한다.

(OR (NOT D1) (AND D0 D1))
(OR (OR D1 (NOT D0) (AND (NOT D10 (NOT D1))
→(OR (AND (NOT D0) (NOT D1) (AND D0 D1))
(OR (OR D1 (NOT D0)) (NOT D1))

[그림 1] 돌연변이의 이전, 이후의 구조

[그림 2] 교배 이전, 이후의 구조

(3) 역 위
한 나무 내에서 임의의 노드를 택하여 그 노드의 자식 가지의 위치를 바꿈

(+(-A(%(BC) D) (^*EF))
→(+(-A(%(CB) D) (^*EF))

(4) 캡슐화
어떠한 기능을 하는 부분(몇 개의 함수와 말단 기호)을 묶어 하나의 덩어리로 취급하여 알고리즘을 실행한다.

(5) 소 거
프로그램이 도달하지 않은 부분을 제거하는 연산자이다.

유전자 프로그래밍의 응용분야

GP는 로봇의 프로그램 생성, 게임의 프로그램, 화상이해, 인공지능에 관한 다양한 문제해결, 학습 등에 탐색의 유효성이 확립되어졌다. 또한 최근에는 함수를 스스로 정의하여 효율적으로 이용하는 수법(자동함수정의, Automatically Defined Function)이 제안되어져 있다.

유전자 프로그래밍의 특징

유전 연산자

유전자 프로그래밍의 응용분야