유전 알고리즘의 힘과 한계 탐구

이번 유전 프로그래밍(GP) 시리즈에서는 유전 프로그래밍이 무엇인지, 정보를 어떻게 표현하는지, 진화 알고리즘에서 유전 연산자가 어떻게 작동하는지, 심볼릭 회귀를 통한 정렬 프로그램 진화 예제를 다뤘습니다.

여기서는 이 기술이 발전함에 따라 무엇을 달성할 수 있는지 고수준에서 살펴보겠습니다.

유전 프로그래밍의 실용적 고려사항

이 시리즈 마지막 장을 이해하기 위해 시리즈 첫 부분에서 다룬 XOR 예제를 상기해 봅시다:

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

리스트 1. XOR 결과.

이전 문서의 심볼릭 회귀 예제도 되짚어 보겠습니다:

구간 (0 <= x <= pi/2)에서 sin(x)의 다항식 근사

(defun program ()
  (+ (* (* (* X X) X)
  (* 0.2283 -0.6535))
  X)
)

위 프로그램을 단순화하면 다음 동등 방정식 도출:

polysin(x) = -.1492 x3 + x

결과:

리스트 4. 심볼릭 회귀.

여기서 제시된 XOR과 심볼릭 회귀 예제 모두 평가 시 단일 값을 반환합니다.

이 특성이 제약은 아닙니다. 함수나 터미널이 실행 시 부작용(side effect)을 가질 수 있기 때문입니다. 정렬 프로그램처럼 벡터 내 요소 쌍을 교환하는 잠재적 부작용을 가진 함수가 포함된 경우가 흔합니다. 변수 간 대입이나 로봇 방향 변경 등 유용한 부작용 예도 많습니다.

함수 세트에는 조건부 함수가 포함되어 진화된 프로그램이 의사결정할 수 있게 합니다. 조건부 함수는 인수를 선택적으로 평가합니다. 예를 들어 (if arg1 arg2 arg3)와 같은 아리티(arity) 3의 함수는 첫 번째 인수를 평가해 결과가 참이면 두 번째 인수를, 거짓이면 세 번째 인수를 평가합니다. 반복 구조도 가능하며, 함수가 인수 중 하나를 여러 번 평가할 수 있습니다. 다만 평가 시간이 과도해지지 않게 반복 횟수와 중첩 수준을 제한해야 합니다. 재귀 공식 허용 연구도 일부 있으나 성공은 제한적이었습니다.

GP 시스템 결과는 LISP형 프로그램이지만, GP 시스템 자체가 LISP로 구현될 필요는 없습니다. 많은 시스템이 C나 C++로 구현됩니다. 프로그램 트리의 선형화된 표현을 사용하면 동적 메모리 오버헤드와 비용이 큰 가비지 컬렉션을 피할 수 있습니다. 피트니스 함수의 효율성은 각 세대마다 수많은 호출이 발생하므로 병목이 되기 쉬워 특별한 주의가 필요합니다. 구현 기법을 다룬 훌륭한 논문은 Advances in Genetic Programming에 실려 있습니다(아래 추천 도서 참조).

신경망 등 다른 머신러닝 패러다임과 마찬가지로, 훈련 데이터(GP 테스트 케이스)에 과적합(overfitting)될 가능성이 있습니다. 과적합은 해법이 데이터를 효과적으로 '암기'하여 정교한 룩업 테이블 이상의 역할을 못 할 때 발생합니다. 이를 완화하는 간단한 방법은 파시모니 요소(parsimony factor)를 사용하는 것입니다. 파시모니 요소는 일반적으로 프로그램 트리 노드 수에 곱해지는 작은 비율로, 그 결과가 피트니스 함수에 반영됩니다. 더 작고 범용적인 해법에 보상하는 개념입니다. 또한 적절한 실험 설계 기법을 사용하는 것이 좋습니다. 예를 들어 예측 모델 개발 시 사용 가능한 데이터의 부분집합으로 피트니스 평가를 제한하면, 나머지 데이터로 결과 모델의 예측 성능을 측정할 수 있습니다.

진화 알고리즘과 마찬가지로 GP는 정확한 해법이나 허용 가능한 해법을 찾음을 보장하지 않습니다. 실행마다 결과가 크게 다를 수 있으며, 종종 조기에 국소 최적해로 조기 수렴합니다. 성능은 문제 복잡도, 함수와 터미널 선택으로 특징지어지는 표현, 피트니스 함수 속성에 크게 의존합니다.

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

유전 프로그래밍은 다음과 같은 분야의 문제에 성공적으로 적용되었습니다.

• 회로 설계
• 조합 최적화
• 제어 시스템
• 곡선 피팅/회귀 분석
• 데이터 압축
• 경제 예측/금융 모델링
• 게임 전략 습득
• 수열 귀납
• 신경망 설계
• 패턴 인식 및 분류
• 난수 생성
• 로봇 내비게이션
• 심볼릭 적분 및 미분
• 3차원 설계

유전 프로그래밍의 미래 방향

문제 복잡도에 따라 여러 번 GP 실행이 필요할 수 있으며, 아예 해법을 못 찾을 수도 있습니다. 이상적으로는 문제 복잡도가 증가해도 GP가 '확장(scale up)'되길 바랍니다. 이를 달성할 좋은 방법을 찾는 것은 활발한 연구 영역입니다. 기존 프로그래밍에서 서브루틴을 통해 고수준 표현을 구축하듯, GP에서도 비슷한 접근이 가능합니다. Genetic Programming II에서 Koza는 재사용 가능한 서브루틴을 발견하는 방법과 계층적 모듈러 프로그램이 더 복잡한 문제를 해결할 수 있음을 뒷받침하는 결과를 제시합니다.

GP는 유전 알고리즘의 자기 조직화 특성과 S-표현의 표현력 및 일반성을 결합합니다. 이 접근의 우아함은 문제 명세를 도메인 특화 피트니스 함수와 적절한 함수 및 터미널 세트 제공으로 단순화합니다. 다양한 문제에 적용 가능하며, GP는 연구의 비옥한 토대로 계속 남을 것입니다.

아직 초기 단계지만, 향후 돌파구는 프로그램을 스스로 작성하는 시스템이라는 성배에 한 걸음 더 다가가게 할 것입니다.

추천 도서

• 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.