reset.

지난번에 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..

Webots 을 이용해 보신 분들이라면 아시겠지만 Webots 내부에서 제공되는 에디터를 이용해 프로그램을 작성하는게 여간 불편한게 아닙니다. 메뉴얼에 이미 있는 내용이지만, 한번 다시 정리해 보겠습니다. 순서대로만 따라서 하면 아주 쉽게 이용하실 수 있습니다. 1. 새로운 Project 생성 위의 그림에서 보이듯이 New 를 눌러서 새로운 Project 를 생성해 줍니다. 2. Project 생성(세부) Win32 Console Application 을 선택해 주신 후, Project name 에 이용하실 Controller의 이름을 넣어줍니다. 3. Project Settings 그리고 Project 가 생성된 후 Project -> Settings 메뉴를 통해 설정을 해 줍니다. 저 메뉴를 누르게되..

초기의 진화연산(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..

오늘은 간단하게 Genetic Programming(GP) 에 대해서 정리해볼까 합니다. GP 라는건 GA 에서 파생되었다고도 할 수 있는 또다른 Evolutionary Computation 의 한 종류 입니다. Genetic Algorithm 에서는 유전자 형태를 Binary 또는 Real Type 의 조합을 이용했습니다. 하지만 Genetic Programming 에서는 유전자 형태를 Tree 구조를 이용합니다. 그림으로 표현해보면 다음과 같습니다. 그림1. GA 와 GP 의 표현의 차이점 GA 와 GP 는 보시는 것과 같이 표현에 차이를 두고 있습니다. CX나 MUT 역시 존재하지만 표현상의 차이로 인해 조금 다른 방식으로 이루어 집니다. CX 방식의 차이에 대해서 그림으로 표현해보면 다음과 같습니..

안녕하세요. 오랜만에 포스팅 입니다. GA 를 이용하고 연구하고자 할 때, 가장 큰 걸림돌이 되는것은 어떤 엔진을 선택하느냐 입니다. 각기 다른 여러가지 엔진이 있고 그 특징과 이용, 활용면에서 워낙 광범위하기에 어떤 엔진을 선택하는지 매우 고민되지 않을수가 없죠. 이에 몇가지 유명한 엔진에 대해 알아보겠습니다. 사실 여러 그룹이나 연구실에서 이용하는 GA 는 기본 SGA의 틀에서 크게 벗어나지 않는 자체의 GA 엔진이 대부분입니다. 왜냐하면 광범위한 목적으로 개발된 GA 에서는 원하지 않는 기능도 많고 우선 알고리즘 자체의 구성부터 살펴봐야하기 때문입니다. 일단은 유명한 GA 엔진들에 대해서 살펴보고 그 특징과 기능면에서 이야기를 해보도록 하겠습니다. 1. Open Beagle(http://beagle..

안녕하세요. 기본적인 SGA( Simple GA ) - David Edward Goldberg(1989) 소스에 f3deceptive function 을 적용시킨 것입니다. 기본 적인 SGA 에는 Elitism 이 적용되어 있지 않기 때문에 세대별로 꾸준한 성능 증가도 없고, 세대가 증가할수록 항상 좋은 결과가 나타나지는 않습니다. 그리고 위의 f3deceptive Problem 같은 어려운 문제들은 30비트 정도도 풀어내질 못합니다. 하지만! 중요한 것은 GA 알고리즘이 어떤방식으로 구성이 되는지에 대한 기초적인 문제와 Fitness Function 의 구성을 어떻게 하는지에 대한 가장 단순한 문제를 파악하기에는 SGA 만한것이 없습니다. 관심이 있으신분은 소스를 유심히 살펴보시면 되겠습니다. 다음 포..

GA 에서 만약 우리가 어떤 새로운 방식의 CX 나 MUT 혹은 기타 MultiPOP 의 이주계획을 만들었다고 가정해봅시다. 하지만 우리는 이 알고리즘이 이전의 알고리즘에 비해 어느정도의 개선 정도를 갖고 있는지 혹은 어려운 문제를 풀어갈 수 있는 능력이 있는지에 대한 여부를 알 수가 없습니다. 어디까지나 이런점에서 더 개선된 성능을 보여줄 것이라고 추측을 하는 것입니다. 하지만 우리는 그것의 성능여부를 증명을 해야 겠죠? 그렇기 때문에 여러가지 수학적인 복잡한 문제들이 나를 GA 혹은 기타 알고리즘으로 풀어달라고 기다리고 있습니다. GA 에 대해 조금 공부를 하신분들은 De jong 의 Test Problem 에 대해서 들어보셨을 것입니다. 이것은 확장이 가능한 문제로서 문제 자체를 아주 어려운 고급의..