유전자 알고리즘(Genetic Algorithm)

I. 유전자 알고리즘의 개요

가. 유전자 알고리즘의 정의

   - 개체 집단을 만들고, 그 집단의 적합도를 평가하며, 유전 연산자를 써서 새로운 집단을 만들고 이 과정을 여러 번 반복함으로써 그 문제를 해결하는 알고리즘

---

II. 유전자 알고리즘의 구성요소

구성요소	주요내용
유전자 및 염색체	- 유전자는 0이나 1로 나타냄, 염색체는 유전자 여러 개로 이루어짐
인코딩	- 염색체를 1과 0으로 된 문자열로 나타냄
평가함수	- 유전 알고리즘은 재생산을 할 때 측정한 개별 염색체의 적합도 값을 사용 - 재생산이 일어나면 교차 연산자는 두 염색체의 일부를 교환하고, 변이 연산자는 염색체에서 임의로 선택한 몇몇 자리에 있는 유전자의 값을 바꿈 - 그 결과, 재생산이 여러 번 연속해서 일어난 후에는 적합도가 낮은 염색체는 소멸되고, 살아남은 염색체가 점차 해집단을 지배
연산자	교차 연산자	- 교차 연산자는 부모 염색체 둘이 ‘끊어지는’ 지점 을 임의로 선택하고 염색체에서 이 지점보다 뒤쪽에 있는 부분을 교환 - 이 결과 새로운 자식 염색체 두 개가 만들어짐
	변이	- 변이는 유전자가 바뀌는 것을 나타냄 - 변이는 탐색 알고리즘이 지역 최적점에 갇히지 않도록 보장하는 역할
	선택	- 적합도에 따라 다음 단계에서 교차라는 개체의 생존 분포 결정 - 적합도의 분포를 근거로 적합도가 높음 개체일수록 많은 자손을 남김 - 개체 선택법은 적합도 비례 선택법, 룰렛 선택법, 기대 값 선택법 - 순위 선택법, 토너먼트 선택법 등이 있음
	기타 연산자	- 서로 인접한 부분의 순서를 역전하여 재배열하는 역위, 염색체 일부분을 다른 염색체의 부분으로 대치하는 치환, 염색체상의 코드 일부분을 중복, 추가, 제거 등이 존재