Previous Contents/Evolutionary Computation

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

shhyun 2007. 7. 9. 18:14

 이번에는 지난번에 언급했던 Island Parallelism 의 방식중에서 Injection 방식에 대해서 언급해보겠습니다.
Injection 방식이란 말그대로 주입식 방식이라고 표현하면 간단하겠습니다.

 GP 나 GA 에서 사용되는 Multi-POP 을 응용해서 만들어진 여러 알고리즘은 크게보면 POP 을 전체적으로 분산, 격리 시켜서 그 상태를 운용하는 방식을 벗어나지 않습니다. 즉, 거의 모든 방식이 Multi-POP 을 이용하게 되는 기본 이론인 Island Parallelism 을 벗어나지 않는 선에서 만들어집니다.
 Injection 방식이라는 것 또한 마찬가지 입니다. 지난번에 Migration 에 의해 몇몇 방식으로 나뉘어 진다고 말씀 드렸는데, Injection 방식 또한 Migration 방식이 약간 변경된 것입니다. 왜 주입(Injection) 방식이라고 불리는가 하면 말 그대로 이 방식은 모든 POP 에 Best 값을 한데 모아서 경쟁시키게 되기 때문입니다. 각각의 POP 은 격리 수용되고, 그 격리 수용된 상태에서 나타난 준 최적해들 혹은 최적해들을 모아 경쟁을 시키게 됩니다.
 그림으로 보면 아래와 같이 되겠습니다.

사용자 삽입 이미지


 Migration 방식의 대표적인 두가지 중에 하나로 지난번의 Ring Migration 보다 좀 더 강한 수렴성을 나타내게 됩니다. 지난번의 Ring Migration 이 수렴성을 낮추고, 불순물 유입을 통한 조기수렴 방지라는 효과를 노리고 이용되는 반면, 이 방식은 매우 강한 수렴성을 나타나게 해서 조금 더 빠른 속도로 최적화를 이루어 내는게 목적입니다.
 하지만 지난번에 말씀 드렸듯이 수렴이라는 것은 너무 빨라도 안되고 너무 늦어도 안되는 것입니다. 수렴 자체도 최적값이 없기 때문에 여전히 많은 학자들에 의해 논란이 일어나고있고, 논의가 되고 있습니다. 수렴이 빠르게 최적값을 향해 된다면 이것이야 말로 최적이지만 그렇지 않다면 최악의 경우가 나타나는 것이지요.
 문제에 따라서 잘 고르는것이 관건 입니다.

(*) 마치며...

  지금까지는 사실 수학적인 내용이라기 보다는 알고리즘 적인 내용이었습니다. 하지만 좀 더 깊이 들어가보자면 GA 나 GP 의 Tree 나 Bit string 이 구성될 확률에 대한 Scheme 이론, 그리고 현재 실수 최적화 문제에서 매우 강력한 성능을 발휘하고 있는 것으로 알려진 PCX나 UNDX 와 같은 것들은 완전히 수학적인 연산자 입니다. 다음부터는 정말 정리하는데 오래걸리겠네요;;