Previous Contents/Evolutionary Computation 11

최적화와 학습이란 용어 대한 생각...

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

GA나 GP의 이론 검증의 어려움

GP 의 해가 가지는 특성을 파악하기 위해 실험을 통해 대규모의 데이터를 수집하였다고 가정하자. 그리고 대부분의 해에서 나타나는 어떠한 특성이 발견 되었다면, 과연 여기서 대부분의 해는 반드시 그 어떤 특성을 갖게 되는 것일까? GA, GP 의 조기수렴이 해의 다양성에 악영향을 끼치고, 좋은 결과로 수렴하는 것을 방해한다고 했을 때, 조기수렴을 막으면 반드시 해가 다양성을 폭넓게 가지면서, 좋은 결과로 수렴할 것인가? 어떠한 명제를 가정했을 때, 그 역이 반드시 참일것이라는 보장 같은 것은 없다. 결국 우리가 일반적으로 데이터를 수집하여 하는 일은 대부분이 그러한 특성을 보인다는 것에서 끝나는 것인데, 이것의 역을 증명해낼 좋은 방법은 없을것인가? 몇년째 계속 고민해보지만, GA, GP 쪽에서는 이를 어..

진화 연산과 병렬 처리 시스템

1. 개요 병렬처리 시스템은 최근에 가장 주목 받고 있는 컴퓨팅 성능 향상 기술 중에 하나입니다. 물론 과거에도 병렬처리 시스템이 주목 받아 왔지만, 그 당시에는 CPU 의 업그레이드 만으로도 50%, 100% 이상의 성능향상을 이룰 수 있었기에 지금보다는 적은 관심을 보였었습니다. 그러나 현재의 CPU 가 가진 한계에 거의 다다름에 따라, 성능 개선의 기법으로 병렬처리 기법들이 주목을 받고 있습니다. 즉, 하드웨어적 한계를 소프트웨어 적인 기법으로서 넘어서려고 한다고 표현할 수 있겠습니다. 이 병럴처리 시스템은 크게 내부, 외부의 두 가지 요소로서 존재한다고 볼 수 있겠습니다. 내부 요소로서는 CPU 의 멀티 코어화, GPU 의 발전 등을 들 수 있겠고, 외부적으로는 대규모 네트워크로 구성된 컴퓨팅 환..

EA 의 군집간 이주 형태

1. 군집간 이주 GA 나 GP 와 같은 진화 알고리즘에서 무시할 수 없는 문제 중에 하나가 조기수렴 문제이다. 이를 해결 하기 위한 여러 가지 방법들이 제안되고 있으며, 대표적으로 유전 연산자의 조절, 선택 연산자의 조절, 군집 형태의 조절 등이 있다. 그 중에서도 다중의 군집 사용과 그것의 조절에 대해서 설명한다. 2. 다중 군집(Multi Population) 군집은 다수의 개체가 하나의 그룹으로 묶여있는 단위이다. 본래 GA 나 GP 에서는 단일의 군집을 사용하여 연산을 수행했었다. 그러나 단일 군집의 효율성을 증가 시키기 위해 군집을 여러 개로 나누어 사용하는 다중 군집 방식이 도입되기 시작했다. 초기에는 군집을 격리시켜 각각의 군집으로 분류해서 이를 발전시켜나가는 방식이 수행 되었으나, 후에는..

기타. CMA(Covariance Matrix Adaptation) 의 시작.

(*) 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). 위의 두 자료를 토대로 나름의 의견을 반영하여 작성 된것임을 미리 밝혀드립니다. 좀 더 정확한 내용을 원하신다면 위의 두 자료를 참고하시는 것이 좋을 것으로 보여집니다. 위의 두 자료는 수치해석법에 대한 기본적 지식을 토대로 보시면 더 쉽게 이해하..

기타. 알고리즘과 적용에 대한 작은 생각들(주로 유전프로그래밍)

본 글은 어떤 일반론적인 생각도 아니고 어디까지나 제 자신의 개인적인 생각들 임을 사전에 밝히도록 하겠습니다. 짧은 지식을 통해 나오는 생각들이기에 편협할 수도 있고, 좁은 식견이 확 보일수도 있고 정리가 안된 그냥 머리속 튀어나오는 대로 쓰는거지만... 그냥 한번 써보렵니다. 사족이므로 반말나갑니다. - 다른 녀석들을 봤을 때 유전프로그래밍이라는 것의 가능성... - 우선 신경회로망 이라는 녀석. 많이 알고 있는 녀석은 아니지만 태어난지 매우 오래되었음에도 불구하고, 과거의 알고리즘에 비해 심대한 변화는 없는 녀석이다. 다층 퍼셉트론 이후에 오류역전파 알고리즘, 그것들을 제외하고는 어째 크게 발전은 없는 모양이다. 사실 내가 크게 관심이 없어서 그럴수도 있지만, 여러 논문을 검색해 보았을때 다 고만고만..

기타 5. Steady-state 와 Generational 방식

오랜만에 Genetic Algorithm 에 대한 포스팅을 하는군요. 크게 언급할 부분은 아니지만, 이부분에 대해 연구하시는 대다수의 분들이 매번 느끼시는 부분이리라고 사료됩니다. Generational 과 Steady-state 의 차이점에 대한 부분입니다. 일반적 유전연산, 즉, Evolutionary Computation 에서, 그것도 유독 GP 와 GA 에서는 Generational 이라 불리는 방식과 Steady-state 라고 불리는 두가지 방식이 있습니다. 이 두 방식의 차이점은 아직 학회에서 확실하게 정의하지는 않았습니다. 반드시 이래야 한다, 라든지 이것이 표준이다 라는 레퍼런스가 없는 것입니다. 하지만 확실한 차이점은 존재합니다. 그 차이점이라는 것은 다음같은 점이지요. Generati..

기타4. 조기수렴 문제의 극복 (3) Island Parallelism(MPOP-Injection)

이번에는 지난번에 언급했던 Island Parallelism 의 방식중에서 Injection 방식에 대해서 언급해보겠습니다. Injection 방식이란 말그대로 주입식 방식이라고 표현하면 간단하겠습니다. GP 나 GA 에서 사용되는 Multi-POP 을 응용해서 만들어진 여러 알고리즘은 크게보면 POP 을 전체적으로 분산, 격리 시켜서 그 상태를 운용하는 방식을 벗어나지 않습니다. 즉, 거의 모든 방식이 Multi-POP 을 이용하게 되는 기본 이론인 Island Parallelism 을 벗어나지 않는 선에서 만들어집니다. Injection 방식이라는 것 또한 마찬가지 입니다. 지난번에 Migration 에 의해 몇몇 방식으로 나뉘어 진다고 말씀 드렸는데, Injection 방식 또한 Migration ..

기타3. 조기수렴 문제의 극복 (2) Island Parallelism(Multi-Population)

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

기타2. 조기수렴 문제의 극복 (1) Island Parallelism 에 대한 간략소개

가장 초기에 조기수렴 문제의 극복에 있어서 제기된 이론은 Island Parallelism 이론 입니다. 한글로 직역하자면 섬 병행진화론 정도가 되겠는데요. 그리고 Multi-Population 방식이라고도 합니다. GA 자체의 출발점이 유전학적인 요소가 강하다보니 유전학적인 측면에서 발전된 이론입니다. 단순히 설명하자면, 각각의 군집(Population) 이 서로 다른 섬에 떨어져 있다고 가정하는 것이죠. 각각의 섬에서 따로 발전, 진화를 거듭하게되면 그 섬에 특성에 맞는 군집으로 발전되어 나간다는 이론입니다. 다윈의 진화론의 출발점이라고 할 수 있는 갈라파고스 제도와 같은 요소를 도입한 해결방식입니다. 조금 더 자세히 기존 방식과 비교해보면 다음과 같이 될 수 있습니다. 1. 기존방식(Single-P..