로봇 게이트 생성 기법을 4족 보행 -> 휴머노이드로 이전하면서, 해공간의 특성 분석이 필요해서 몇가지 샘플트리에 대해 적합도 공간 변화가 어떤지 체크해본 그래프이다. 4족 보행 로봇의 경우 네 발로 지탱하는 특성 때문에, 안정성에 대한 지표가 크게 변하지 않지만, 휴머노이드는 넘어짐이라는 특성이 발생하기 때문에 아주 작은 변화에도 결과에 매우 큰 영향을 주는 현상이 나타날 수 있다고 생각했고, 그것을 증명하기 위한 그래프 자료이다.

아래와 같은 각각의 트리에서 ERC 값, 즉 실수값을 P1, P2, ... ,P8 의 변수로 표현하여, 각각 0.001 씩 증가시키면서 해공간의 변화를 나타낸 것이다. x 축은 0.001씩 몇번이나 증가 시켰는지를 의미하며, y 축은 적합도값을 의미한다.

HP:
 (/ (/ X -1.23399)
    (- X -0.34431))
KP:
 (/ (+ (sin 0.41949)
       (* -0.09291 X))
    (/ (cos 0.20874)
       (sin 0.41949)))
AP:
 (- -0.44653 -0.39964)

적합도 함수는 거리를 기반으로 한 형태이며, fitness = 0.8 * 전진거리 - 0.2 * 좌,우 틀어짐 으로 사용한다. 또한, 넘어지거나 유도한 방향으로 움직이지 않을 경우, 적합도를 0 으로 할당한다.


결과를 보면 실수값의 아주 미묘한 변화에도 해 특성이 매우 심하게 변동됨을 확인할 수 있다.
그러나 P5 변수 후반부를 보면, 크게 변동하지 않는 후반부(71~이후)가 발생하는데, 이는 조금은 의외의 결과이다. P4, P5, P6 모두 초기값이 양수이며, 동일한 형태로 증가하고, 최종적으로 증가된 결과가 시뮬레이터에 정밀하게 반영되기 어려울 수 있는데, P4, P6 는 중간에 적합도값이 음수값으로 크게 가라앉는 형태를 확인할 수 있다. 그러나 P5 에서는 71~이후 의 결과가 계속적으로 동일한 결과가 나타났으며, 생각과는 다른 해공간 특성을 가지는 것을 확인할 수 있다.

결론적으로 저러한 예외가 발생함에도 불구하고, 아주 미묘한 실수값에 의해 매우 큰 변동 수치의 적합도를 갖는다는 사실에는 변함이 없다. 즉, GP 자체의 구조적 튜닝도 매우 중요하지만, 이러한 문제의 경우 파라미터 수치의 중요성도 매우 높다는 사실을 확인할 수 있다.
Posted by SHHyun

GP 의 해가 가지는 특성을 파악하기 위해 실험을 통해 대규모의 데이터를 수집하였다고 가정하자. 그리고 대부분의 해에서 나타나는 어떠한 특성이 발견 되었다면, 과연 여기서 대부분의 해는 반드시 그 어떤 특성을 갖게 되는 것일까?

GA, GP 의 조기수렴이 해의 다양성에 악영향을 끼치고, 좋은 결과로 수렴하는 것을 방해한다고 했을 때, 조기수렴을 막으면 반드시 해가 다양성을 폭넓게 가지면서, 좋은 결과로 수렴할 것인가?

어떠한 명제를 가정했을 때, 그 역이 반드시 참일것이라는 보장 같은 것은 없다. 결국 우리가 일반적으로 데이터를 수집하여 하는 일은 대부분이 그러한 특성을 보인다는 것에서 끝나는 것인데, 이것의 역을 증명해낼 좋은 방법은 없을것인가?

몇년째 계속 고민해보지만, GA, GP 쪽에서는 이를 어떤 수로 증명할 것인지 딱히 머리속에 떠오르는 것이 없다. 실험을 통해 명제 자체가 참임을 증명해낼 수는 있지만, 그 명제를 토대로 알고리즘을 구성하고 타당성을 갖기 위해서는 반드시 그 명제의 역이 참임을 증명해야 하는데 아직까지는 부족한게 많은지 딱히 좋은 방법이 떠오르지 않는다.

하지만 이 부분이 해결되지 않는 한, 결국 어떠한 알고리즘을 만든다 하더라도 이것이 타당성을 갖기는 어려울 것이 분명하기 때문에 앞으로도 계속 고민할 것 같다. 뭔가 좋은 방법은 없는 것일까?

Posted by SHHyun
1. 개요

병렬처리 시스템은 최근에 가장 주목 받고 있는 컴퓨팅 성능 향상 기술 중에 하나입니다. 물론 과거에도 병렬처리 시스템이 주목 받아 왔지만, 그 당시에는 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억개 이상의 개체의 진화나 이로 인해 나타나는 현상들은 기존의 알고리즘으로 접근하는 방식들과는 다를 것이라 생각되기 때문에, 진화 연산 자체의 병렬처리 시스템은 기존의 방식들과는 별도로 매우 중요한 테마가 되지 않을까 생각합니다.


4. 참고문헌

[1] John. R. Koza – http://www.genetic-programming.com/johnkoza.html

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

[11] ECJ - http://cs.gmu.edu/~eclab/projects/ecj/

Posted by SHHyun

Homologous CX 연산자는 기본적으로 동일 구조를 가진 서브트리들 간의 교환만 허용하는 연산자 입니다. 즉, 위의 그림에 Tree1 과 Tree 2 에서, 1-1, 2-2, 3-3, 6-4, 7-7 간의 교환만을 허용한다는 이야기 입니다.

이 연산자의 출발점은 생물체의 교배에 있어서 동일 형질의 유전자 만을 교환한다는 것으로 기억하고 있습니다. 예로서 팔의 유전자와 다리의 유전자를 교환해서는 이상형질이 나타날 수 있다는 것을 들 수 있겠습니다.

실제로 몇가지 테스트 문제에 대해 실험해 보면 매우 빠른 속도로 연산이 이루어지고, 코드의 증가 또한 기본 연산자에 비해서 매우 적게 증가하는 것을 확인할 수 있었습니다.

본 소스코드에 어떤 오류가 있을지는 모르겠습니다만, 혹시 참고하실 분은 첨부된 소스를 받으셔서 돌려보시면 되겠습니다.


homologous.c





Posted by SHHyun
유사 - [명사]{주로 일부 명사 앞에 쓰여} 서로 비슷함.

그렇습니다. 유사하다는 말을 서로 비슷하다는 말입니다.
비슷하다? 그럼 비슷하다는 말은?

비슷하다
[형용사]
『(…과)』 {‘…과’가 나타나지 않을 때는 여럿임을 뜻하는 말이 주어로 온다} 두 개의 대상이 크기, 모양, 상태, 성질 따위가 똑같지는 아니하지만 전체적 또는 부분적으로 일치하는 점이 많은 상태에 있다. {명사의 단독형 뒤에 쓰여}
1 정체가 확인되지 아니한 어떤 대상에 대하여 누구 또는 무엇이라고 짐작되는 상태에 있다.
2 비교가 되는 대상과 어느 정도 일치되지만 다소 미흡한 면이 있다.

네 그렇습니다. 크기, 모양, 상태, 성질 따위가 똑같지는 않지만, 전체적 또는 부분 적으로 일치하는 점이 많은 상태에 있다 라고 하고 있습니다.

일반적으로 진화 연산에서 각 개체군의 유사함을 평가하는데에 이용되는 방식은 크게 두가지 방식이라고 할 수 있겠습니다.

그것은 Genotype 과 Phenotype 의 형태에서 유사함을 평가하는 것 입니다.

여기서 Genotype 은 순수한 그 개체 자신을 나타내는 것이고,
Phenotype 은 개체가 어떤 적합도 함수를 거쳐서 결과물로서 나타나는 것을 말합니다.

Phenotype 을 통한 개체의 유사성 분류는 크게 문제될 것이 없습니다. 일반적인 적합도 함수를 이용한다면, 두개 이상의 값이 나타나지 않습니다. (물론 동시진화기법 (Co-evolution) 을 이용할 경우에는 달라질 수 있습니다만, 이것은 특이한 경우로 분류하겠습니다.) 그러므로, 적합도의 값의 차이, 즉, 유클리디안 거리를 통한 유사도 분류가 가능합니다.

Phenotype 을 통한 유사성 분류방식은 초기 진화연산 기법에서 많이 이용된 방식 이었습니다. 하지만 금방 단점이 나타나게 되었죠.

가장큰 단점은 아마도 이것이겠지요.

" 완전 다른 개체일 경우에도 비슷한 개체로 분류될 수 있다. "

그렇습니다. 여러분 께서 만약에 GA의 대표적 벤치마크 문제인 f3deceptive 문제를 접해 보셨다면, 무슨 의미인지 확실하게 이해하실 수 있을 것입니다.
000011000 는 1.8 의 적합도를 가집니다.
111000001 또한 1.8 의 적합도를 가집니다.

과연 위의 두 개체를 비슷한 개체라고 부를 수 있을까요?

이렇듯, 개체의 특성 자체가 반영되지 않은 상태에서 단지 적합도 만을 가지고 유사성을 논하는 것은 매우 큰 오류를 범하는 것을 확인할 수 있습니다.

그래서 많은 학자들이 Genotype 상태에서의 유사성 분류에 대한 기준을 마련하기 시작했습니다.

수많은 유전연산 기법들은 그들만의 표현양식(Representation)에 따라 그 유사성 분류 방식이 다를 수 밖에 없습니다. Bit String 표현 기법을 갖는 GA 의 경우에는 해밍거리 를 통한 측정방식이 있습니다. 각각의 위치한 비트를 비교하여 몇개의 비트가 서로 다른 비트 값을 갖는지를 이용하여 측정하는 방식입니다. Real Number 로 표현되는 GA 나 ES 의 경우에는 각각의 개체에 대해 유클리디언 거리측정을 통하면 그 차이를 측정할 수 있죠.

하지만 GP 의 트리는 아직까지도 확실한 유사성 분류 기준이 없습니다. 트리구조의 유사성을 분류하는 수학적인 기준도 아직까지 없는 것으로 알고 있습니다.

여기서 짚고 넘어가야 할 게 있는데, 왜 유사성을 분류하는 것이 중요한지에 대한 것입니다. 예전에 GA 나 GP 등의 진화연산에서 중요하게 생각하는 문제중의 하나가 조기수렴 문제라고 언급한 적이 있었습니다. 이는 거의 모든 개체가 한 점으로 수렴해 나가는 현상을 말한다고 말씀 드린 적이 있습니다. 이것은 일반적으로 Phenotype 의 관점에서 봤을 때, 한 점으로 수렴하는 현상을 말 합니다. 하지만, Phenotype 의 관점에서는 한점에 수렴 했다 하더라도, Genotype 의 관점에서는 수 많은 곳으로 분포해 있을 수 있는 것입니다. 이 가능성은 개체들을 여러곳으로 분산시킬 수 있는 다른 효과를 기대해 볼 수 있습니다.

즉, 유사성 분류기준, 혹은 유사성 측정에 대한 것은 조기수렴을 현상을 돌파할 수 있는 또다른 가능성을 제시해 줄 수 있다고 생각합니다.

다시 본론으로 돌아가서 트리구조의 유사성 측정에 대해 생각해 보도록 하겠습니다.

과연 우리가 어떨 때 이 트리가 유사하다고 생각할 수 있을까요?

제 생각은 이렇습니다.

1. 트리의 깊이가 비슷하다.
2. 트리의 퍼진 형태가 비슷하다.
3. 트리에 분포되어 있는 함수의 형태가 비슷하다.
4. 마지막으로 트리가 가진 적합도도 비슷하다.

한마디로 이렇습니다. 우리가 트리가 유사하다라고 하는 것은 트리의 겉 모양을 보고 "아 이것은 생긴게 비슷하다." 라고 할 수 있고, "트리를 거쳐 처리된 결과물이 비슷하다" 라고도 할 수 있습니다.

하지만, 이것에는 어느정도 괴리가 있습니다.
저 말들 중에 비슷하다 라는 것을 어떻게 표현할 것인가?

그래서 이런 방식을 제안해 보고자 합니다.
트리의 깊이, 터미널 노드의 개수(트리의 퍼진정도), 트리에 분포되어 있는 함수들
이 세가지 기준에 트리가 가진 적합도까지 추가하여

퍼지를 통한 분류 기법을 이용해보고자 합니다.
아직은 추상적이기 때문에, 조금 더 많이 구체화 시켜야 합니다만,
인간의 주관으로서 비슷하다라고 느끼는 것을 표현할 수 있다면,
그것을 통한 조기 수렴의 극복 및 새로운 연산기법의 적용이 가능 할 것 같습니다.
Posted by SHHyun

본 글은 어떤 일반론적인 생각도 아니고 어디까지나 제 자신의 개인적인 생각들 임을 사전에 밝히도록 하겠습니다. 짧은 지식을 통해 나오는 생각들이기에 편협할 수도 있고, 좁은 식견이 확 보일수도 있고 정리가 안된 그냥 머리속 튀어나오는 대로 쓰는거지만... 그냥 한번 써보렵니다. 사족이므로 반말나갑니다.

- 다른 녀석들을 봤을 때 유전프로그래밍이라는 것의 가능성... -

우선 신경회로망 이라는 녀석. 많이 알고 있는 녀석은 아니지만 태어난지 매우 오래되었음에도 불구하고, 과거의 알고리즘에 비해 심대한 변화는 없는 녀석이다. 다층 퍼셉트론 이후에 오류역전파 알고리즘, 그것들을 제외하고는 어째 크게 발전은 없는 모양이다. 사실 내가 크게 관심이 없어서 그럴수도 있지만, 여러 논문을 검색해 보았을때 다 고만고만 하다. 신경회로망을 어디에다가 적용시켰느냐가 초점이 되는 것이지, 신경 회로망 자체를 어떻게 바꾸었느냐는 그다지 관심들이 없는 모양이다. 더이상 바꿀게 없는건지, 저것 자체로도 충분한건지... 많이 발전되었다고 보인다 해도 사실 다층 퍼셉트론의 컨셉에 오류역전파 알고리즘의 약간 변형된 형태를 크게 벗어나지는 않는것 같다. ( 어디까지나 내가 잘 몰라서 그런걸수도... )

그리고 유전 알고리즘... 요샌 ES 나 DE 이런 애들한테 입지를 참 많이 뺏기는 느낌? 아니 그것보다도 더이상 전통적 유전알고리즘 이라고 불리는 녀석을 많이 쓰지 않는듯 싶다. 오히려 각각의 알고리즘들의 장점들만 빼와서 조합한 새로운 형태의 알고리즘이 많이 쓰이는거 같고, SGA 자체가 처음 등장때보다도 획기적 성능향상에 기여하고 있는 것 같지도 않다. 개발개발개발 또 개발 되어온 녀석이고, 여러가지 연산자, 표현방식, 알고리즘의 흐름 등등이 새롭게 바뀌었지만... 이젠슬슬 더 바꿀게 없을듯한 그런 한계에 도달 하는 거 같기도 하고, 이녀석은 탄생하고 그것이 전성기를 맞이한 후에 쇠퇴해가는 알고리즘의 한 형태가 아닐까...

이제 내가 언급하고 싶은 유전 프로그래밍... 이건 한마디로 말해서 너무 어렵다. 다른 ES, EA, GA, PSO, DE,뭐 기타등등 수많은 진화연산 알고리즘 중에서 가장 어렵다고 단언할 수 있다. 여기서 어렵다는 말의 의미는 일단 접근 자체도 너무 힘들고, 한글로 된 GP관련 자료를 찾는건 더 머리아프고, 프로그래밍을 해야하는데 이게 완전 사람 잡는다. 특히 C 언어로 GP를 짜겠다고 덤벼드는 자들... 100에 99는 자빠져서 쓰러질꺼라고 생각한다. 100에 90도 아니다. 99다 99. 자료구조의 기본지식에 응용까지 확실하지 못한자가 여기에 달라든다는건 애초에 자살행위. 위의 녀석들과 비교했을때 난이도가 가장 높다고 생각한다. 문제는 그거다. 이녀석은 정말 난이도가 높다. 하지만 적용시키는 것 자체로 확실한 성능을 보장할 수 있느냐?... 이게 좀 불확실하기에 많은 학자들이 섣불리 뛰어들지는 않는것 같다. 이녀석의 가능성... 글쎄... 어지간한 능력으로 건드릴수 없기에 확실히 대단한 녀석이지만 현재로서는 거의 불확실한 미래에 대한 도전 정도가 되는것 같다.

- 유전프로그래밍이 대체 뭐가 어떻다고... -

혹시라도 국내에서 유전프로그래밍 관련 책을 본 사람이 있는지.... 없다. 한마디로 없다. 딱잘라말해 없다. 2007년 11월 11일 현재 책에 섞여있는 몇장에 걸친 언급 외에... 있는걸 본 사람이 있는가? 없다. 없어. 어딜 뒤져도 안나온다. 즉, 이녀석에 대해 알고싶다면 일단 머리아픈 영어에 익숙해야 한다는거... 아니 익숙하지 않아도 좋다. 어쨌든 외국 논문, 외국 서적, 외국 자료들을 봐야 한다. 그 뜻과 의미도 모호한 부분에 대해 정확히 이해할 수 없는 외국인들의 자료들...

국내에서는 접근 자체도 폐쇄적인데다가 대학원 아니고서는 유전 프로그래밍에 대해 접근하는건 정말 힘들다. 접근성이 너무 나쁘다. 누가 만약에 지나가다 날 붙잡고 유전프로그래밍에 대해 설명좀 해주세요라고 묻는다면... 이론을 요래요래 요런거예요. 그럼 실제 예를 한번 보여 주시겠어요? 가장 깔끔한편인 lil-gp 를 예로 보여주면, 소스에 대해서 좀 언급을 해주시면... 멍... 멍... 왈왈 -_-... 내가 언급을 해줘도 상대가 이해할 수 있을 까도 궁금하지만, 사실 소스를 열었을 때 상대가 과연 저 소스를 이해하고 싶을까... 이게 더 궁금하다. 그정도다 한마디로... 다른것도 그다지 다르지 않다. 내가 그래도 이제까지 봐온 GP 소스 중에서는 lil-gp 가 가장 깔끔한 편에 속한다.

그래 이렇게 어렵다. 하지만 더 문제는 국내에서 GP 에 대해 같이 연구할 자들도 거의 없다는거다. GA는 참 많다. ES 는 슬슬 많아질 형편이다. 얘가 CMA 라는 획기적인 녀석이 등장한 이후부터는 GA 보다도 더 초점이 맞춰지고 있는 분위기이기 때문에... 하지만 GP는 여전히 크게 뭐 없다. 아무리 외국논문을 보고 연구하고 생각한다고 해도, 내 생각에 절대 혼자하는 연구는 연구가 될 수가 없다. 연구는 고독 한거? 무슨 연구가 원맨쇼도 아니고 어떻게 연구를 고독하게해. 많은 부분에서 연구가 되고 있는것은 분명하지만 그 결과자체를 공개하기도 꺼려지고(왜냐고? 논문 써야지...) 서로간의 연구에 대해서 서로 공유하려는 움직임이 적은것 자체도 있다. 난 내 실력이 부족하지만, 좀 여러 분들과 연구해보고 싶다.

- 알고리즘에 대한 연구들...(유전프로그래밍 자체에 대한...) -

국내에서는 사실 알고리즘 자체에 대해 연구하는 분들 몇분 안계신다. 논문 나오는걸 보면 안다. 알고리즘 자체를 어떤 개선을 이루어내서 그것에 대해 외국애들하고 결과비교를 해서 역전했다 라는 결과보다는 그냥 어떤 분야에 이 알고리즘을 어떻게 적용 시켰더니 결과가 좋더라... 뭐 이런 식이다. (다 그렇다는건 아니고... 어디까지나 대부분이... ) 아예 새로운 뭔가를 만들어 냈다는건 더더욱 가뭄에 콩나듯이 찾기 힘들다. 사실 내 생각에도 우리나라 같이 수학적으로 풀어내는데 주력이되고 수학적 이론을 뭔가 발전시키고 이런 공부가 전혀 안되있는 환경에서는 뭘 더 발전시킬래야 발전 시킬 껀덕지가 있어야지... 수식을 보면 그걸 이해하기보다는 풀어내는데 급급한데...

공학자라는게 사실 그런입장이라는 걸 모르는건 아니지만 늘 아쉽다. 외국애들 알고리즘이라고 만든거 보고 움찔움찔 한다. 생각도 못한 거다 사실. 기본적인 고등학교 정석에나 나오는 그런 공식들도 곧잘 이용해서 새로운걸 만들어낸다. 참 이런거 볼때마다 난 이제까지 무슨 공부를 해온것인가... 회의적인 생각도 든다.

- 마지막 사족 -

그렇다. 유전 프로그래밍이건... 유전 알고리즘 이건 문제는 이녀석들 자체로는 돈이 안된다. 그래 돈이 문제지. 이녀석 자체로 돈버는건 미국에서나 가능한 거고... 우리나라에서 "유전프로그래밍 전문가 입니다." 그래서 넌 뭘할줄 아는데?... 글쎄
유전프로그래밍 전문가래잖아. 그래서 그걸로 뭘 할수 있는데... 이것저것... 근데 어쩌라고. 뭐 이런식? 그렇다. 알고리즘에 대한 중요도는 어디서 굴러먹다온 개뼉다귀만도 못한거다. 알고리즘 자체만 갖고는 아무것도 못하는게 문제... 이걸 어디다가 적용시켜야 그게 비로소 가치를 발한다. 알고리즘 자체가 엄청 발전되어 있다면 물론 적용 시켰을때 좋은 결과를 기대해 볼 수 있다. 하지만 그것만 가지고 있다고 해서 인정해줄 사람은 적어도 난 우리나라 에서는 없다고 본다. 학계에서 논문이 응용분야 적용에 대다수를 차지하는 것도 그런 이유라고 생각한다. 공학이니까. 돈의 논리가 적용되야하는 공학이니까. 하지만 한편으로는 아쉽다. 어디에다가 적용시킬 수 있느냐와 적용시켰을 때의 다른것에 비해 엄청난 향상을 이룰수 있다. 이 둘의 균형이 이루어 질 때에 비로소 가치를 발하는 것이라고 생각하지만, 지금 현 상황에서는 누가봐도 어디에다가 적용시킬 수 있느냐에 초점이 맞춰져 있기에... 그냥 개인적으로 아쉬울 따름이다.

P.S 그냥 알고리즘과 적용분야에 대해 연구하는 학생으로서 끄적여 봤습니다.

Posted by SHHyun

 오늘은 간단하게 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 같은 벤치마크 문제와 함께 제 블로그에서 공개할 예정입니다.
Posted by SHHyun