'f3deceptive'에 해당되는 글 2건

  1. 2007.04.02 F3deceptive 를 SGA 에 적용시킨 소스입니다.
  2. 2007.03.15 7. Deceptive Problem 이란?
안녕하세요.

기본적인 SGA( Simple GA ) - David Edward Goldberg(1989) 소스에

f3deceptive function 을 적용시킨 것입니다.

기본 적인 SGA 에는 Elitism 이 적용되어 있지 않기 때문에 세대별로 꾸준한 성능 증가도 없고,

세대가 증가할수록 항상 좋은 결과가 나타나지는 않습니다.

그리고 위의 f3deceptive Problem 같은 어려운 문제들은 30비트 정도도 풀어내질 못합니다.

하지만!

중요한 것은 GA 알고리즘이 어떤방식으로 구성이 되는지에 대한 기초적인 문제와

Fitness Function 의 구성을 어떻게 하는지에 대한 가장 단순한 문제를 파악하기에는

SGA 만한것이 없습니다.

관심이 있으신분은 소스를 유심히 살펴보시면 되겠습니다.

다음 포스팅 때에는 이보다 더 발전된 형태의 GA 소스에 대해서 살펴보도록 하겠습니다.

물론,

저작권 문제때문에 소스의 주소 및 소개만 있을것입니다.

- P.S - 혹시 특정 부분에 대해서 모르신다면 이메일 혹은 답글 남겨주시면 답변을 드리겠습니다. ^^

Posted by SHHyun

댓글을 달아 주세요

GA 에서 만약 우리가 어떤 새로운 방식의 CX 나 MUT 혹은 기타 MultiPOP 의 이주계획을 만들었다고 가정해봅시다.
 하지만 우리는 이 알고리즘이 이전의 알고리즘에 비해 어느정도의 개선 정도를 갖고 있는지 혹은 어려운 문제를 풀어갈 수 있는 능력이 있는지에 대한 여부를 알 수가 없습니다.
  어디까지나 이런점에서 더 개선된 성능을 보여줄 것이라고 추측을 하는 것입니다.

하지만 우리는 그것의 성능여부를 증명을 해야 겠죠?
그렇기 때문에 여러가지 수학적인 복잡한 문제들이 나를 GA 혹은 기타 알고리즘으로 풀어달라고 기다리고 있습니다.

  GA 에 대해 조금 공부를 하신분들은 De jong 의 Test Problem 에 대해서 들어보셨을 것입니다. 이것은 확장이 가능한 문제로서 문제 자체를 아주 어려운 고급의 문제로 확장이 가능한 문제입니다. 하지만 이 문제는 수학적인 문제이기 때문에 구현이 까다롭습니다.

 제가 여기서 말하려고 하는 것은 Deceptive Problem 입니다. 이 문제들은 구현 자체도 간단하고 확장 또한 아주 쉽습니다. 그리고 알고리즘 자체가 지역극소점에 빠지는 현상을 유도적으로 만들어 냅니다. 하지만 영리한 알고리즘은 그것을 피해가는 경향을 나타나게되고 최종적으로 해답을 만들어 내게 됩니다.

 가장 간단한 f3deceptive 에 대해서 살펴보면 다음과 같습니다.

  3비트를 한 묶음으로 보고 하나의 Problem 단위로 생각을 합니다. 조건식은 다음과 같습니다.
 
  000   = 0.9
  001   = 0.8
  011   = 0
  111   = 1

  이것이 끝입니다..... 뒤에 적힌 수치는 Fitness 의 값입니다.

  만약 0 이 3개 있을경우 0.9 의 Fitness 값을 반환하고, 0 이 2개 있을 경우 0.8, 1개는 0, 그리고 1이 3개가 있을 경우에는 1 의 Fitness 값을 반환하게 됩니다.

  이것은 알고리즘 자체가 해답을 0으로 몰고나아가게 되는 현상을 유도하게 됩니다. 111이 분명 최고의 Fitness 값을 지닌 해답이지만, 0이 많아 질수록 Fitness 값이 좋아지는 현상을 보여주기 때문에 알고리즘이 0을 해답으로 생각하고 모든 비트가 0으로 수렴하게 되는 지역 극소에 빠질 확률이 매우 높아집니다. 알고리즘의 성능이 좋다면 짧은 시간 내에 111 을 찾아내는 것입니다.
 
  사실 이걸 1 Problem 에서 본다면 아주 쉬운 문제지요. 하지만 이 문제는 확장가능한 문제이기에 자주 쓰입니다. 보통 200~300 Problem 정도를 해결하려고 하면 정말 좋은 알고리즘의 경우에 10만 Evaluation(1) 정도에 해결하게 됩니다.

  오늘은 갑자기 벤치마크 문제에 대해 다뤘기 때문에 기존에 정리하지 않았던 말들도 쓰이고 난잡한 면이 조금 보입니다. 하지만 벤치마크 문제에 대해 논한 것은 기본적인 것에 대해서는 전부 정리를 했다고 판단되기 때문입니다.

  다음 번에는 SGA (Simple Genetic Algorithm) 에 f3deceptive 를 구현한 것을 Source 와 함께 정리해 보도록 하겠습니다. 또 다음번 글을 언제 쓸지는 모르겠지만 -_-;;; 최대한 빨리 정리하도록 하겠습니다.


(1) Evaluation -> GA가 몇번이나 Fitness 값을 계산했는지를 기록하는 변수

Posted by SHHyun

댓글을 달아 주세요