(*) 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에 대한 서술한 내용보다 더 많은 내용을 건드리게 되지 않을까 싶습니다.

    + Recent posts