이번에는 지난번에 언급했던 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 와 같은 것들은 완전히 수학적인 연산자 입니다. 다음부터는 정말 정리하는데 오래걸리겠네요;;

Posted by SHHyun

댓글을 달아 주세요

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

댓글을 달아 주세요

가장 초기에 조기수렴 문제의 극복에 있어서 제기된 이론은 Island Parallelism 이론 입니다.
한글로 직역하자면 섬 병행진화론 정도가 되겠는데요.
그리고 Multi-Population 방식이라고도 합니다.
GA 자체의 출발점이 유전학적인 요소가 강하다보니 유전학적인 측면에서 발전된 이론입니다.

단순히 설명하자면, 각각의 군집(Population) 이 서로 다른 섬에 떨어져 있다고 가정하는 것이죠.
각각의 섬에서 따로 발전, 진화를 거듭하게되면 그 섬에 특성에 맞는 군집으로 발전되어 나간다는 이론입니다.
다윈의 진화론의 출발점이라고 할 수 있는 갈라파고스 제도와 같은 요소를 도입한 해결방식입니다.

조금 더 자세히 기존 방식과 비교해보면 다음과 같이 될 수 있습니다.

1. 기존방식(Single-Population)

  하나의 군집을 이용하여 매우 큰 개체수를 이용하여 발전시킨다.
  개체수가 커진다면 그만큼 다양한 탐색영역을 초기에 조사, 탐색하게 되고 그것으로 더 최적화된 요소를 찾아낼 수 있다.
  하지만 개체수가 크더라도 일반적인 선택 연산자(Tournament 혹은 Rank 외 기타등등)를 이용하게 된다면 매우 빠른속도로 한 값에수렴해가는 양상을 보이게 된다.

2. Island Parallelism (Multi-Population)

  다양한 군집으로 나누어 조금씩의 개체를 이용하여 발전시킨다.
  각각의 군집으로부터 특정세대, 혹은 어떤 조건에 의해 서로의 개체를 교환하는 등의 조건을 정해야한다.
  수렴속도를 늦춰주는 효과는 서로의 군집에서 개체를 교환할 때 이루어진다.
  개체수에 큰 관계 없이 서로 다양한 개체를 교환해 나가며 연산이 이루어 지기에 기존방식 보다는 수렴 속도가 늦춰지게 된다.
  이 방식도 기존 방식보다는 수렴속도가 늦어지지만 결과적으로는 수렴에 다다르게 된다.

전체적으로 Multi-Population 을 이용하는 것이 기존의 Single-Population 방식보다 좋은성능을 보여주는 것으로 알려져 있습니다. 사실 Multi-Population 을 이용하는 것이 좋은 성능을 보여주기는 합니다. 하지만, 문제의 특성에 따라서, 그리고 개체의 군집은 몇개를 할것이며 몇 세대마다 얼마나 많은 개체를 옮겨주겠느냐와 같은 것에 따라서 성능에 많은 차이를 보여주기에 그에 대한 논문들도 매우 많이 나와 있습니다. 보통 Parallelism, Genetic Algorithm, Migration rule 과 같은 검색어를 이용해서 검색을 해보시면 많은 내용을 찾아보실 수 있습니다.

마지막으로 Island Parallelism 을 구성하게 될 경우 알고리즘의 변화에 대해서 알아보겠습니다.

 기존의 GA 의 알고리즘은 매우 단순합니다.

  Initialize -> Generation(CX, MUT, SELECTION, ETC...) -> Statistics -> Loop -> ... -> Condition -> END

 하지만 Island Parallelism 을 이용하게 될 경우에는

  Initialize -> Generation -> Statistics -> Migration -> Loop -> ... -> Condition -> END

 로서 Migration 부분이 추가 되게 됩니다. 그리고 초기화 조건이나 기타 다른 Generation 부분에 대해서 각각의 군집(Sub-Population) 에 대해서 추가적인 연산이 이루어 져야 되기 때문에 그에 대한 연산이 필요합니다. 그리고 Migration 을 어떻게 수행하느냐에 따라서도 많은 방식이 존재하기에 그에대한 고려 또한 해 주어야 합니다.

(*) 마치며...

  간략하게 말로서 설명을 해 보았습니다. 사실 자세히 정리하고자 한다면 A4 용지 20장 이상의 분량은 나오지 않을까 싶습니다. 그 안에서도 너무 많은 분류와 세부적인 연구결과들이 존재하기 때문에 그에 대한 총체적인 정리를 하기에는 조금 무리가 있지 않나 싶어서 우선은 간략하게 Island Parallelism 에 대해서 서술했습니다. 다음에는 이에 대한 세부적인 내용에 대해서 몇가지만 정리해 보려고 합니다.
Posted by SHHyun

댓글을 달아 주세요

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

댓글을 달아 주세요