reset.

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

너무나 오랜만에 글을 포스팅 합니다. 요 근래 너무 바빠서 별다른 정리의 시간을 갖지를 못했네요. 어쨌든 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 시킨다고..

이번에는 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..

몇가지 용어에 대해서 정리해 보도록 하겠습니다. 사실 GA 에서는 크게 2가지의 알고리즘으로 나뉘어 있고 흐름에 의한 알고리즘 자체의 차이가 있을뿐이지 용어에 대해서는 차이가 없습니다. 하지만 GA 를 구현한 프로그램들마다 용어자체에 약간의 차이를 두고 구현되어 있는 경우가 있습니다. 그에 대해서 한번 생각해 보기 위해 용어에 대해 정리해 보는 것입니다. 가장 하위계층의 개체부터 개체의 조합. 그리고 연산자까지 정리해보도록 하겠습니다. 먼저 하나의 개체는 일반적으로 다음과 같이 되어 있습니다. Chromosome - 유전자표현 Fitness - 적합도 OBJ(x) - 유전자표현을 10진수로 변환한것, 다른형태로 표현하기도 합니다. parent1 - parent2 - parent1과 2는 현재의 개체가 C..

오늘은 GA 의 간단한 예제에 대해서 올려봅니다. 우선 하나의 가정을 하죠. 다음과 같은 수식이 있고 그것의 범위를 다음과 같이 할당해 줍니다. 우리는 이 수식의 최대값을 알아내려고 하는 것입니다. y = x^2 - 2*x + 4 x = [ -10 , 10 ] 이렇다고 가정을 해보는 것입니다. 위 문제는 누구라도 간단하게 구할수 있는 문제이지만 그냥 하나의 예로서 들어본 것입니다. 그렇다면 GA 의 흐름에서 이 문제를 어떤 식으로 풀어나가는지 알아보도록 하죠. 우리는 GA 연산에서 쓰일 몇가지 구체적인 변수에 대해 설정을 해 줘야 합니다. 우선 GA 에서 초기화에 몇가지의 개체를 이용할 것인지 설정해 줘야 하고, 몇개의 비트로서 그 개체에 대해 표현을 할지도 결정을 해 줘야 합니다. 어느정도 확률로서 C..

GA 는 하나의 알고리즘으로서 기본적으로 다음과 같은 순서로 동작합니다. (여기서 설명하는 것은 일반적인 알고리즘이고 변형된 알고리즘으로서 Steady-State 알고리즘이 있습니다.) 1. 초기화(Initialize) 유전자 개체를 초기화 합니다. 임의로 지정한 수치 만큼의 유전자를 생성해 내는 것입니다. 2. 평가(Evaluate) 위에 생성된 유전자 개체에 대해 평가를 합니다. 평가의 기준은 사용자가 만드는 것입니다. 생성된 유전자가 문제에 어느정도 적합한 유전자 인지 평가하는 것입니다. 3. 반복(Loop) 여기서 부터는 몇가지 반복작업이 계속 이루어 집니다. 반복이 멈추는 조건은 사용자가 지정한 최대 세대수[1]에 도달하거나 사용자가 지정한 최대조건에 도달 했을 경우 입니다. 멈추지 않을경우 밑..

우선 크게 분류를 나눠보고 제가 어느 분야를 공부하고 있는지를 말씀드리자면 Artificial Intelligence 와 Computational Intelligence 로 구분할 수 있는데 A.I. 는 흔히 알고 있는 인공지능 이고 C.I. 는 계산지능이라고 표현하면 올바를것 같습니다. 저는 C.I. 쪽을 공부하고 있습니다. 이것은 Fuzzy System(FS), Neural Network(NN), Evolutionary Computation(EC) 등 으로 구분할 수 있는데 저는 이중에서도 Evolutionary Computation 쪽을 공부하고 있습니다. 그 중에서도 Genetic Algorithm 과 Genetic Programming 에 대해서 공부를 하고 있습니다. 유전적인 이론(예: 다윈의..