내가 주로 연구하는 것은 최적화(Optimization)이다. 학습에 대해서는 분명 최적화만큼의 지식이 없으며, 이에 대해 여전히 상당한 혼란을 겪고 있음을 사전에 밝힌다.

최적화는 일반적으로 수학에서 많이 쓰이는 용어이며, 가장 대표적인 예로는 실수 최적화가 있다. 어떠한 주어진 함수 f(x) 의 최대 혹은 최소 값을 찾아내는 문제로서, 미분이 가장 대표적으로 사용되는 기법이다. f'(x) = 0 인 지점을 변곡점이라 하고, 이 변곡점들에서 최대, 최소값이 발견될 수 있다. 유전 알고리즘이나 진화 전략(Evolutionary Strategies) 혹은 PSO(Particle Swarm Optimization) 기법들 또한 이런 최적화를 위한 도구이며, 종종 최적화라는 이름으로 언급되곤 한다.

학습(Learning)이라는 이름으로 불리는 기법들이 있다. 일반적으로 최적화 라는 의미와 비교되는 것은 Machine Learning 에 대한 이야기 인데, 상당히 애매한 부분이 있다. 유전 프로그래밍(Genetic Programming)은 분명 최적화 기법이다. 그런데 어떤 의미로서는 Machine Learning 의 한 부류로 분류되기도 한다[각주:1]. 신경회로망(Artificial Neural Network)은 어떤 의미에서는 학습도 최적화도 아니라고 생각할 수 있다. 그것 자체로는 아무것도 할 수 없고, 이를 특정한 트레이닝 모델에 대해 "학습"을 시켜야 이를 하나의 알고리즘으로서 적용할 수 있다.

사실 학습과 최적화에 대한 경계에 대해 가장 큰 의문이 생긴 이유가 "신경회로망" 때문이다. 분명 신경회로망은 어떠한 학습 데이터에 대해 최적의 가중치값을 갖게 하기 위해 "학습" 이라는 과정을 수행한다고 한다. 문제는 여기서 발생하는데, 신경회로망의 대표적인 학습 방법으로는 오류역전파 알고리즘(BP, Back-Propagation)이 있고, 이는 특정한 트레이닝 세트에 대해 발생하는 오차를 앞에 있는 노드에 반영 시켜 해당 오차를 점점 줄여나가는 것이다. 그리고 LMA(Levenberg-Marquardt Algorithm)이 있는데, 이는 가우스-뉴튼 메소드의 확장으로서 Non-linear least square problem 을 해결하는데 사용한다.

바로 여기서 발생한 문제다. 분명 LMA 알고리즘은 Non-linear least square problem 에 대한 최소의 error 값을 찾아내기 위한 알고리즘이다. 또한, 이 알고리즘은 최적화 알고리즘의 성능 테스트에 대표적으로 사용되는 Rosenbrock Problem 을 해결하기 위한 방법으로도 사용된다. 그런데 이를 신경회로망에서는 학습 알고리즘으로 분류하기도 한다[각주:2].

분명 어딘가에선 "학습" 이라는 이름으로 불리고 있지만, 이것들이 엄밀히말하면 "학습"이라고 할 수 있을까? 만약, 위의 논문에서 사용하는 바와 같이 신경회로망의 "학습"을 위한 도구로서 사용된 알고리즘을 "최적화"라는 기법으로 말하지 않고, "학습"이라는 기법으로 소개한다면, 그렇다면 NEAT(Neuro-Evolution of Augmenting Topologies)와 같은 기법[각주:3] 또한 최적화라 분류하지 말고, "학습" 이라는 형태로 분류해야 하는가? (NEAT는 유전 알고리즘을 통해 신경회로망을 구축하고 가중치값을 조절하는 기법이다.)

학습이건 최적화건 본질적으로는 중요하지 않을 수도 있다. 어디까지나 내 생각이지만, 사람이 느끼기에 학습이라 불린다면, 어떠한 것이든 적응할 수 있을 것 같고, 인간이 학습한다는 것을 생각하기 때문에 보다 나은 어떠한 결과물을 만들어낼 것이라는 일종의 기대감 같을 것을 줄 수도 있다. 그런데 최적화라 한다면, 분명 이는 어떠한 특정한 환경에 대해 최적의 결과를 만들어낼 것 같은 기대감을 갖게 한다. 분명 하나의 기법에 대해 다른 용어를 사용해서 나타낸 것이지만, 이것이 적용될 환경에 대해 나타날 결과가 다르게 느껴질 수 있다는 것이다. 나만 그렇게 생각할 수도 있지만 말이다.

어쩌면 학습과 최적화라는 용어는 좀 더 명확하게 표기해야되는 것이 아닐까? 어떤것들은 어떠한 특정 목적에만 딱 부합될 수 있는 최적화의 접근방식인데도 학습이라는 표현을 사용하곤 한다. 물론 최적화 접근 방식인데도 학습이라는 용어를 쓰는데는 그만한 이유가 있겠지만, 이것에 대해 적용된 기법 자체에 초점을 두고 명확하게 표현하는 것이 좋지 않을까?

  1. http://en.wikipedia.org/wiki/Machine_learning 물론 위키의 신뢰성을 봤을 땐, 누군가 편집한 사람의 개인적인 의견일 확률도 높다. [본문으로]
  2. Bogdan M. Wilamowski, "Neural Network Architectures and Learning Algorithms, How Not to Be Frustrated with Neural Networks", IEEE INDUSTRIAL ELECTRONICS MAGAZINE, DECEMBER 2009. [본문으로]
  3. http://www.cs.ucf.edu/~kstanley/neat.html [본문으로]
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


1. 군집간 이주

GA 나 GP 와 같은 진화 알고리즘에서 무시할 수 없는 문제 중에 하나가 조기수렴 문제이다. 이를 해결 하기 위한 여러 가지 방법들이 제안되고 있으며, 대표적으로 유전 연산자의 조절, 선택 연산자의 조절, 군집 형태의 조절 등이 있다. 그 중에서도 다중의 군집 사용과 그것의 조절에 대해서 설명한다.


2. 다중 군집(Multi Population)

군집은 다수의 개체가 하나의 그룹으로 묶여있는 단위이다. 본래 GA 나 GP 에서는 단일의 군집을 사용하여 연산을 수행했었다. 그러나 단일 군집의 효율성을 증가 시키기 위해 군집을 여러 개로 나누어 사용하는 다중 군집 방식이 도입되기 시작했다. 초기에는 군집을 격리시켜 각각의 군집으로 분류해서 이를 발전시켜나가는 방식이 수행 되었으나, 후에는 이 군집들간의 몇몇 데이터를 서로 다른 군집으로 이동시켜서 이를 발전시켜 나가는 방식이 수행되곤 했다.

서로 다른 군집들간의 데이터가 어떤 원리에 의해 이동을 하는지에 따라 여러 가지 방식이 존재한다. 가장 기본적인 형태로 원형이주가 있고, 발전된 형태로 HFC 나 ALPS 와 같이 특정 조건에 의해 서로 다른 군집으로 격리 시키는 형태가 있다. 이 방식들은 전체적으로 알고리즘 자체의 조기수렴은 방지 하면서 최적해를 찾아가는 성능은 발전 시키는 방향을 염두로 설계한 방식들이다.



3. 원형 이주 방식(Ring Migration)

원형 이주 방식은 군집들 간의 데이터 이동 방향이 하나의 흐름을 가진다. 그리고 일정한 주기마다 특정 개체를 다음의 군집으로 이동시키는 방식이다. 이 때, 이동되는 개체들을 수용할 공간을 할당하는 방식과 이동 시킬 개체를 선택하는 방식의 조절이 가능하며, 이에 따라서 각기 다른 효과가 나타난다.

일반적으로 많이 쓰이는 방식은 가장 높은 적합도의 개체를 다음 군집의 가장 적합도가 낮은 개체로 대체 시키는 방식이고, 일반적으로 해당 군집의 10%의 개체를 변경하는 방식을 사용한다. 여기서 너무 많은 개체를 변경하는 방식을 사용할 경우 전체적으로 군집 전체가 비슷한 개체들로 수렴해버리는 현상이 나타나며, 이로 인해 오히려 더 빠르게 조기수렴하는 현상이 나타나는 경우도 있다.


4. 주입형 이주 방식(Injection Migration)

주입형 이주 방식은 여러 개의 개체군에서 최고의 적합도를 갖는 개체들이 한 군집으로 모여 경쟁을 하는 방식이다. 기본적인 원리는 가장 좋은 형질의 유전자들끼리의 교배를 통해 좀 더 좋은 결과를 기대하는 방식이지만, 여러 군집이 수렴될 경우에 오히려 비슷한 유전자들이 하나의 군집에 모이게 되어 조기에 수렴하는 결과가 나타나는 경우도 있다.

주입형 이주 방식도 원형 이주 방식과 같이 일정 주기에 약 10% 의 개체를 주입 받아 사용하는 것이 대부분이며, 단일 적합도 함수를 가진 경우보다는 다수의 적합도 함수를 갖는 경우에 주로 사용된다.

5. HFC(Hierarchical Fair Competition)


HFC는 교육이론으로부터 파생된 군집의 교환 방식이다. 일반적인 교육 시스템은 같은 학년의 학생들, 즉 비슷한 수준의 학생들끼리의 경쟁을 모토로 한다. 그러나 일반적 진화연산의 경우에는 적합도가 높고 낮음에 관계 없이 모두 같은 환경에서 경쟁을 하게 된다. 이로 인해 적합도가 높은 개체만이 살아남고, 적합도가 낮은 개체가 비록 좋은 형질을 지녔더라도 이것이 보존되지 않는 현상이 발생한다.

HFC 에서는 이러한 불공정한 막기 위해 적합도에 따른 개체간의 분류가 이루어지고, 이를 이용해 적합도가 비슷한 개체들끼리만 공정한 경쟁을 하도록 한다. 이로 인해 조기수렴 효과가 억제되는 효과를 가지며, 적합도는 낮을 지라도 우수한 형질을 가지고 있는 개체들이 탈락되는 현상을 억제하는 효과를 가진다. 구체적인 알고리즘의 여러 가지의 파라미터 및 제한 요건은 아래에 정리되어 있다.


(*)HFC 모델의 구성요소


The Hierarchical Organization of Subpopulations to Establish a Fitness Gradient


낮은 적합도의 개체들은 낮은 레벨에 머무는 것을 허용한다.

낮은 적합도의 개체들은 더 낮은 레벨의 군집으로 이주할 수 있다.

허용 범위의 적합도 아래로 생성된 자손들은 해제시킬 수 있으며, 반복적으로 연산을 수행할 수 있다.

그들의 부모보다 낮은 적합도를 가진 생성된 어떠한 자손도 해제 당할 수 있다.

선택된 부모로부터 생성된 자손들은 적어도 한 부모의 적합도보다 높은 경우 생성될 수 있다.

   

Random Individual Generator : The Source of Genetic Material

   

최하위 레벨의 군집은 지속적으로 새로운 임의의 개체를 유입한다.

   

The Migration Policy from Lower to Higher Fitness Levels

   

몇몇 레벨의 군집에서 해당 군집의 허용 범위에 적합하며 이주되는 개체들은 몇몇의 적합도가 좋지 않은 개체들을 대체하게 된다.

만약에 허용된 버퍼로부터 개체가 이주된 후에 빈 공간이 생기게 되거나 혹은 그 허용 버퍼에 빈 공간이 생길 경우, 그것은 현재 멤버로부터 변이 연산을 수행하거나 두 개의 멤버를 크로스 오버 연산하여 필요한 만큼의 새로운 개체로 추가하거나, 더 낮은 레벨로부터 개체를 이주할 수 있다.(최 하위 레벨의 개체는 새롭게 생성하여 추가한다.)

이주는 오직 한 레벨에 대해서만 허용한다.

   

Setting the Parameters of the HFC Model

   

적합도 레벨의 개수,

각 레벨의 적합도 범위

6. ALPS(Age-Layered Population Structure) (2)

ALPS 는 HFC 와 비슷한 개념을 가지고 탄생한 알고리즘이다. ALPS 에서 공정한 경쟁의 요소로 사용되는 것은 개체의 나이가 된다. 여기서 나이란 해당 개체가 얼마나 오랜 시간 동안 진화가 되어 왔느냐를 의미하는 것이다. 즉, 비슷한 시간 동안 진화가 되어온 개체 들 간의 교배만을 허용하는 알고리즘이다.

마찬가지로 HFC 와 같이 조기수렴의 효과를 획기적으로 억제하는 효과를 보여주며, 특히 매우 어려운 문제에서 아주 오랜 세대에 걸쳐 진화연산을 수행할 때에 그 효과가 뛰어난 것으로 알려져 있다.


(*) 약 10만 세대까지는 비슷하지만, 그 세대수가 80만, 100만이 넘어서는 경우에는 확실한 성능차를 보여줌. ((2)참조)


이 ALPS 알고리즘의 구체적인 파라미터나 제한요소들은 아래에 정리되어 있다.


  1. 흐름
    1. 새롭게 임의로 생성되는 개체는 나이 0 을 부여 받는다.
    2. 변이나 재조합에 의해 생성된 개체는 가장 오래된 부모의 나이에 +1만큼 부여 받는다.
    3. 엘리티즘과 같은 방식에 의해 변형 없이 복사될 경우, 나이를 1 증가 시킨다.
    4. 만약에 한 개체가 그 세대에서 여러 번 선택되어 변이될 경우에는 오직 나이를 1만 증가시킨다.
    5. 각각의 개체들은 나이에 의한 계층으로 구분된다.
    6. Age-gap parameter 는 계층에 곱해지는 수치이다. 예를 들어 Polynomial Aging-scheme 에 age gap 20이 곱해질 경우, 20, 40, 80, 180, 320, … 이 된다.

         

  2. 기존의 EA와 다른 몇가지 형태
    1. 개체들은 오직 자신의 계층과 그 이전의 계층과 교배연산을 수행할 수 있다. 예를들어 layer n 의 경우 layer n-1 과 n 의 계층이 교배연산에서 선택될 수 있다.
    2. Layer 0 은 age-gap 세대 마다 새롭게 생성된 개체로 대치된다.
    3. 현재 계층의 개체가 너무 늙게 되면, 이것은 다음의 늙은 계층과 비교하게 되어 만약에 이것이 적어도 하나의 개체보다 좀더 좋은 적합도를 갖는다면 그것은 다음 계층의 개체와 교체하게 된다.
    4. 각각의 계층은 고정된 개체수를 가짐. 논문에서는 총 10개의 계층으로 구분 하여 100개씩의 개체를 갖도록 만들어졌음.
    5. 처음부터 모든 계층이 활성화 되는 것이 아닌, 초기 계층부터 age-gap 마다 새롭게 생성되는 계층에 대해 점증적으로 수행되는 방식. 만약 age-gap 이 20 일 경우, 초기 20 세대에는 첫번째 계층만 수행, 그리고 40세대 까지 첫번째와 두번째 계층만을 유전연산 및 수행, 60 세대 까지는 첫번째, 두번째, 세번째 계층만을 수행하는 방식.


7. 정리

이주 방식 자체는 조기수렴의 감소를 타겟으로 계획된다. 어떤 특정 문제에 대해 연산 자체의 획기적 성능 개선이나 전체적인 리소스의 점유와 같은 것을 염두 하는 것이 아니다. 이주 방식은 오히려 어떠한 문제에서든지 연산 자체의 효율성을 극대화 시켜주는 것을 타겟으로 하기 때문에 범용적인 사회적 문제나 현상을 토대로 알고리즘 화 된 것이 많다. 그러므로 실제적인 문제의 해결에 있어서 문제의 성질에 따른 연산자의 선택이 가장 우선적이며, 그 연산자의 올바른 발전 양상을 유도할 수 있는 이주 방식의 설정은 부차적인 문제가 될 수 있다.


참고 문헌

1. Jianjun Hu, Erik Goodman, Kisung Seo, Zhun Fan, Rondal Rosenberg The Hierarchical Fair Competition(HFC) Framework for Suitable Evolutionary Algorithms. Evolutionary Computation, 2005.

2. G. S. Hornby, "ALPS : The Age-Layered Population Structure for Reducing the Problem of Premature Convergence. " GECCO'06, pp. 815-822, July 8–12, 2006.



Posted by SHHyun
(*) CMA(Covariance Matrix Adaptation)
- 공분산 행렬 적응 방식 입니다.
- CMA 통장 말하는거 아니예요 ^^; 그걸 기대하셨다면 back space 를 살포시;;

본 자료는 http://www.bionik.tu-berlin.de/user/niko/cmaesintro.html 
  • Four slides on randomized search and the CMA-ES (pdf).
  • A written tutorial (pdf 460KB).
  • 위의 두 자료를 토대로 나름의 의견을 반영하여 작성 된것임을 미리 밝혀드립니다.
    좀 더 정확한 내용을 원하신다면 위의 두 자료를 참고하시는 것이 좋을 것으로 보여집니다.
    위의 두 자료는 수치해석법에 대한 기본적 지식을 토대로 보시면 더 쉽게 이해하실 수 있을 것으로 보여집니다.

    우선은 문제를 정의할 필요가 있습니다.

    주어진 문제가 다음과 같습니다.

    연속적인 도메인에서 적합도를 최소화 하는 문제 입니다.
    어떤 변수 x 에 대해 f(x) 값을 최소화 하는 문제 라고 가정합니다.

    즉, x -> (B) -> f(x) 이런 시나리오가 됩니다.
    여기서 (B) 는 블랙박스로 어떤 처리가 이루어지는지 알 수 없는 것으로 가정합니다.
    중요한 것은 어쨌든 x 는 블랙박스를 거쳐 f(x) 가 된다는 것입니다.
    저것이 일반적인 ES나 GA에서 사용하는 적합도 함수의 형태가 되는 것입니다.

    한마디로 말해서 우리가 일반적으로 수행해서 최적화(또는 최소화)를 시키고자하는 목적함수가 어떤 속성을 가지고 있는지 알 수 없는 것입니다. 이는 대부분의 실제 일상에서 쓰이는 여러가지 복잡한 문제에서 나타나는 형태입니다. 실세계의 문제들. 즉, 공장자동화가 될 수도 있고, 로봇 게이트 생성 문제일 수도 있고, 다리를 만드는 문제일 수도 있습니다. 이런 문제들의 해로서 이용하는 값들은 그 중간 처리과정을 알 수가 없다는 것이 문제입니다.

    문제 자체가 가지고 있는 어려움들(불연속성, 컨벡스하지 않은 것, 조건이 특이한 경우등등)이 이를 해결하기가 매우 어려운것에 초점을 맞추고 있습니다. 이의 해결을 위해 기존의 GA 나 ES 를 이용했습니다만, 문제가 어려울수록 시간이 오래걸리고 연산량이 늘어나는 단점이 있습니다. 가장 중요한 것은, 확률. 즉 우연에 의존하기 때문에 그 이론적 근거가 매우 미약하다는 단점이 있었죠. 그래서 GA나 ES가 그 효과가 잘 나옴에도 불구하고 많은 무시(뭐.. 말이 그렇다는 거죠. 너무 진지하게 받아들이실 필요는 없어요 ^^)를 당했었습니다.

    하지만 ES 에서 CMA 기법의 등장 이후로 수많은 학자들로부터 관심을 받게 되었습니다. 왜냐면 이녀석은 이론적 근거를 가지고 있고, 그 효과까지 이제까지 나온 거의 모든 기법들에 비해서 매우 우수하기 때문이죠. (하지만 Local Search 기반의 비슷한 알고리즘인 G3 PCX 와 CMA-ES 를 로봇 게이트 문제에서 테스트한 결과는 기본적인 SGA 보다도 좋지 않았습니다.)

    실험 결과를 보면 대표적인 벤치마킹 문제인 Rosenbrock 문제나 Rastrign 문제에 대해서 엄청 우수한 결과를 보여주고 있습니다. 그 결과치에 대해서는 위에 링크한 홈페이지에 가셔서 논문을 뒤져보시면 알 수 있습니다.

    어쨌든 기존의 방식은 랜덤하게 여러가지 포인트를 여러군데를 막 집어 낸 후에 이것을 파악해 나가는 방식이었죠. 하지만 CMA 라는 방식은 비슷하긴 한데 확률적인 데이터를 통한 지점의 변형을 이루어 나갑니다. 공분산행렬이 가지고 있는 정보는 모든 세대에 걸쳐 누적되기도 하고, 바로 전 세대의 데이터만을 누적 시키기도 합니다만, 그 정보를 통해 함수를 어떤 방향으로 진화시켜 나갈지를 결정해 줍니다. 그 방식에 대해서는 차차 알아봐야 겠죠 ^^;;

    어쨌든 오늘은 CMA에 대한 개략적인 내용에 대해서 소개했습니다. 하나하나 천천히 다 집어 들어가게되면 이제까지 GA에 대한 서술한 내용보다 더 많은 내용을 건드리게 되지 않을까 싶습니다.

    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 Algorithm 에 대한 포스팅을 하는군요.

    크게 언급할 부분은 아니지만, 이부분에 대해 연구하시는 대다수의 분들이 매번 느끼시는 부분이리라고 사료됩니다.

    Generational 과 Steady-state 의 차이점에 대한 부분입니다.

    일반적 유전연산, 즉, Evolutionary Computation 에서, 그것도 유독 GP 와 GA 에서는 Generational 이라 불리는 방식과 Steady-state 라고 불리는 두가지 방식이 있습니다.

    이 두 방식의 차이점은 아직 학회에서 확실하게 정의하지는 않았습니다.
    반드시 이래야 한다, 라든지 이것이 표준이다 라는 레퍼런스가 없는 것입니다.

    하지만 확실한 차이점은 존재합니다.

    그 차이점이라는 것은 다음같은 점이지요.

    Generational ==> 이전 세대의 모든 개체에 대해 유전연산이 수행되어야 하고, 다음 세대의 개체는 이전 세대의 모든 개체의 유전연산이 수행된 형태여야 한다. ( 여기서 유전연산이란 Reproduction 또한 포함됩니다 , Reproduction 은 개체를 그대로 보존시키는 연산을 의미합니다. )

    Steady-State ==> 이전 세대에서의 몇몇의 개체에 대해서만 유전연산이 수행되어야 하고, 이전세대에서 유전연산이 이루어 졌음에도 성능개선이 없다면 그 개체는 소멸될수도 있고, 유지 될 수도 있다 ( 대다수는 소멸시킵니다 ).

    라는 것입니다.
    저 두가지 점이 바로 Generational 방식과 Steady-state 방식을 구분하는 차이점입니다. 뜬구름 잡는듯한 느낌이죠. 사실 그 내부의 수많은 연산 부분에 대해 정의하는 부분이 없기때문에, 어떤 연산들은 Generational 같기도, 혹은 Steady-state 같기도 합니다. 애매한 구분이죠. 그래서 가장 큰 구분점으로는 이전세대에서 다음세대로 몇개의 개체가 유지되어 갈 지에 대한 점이 될 수 있습니다. 그리고 구분을 짓는데 가장 큰 구분점들을 이용합니다.

    그러므로 우리가 Evolutionary Strategies(이하 ES) 같은 경우는 Steady-State 방식이라고 할 수 있는것이지요. 몇개의 개체만 선택하고 그것에 대해서 연산을 한후에 그것들을 다음세대로 넘기게 될지, 소멸 시킬지를 결정하기 때문이죠.

    SGA 같은 경우에는 Generational 방식이라고 할 수 있습니다. 모든 개체들이 유전연산에 의해 대체되기 때문이죠.

    Generational 방식과 Steady-State 방식을 구분하는 것이 무슨 의미가 있냐면, 서로의 연산 방식의 차이로 인해 서로 고민해야 하는 문제가 달라지기 때문입니다.

    Generational 방식은 모든 개체, 모든 세대에 걸쳐 연산이 전범위적으로 일어나기에 수렴속도가 매우 빠릅니다. 일반적인 연산에서 Generational 방식이 많이 이용 되는 것은 그만큼 빠른 수렴을 통해 최소한의 Local Optima 에 도달하는 속도가 빨라지기 때문이죠. 하지만 그것을 다시 생각해보면, 오랜 시간 최적화를 거쳐서 Global Optima 에 도달하는 확률은 적어질 수가 있습니다. 게다가 유전연산을 한번 수행할때마다 걸리는 수행속도를 생각하게 된다면, 오히려 비 효율적인 연산이 될 수도 있습니다. 그래서 수렴 속도를 늦추는 Multi-pop 이나 HFC(Hierarchical Fair Competition) - Kisung Seo, Jianjun Hu, Erik Goodman 등 , ALPS(Age-Layered Population Structures) - Gregory S. Hornby, 등의 기술들이 도입된 것이지요. 이런 기법들을 통해 Generational 방식을 개선시켜 나가게 되었습니다.

    하지만 Steady-State 방식은 조금 다릅니다. Steady-State 방식은 소수의 개체에 대해 적은양의 연산이 매우 긴 세대동안에 일어나게 됩니다. 그래서 수렴속도도 일반적 Generational 보다는 느린편이고, Local Optima 에 도달할 확률보다 Global Optima 에 도달할 확률이 높습니다.(짧게짧게 여러 경우의수를 가지고 개선여부를 테스트하기 때문입니다.) 하지만, 다시 생각해보면 Global Optima 에 도달하는 시간이 그만큼 길어진다는 것은 Local Optima 에 조차 빨리 도달하기 어렵다는 말이며, 그만큼 연산의 수행시간이 길어질 수 있다는 것입니다. 양날의 칼인 셈이지요. 그래서 이를 개선하기 위한 기술들로 한번에 확실한 해를 찾아 이동하는 기술들이 많이 제안이 되어 있습니다. UNDX(Unimodal normal distribution crossover), PCX(a generic parent-centric recombination operator) - Kalyanmoy Deb 등, CMA-ES(Covariance Matrix Adaptation ES) - Hansen 등의 기술들이 소개되어 있습니다. Steady-State 자체의 깊고 세밀한 탐색 덕분에 Steady-State 방식은 최근에 각광을 받고 있는 방식이고, 특히 실수최적화 문제에서 최고의 성능을 발휘하고 있는 기술입니다.

    가장 핵심이 되는 이야기는 사실 Generational 과 Steady-state 방식이 각각 Bit나 non-permuation 문제, 그리고 실수최적화 문제에 적합하다는 사실이겠죠. Generational 이 Steady-state 방식보다도 아직은 Bit 나 non-perm 문제등에 더 많이 이용이 되는것이 현실이고, 실수최적화 에서는 Steady-State 방식이 ES의 등장과 더불어 가장 널리 쓰이게 되는 방식이 되었습니다.

    두 알고리즘의 차이점은 사실 언급하기가 애매한 면도 없지않습니다. 말씀 드렸듯이, 단지 몇개의 개체나 유전연산이 일어나는지에 대한것이 가장 큰 이유이기 때문이죠. Generational 방식을 이용할때에 Reproduction 이 90%이상을 차지하게 된다면 사실 이모델은 Steady-State 와 차이가 없겠지만, 일반적으로는 그렇지 않겠죠. 어디까지나 서로 일반적인 면에서 바라보는 입장입니다. 정확하게 반드시 이렇다 라는건 없는것이지요.

    여러분께서도 만약 실수최적화 문제를 해결하시는데에 기존 이용방식이 맘에 드는 결과를 도출해 내지 않는다면, 메인 알고리즘을 Generational 혹은 Steady-state 방식중 어떤 것을 이용하는지 한번 확인해보세요. 모든 분야에서 완벽하게 차이를 보일 수 밖에 없다는 결과발표는 아직 없지만, 일반적으로 각각의 장점이 존재하니까요.


    P.S. 정말 오랜만에 포스팅이었습니다. 시험을 앞두고 있는 마당에 이정도도 못하면 정말 더는 못할것 같더군요;; 뭐가이렇게 일이 많은지, 일에 치이고 치이다보니 일반론적인 부분조차도 머리속에서 자꾸 왔다갔다 거리는 바람에 정리하는데 시간이 꽤걸렸습니다. 혹시라도 유전연산이나 이런분야에 대한 연구를 하시는 분이 계시다면 제 자료들이 도움이 되셨으면 좋겠습니다.

    참고문헌

      ALPS:The Age-Layed Population Structure for Reducing the Problem of Premature Convergence - Gregory S. Hornby, GECCO'06 July 8-12, 2006, Seattle, Washing ton, USA. ACM 1-59593-186-4/06/0007.
      The Hierarchical Fair Competition(HFC) Framework for Sustainable Evolutionary
    Algorithms - Jianjun hu , Erik Goodman, Kisung Seo, Zhun Fan, Rondal Rosenberg, 2005 by the Massachusetts Institute of Technology ,Evolutionary Computation 13(2): 241-277
      A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization - Kalyanmoy Deb, Ashish Anand, Dhiraj Joshi, 2002 by the Massachusetts Institute of Technology, Evolutionary Computation 10(4): 371-395
      The CMA Evolution Strategy: A Tutorial, Nikolaus Hansen, November 11, 2005

     보시면 아주 좋을 논문들입니다. (마지막 논문은 수학적 지식이 없으시면 절대 이해하기 어렵습니다.)
    Posted by SHHyun

     이번에는 지난번에 언급했던 Island Parallelism 의 방식중에서 Injection 방식에 대해서 언급해보겠습니다.
    Injection 방식이란 말그대로 주입식 방식이라고 표현하면 간단하겠습니다.

     GP 나 GA 에서 사용되는 Multi-POP 을 응용해서 만들어진 여러 알고리즘은 크게보면 POP 을 전체적으로 분산, 격리 시켜서 그 상태를 운용하는 방식을 벗어나지 않습니다. 즉, 거의 모든 방식이 Multi-POP 을 이용하게 되는 기본 이론인 Island Parallelism 을 벗어나지 않는 선에서 만들어집니다.
     Injection 방식이라는 것 또한 마찬가지 입니다. 지난번에 Migration 에 의해 몇몇 방식으로 나뉘어 진다고 말씀 드렸는데, Injection 방식 또한 Migration 방식이 약간 변경된 것입니다. 왜 주입(Injection) 방식이라고 불리는가 하면 말 그대로 이 방식은 모든 POP 에 Best 값을 한데 모아서 경쟁시키게 되기 때문입니다. 각각의 POP 은 격리 수용되고, 그 격리 수용된 상태에서 나타난 준 최적해들 혹은 최적해들을 모아 경쟁을 시키게 됩니다.
     그림으로 보면 아래와 같이 되겠습니다.

    사용자 삽입 이미지


     Migration 방식의 대표적인 두가지 중에 하나로 지난번의 Ring Migration 보다 좀 더 강한 수렴성을 나타내게 됩니다. 지난번의 Ring Migration 이 수렴성을 낮추고, 불순물 유입을 통한 조기수렴 방지라는 효과를 노리고 이용되는 반면, 이 방식은 매우 강한 수렴성을 나타나게 해서 조금 더 빠른 속도로 최적화를 이루어 내는게 목적입니다.
     하지만 지난번에 말씀 드렸듯이 수렴이라는 것은 너무 빨라도 안되고 너무 늦어도 안되는 것입니다. 수렴 자체도 최적값이 없기 때문에 여전히 많은 학자들에 의해 논란이 일어나고있고, 논의가 되고 있습니다. 수렴이 빠르게 최적값을 향해 된다면 이것이야 말로 최적이지만 그렇지 않다면 최악의 경우가 나타나는 것이지요.
     문제에 따라서 잘 고르는것이 관건 입니다.

    (*) 마치며...

      지금까지는 사실 수학적인 내용이라기 보다는 알고리즘 적인 내용이었습니다. 하지만 좀 더 깊이 들어가보자면 GA 나 GP 의 Tree 나 Bit string 이 구성될 확률에 대한 Scheme 이론, 그리고 현재 실수 최적화 문제에서 매우 강력한 성능을 발휘하고 있는 것으로 알려진 PCX나 UNDX 와 같은 것들은 완전히 수학적인 연산자 입니다. 다음부터는 정말 정리하는데 오래걸리겠네요;;

    Posted by SHHyun

      지난번에 Island Parallelism(이하 Multi-POP) 에 대해서 간략한 언급을 했습니다. 이번에는 세부적으로 Multi-POP 이 동작하는 방식과 조기수렴을 막는 것을 살펴보겠습니다.
      Multi-POP 자체는 여러개의 POP 을 사용하는 것 외에는 큰 의미를 가지지 않습니다. 하지만 Multi-POP 을 이용할 때 사용할 수 있는 여러가지 기법들에 의해 그 효용성 이 나타납니다. 그러한 기법들 중 Migration 방식에 의해 여러가지 효용성이 나타날 수 있습니다. 여기서 Migration 이라는 것은 개체들이 이주하는 규칙입니다. 오늘은 이 이주 규칙(Migration Rules) 중 가장 대표적으로 쓰이는 2가지 방식에 대해 이야기해 보겠습니다.

    1. 기본적인 Multi-POP(이주 계획 없음)

      가장 기본적인 알고리즘 입니다. 단지 Island Parallelism 을 이용해서 각각의 POP 을 고립시키고 발전 시키는 방식 입니다. 효과로서 기대해 볼 수 있는 것은 지난 시간에 언급했던 갈라파고스 제도와 같은 효과 입니다. 즉, 유전자 개체는 우수한 개체만이 살아남게 되는데 이때, 각각의 섬의 환경에 따라 우수한 개체가 서로 다르게 되어 다른 여러가지 형태의 우수한 개체가 남게 되는 것입니다. 그림으로 보면 아래와 같습니다.

    사용자 삽입 이미지

    (*) 단지 각각의 개체를 독립시켜 연산을 수행하는 방식

      결과적으로, 이 알고리즘이 처음 도입되고 기대한 것은 위에서 언급한 것과 같은 효과 입니다. 하지만 실제적인 효과는 미비했습니다. 하지만 이 알고리즘이 여전히 쓰이는 부분이 있습니다. Multi Fitness 를 이용하는 방식에서 쓰이게 되는데, 같은 유전자를 사용하면서 서로 다른 여러개의 Fitness 를 사용해서 각각의 방식에 대해 최적화 시키는데에 이러한 방식이 쓰입니다.

    2. Ring Migration 방식
     
      이 방식은 위의 기본적인 Multi-POP 에 대해 아주 간단한 이주계획을 추가시킨 것 입니다. 일정 세대의 수행이 끝나게 되면 각각의 군집에서 가장 우수한 염색체를 n 개 만큼 추출해서 다른 개체의 가장 성능이 좋지 않은 n 개의 염색체를 대체 시키게 되는 방식입니다. 이것이 Ring 인 이유는 모든 군집이 순환하도록 되어 있는 구조 때문입니다. 그림으로 보면 다음과 같습니다.

    사용자 삽입 이미지

    (*) 링 처럼 서로의 POP 을 연결하는 형태이기에 Ring Migration 이라고 한다.

      이 방식의 장점은 서로 다른 형태의 군집에 어떠한 다른 형태의 우수한 인자를 유입하기 때문에 또다른 형태의 경쟁이 시작되게 됩니다. 여기서 Local Search 와 Global Search 의 이론이 다시 나오게 되는데, 밑의 그림을 보고 이해하시면 쉽게 이해하실 수 있습니다.

    사용자 삽입 이미지

    (*) 어떤 문제 f(x)의 해가 분포해 있는 단순한 그래프 형태
     
      지난번에 한번 언급했던 문제 입니다. 위의 그래프와 같이 해가 분포해 있다고 가정 하고, 가장 높은 성능의 해를 찾는 것을 목적이라고 가정합니다. 그렇게되면 우리의 최종적 목표는 A1 지점 이라는 것을 아실 수 있습니다.
    여기서 목표를 찾기위해서는 최대한 A1 지점의 계곡과 같은 그래프에 근접해서 해의 탐색을 시작해야 A1 지점에 도달 할 수 있다는 사실을 알 수 있습니다.
      만약 Single-POP 방식을 이용해서 탐색을 시작했는데, A3 지점에 근접한 곳에서 탐색을 시작했다고 가정 합니다. 그렇다면 GA 엔진이 Local Search 를 하기 시작한다면, 최고점으로 A3 지점을 찾는데 만족하게 될 것입니다. 하지만 문제의 최적값은 A1 의 지점입니다. 결국 준 최적점을 찾는데 그치게 된 것입니다.
      하지만 Multi-POP 방식을 이용해서 탐색한다고 가정 했을 경우에는 각각의 POP 의 시작 지점이 좀더 여러곳으로 분포할 수 있기 때문에 최대한 A1 지점에서 시작할 수 있다고 예측할 수 있습니다. 그러나 기본적 Multi-POP 방식을 이용해서 탐색 할 경우에 만약 A1 지점 과 A2 지점의 사이의 계곡점에서 A2 쪽으로 탐색이 시작되었다고 한다면, 결국 우리는 최적점을 못찾게 될 수 있습니다.
      우리가 Multi-POP 방식 중 Ring-Migration 을 이용하게 되었다고 가정하게 되면, 각 지점별 탐색이 이루어 지다가 서로의 지점에서 가장 높은 Fitness 를 가진 개체가 다른 지점에서의 가장 낮은 Fitness 의 개체를 대체하게 됩니다. 결과적으로 최적값을 찾아낼 확률이 조금 더 높아지는 것 입니다.

      하지만 결국은 이 모든 것이 확률의 문제입니다. 그렇기에 우리가 새로운 알고리즘을 만들어 내는 것들은 이 확률을 높히는데에 주력하게 되는 것입니다. 최적화된 값을 찾아낼 확률을 높히는데에 초점이 맞추어져 있는 것입니다.

    (*) 마치며..

      위의 두가지 외에도 많은 방식이 존재합니다. 이주 규칙 및 방식에 의한 미묘한 차이로도 최적화 값을 찾아 낼 경우도 있고 Multi-POP 을 이용하지 않고, Single-POP 에 다른 연산자들을 적용하는 것만으로도 최적화 값을 찾아낼 수 도 있습니다. 하지만, 가장 중요한 것은 이 기초 이론들이 왜 만들어 졌으며 어떤 근거를 두고 만들어 졌는지를 이해하는 것 입니다. 그래야 새로운 방식을 만들어 낼 때도 그런 근거와 이론에 의해 만들어 낼 수 있기 때문이죠. 모자란 지식으로 많은 것을 정리하다보니 애매한 부분이 많을 수도 있습니다. 틀린 곳 있으면 항상 xjavalov@shhyun.com 으로 메일 보내주시면 감사하겠습니다. (스팸은 사절이예요 ㅠㅠ)
    Posted by SHHyun
    가장 초기에 조기수렴 문제의 극복에 있어서 제기된 이론은 Island Parallelism 이론 입니다.
    한글로 직역하자면 섬 병행진화론 정도가 되겠는데요.
    그리고 Multi-Population 방식이라고도 합니다.
    GA 자체의 출발점이 유전학적인 요소가 강하다보니 유전학적인 측면에서 발전된 이론입니다.

    단순히 설명하자면, 각각의 군집(Population) 이 서로 다른 섬에 떨어져 있다고 가정하는 것이죠.
    각각의 섬에서 따로 발전, 진화를 거듭하게되면 그 섬에 특성에 맞는 군집으로 발전되어 나간다는 이론입니다.
    다윈의 진화론의 출발점이라고 할 수 있는 갈라파고스 제도와 같은 요소를 도입한 해결방식입니다.

    조금 더 자세히 기존 방식과 비교해보면 다음과 같이 될 수 있습니다.

    1. 기존방식(Single-Population)

      하나의 군집을 이용하여 매우 큰 개체수를 이용하여 발전시킨다.
      개체수가 커진다면 그만큼 다양한 탐색영역을 초기에 조사, 탐색하게 되고 그것으로 더 최적화된 요소를 찾아낼 수 있다.
      하지만 개체수가 크더라도 일반적인 선택 연산자(Tournament 혹은 Rank 외 기타등등)를 이용하게 된다면 매우 빠른속도로 한 값에수렴해가는 양상을 보이게 된다.

    2. Island Parallelism (Multi-Population)

      다양한 군집으로 나누어 조금씩의 개체를 이용하여 발전시킨다.
      각각의 군집으로부터 특정세대, 혹은 어떤 조건에 의해 서로의 개체를 교환하는 등의 조건을 정해야한다.
      수렴속도를 늦춰주는 효과는 서로의 군집에서 개체를 교환할 때 이루어진다.
      개체수에 큰 관계 없이 서로 다양한 개체를 교환해 나가며 연산이 이루어 지기에 기존방식 보다는 수렴 속도가 늦춰지게 된다.
      이 방식도 기존 방식보다는 수렴속도가 늦어지지만 결과적으로는 수렴에 다다르게 된다.

    전체적으로 Multi-Population 을 이용하는 것이 기존의 Single-Population 방식보다 좋은성능을 보여주는 것으로 알려져 있습니다. 사실 Multi-Population 을 이용하는 것이 좋은 성능을 보여주기는 합니다. 하지만, 문제의 특성에 따라서, 그리고 개체의 군집은 몇개를 할것이며 몇 세대마다 얼마나 많은 개체를 옮겨주겠느냐와 같은 것에 따라서 성능에 많은 차이를 보여주기에 그에 대한 논문들도 매우 많이 나와 있습니다. 보통 Parallelism, Genetic Algorithm, Migration rule 과 같은 검색어를 이용해서 검색을 해보시면 많은 내용을 찾아보실 수 있습니다.

    마지막으로 Island Parallelism 을 구성하게 될 경우 알고리즘의 변화에 대해서 알아보겠습니다.

     기존의 GA 의 알고리즘은 매우 단순합니다.

      Initialize -> Generation(CX, MUT, SELECTION, ETC...) -> Statistics -> Loop -> ... -> Condition -> END

     하지만 Island Parallelism 을 이용하게 될 경우에는

      Initialize -> Generation -> Statistics -> Migration -> Loop -> ... -> Condition -> END

     로서 Migration 부분이 추가 되게 됩니다. 그리고 초기화 조건이나 기타 다른 Generation 부분에 대해서 각각의 군집(Sub-Population) 에 대해서 추가적인 연산이 이루어 져야 되기 때문에 그에 대한 연산이 필요합니다. 그리고 Migration 을 어떻게 수행하느냐에 따라서도 많은 방식이 존재하기에 그에대한 고려 또한 해 주어야 합니다.

    (*) 마치며...

      간략하게 말로서 설명을 해 보았습니다. 사실 자세히 정리하고자 한다면 A4 용지 20장 이상의 분량은 나오지 않을까 싶습니다. 그 안에서도 너무 많은 분류와 세부적인 연구결과들이 존재하기 때문에 그에 대한 총체적인 정리를 하기에는 조금 무리가 있지 않나 싶어서 우선은 간략하게 Island Parallelism 에 대해서 서술했습니다. 다음에는 이에 대한 세부적인 내용에 대해서 몇가지만 정리해 보려고 합니다.
    Posted by SHHyun

      초기의 진화연산(Evolutionary Computation, 이하 EC) 에서 더 최적 값을 찾기 위해 논의 되었던 최적해에 관련된 두가지 논제가 있습니다. 그것은 바로 조기수렴 문제와 Local Search 문제 입니다. 오늘은 조기수렴 문제와 Local Search 문제가 왜 논의 되었는지 알아보겠습니다.

      GA를 이용한 최적화 문제에서는 보통 Crossover Rate = 0.9, Mutation Rate = 0.1 을 사용합니다. 이는 보다 빠르게 최적값을 찾기 위해 사용하게 됩니다. 하지만 이 문제에서 큰 단점이 있으니, 그것이 바로 조기 수렴의 문제 입니다. 최적값이 저 멀리에 있어도, 그 값에 도달하지 못하고 적당한 중간값을 최적값으로 인식하고 그 값 근처에 머무르게 되는 것입니다. 실제 최적값에 도달하지 못하고, 준 최적값에 도달하거나 전혀 다른 값에 도달해서 머물러 버리는 것입니다. ( f3deceptive 문제와 같은 문제를 참조하시면 엔진 성능이 좋지 않을경우 모든 값이 0에 수렴해 버리는 현상을 확인하실 수 있습니다. 정답은 전부 1에 수렴해야 하는데도 말이죠. ) 
      그러면 CX 와 MUT Rate 를 낮은 값을 사용하면 되지 않겠느냐 라고 반문하실지도 모르겠습니다. 사실 그렇게 하게되면 특정 문제에 대해서는 효과를 볼 수 있습니다. 하지만 실제 GA 가 이용 되는 문제들은 상당한 연산을 하게되는 어려운 문제들 입니다. 그런 문제에서 낮은 CX 와 MUT Rate 를 사용하게 된다면, 최적값을 찾는데 한달, 혹은 몇 달 이상 걸리게 될 수도 있습니다. 그렇기에 보통 CX = 0.9 MUT = 0.1 를 이용하게 됩니다.
      이와같은 이유로 GA 에서는 조기수렴 문제의 극복에 대해 많은 논의가 이루어 졌습니다.

      ES에서는 GA 와는 조금 다른 형태의 문제에 봉착하게 되었습니다. ES 에서는 보통 조기수렴의 문제에 빠지지 않습니다. ES 는 GA 와는 다르게 실수값을 이용하고, 실수 최적화에 최적화 되어있기 때문에 수치를 탐색하는 범위를 어떻게 설정하느냐가 문제가 되었습니다. 이때문에 Global Search 와 Local Search 에 대한 논의가 진행 되게 되었습니다. Global Search 는 해의 공간(Space) 를 아주 넓게 찾는 방식이고, Local Search 는 해의 공간을 아주 좁게 매우 세밀하게 탐색하는 방식입니다. 밑의 그래프는 Rosenbrock 함수(실수최적화문제)의 그래프 입니다.

    사용자 삽입 이미지

    (*) http://mathworld.wolfram.com/RosenbrockFunction.html 의 자료입니다.

      해의 범위가 매우 특이한 형태를 갖추고 있음을 알 수 있습니다. 가운데 부분에도 굴곡이 있고, 매우 넓은 범위에 걸쳐 굴곡이 펼쳐져 있기 때문에 이를 찾아내기 위해서는 매우 조밀한 Local Search 가 필요하다는 것을 확인할 수 있습니다. 하지만 저 값에 다가가기 위해서는 Global Search 도 필요한 것이죠. 그래서 ES 에서는 이 둘을 조합하는 방식에 대해서 논의가 되게 되었습니다.

    (*) 마치며...
     
      오늘은 간단하게 EC 에서 논의된 중요한 두가지 문제에 대해 알아보았습니다. 어째 기초에 대한 것은 많이 모자르게 정리하면서 어려운 문제에 대한 논의만 잔뜩하는 기분이 들기도 합니다. 하지만 기초에 대한 것은 책을 펼쳐보면 쉽게 알 수있는 것들이 많기에 슬슬 어려운 논제와 수학적 논제들에 대해 정리해 보려고 합니다. 아마 포스팅 하나 하는데 2~3일 걸리던게 일주일 넘게 걸릴수도 있겠네요. 하지만 정리를 해야 저도 공부도 하고 그러는 지라 ^^;; 다음에는 조기수렴 문제의 극복에 대한 이야기를 해보겠습니다.
    Posted by SHHyun