유전 알고리즘: 두 판 사이의 차이

{{제목 변경|토론=알고리즘}}{{통용 표기 사용}}

 

* 유전 알고리즘은 '''유전자 알고리즘'''이라고도 한다. 그러나 유전 알고리즘은 유전 현상을 문제 해결이나 시뮬레이션에 이용하는 것일 뿐, 유전자의 이용에 초점을 두지 않는다. 따라서 {{lang|en|genetic algorithm}}을 유전자 알고리즘으로 번역한 것은 오역이라고 볼 수 있다.<ref>문병로, 8쪽</ref>

 

유전 알고리즘을 어떤 문제에 적용하기 위해서는 [[유전자 표기]]와 [[적합도 함수]]를 정의해야한다.d 일반 생명체의 특성이 [[유전체]]의 집합인 [[유전자]]로 나타나는 것과 같이, 유전자 표기는 문제의 특성을 숫자나 문자열과 같은 값의 집합으로 표시하게 된다. 적합도 함수는 특정 해가 얼마나 적합한지 나타내는 함수이다. 일반 생명체가 유전자에 따라 특정 환경이나 [[질병]]에서 살아 남을 수 있는 확률이 존재하는 것과 같이, 적합도 함수는 주어진 해가 다음 세대를 생산할 수 있을지, 혹은 세대를 남기지 못하고 없어질지를 정하게 된다.

 

다음 세대를 형성하기 위해, 이 세대의 개체중 2개의 유전자를 선택한다. 이때 선택은 적합도를 기준으로 확률적선택([[룰렛 알고리즘]]이 자주 쓰인다)이다. 따라서 위의 예에서 (8,0,9)는 (9,9,8)에 비해 훨씬 높은 선택 기회를 가진다. 선택된 2개의 유전자의 유전체는 랜덤한 위치에서 교환되어 새로운 세대가 형성된다. 예로 (8,0,9), (9,9,8) 이 선택되었고 교배위치가 2번째 자리로 무작위로 결정되었다면 다음 세대의 개체는 (8,9,8) ,(9,0,9)로 된다.

 

* [[개미 집단 최적화]] (ACO): 먹이를 찾아다니는 개미 집단의 행동에서 영감을 얻은 기법이다.

* [[담금질 기법]] (SA): 해를 하나만 사용한다는 점이 가장 큰 차이점이다.

* [[진화 프로그래밍]]: 변이를 주로 사용하는 기법으로 진화 전략과 유사하다. 초기에는 해를 유한 오토마타로 나타내었고 지금도 고정된 표현을 쓰지 않는 것이 특징이다.

 

 

 

== 주석 ==

[[simple:Genetic algorithm]]

[[sk:Genetický algoritmus]]

[[sv:Genetisk programmering#Genetisk algoritm]]

[[th:ขั้นตอนวิธีเชิงพันธุกรรม]]