Previous Contents/Evolutionary Computation

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

shhyun 2007. 6. 20. 13:57

  지난번에 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 으로 메일 보내주시면 감사하겠습니다. (스팸은 사절이예요 ㅠㅠ)