오늘은 실수최적화 문제에서 이용되는 CX 연산자중
지난번에 다루었던 Arithmetical Crossover[Michalewicz 1996] 의 변형판에 대해서 다루겠습니다.
기존 Arithmetical Crossover 의 특징에 대해 간략하게 알아보면
1. 적용이 쉽다.
매우 단순한 알고리즘으로 구성되어 있기 때문에 적용이 쉽습니다. 물론 random 으로 lambda 값을 산출해 내는 과정에 어떤 알고리즘을 적용시키느냐가 관건이 되지만( 사실 시간에 의한 난수값이 출력되는 것은 신뢰도나 정확도면에서 그다지 높지 않기때문에 다른 알고리즘에서는 잘 쓰이지 않는 경향이 있습니다. ) 그 부분에 대해서만 제외한다면, 서로의 Chrom 값에 lambda 값의 곱과 1- lambda 값의 곱만으로 새로운 Individual 을 만들어 낼 수 있습니다. 이런 면에서 Arithmetical CX 는 적용이 매우 쉬운 CX 연산자 임을 알 수 있습니다.
2. Local Search 에 적합한 연산자
다음 글에서 Local Search 와 Global Search 에 대해서 자세히 알아볼 것이지만, 우선 Local Search 라는 것은 값 자체를 크게 변화없이 조금조금씩 변화시킴으로써 올바른 값으로 수렴해 나가는 원리 입니다. 그렇기에 Local Search 에 적합한 변모를 보이고 있고, 조기 수렴하는 경향을 보이게 됩니다.
3. Individual 전체를 변화시키는 연산자
Artithmetical CX 는 Individual 전체를 변화시키게 됩니다. 일부만을 변화시키는 것이 아니라 모든 Chrom 에 걸쳐 연산이 이루어 지기 때문에 Individual 전체를 변화시킵니다. 이는 초기에 전체적으로 좋은 변화를 이끌어 낼 수 있지만, 실제 이상적인 값에 도달하기 위해서 일부분만을 수정하게 되는 일에 약한 면모를 보이기 때문에 정밀한 최적화 작업에는 적합하지 않음을 의미합니다.
위의 특징을 살펴보시면 아시겠지만, Arithmetical CX 는 초보적인 알고리즘이고, 구현이 쉽고 적당한 결과값을 알아내는 데에 적합합니다. 고로 매우 정교한 작업에는 적합하지 않음을 알 수 있습니다. 하지만 잘 생각해보시면 Individual 전체가 변화하는 문제 때문에 최적화가 거의다 끝날무렵에 미묘한 변화치에 대한 것들을 제대로 캐치하지 못함을 알 수 있습니다. 이런 특징적인 면을 개선시켜서 나온 연산자가 바로 오늘 설명할 수정단순교배(Modified Simple Crossover) 입니다.
-- 사실 이 연산자는 유전알고리즘과 그 응용(진 강규 저) 에도 소개되어 있기에 저작권 문제도 있을 것 같고 해서 제가 소개하기가 조금 껄끄러운게 사실입니다. 저자 이신 진 강규님께서 2000년 도에 직접 작업하신 연산자 인 것 같습니다. 그렇기에 자세한 설명에 대한 것은 위의 책을 참고하시거나 진 강규님의 논문을 참고하시는 것이 좋을 것 같습니다. 저는 개략적인 설명만을 해보겠습니다. --
위에 설명드렸듯이 간단합니다.
지난 번에 소개해 드렸던 Arithmetical Crossover 에
어떤 Chrom 을 변화시킬지를 선택하는 변수가 하나 추가되어 있습니다.
고로
지난번에 소개한 Arithmetical CX 를
특정 선택된 Chrom 에 대해서만 변화시키는 연산자가 되겠습니다.
본 연산자에 대해서 자세한 설명과 그림을 첨부하고자 했습니다만 왠지 저작권 관련한 문제가 있을 것 같아서 간략한 알고리즘에 대한 설명만을 했습니다. 뭐 저정도로도 충분하다고 생각하지만 그렇지 않을 수도 있구요. 만약 추가적인 설명이나 다른 것에 대해서 알고 싶으시다면 제 블로그에 글을 남겨주시거나 연락주시면 제가 따로 연락을 드리겠습니다. 다음에는 매우 중요한 개념중에 하나인 Local Search 와 Global Search 에 대해서 정리해 보겠습니다. 이 부분은 GA 와 ES 의 성능을 개선시키기 위해 학자들이 연구하는 두 부분중에 하나 입니다. CX 연산자에 대한 소개는 잠시 접어두고, Local Search 와 Global Search 에 대해서 먼저 알아보도록 하겠습니다.