유전 프로그래밍 설명: 기계가 스스로 코드를 작성하는 법

우리 기계가 스스로 프로그램을 작성하는 날이 오면 컴퓨터 과학의 '성배(Holy Grail)'가 발견된 셈일 것입니다. 유전 프로그래밍(GP)은 그 방향으로 나아가는 비교적 새로운 머신러닝 패러다임입니다.

GP는 제어 공학 분야에서 큰 가능성을 보여줍니다. 이 기사에서는 유전 프로그래밍이 무엇인지, 어떻게 표현되는지, 예제 프로그램을 살펴보겠습니다.

이 기사는 시리즈 첫 번째입니다. 다음 항목으로 넘어가려면 아래에서 선택하세요:

• 진화 알고리즘의 유전 연산자
• 유전 알고리즘 예제: 정렬 프로그램 진화와 심볼릭 회귀
• 유전 프로그래밍의 응용과 한계

유전 프로그래밍과 유전 알고리즘

GP는 본래 존 홀랜드(John Holland)가 고안한 유전 알고리즘(GA)의 변형입니다. GA처럼 GP는 적합도 비례 복제, 교차(crossover), 돌연변이(mutation) 같은 유전 연산자에 의존하는 진화 알고리즘으로, 인코딩된 프로그램 또는 '개체(individual)' 집단을 세대를 거치며 해법을 향해 진화시킵니다.

하지만 GA가 일반적으로 고정 길이 비트 문자열 인코딩을 사용하는 반면, GP는 실제 프로그램의 가변 크기 트리 기반 표현을 사용합니다. 따라서 성공적인 GP 실행 결과는 적절한 입력을 받아 실행했을 때 원하는 결과를 산출하는 컴퓨터 프로그램을 생성합니다.

니콜 크레이머(Nichael Cramer)와 존 코자(John Koza)는 GP의 기초를 닦은 것으로 평가받습니다. 존 코자(GP 특허 보유자)는 GP에 대한 상당한 연구를 수행했으며, 그의 저서 "Genetic Programming"은 이 분야의 대표적 저작으로 여겨집니다. 현재 연구는 로봇 내비게이션, 게임 전략 습득, 심볼릭 회귀 분석, 제어 시스템 등 광범위한 응용에서 GP의 고무적인 성공을 보여주고 있습니다.

유전 프로그래밍 표현

앞서 언급한 트리 기반 표현은 GP의 핵심으로, 사실상 모든 컴퓨터 프로그램을 이 방식으로 표현할 수 있습니다. 실제로 LISP 같은 함수형 언어는 이 형태에 잘 맞으며, LISP S-표현이 어떻게 트리로 도식화될 수 있는지 쉽게 알 수 있습니다(그림 1).

아래는 동일한 정보를 표현하는 세 가지 별도 표현입니다:

단순 프로그램 조각:
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;
END


LISP 등가물:
(progn (if (a < b)
 (setq a (+ a 1))
 (setq b (* b b))
 )
 (setq c (* (* a b) 2))
)

그림 1. 프로그램의 트리 표현. (progn arg1 arg2 arg3 ... argn)은 각 인수를 순차적으로 평가합니다.

트리의 내부 노드는 함수로 구성되고, 리프 노드는 터미널로 구성됩니다. 함수는 최소 1개의 인수 개수(일반적으로 아리티arity라고 함)를 가져야 하며, 다른 함수나 터미널과 연결되어 트리 내 가지의 '접착제' 역할을 합니다.

터미널은 일반적으로 상수와 변수를 포함합니다. 터미널이 트리의 리프를 형성하므로 아리티는 항상 0입니다. 해결하려는 문제에 대한 함수 세트와 터미널 세트를 선택해야 합니다. 예를 들어 논리 함수 AND, OR, NOT과 두 불리언 입력 변수를 나타내는 터미널 X1, X2는 XOR 불리언 함수를 합성할 수 있는 프로그램을 발견하려는 시도에 적합합니다. 또한 한 프로그램이 주어진 문제를 다른 프로그램보다 더 잘 푸는지 측정할 수 있는 피트니스 함수도 필요합니다.

예를 들어 XOR 경우, X1과 X2에 대한 4가지 가능한 불리언 입력(0 0, 0 1, 1 0, 1 1)에 해당하는 각 피트니스 케이스마다 프로그램을 한 번씩 실행하고, 각 테스트 케이스에 대한 올바른 응답(0, 1, 1, 0)의 수를 합산해 프로그램의 피트니스를 테스트할 수 있습니다.

분명히 완벽한 점수 4를 내는 프로그램은 XOR 문제의 해법으로 간주되며, 리스트 1에 나와 있습니다.

GP로 발견한 XOR 문제의 완벽한 해법:
(defun program ()
  (AND (OR X1 X2)
  (NOT (AND X1 X2) )
  )
)

리스트 1. XOR 결과

다음: 유전 연산자

다음 기사에서는 진화 알고리즘을 가능하게 하는 유전 연산자를 살펴보겠습니다. 더 복잡한 예제 알고리즘에서도 이를 사용할 것입니다.

추천 도서

• Kinnear, Jr., K. E. (ed.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass.: Addison-Wesley, 1973
• Koza, J. R. Genetic Programming. Cambridge, Mass.: The MIT Press, 1992.
• Koza, J. R. Genetic Programming II. Cambridge, Mass.: The MIT Press, 1994.
• Montana, D. J. “Strongly Typed Genetic Programming.” BBN Technical Report #7866, May 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.