reset.

이전에 간단하게 만들어두었던 SGA의 Fitness Evaluation 동작만을 CUDA 에서 실행하는 코드 난 지금까지 이걸 올렸다고 생각하고 있었는데, 다시보니 그게 아니었다. 이건 뭐 XX도 아니고...;; (*) 일단 코드는 최적화는 전혀 되어 있지 않은 상태이며, 오히려 기본 GA보다도 Evaluation 성능이 떨어질 수 있다. 컴파일 환경은 쓰고싶은대로 아무거나 써도 이상이 없을 코드이며, 이전엔 Visual Studio 2008 에서 작업했었다. CUDA에 대해서 가장 기본적인 코드라고 생각해도 될 코드이기때문에 혹시라도 이런 종류의 알고리즘을 다뤄보고 싶으신분은 살펴보면 좋을 것 같다.

GAlib 가 가볍고 잘 만든 Genetic Algorithm Library 인데 개발 중단된지도 오래되었고, 현재 최신버전의 컴파일러에서 컴파일은 되지만 링크가 되지 않는 문제가 있다. http://www.hyperdrifter.com/software/tutorial/compiling_galib_using_microsoft_visual_cpp.html 위의 링크에서 말하는대로 컴파일하면 링크이상없이 잘 수행되는 것을 확인할 수 있고, 첨부된 파일은 귀찮고 단지 library 파일만 쓰고싶은 사람을 위한 것이다.

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

오늘은 실수최적화 문제에서 이용되는 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..

안녕하세요. 오랜만에 포스팅 입니다. 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 시킨다고..