Previous Contents/Evolutionary Computation

기타 1. 조기수렴 문제와 Global Search, Local Search 문제

shhyun 2007. 6. 1. 12:31

  초기의 진화연산(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일 걸리던게 일주일 넘게 걸릴수도 있겠네요. 하지만 정리를 해야 저도 공부도 하고 그러는 지라 ^^;; 다음에는 조기수렴 문제의 극복에 대한 이야기를 해보겠습니다.