reset.

오랜만에 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 에 대해서 들어보셨을 것입니다. 이것은 확장이 가능한 문제로서 문제 자체를 아주 어려운 고급의..

크게 두가지 방법이 있습니다. Physics Controller 를 이용한 접근 혹은 Supervisor Controller 를 이용한 접근 이렇게 두가지 방법이 있는데 제가 테스트 해본 바로는 신뢰성이 Physics Controller 가 더 높아보입니다. Aibo ERS-7 의 Trajectory 를 구성하고 로봇이 실제 움직이는 모양이 Trajectory 와 어느정도 비슷한지를 평가하기 위해 Supervisor Controller 의 supervisor_field_get 함수를 이용해서 값을 추출해 봤는데 좌표값이 제대로 매칭이 안되는 것으로 판단됩니다. 로봇의 루트 노드를 타겟으로 잡고 값을 추출 할 때는 매칭이 되지만 하나의 일부 노드를 타겟으로 잡고 값을 추출 할 때는 제대로 매칭이되지 않는 ..

너무나 오랜만에 글을 포스팅 합니다. 요 근래 너무 바빠서 별다른 정리의 시간을 갖지를 못했네요. 어쨌든 Selection 연산자에 대해서 알아보겠습니다. 우선 Selection 연산자는 유전자 선택에 쓰이는 연산자 입니다. 밑에 설명한 Mutation 과 Crossover 를 해주기 위해서는 그 대상이 필요하겠죠? 그 대상을 골라주는 역할을 해주는 것이 바로 이 Selection 연산자입니다. Selection 연산자도 꽤 많은 종류가 있는데 몇가지에 대해서만 알아 보겠습니다. 알아볼 Selection 연산자로는 1. 룰렛휠(Roulette Wheel Selection) 2. 균등선택(Stochastic Universal Sampling Method) 3. 랭크선택(Rank-based Selection..

오랜만에 글을 포스팅 합니다. 이래저래 하고 있는건 많고 정리할 시간이 부족하다보니 이제야 포스팅합니다. 일반적으로 쓰이는 MUT 연산자는 다음과 같은 2가지가 있습니다. 1. Single MUT 2. Multi MUT 하나는 하나의 Bit 를 MUT 시키는 것이고 다른 하나는 여러개의 Bit 를 대상으로 MUT를 수행합니다. 1. Single MUT 이것은 하나의 Bit 만을 MUT 시킵니다. 아주 간단하게 알아 볼 수 있습니다. (1) 선택연산자를 통하여 선택이 이루어진다. (2) 선택된 개체의 한 bit 를 선택하여 MUT 시킨다. 예를 보면 간단하게 변화를 알아볼 수 있습니다. 만약 다음과 같은 유전자가 있다면 0 0 0 0 0 0 1 0 이것이 선택되어 7번째 bit 를 Mutation 시킨다고..

Webots 시뮬레이터를 혹시라도 이용하시는 분이 있으시다면 참고해 볼만한 내용 입니다. 제작자인 Olivier 씨에게 문의를 해 보았는데 x,y,z 좌표계의 1 이라는 수치가 의미하는 길이가 실세계의 1 미터 라고 하는 군요 그리고 Webots 에서 구현되어 있는 모든 로봇들의 좌표계에 대한 것인데 좌표들은 다 부모 노드에 종속되어 있는 상대적 좌표계 라고 하네요 즉 가장 외부로 나와 있는 것은 dWorld 객체에 종속되어 있는 좌표계를 이용하는 것이고 로봇의 각각의 부분은 그것이 부착되어 있는 부모 노드의 좌표를 원점으로 종속되어 있다고 하는군요. 혹시 웹봇을 이용하시는분이 계신다면 저한테 연락좀 주시겠습니까? 서로 자료에 대해 공유도 하고 토론도 하게요 ^^

이번에는 GA 의 핵심 연산자인 Crossover 연산자 입니다. GA 의 연산자 중에서 가장 많은 연산을 수행하고 그만큼 중요도도 높은 Crossover 연산자 입니다. 수많은 방식의 연산자 들이 존재하지만 오늘은 밑에 있는 것에 대해서만 알아보겠습니다. 1. Onepoint crossover(Single) 2. Twopoint crossover(Multi) 3. Uniform crossover 위의 1,2 번 연산자는 대표적인 기본 연산자 이고, 거의 모든 bit 연산에서 쓰입니다. 3번은 거의 쓰이지 않지만 어떤 문제에는 쓰이기도 합니다. 그래서 소개하는 것입니다. 어쨌든 하나하나 알아보도록 하죠. 1. One-point Crossover(Single Crossover) Onepoint Crosso..