|
|
|
English |
|
|
유전자 알고리즘( Genetic Algorithm, GA ) This article was contributed by Jung, Hyun-chul.
GA란 무엇인가?
- 자연 선택(natural selection) 또는 적자 생존(survival of the fittest)의 원칙에 입각한 알고리즘(search algorithm)이다.
- 개체군(population) 중에서 환경에 대한 적합도(fitness)가 높은 개체(individual) 일수록 재생(reproduction)할 수 있게 되며, 개체군(population)은 환경에 적응을 할 수 있게 된다.
유전 알고리즘이 일반적인 탐색, 최적화 방법과 다른 점은 크게 네 가지 정도가 있다.
1. 매개 변수(parameter)를 직접 이용하지 않고 매개 변수의 집합(parameter set)을 사용하여
탐색한다. 2. 점(point)이 아닌 다점(multi points, : 군(population)) 탐색 방법이다.
3. 부가적인 지식을 사용하지 않고 적합성(fitness function)을 이용한다.
4. 결정론적인 규칙이 아닌 확률적 규칙( crossover or mutation )을 사용하여 수행된다.
유전 연산자
재생산 (reproduction)
적합도에 따라 개체들을 선택하며, 다음 세대(next generation)를 생성하는 과정이다. 다시 말해서, 적합도가 높은 개체일수록 다음 세대에 자식 개체들이 번식할 가능성이 높아진다.
교배 (crossover)
교배는 2개의 개체간에 염색체를 부분적으로 서로 바꿈으로써 새로운 개체를 생성하는 것이다. 아래 그림은 간단한 교배 방법을 표현한 것이다.
돌연변이 (mutation)
임의의 유전자좌(locus)의 특성치(feature value)를 변형시킴으로써 유전 형질의 다양성을 유지하기 위해 사용되는 연산자이다.
예) 환경 ( 또는 적합도 함수)이 f(x) = x^2일 때 GA의 과정을 도식한 한 그림이다.
개체들은 5bit로 구성된 스트링이다.
적합도 함수 ( fitness function )
개체들의 적합도를 평가하는 함수이다. 높은 적합도를 가진 개체는 적절한 해를 찾기도 전에 개체군을 과도 선점하여 해를 찾는 데 필요한 개체군의 다양성을 감소시킨다. 이를 해결하기 위해 적합도를 비례적으로
수정(scaling)하기도 한다.
룰렛 선택법(roulette wheel selection)
개체군의 적합도 합에 대한 개체의 적합도 비율에 따라 roulette wheel을 아래 그림과 같이 구성한 다음 확률적으로 개체를 선택하는 방법이다.
다음 세대에서 재생산될 가능성은 ②→④→①→③순서이다.
출처 : 인공생명 연구팀 Altoz (http://myhome.naver.com/altoz) |
인공생명이란?
|
2004 Copyright HS Games.,pe or Copyleft e-mail : hssoft83@hotmail.com |
|
|
