유전 알고리즘(Genetic Algorithm)이란?
진화의 원리를 문제 해결에 이용한 알고리즘이다. 컴퓨터 과학, 물리학, 생물학, 화학, 경제학 등 다양한 분야에 적용된다.
주요 용어
– Chromosome(염색체) : 하나의 해
– Population(해집단) : 염색체의 집합
– Selection(선택) : 교차를 위해 해집단에서 임의의 해 선택
– Crossover(교차) : 두 개의 부모해로부터 자식해 생성
– Mutation(변이) : 해를 임의로 변형
최적화 기법
최적화(Optimization)란?
목적 함수 달성을 위한 가장 좋은 해를 찾는 것이다.
* 유전 알고리즘을 설계할 때, 최적해의 정확한 값이나 패턴을 알지 못하기 때문에 목표 적합도를 추정해야한다. 이 과정에서 절대로 나올 수 없는 목표 적합도를 설정하게 되는 경우가 있는데, 이러한 경우에는 알고리즘이 끝나지 않는다. 그래서 매우 복잡한 문제를 풀어야 할 때는 목표 적합도뿐만 아니라, 최대 반복 횟수도 같이 설정해주는 것이 일반적이다.
(출처 : http://twinw.tistory.com/1 [흰고래의꿈])
유전 알고리즘은 어떤 미지의 함수 Y = f(x)를 최적화하는 해 x를 찾기 위해, 진화를 모방한(Simulated evolution) 탐색 알고리즘이라고 말할 수 있다.
각 chromosome을 한 번에 뿌려서 해를 찾기 시작하기 때문에, local optima에 빠지지 않고, 전역해를 찾을 가능성이 높아진다.
유전 알고리즘의 구조
: 개체가 환경에 적응하기 위해 선택적으로 번성하는 모습이다.
1. 임의로 생성된 N개 염색체로 구성된 모집단 A가 있다.
2. 이 모집단 A에서 적합도가 높은 염색체들을 선택한다.
3. 선택된 염색체들을 교차하여 새로운 염색체를 생성한다.
4. 탐색 공간을 넓히고, local search mechanism을 위해 변이과정을 실행한다. (교차는 변이에 비해 상대적으로 변화가 크다.)
5. 기존 염색체 중에서 열등한 것과 새로운 염색체를 교체한다.
6. 새로운 모집단 B가 형성된다.
7. 목표 적합도에 만족되는 염색체가 나타나면, 종료한다.
적용한 예를 들어보자.
선택(Selection)
교차에 쓰이기 위한 두 개의 부모해를 고르기 위해 연산한다.
우수한 해가 선택될 확률이 높아야 한다.
염색체 선택의 방법에는 룰렛휠 선택, 토너먼트 선택, 순위기반 선택 등이 있다.
1) 룰렛휠 선택 방법 : 각 해의 품질을 평가한 후 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 K배가 되도록 조절하는 방법이다. (일반적으로 k는 3~4 정도의 값을 적용한다.)
2) 토너먼트 선택 방법 : 두 개의 염색체를 임의로 선택하여 [0,1) 범위의 난수를 발생시킨 후, 이것이 t보다 작으면 두 염색체 중 품질이 좋은 것을 선택하고, 그렇지 않으면 품질이 나쁜 것을 선택하는 방법이다. t값이 높을수록 선택압이 높아진다.
3) 순위기반 선택 방법 : 룰렛휠 방법처럼 k값을 조정하는 동시에, 해들의 적합도 분포를 조절하기 위해, 해집단 내의 해들을 품질 순위로 순위를 매긴 후 가장 좋은 해부터 일차 함수적으로 적합도를 배정하는 방법이다.
교차(Crossover)
교차에는 일점교차, 다점교차, 균등교차 등 다양한 방법이 있다.
균등교차 : 일점교차나 다점교차와 같은 지름선이 아닌 임계확률을 활용하여 교차하는 방법이다.
임계확률 P를 설정한 후 s1,s2 각각의 유전자 위치에 난수를 발생시킨 후 P 이상이면 s1 유전자를, P이하이면 s2 유전자를 복사한다.
변이(Mutation)
염색체가 얼만큼 변화되도록 할 것인가
부모해에 없는 속성을 도입하여 탐색 공간을 넓히기 위해 수행한다.
각각의 유전자에 [0,1) 범위의 난수를 생성하여 임계값 미만의 수가 나오면 임의로 변형시킨다.
<출처 및 참고>
CHAN Coffee.com 
댓글 남기기