쉽게 배우는 유전 알고리즘 - 정리

유전 알고리즘의 기본

1. 용어

---

 - 임의의 해 : 염색체

 - 염색체의 집단 : 해집단

 - 염색체의 각 인자 : 유전자

 - 유전자형(제노타입) : 유전자 조합

 - 표현형(페노타입) : 유전자형과 관계 되는 형질

 - 염색체 : 유전자형 : 제노타입

 - 해의 성격, 품질 : 표현형

2. 유전 알고리즘의 전형적인 구조

---

n개의 초기 염색체 생성;

repeat {

for i = 1 to k { 

두 염색체 p1, p2 선택;

offspringi = crossover(p1, p2);

offspringi = mutation(offspringi); /* offspring ; 자식 */

}

} until(정지 조건 만족);

남은 염색체 중 최상의 염색체를 return;

3. 표현

---

 이진수, 16진수, 실수, 그레이 코딩 등등 여러 방식으로 표현이 가능하다.

4. 스키마

---

 임의의 염색체는 많은 패턴을 가지고 있다.

 이런 패턴을 스키마라 한다.

 예로, 101 이란 염색체는 1**, *0*, **1, 10*, *01, 101 과 같은 부분패턴을 가지게 된다.

 * 는 무관기호(don't-care symbol)이라 하고, 무관기호가 아닌것을 특정 기호(specific symbol)이라한다.

5. 선택

---

 임의의 해를 2개 이상 선택하는 것을 의미한다. 

 선택된 해는 교차, 변이, 대치에 사용된다. 

6. 교차

---

 두 해의 특징을 결합하여 새로운 해를 만들어낸다.

 예: 일점교차

1번과 2번의 해를 선택한 값은 아래와 같다.

1번 해	a	b	c	d	e	f	g	h	i	j
2번 해	k	l	m	n	o	p	q	r	s	t
새로운 해	a	b	c	d	e	f	q	r	s	t

1번해와 2번해를 나란히 둔 뒤, 자름선(위의 파란색 선)을 임의로 자른다. 

그런 뒤, 자름선을 기준으로 앞에 것을 1번해의 값으로

자름선의 뒤에 것을 2번해의 값으로 하면

새로운 해가 생겨난다.

자름선을 여러번 사용하여 교차했을 경우, 다점교차라한다.

교차점이 많아질수록 패턴이 늘어나고, 해의 품질도 낮아질수 있다.

 

 일점교차, 다점교차, 균등교차, 싸이클 교차, PMX 등의 연산 방법이 있다.

7. 변이

---

 변이는 선택 된 해의 값 중 일부를 난수로 변경하는 것을 의미한다. 즉, 돌연변이가 된다.

 a b c d e f g h i j 중 h의 값을 x라는 임의 값으로 바꾸면 아래와 같은 돌연변이가 된다.

 a b c d e f g x i j

 교차가 지닌 속성이 모두 부모해로 부터 물려받았다면 변이는 해 스스로가 변이한 것이다.

8. 대치

---

 해를 대치하는 것으로, 반드시 교차, 변이연산과 연관되어 결정되어야 한다.

 교차/변이 연산 쌍이 부모해를 많이 변형시키면, 즉 perturbation이 강하면 다소 수렴성이 

강한 대치연산을 사용해도 무리가 없다. 또한 변형력이 아주 약하면 수렴성보다는 해집단의 다양성을

지속시킬 수 있는지에 무게를 두고 대치 연상을 택하는 것이 좋다.