유전 알고리즘 Genetic Algorithm

유전 알고리즘이란?

존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나다.

 

생물의 진화를 모방하여 만든 알고리즘으로 변이, 교배 등 과 같은 연산이 존재한다. 이러다보니 수학적으로 증명되지 않은 문제를 해결하기 좋은 방법 중 하나가 되기도 한다.

 

유전 알고리즘은 목표 값을 얻기 위해 유전자(자료구조)를 변이(데이터의 변형)하고 교배(근접한 데이터들을 서로 섞어서)를 통해 목표 값에 근접해간다. 즉, 유저 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한 (Simulated evolution) 탐색 알고리즘이라 할 수 있다.

유전 알고리즘

유전 알고리즘은 정해진 공식 또는 예제 코드가 있는것은 아니기 때문에 원리를 이해하고 알고리즘을 작성해야한다.

알고리즘을 살펴보기 전에 용어에 대한 개념을 정리해야 한다.

유전 알고리즘의 용어

• 염색체(Chromosome): 생물학적으로 유전 물질을 담고 있는 하나의 집합을 의미한다. 염색체는 유전자를 포함하고 있다.
• 유전자(Gene): 염색체(chromosome)을 구성하는 하나의 유전 정보를 의미한다. 예를들어 A, B, C를 가지는 염색체가 있을때 A는 유전자(gene)라고 할 수 있다.
• 자손(Offspring): 특정 시간에 존재한 부모 염색체의 성질을 이어받은 다음세대 염색체들을 부모 염색체의 자손 염색체라 할 수 있다. (자손 염색체는 부모 염색체와 비슷한 성질을 가지게 된다)
• 적합도(Fitness): 각각의 염색체가 가지는 고유 값으로, 해당 문제의 해(목표값)에 얼마나 적합한지를 나타낸다.
• 교차율 또는 교배 (Crossover): 2개의 염색체를 조합하여 새로운 염색체를 생성한다. (보통 교차율은 0.7 (70%)로 정의)
• 돌연변이(Mutation): 생물학적 돌연변이와 같은 것으로 특정 확률로 염색체 또는 유전자를 변형한다. 변이 없이 알고리즘을 진행하다보면 여러 세대가 지나고 같은 데이터를 가진 염색체만 남는 경우가 있다. 변이를 통해 새로운 데이터에 대한 가능성을 열어둔다. (보통 변이율은 0.001 (0.1%)로 정의)

알고리즘의 순서

유전 알고리즘은 아래와 같은 순서로 진행된다.

 

1. 초기 염색체 집합 생성
2. 염색체의 적합도(fitness) 연산
3. 연산된 적합도를 이용하여 종료 조건이 만족하는지 확인
   • 종료 조건에 만족한다면, 알고리즘 종료
   • 종료 조건에 만조하지 않으면, 이어서 진행
4. 초기 염색체(부모)로 부터 자손 염색체들을 생성
   • 자손 염색체를 생성하면서 교배(cross) 또는 변이(mutate)의 가능성을 열어둔다.
5. 2번으로 이동하여 반복작업을 수행 ( -> 적합도 연산 -> 종료 조건 판단 -> 자손 염색체 생성 -> )

알고리즘만 봤을때는 간단한 로직이다. 그러나 자손 염색체 생성중에 교배, 변이, 적합도 계산 방법 등 여러가지 변수에 따라 알고리즘의 최적도가 달라지게 된다.

Reference

https://ko.wikipedia.org/wiki/%EC%9C%A0%EC%A0%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

유전 알고리즘 - 위키백과, 우리 모두의 백과사전

https://untitledtblog.tistory.com/110

[최적화/전역 최적화] 유전 알고리즘 (Genetic Algorithm)

https://twinw.tistory.com/1

유전 알고리즘(Genetic Algorithm)(1)-알고리즘 설명

https://m.blog.naver.com/jerrypoiu/221281257452

유전 알고리즘 (Genetic Algorithm)