Genetic Algorithm

See SchemaTheory.

생명체가 긍정적인 방향으로 진화를 하는 이유는 우수한 유전자가 살아 남아서 자식을 남길 확률이 높기 때문이다. 그러나, 만약 단세포 생물과 같은 성이 하나인 생물처럼 자기 자신을 복제함으로써 2세를 만드는 생물이라면 Local Optima, 즉 여러 골짜기 중 가장 낮은 지점인지 어쩐지도 모르는 골짜기를 골라 거기에 안주하게 될 가능성이 많다. see SimulatedAnnealing.

따라서 부모, 즉 2개의 서로 다른 유전자를 선택하여 그것들을 기준으로 자식 유전자를 만드는 방법을 유전자 알고리즘에서 채택한 것이다.

--PuzzletChung의 생각.

GA(혹은 넓게 보아 EC)에는 기본적인 가정이 있다. "좋은 해(개체, 유전자)와 또 다른 좋은 해 각각의 성질을 잘 버무려 얻은 해는 역시 좋거나 혹은 더 좋다." (여기에 하나 덧붙이자면 랜덤하게 얻은 해보다 이런 과정을 통해 얻은 해가 평균적으로 더 좋아야 한다)

여기에 GA의 맹점과 핵심이 공존한다. 어떻게 좋은 해를 판별할지를 알아야 하고, "좋은 성질"이 최소한 유지되거나 혹은 더 좋아질 수 있는 교배법이 있어야 하며, 현실적인 세대 수(기간) 내에 만족할 만한 정도의 "좋은 해"가 나올 수 있어야 한다.

--김창준

• 장점
  
  • NeuralNetwork 과는 달리, encoding을 잘 하면 결과를 어느정도 분석할 수 있다.
    
  • 의미있는 초기값을 설정할 수 있다. (예를 들면 복잡한 function에서 min/max값을 찾는 문제를 유전자 알고리즘을 사용해 푼다면, initial value에 후보가 되는 값들을 포함시킬 수 있다.
    
• 단점
  
  • 이론적인 배경(SchemaTheory)이 약하다.
    
  • 엄청나게 많은 개체수와 세대를 필요로 하는 경우가 대부분이다. (즉, 계산량과 기억용량이 많이 필요하다.)
    
  • [ISBN-155860510X]에서는 GeneticAlgorithm의 Crossover와 Biological crossover의 차이점을 다음과 같이 든다.
    
    1. Biological crossover는 같은 종끼리만 일어난다. 그래서 나이팅게일은 동족만 알아들을 수 있는 나이팅게일만의 울음 소리로 운다.
       
    2. Biological crossover에서는 같은 특성의 유전자는 같은 특성의 유전자끼리만 교차된다. 즉 머리색을 결정하는 유전자와 키를 결정하는 유전자가 서로 섞이지 않는다.
       
  이 책에서 저자는 묻는다. Microsoft Word와 Word Perfect의 코드를 crossover시켜서 더 나은 워드를 만들 수 있느냐고.
  

• Holland의 모든 책. 특히 그의 Hidden Order는 일반인이 보기에도 좋다.
  
• Goldberg의 모든 책. 특히 그의 Genetic Algorithms는 기본 교과서에 해당한다.
  
• Zbigniew Michalewicz의 Genetic Algorithms + Data Structures = Evolution Programs
  

John R. Koza의 모든 책. Genetic Programming 관련.

comp.ai.genetic FAQ에서는 Goldberg, Koza, Michalewicz와 함께, Davis를 "기본/개론 교과서"로 소개한다.

see also http://www.geneticprogramming.com/ga/books.html

지원의 짧은 생각으로는 GeneticAlgorithm은 그냥 heuristic random search정도로 볼 수 있을 듯 하다.

GeneticAlgorithm을 사용할 때에는,

• mutation/crossover 확률과
  
• elitism의 사용여부
  
• chromosome encoding 방식 등
  

이 상당히 중요한 변수가 된다. encoding을 엉망으로 해놓고, 성능이 별로 좋지 않다고 불평하는 사람이 많다. encoding 방식만 잘 바꿔도 열 배 이상 성능 향상이 있었다. 또 mutation/crossover의 발생 확률도 중요하다. --김창준

StarCraft같은 세계에서 몇개의 인공생명이 돌아다닌다. 그러다 그 인공생명들이 서로 만나면 서로 이런바 GeneticAlgorithm적인 섹스를 해서 객체를 양성하거나 또는 서로서로의 변신을 꾀한다.(음, 이방식으로 전략게임 만들어도 히트를 칠꺼같은 느낌이 드네요) -- rururara

SeeAlso:

• ArtificialIntelligence~인공생명
  
• GeneticAlgorithm
  

컴퓨터분류