로봇 게이트 생성 기법을 4족 보행 -> 휴머노이드로 이전하면서, 해공간의 특성 분석이 필요해서 몇가지 샘플트리에 대해 적합도 공간 변화가 어떤지 체크해본 그래프이다. 4족 보행 로봇의 경우 네 발로 지탱하는 특성 때문에, 안정성에 대한 지표가 크게 변하지 않지만, 휴머노이드는 넘어짐이라는 특성이 발생하기 때문에 아주 작은 변화에도 결과에 매우 큰 영향을 주는 현상이 나타날 수 있다고 생각했고, 그것을 증명하기 위한 그래프 자료이다.
아래와 같은 각각의 트리에서 ERC 값, 즉 실수값을 P1, P2, ... ,P8 의 변수로 표현하여, 각각 0.001 씩 증가시키면서 해공간의 변화를 나타낸 것이다. x 축은 0.001씩 몇번이나 증가 시켰는지를 의미하며, y 축은 적합도값을 의미한다.
적합도 함수는 거리를 기반으로 한 형태이며, fitness = 0.8 * 전진거리 - 0.2 * 좌,우 틀어짐 으로 사용한다. 또한, 넘어지거나 유도한 방향으로 움직이지 않을 경우, 적합도를 0 으로 할당한다.
결과를 보면 실수값의 아주 미묘한 변화에도 해 특성이 매우 심하게 변동됨을 확인할 수 있다.
그러나 P5 변수 후반부를 보면, 크게 변동하지 않는 후반부(71~이후)가 발생하는데, 이는 조금은 의외의 결과이다. P4, P5, P6 모두 초기값이 양수이며, 동일한 형태로 증가하고, 최종적으로 증가된 결과가 시뮬레이터에 정밀하게 반영되기 어려울 수 있는데, P4, P6 는 중간에 적합도값이 음수값으로 크게 가라앉는 형태를 확인할 수 있다. 그러나 P5 에서는 71~이후 의 결과가 계속적으로 동일한 결과가 나타났으며, 생각과는 다른 해공간 특성을 가지는 것을 확인할 수 있다.
결론적으로 저러한 예외가 발생함에도 불구하고, 아주 미묘한 실수값에 의해 매우 큰 변동 수치의 적합도를 갖는다는 사실에는 변함이 없다. 즉, GP 자체의 구조적 튜닝도 매우 중요하지만, 이러한 문제의 경우 파라미터 수치의 중요성도 매우 높다는 사실을 확인할 수 있다.
병렬처리 시스템은 최근에 가장 주목 받고 있는 컴퓨팅 성능 향상 기술 중에 하나입니다. 물론 과거에도 병렬처리 시스템이 주목 받아 왔지만, 그 당시에는 CPU 의 업그레이드 만으로도 50%, 100% 이상의 성능향상을 이룰 수 있었기에 지금보다는 적은 관심을 보였었습니다. 그러나 현재의 CPU 가 가진 한계에 거의 다다름에 따라, 성능 개선의 기법으로 병렬처리 기법들이 주목을 받고 있습니다. 즉, 하드웨어적 한계를 소프트웨어 적인 기법으로서 넘어서려고 한다고 표현할 수 있겠습니다.
이 병럴처리 시스템은 크게 내부, 외부의 두 가지 요소로서 존재한다고 볼 수 있겠습니다. 내부 요소로서는 CPU 의 멀티 코어화, GPU 의 발전 등을 들 수 있겠고, 외부적으로는 대규모 네트워크로 구성된 컴퓨팅 환경을 제공하는 것이 되겠습니다. 대표적으로는 근래에 각광을 받고 있는 클라우드 컴퓨팅이 있겠습니다.
진화연산은 기존의 알고리즘 들에 비해 엄청난 반복작업이 필요하며, 거대한 리소스를 갖출수록 더 좋은 효과를 가질 수 있는 특징이 있습니다. 이 거대한 리소스에 대한 것은 반박의 여지가 충분히 존재하며, 각 문제에 따른 특화된 알고리즘의 적용으로 이를 개선할 수 있습니다만, 그렇다고 해도 아주 오랜시간에 걸쳐 반복작업이 이루어져야 그에 따른 최적값을 기대해 볼 수 있다는 것은 부정할 수 없는 사실입니다.
2. 진화 연산에 적용된 병렬처리기법
2.1 다수의 CPU 사용
초창기 유전프로그래밍(이하 GP)의 창시자라고 언급되는 John. R. Koza 의 경우에는 천 대의 컴퓨터를 하나의 클러스터로 활용해 GP를 수행하였으며, 이를 통해 과거에 발표되었던 특허들을 그대로 GP의 결과물로서 만들어내는 결과를 보여주었습니다.[1] (첫 페이지의 팔짱을 끼고 있는 그의 모습 뒤로 펼쳐진 것들이 수많은 컴퓨터의 클러스터입니다.)
그러나 일반적인 연구자들이 이러한 리소스를 활용할만한 능력을 갖추기는 어려웠기 때문에 사실상 대규모 클러스터링을 활용한 연구는 Koza 의 이후로 거의 나타나지 않고 있었습니다. 소수의 연구자들에 의해 소규모의 분산 처리 시스템[2]이나 여러 개의 CPU 를 사용한 연구[3]는 이루어지고 있었습니다. ([3] 논문은 가상의 병렬 처리 머신을 통해 데이터를 주고받는 것에 대한 논문입니다만, 저 논문의 결과물로서 lil-gp 의 병렬화된 형태를 언급하는 데 이것은 다중의 CPU 를 사용하는 병렬 처리 기법이 사용되어 있습니다.)
2.2 GPU
시간이 흐른 뒤, nVidia 에서 GPU 가 나오게 되었습니다. 이것은 벡터 연산에 특화되어 있고, CPU 에 비해 압도적인 처리성능을 보여주기에 수 많은 알고리즘이 이를 해당 알고리즘에 적용시키기 시작하였습니다. 물론 진화연산에서도 절대 예외일 수는 없었습니다.
대표적인 논문으로 몇가지를 언급하자면, 우선은 진화 연산을 타겟으로 삼은 것은 아니지만, GPGPU(General-Purpose computation on Graphics Processing Units) 의 개념을 활용해 알고리즘에 적용하는 것이 좋겠다고 제안한 논문이 있습니다. [4] 그리고 실제 GPU 를 사용해서 GP를 수행하고, 이에대한 성능 비교를 수행한 논문이 발표되게 되었습니다. [5,6,7]
일반적으로 생각하기에 GPU 를 통해 병렬적으로 개체의 해석을 수행하게 되면 CPU 만을 사용하는 현 GP 에 비해서 엄청난 속도 향상을 기대 하지만, 실제로는 모든 문제에 대해서 그렇지는 않았다는 내용이 [6] 논문에서 나타나고 있습니다. 그러나 위의 논문에서 사용된 컴퓨터의 사양은 T2400 (1.83 Ghz), 1.5GB ram, GeForce 7300 GO with 512 RAM 으로서, 노트북 컴퓨터라고 보시면 됩니다. 즉, 일반적으로 사용하는 GPU 에 비해서는 그다지 좋은 성능을 보여주는 것은 아니었던 것입니다.
그리고 [7] 논문에서는 GPU 에 최적화된 GP 연산 기법을 소개하고, SIMD 처리 형태에 알맞은 데이터 처리 방식을 사용하여 더 좋은 효율을 보여준다는 것을 나타내고 있습니다. 또한, 이 논문에서 더 주목해 볼 수 있는 것은 Geforce 8800 GTX 라는 고사양의 GPU를 사용했다는 것과 이를 통해 CPU 의 오버헤드가 0.1%에 근접한다는 내용, 그리고 기존에 해결하는데 매우 오랜 시간이 걸렸던 거대한 형태의 Regression 문제를 해결했다는 것에 있습니다. 1024 x 1024 x 1000 의 크기의 문제를 200번 수행하는데 6시간 46분 17초가 걸렸다는 건, 기존에 우리가 처리할 엄두도 못 내던 거대한 크기의 문제들을 GPU 를 사용하여 처리한다면 더 큰 효율과 빠른 결과를 얻을 수 있다는 것을 의미합니다.
[8] 논문에 이르러서는 Xbox360 이라는 이 종의 하드웨어를 통해 GP를 수행하게 됩니다. 컴퓨터의 GPU 를 통한 결과와 Xbox 360 의 GPU 를 통한 결과를 서로 비교하는 내용이 있는데, 특이할 만한 점은 C# 과 XNA Framework 를 통해 구현된 동일한 프로그램(GP)을 Xbox360 과 PC 에서 변환 없이 수행할 수 있었다는 것, 그리고 결국 성능은 PC 가 더 좋았다는 것이 되겠습니다.
2.3 기타 웹이나 네트워크 기반의 진화연산 기법
이렇듯 GPU 의 등장과 함께 진화 알고리즘은 매우 빠른 병렬처리 알고리즘을 통한 복잡한 문제의 해결, 그리고 GPU 에 걸맞는 형태의 알고리즘의 변화 등이 이루어져 왔습니다. 그러나 사실 GPU 를 통한 GP 의 발전은 아직은 한계가 있습니다. 가장 큰 한계점이라면 단순 Regression 문제나 디지털 논리회로를 벗어나는 문제에 대해서는 아직 그 위에서 해석할 방법이 없다는 것 입니다. 즉, 단순한 문제지만 거대한 데이터 셋을 갖는 문제에 대해서는 그 효율을 극대화 하여 이용할 수 있지만, 복잡한 시뮬레이션의 경우에는 아직 GPU 에서 그것을 수행하기에는 많은 무리가 따르게 됩니다.
GPU 의 진화 연산보다는 살짝 앞선 시기에 웹을 통한 진화 연산의 수행기법들에 대한 연구가 이루어 졌습니다. [9] 논문의 경우에는 웹을 통해 사람이 어떠한 평가를 내리고, 이를 서버에서 모아서 진화연산을 수행하는 형태에 대한 연구기법에 대해 논하고 있습니다. 이는 기계로 평가를 내리기 어려운 적합도 함수, 즉 좋은 음악이나 색의 조합 등 인간의 주관이 개입되어야 하는 문제에 대해서도 진화연산의 수행이 가능하다는 것을 보여준 사례가 되겠습니다.
2007년에 발표된 [10] 논문의 경우에는 XML 과 Ajax 를 통해 웹브라우저로 데이터를 서로 주고받고, 적합도 함수를 평가하며 해결하는 시스템을 구축하였습니다. 이 논문에서 아쉬운 점은 비교할만한 대상이 없었기 때문에, 해당 기법이 기존의 기법에 비해 어느 정도 효율성을 갖는지가 나타나지 않았고, 매우 빠른 연산을 보여주었다는 시간만을 언급하고 있다는 것이었습니다.
그리고 ECJ Framework[11] 에서는 TCP/IP 상의 Asynchronous Island Model 을 지원함에 따라 기존의 진화 연산 문제를 대규모 네트워크를 통한 처리 형태를 쉽게 사용해 볼 수 있습니다. 이미 모든 구현이 이루어져 있기 때문에 약간의 파라미터 수정만 거치면 바로 네트워크를 통한 진화연산 기법의 연구가 가능하다는 장점이 있습니다. 관심 있으신 분은 한번쯤 해보시면 좋을 것 같습니다.
3. 정리
이보다도 이른 시기에 네트워크를 통한 데이터 교환을 통해 진화 연산의 병렬화의 효율에 대해 논하는 것들이 많이 있었지만, 사실상 GPU 와 같이 핵심 테마로서 자리를 잡을 만큼의 파급력을 갖출 수 없었습니다. 이는 어쩌면 진화 연산 자체를 병렬처리로 수행한다는 것은 하나의 연구테마로 갖추기가 어려운 것이었을 수도 있고, 기존의 방법들에 비해 획기적인 성능을 보여주는 사례가 없었기 때문일 수도 있습니다. 혹은 고도의 시뮬레이터를 통한 시뮬레이션을 필요로 하는 그런 문제가 정의되지 않았기 때문일 수도 있습니다.
진화연산에서는 알고리즘 자체가 적은 수행 횟수를 통해 더 개선된 성능을 보여주는 것은 여전히 중요한 테마입니다. 단위 시간에 대해 더 효율적인 공간의 탐색을 할 수 있다면, 성능 개선을 위한 가장 훌륭한 접근이 될 수 있겠습니다. 거기에 같은 단위 시간에 대해 두 배 아니 열 배 이상의 수행이 가능하다면 더 좋은 성능을 보여주기 위한 가장 좋은 해결책이 아닐까 생각이 듭니다. 물론 이렇게 말하게 되면, 병렬처리 자체는 기존의 알고리즘의 개선을 위한 접근 방법들에 비해서는 중요도가 떨어져 보이는 것이 사실입니다. 그러나 이전에는 접근해 볼 수 없었던 100만개~1억개 이상의 개체의 진화나 이로 인해 나타나는 현상들은 기존의 알고리즘으로 접근하는 방식들과는 다를 것이라 생각되기 때문에, 진화 연산 자체의 병렬처리 시스템은 기존의 방식들과는 별도로 매우 중요한 테마가 되지 않을까 생각합니다.
[2] F. S. Chong and W. B. Langdon. Java based distributed genetic programming on the internet. In W. Banzhaf, et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, page 1229, Orlando, Florida, USA, 13-17 July 1999. Morgan Kaufmann. ISBN 1-55860-611-4.
[3] F. Fernandez, J. M. Sanchez, M. Tomassini, and J. A. Gomez. A parallel genetic programming tool based on PVM. In J. Dongarra, et al., editors, Recent Advances in Parallel Virtual Machine and Message Passing Interface, Proceedings of the 6th European PVM/MPI Users' Group Meeting, volume 1697 of Lecture Notes in Computer Science, pages 241-248, Barcelona, Spain, September 1999. Springer-Verlag.
[4] J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26(1):80-113, March 2007.
[5] D. M. Chitty. A data parallel approach to genetic programming using programmable graphics hardware. In D. Thierens, et al., editors, GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 2, pages 1566-1573, London, 7-11 July 2007. ACM Press.
[6] S. Harding and W. Banzhaf. Fast genetic programming on GPUs. In M. Ebner, et al., editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 90-101, Valencia, Spain, 11 - 13 April 2007. Springer.
[7] W. B. Langdon and W. Banzhaf. A SIMD interpreter for genetic programming on GPU graphics cards. In EuroGP, LNCS, Naples, 26-28 March 2008. Springer.
[8] G. Wilson, W. Banzhaf, Linear Genetic Programming GPGPU on Microsoft’s Xbox 360, in Proceedings of 2008 IEEE World Congress on Computational Intelligence, Hong Kong, 2008.
[9] W. B. Langdon. Pfeiffer - A distributed open-ended evolutionary system. In B. Edmonds, et al., editors, AISB'05: Proceedings of the Joint Symposium on Socially Inspired Computing (METAS 2005), pages 7-13, University of Hertfordshire, Hatfield, UK, 12-15 April 2005a.
[10] J. Klein and L. Spector. Unwitting distributed genetic programming via asynchronous javascript and XML. In D. Thierens, et al., editors, GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 2, pages 1628-1635, London, 7-11 July 2007.
J. R. Koza 의 94년에 발간된 Genetic Programming II 에 보면 나오는 용어입니다. 말 그대로 풀이하면 자동적으로 정의된 함수들 쯤 될꺼 같습니다. 그 책의 내용에 따르면 이 기법을 사용하게 되면 트리 안에서 어떤 강제적인 흐름을 가지는 구조물을 위치시키게 되고, 이 구조물은 트리 안에서 반복적으로 사용될 수 있게 된다고 하고 있습니다.
?
GP 는 터미널 노드와 함수 노드를 사용하여 일정한 흐름의 프로그램을 만들어내죠. 이 ADFs 라는 녀석은 그 일정한 흐름의 프로그램들의 한 부분을 ADFs 라는 하나의 구조물안에 가두어서 반복적으로 사용할 수 있는 효과를 가지게 됩니다. 한마디로 어떤 구조가 반복적으로 사용되어 해결하기 좋은 문제일 경우에는 이를 사용할 경우에 톡톡한 효과를 볼 수 있다는 뭐 그런 말입니다.
?
GP 를 처음 접할 때 ADFs 라는 용어를 듣고, 그 녀석을 접하는 순간, 어떤 문제든 다 갖다 붙이고 싶은 욕구가 마구마구 싹텄었던 기억이 나는군요. 근데 사실 이녀석은 생각보다 널리 쓰기가 어려운 녀석입니다. 특정 몇몇 문제가 아니라면, 사용하는 자체가 오히려 전체적인 구조를 변화하지 못하게 만드는 주요 요인중에 하나가 됩니다.
?
예를들면, 어떤 회귀문제(어떤 특정 주어진 몇개의 점을 모두 지나가는 함수를 만드는 그런종류의 문제들)에 ADFs 를 사용한다고 생각해 봅시다. 우리가 일반적으로 생각하는 수식들에서 특정 구조가 지속적으로 반복되는 수식이 과연 얼마나 있을까요? ADFs 는 이런 문제의 경우에는 해당 문제를 오히려 특정 구조가 반복되게 만들 수도 있기 때문에 가급적 피하는것이 좋을 수 있습니다.
?
그러나 회로를 설계하는 문제를 생각해보면 달라집니다. 만약에 어떤 회로에 특정 필터를 사용하는 부분이 반복적으로 나타나야 한다면? ADFs 가 이 필터의 구조를 가지고 있다면, 지속적으로 특정 필터를 사용하는 그런 효과를 낼 수 있겠지요? 하지만 역시 이것도 현실적으로 잘 생각해보시면, 사람이 ADFs 가 아닌 DFs 로 정의해 놓지 않는한 과연 이것을 필터로 인식하고 지속적으로 사용할 것인가는 쉽게 결론이 나오지 않는 문제가 됩니다. 그러나 엄청난 컴퓨팅파워를 갖추고 있다면, 말도 안되는 군집크기와 진화 세대의 반복을 통해 아마도 좋은 결과를 얻어낼 수도 있지 않을지 생각해봅니다.
?
또한, 네트워크의 다중입출력 관계에 대한 어떤 구조설계를 한다고 할 경우에도 ADFs 를 사용할 수 있습니다. 기본적으로 GP 는 하나의 출력을 가집니다. 루트노드가 곧 출력이 되는 것이지요. 그리고 노드에 대한 다중상속구조를 지원하지 않습니다. 이런 것을 토대로 볼 때, 이를 해결하는 가장 쉬운 방법은 다중의 트리를 사용하고 모든 트리들은 같은 ADFs 를 공유하는 것 입니다. 이렇게 하면 만약 루트 노드 바로 아래에 ADFs 가 위치한다면 서로 특정 같은 구조의 노드들을 가지게 되는 것이므로 다중상속구조를 살짝이나마 가질 수 있는 것이지요.
?
ADFs 라는 것은 이렇듯 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 같은 벤치마크 문제와 함께 제 블로그에서 공개할 예정입니다.
homologous.c
