reset.

GP 의 해가 가지는 특성을 파악하기 위해 실험을 통해 대규모의 데이터를 수집하였다고 가정하자. 그리고 대부분의 해에서 나타나는 어떠한 특성이 발견 되었다면, 과연 여기서 대부분의 해는 반드시 그 어떤 특성을 갖게 되는 것일까? GA, GP 의 조기수렴이 해의 다양성에 악영향을 끼치고, 좋은 결과로 수렴하는 것을 방해한다고 했을 때, 조기수렴을 막으면 반드시 해가 다양성을 폭넓게 가지면서, 좋은 결과로 수렴할 것인가? 어떠한 명제를 가정했을 때, 그 역이 반드시 참일것이라는 보장 같은 것은 없다. 결국 우리가 일반적으로 데이터를 수집하여 하는 일은 대부분이 그러한 특성을 보인다는 것에서 끝나는 것인데, 이것의 역을 증명해낼 좋은 방법은 없을것인가? 몇년째 계속 고민해보지만, GA, GP 쪽에서는 이를 어..

1. 개요 병렬처리 시스템은 최근에 가장 주목 받고 있는 컴퓨팅 성능 향상 기술 중에 하나입니다. 물론 과거에도 병렬처리 시스템이 주목 받아 왔지만, 그 당시에는 CPU 의 업그레이드 만으로도 50%, 100% 이상의 성능향상을 이룰 수 있었기에 지금보다는 적은 관심을 보였었습니다. 그러나 현재의 CPU 가 가진 한계에 거의 다다름에 따라, 성능 개선의 기법으로 병렬처리 기법들이 주목을 받고 있습니다. 즉, 하드웨어적 한계를 소프트웨어 적인 기법으로서 넘어서려고 한다고 표현할 수 있겠습니다. 이 병럴처리 시스템은 크게 내부, 외부의 두 가지 요소로서 존재한다고 볼 수 있겠습니다. 내부 요소로서는 CPU 의 멀티 코어화, GPU 의 발전 등을 들 수 있겠고, 외부적으로는 대규모 네트워크로 구성된 컴퓨팅 환..

대단한건 아니지만;; 어쨌든, (1) 조기수렴 문제? 조기수렴 문제의 해결에 대해서 연구를 좀 했습니다. 그러던 중에 나온 많은 알고리즘들, 적합도 공유방식(Fitness Sharing), 군중 분산 방식(?, 말이 좀 이상합니다만, 본래는 Crowding 방식입니다. 제 생각에 저 표현이 의미와 잘 부합되는것 같습니다.), 다중군집을 기반으로한 새로운 모델들(Multi-pop 을 기반으로한 HFC(Hierarchical Fair Competition) 혹은 ALPS(Age-Layered Population Structure)) 이 있습니다. 우선 적합도 공유방식은 적합도가 높은 개체들이 적합도가 낮은 개체들에게 자신의 적합도를 나눠준다고 생각하면 간단합니다. 즉, 비슷한 수준의 적합도를 이용해서 다른 ..

오랜만에 Genetic Algorithm 에 대한 포스팅을 하는군요. 크게 언급할 부분은 아니지만, 이부분에 대해 연구하시는 대다수의 분들이 매번 느끼시는 부분이리라고 사료됩니다. Generational 과 Steady-state 의 차이점에 대한 부분입니다. 일반적 유전연산, 즉, Evolutionary Computation 에서, 그것도 유독 GP 와 GA 에서는 Generational 이라 불리는 방식과 Steady-state 라고 불리는 두가지 방식이 있습니다. 이 두 방식의 차이점은 아직 학회에서 확실하게 정의하지는 않았습니다. 반드시 이래야 한다, 라든지 이것이 표준이다 라는 레퍼런스가 없는 것입니다. 하지만 확실한 차이점은 존재합니다. 그 차이점이라는 것은 다음같은 점이지요. Generati..

이번에는 지난번에 언급했던 Island Parallelism 의 방식중에서 Injection 방식에 대해서 언급해보겠습니다. Injection 방식이란 말그대로 주입식 방식이라고 표현하면 간단하겠습니다. GP 나 GA 에서 사용되는 Multi-POP 을 응용해서 만들어진 여러 알고리즘은 크게보면 POP 을 전체적으로 분산, 격리 시켜서 그 상태를 운용하는 방식을 벗어나지 않습니다. 즉, 거의 모든 방식이 Multi-POP 을 이용하게 되는 기본 이론인 Island Parallelism 을 벗어나지 않는 선에서 만들어집니다. Injection 방식이라는 것 또한 마찬가지 입니다. 지난번에 Migration 에 의해 몇몇 방식으로 나뉘어 진다고 말씀 드렸는데, Injection 방식 또한 Migration ..

지난번에 Island Parallelism(이하 Multi-POP) 에 대해서 간략한 언급을 했습니다. 이번에는 세부적으로 Multi-POP 이 동작하는 방식과 조기수렴을 막는 것을 살펴보겠습니다. Multi-POP 자체는 여러개의 POP 을 사용하는 것 외에는 큰 의미를 가지지 않습니다. 하지만 Multi-POP 을 이용할 때 사용할 수 있는 여러가지 기법들에 의해 그 효용성 이 나타납니다. 그러한 기법들 중 Migration 방식에 의해 여러가지 효용성이 나타날 수 있습니다. 여기서 Migration 이라는 것은 개체들이 이주하는 규칙입니다. 오늘은 이 이주 규칙(Migration Rules) 중 가장 대표적으로 쓰이는 2가지 방식에 대해 이야기해 보겠습니다. 1. 기본적인 Multi-POP(이주 계..

가장 초기에 조기수렴 문제의 극복에 있어서 제기된 이론은 Island Parallelism 이론 입니다. 한글로 직역하자면 섬 병행진화론 정도가 되겠는데요. 그리고 Multi-Population 방식이라고도 합니다. GA 자체의 출발점이 유전학적인 요소가 강하다보니 유전학적인 측면에서 발전된 이론입니다. 단순히 설명하자면, 각각의 군집(Population) 이 서로 다른 섬에 떨어져 있다고 가정하는 것이죠. 각각의 섬에서 따로 발전, 진화를 거듭하게되면 그 섬에 특성에 맞는 군집으로 발전되어 나간다는 이론입니다. 다윈의 진화론의 출발점이라고 할 수 있는 갈라파고스 제도와 같은 요소를 도입한 해결방식입니다. 조금 더 자세히 기존 방식과 비교해보면 다음과 같이 될 수 있습니다. 1. 기존방식(Single-P..

초기의 진화연산(Evolutionary Computation, 이하 EC) 에서 더 최적 값을 찾기 위해 논의 되었던 최적해에 관련된 두가지 논제가 있습니다. 그것은 바로 조기수렴 문제와 Local Search 문제 입니다. 오늘은 조기수렴 문제와 Local Search 문제가 왜 논의 되었는지 알아보겠습니다. GA를 이용한 최적화 문제에서는 보통 Crossover Rate = 0.9, Mutation Rate = 0.1 을 사용합니다. 이는 보다 빠르게 최적값을 찾기 위해 사용하게 됩니다. 하지만 이 문제에서 큰 단점이 있으니, 그것이 바로 조기 수렴의 문제 입니다. 최적값이 저 멀리에 있어도, 그 값에 도달하지 못하고 적당한 중간값을 최적값으로 인식하고 그 값 근처에 머무르게 되는 것입니다. 실제 최..

오늘은 실수최적화 문제에서 이용되는 CX 연산자중 지난번에 다루었던 Arithmetical Crossover[Michalewicz 1996] 의 변형판에 대해서 다루겠습니다. 기존 Arithmetical Crossover 의 특징에 대해 간략하게 알아보면 1. 적용이 쉽다. 매우 단순한 알고리즘으로 구성되어 있기 때문에 적용이 쉽습니다. 물론 random 으로 lambda 값을 산출해 내는 과정에 어떤 알고리즘을 적용시키느냐가 관건이 되지만( 사실 시간에 의한 난수값이 출력되는 것은 신뢰도나 정확도면에서 그다지 높지 않기때문에 다른 알고리즘에서는 잘 쓰이지 않는 경향이 있습니다. ) 그 부분에 대해서만 제외한다면, 서로의 Chrom 값에 lambda 값의 곱과 1- lambda 값의 곱만으로 새로운 In..

오랜만에 GA 관련 포스팅 입니다. 예전에 한번 설명 드렸지만, GA 는 원래 Bit 형태의 유전자를 이용해서 연산을 하게 됩니다. 이 Bit 형태의 유전자를 이용해서 연산을 하게 되면, Bit -> Real Number -> Bit 의 변환과정을 거쳐서 적합도평가(Fitness Evaluation)가 이루어집니다. 결과적으로 변환 과정의 해상도(Bit 의 갯수를 얼마나 더 확장시키는지)가 성능에 어느정도 영향을 미치는 꼴이 됩니다. 이 문제에 대해 간단한 예제로 설명하자면 밑의 More 부분을 클릭하시면 됩니다. 만약 10bit 의 유전자를 사용해서 0~1 사이의 숫자를 표현한다고 가정해봅니다. 그렇다면 가장 작은 숫자인 0은 0000000000 (2진수) 으로 표현되겠고, 가장 큰 숫자인 1은 111..