Previous Contents/Genetic Programming

1. Genetic Programming 이란?

shhyun 2007. 5. 14. 23:15

 오늘은 간단하게 Genetic Programming(GP) 에 대해서 정리해볼까 합니다.

 GP 라는건 GA 에서 파생되었다고도 할 수 있는 또다른 Evolutionary Computation 의 한 종류 입니다.
 Genetic Algorithm 에서는 유전자 형태를 Binary 또는 Real Type 의 조합을 이용했습니다.
 하지만 Genetic Programming 에서는 유전자 형태를 Tree 구조를 이용합니다.

 그림으로 표현해보면 다음과 같습니다.

사용자 삽입 이미지사용자 삽입 이미지

그림1. GA 와 GP 의 표현의 차이점


 GA 와 GP 는 보시는 것과 같이 표현에 차이를 두고 있습니다. CX나 MUT 역시 존재하지만 표현상의 차이로 인해 조금 다른 방식으로 이루어 집니다. CX 방식의 차이에 대해서 그림으로 표현해보면 다음과 같습니다.

사용자 삽입 이미지사용자 삽입 이미지

그림2. GA 와 GP 의 CX 의 차이점


 GA 와 GP 는 위와같이 표현상의 차이로 인해, 서로 해결하기 좋은 분야도 틀리고, 구현하는 방식도 틀립니다. GP는 쉽게 접하기 어려운 이유가 바로 저 Tree 구조를 이용하기 때문인데, GP 에서 Tree 각각의 노드(Tree의 구성요소 하나하나를 노드라고 합니다.)가 함수 그 자체의 역할을 하기 때문에 구현상 매우 어려움이 따릅니다. 그리고 도식화 시키기도 힘들뿐더러 Tree 를 해석하기 위해서는 Lisp 언어와 같은 표현방식에 익숙해 져야 하는 어려움이 따릅니다.
 
 하지만 GP 는 Genetic Programming 이라는 말과 같이 프로그램이 프로그램을 파생시키고 만들어내는 방식이기때문에 어떤 구조를 최적화 시키는데에 적합합니다. GA 는 각각의 유전자가 수치정보를 가지고 있기때문에 수치최적화에 적합하지만, GP 는 각각의 유전자가 함수형태의 정보도 취할 수 있기때문에 구조최적화에 적합한 것입니다.

 GP로 해결되는 대표적인 예는 다음과 같습니다.
어떤 말도 안되는 형태의 그래프가 주어지고, 이 형태와 가장 유사한 구조를 가지는 함수를 찾아내는 것이지요. Symbolic Regression 이라고 불리는 이 문제는 GP로 해결되는 대표적인 예중에 하나입니다. 그리고 Ant Problem 이라고 하는 문제가 있는데, 개미가 주어진 먹이를 정해진 시간동안 가장 정확하게, 가장 많이 찾아내는 것이 문제인 목표입니다. 그리고 Multiplexer Problem 같은 논리회로의 구조를 찾아내는 문제나, Filter Problem 과 같이 전자회로에서 주어진 입력값과 출력값을 올바르게 표현할 수 있는 아날로그 회로를 찾아내는 문제에도 이용되었습니다.

 GP는 GA 에 비해서 다루기가 많이 힘듭니다. 우선, 기본적으로 프로그래밍에 매우 능숙해야 그 구조나 형태를 파악할 수 있고, GA 나 ES 와 같이 오래된 역사를 갖고 있는 것도 아니기 때문에 GP에 대한 서적도 매우 적은 편입니다. 그래서 GP 에 대한 자료를 한번 이것저것 모아보려고 합니다. GA 와 마찬가지로 제 공부도 하면서 이제까지 아는 것도 정리하는 겸 하나씩 글을 써볼까 합니다.

 P.S. GA 를 0.001 버전을 완성하기는 했습니다만, SGA에 비해서 큰 차이를 보이지 못하기에 아직 웹상에 공개하기는 조금 그렇네요 ^^ HFC 알고리즘에 대한 구현을 마치게 되면 Rosenbrock 이나 Griewangk 같은 벤치마크 문제와 함께 제 블로그에서 공개할 예정입니다.