가장 초기에 조기수렴 문제의 극복에 있어서 제기된 이론은 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 에 대해서 서술했습니다. 다음에는 이에 대한 세부적인 내용에 대해서 몇가지만 정리해 보려고 합니다.
한글로 직역하자면 섬 병행진화론 정도가 되겠는데요.
그리고 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 에 대해서 서술했습니다. 다음에는 이에 대한 세부적인 내용에 대해서 몇가지만 정리해 보려고 합니다.