Overview
유전 알고리즘 - 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아내는 검색 방법
- 염색체 - 하나의 해 (solution)을 나타냄
- 유전자 - 염색체를 구성하는 요소러써, 하나의 유전 정보를 나타냄
- ex) 염색체가 {A, B, C}라면 이 염색체는 A, B, C라는 3개의 유전자를 가지고 있음
- 자손 -특정 시간 t에 존재했던 염색체들로부터 생성된 염색체를 t에 존재했던 염색체들의 자손이라고 함
- 자손은 이전 세대와 비슷한 유전 정보를 가짐
- 적응도 - 어떠한 염색체가 갖고 있는 고유값으로, 해당 문제에 대해 염색체가 표현하는 해가 얼마나 적합한지를 나타냄
알고리즘 구조
1) 초기 염색체 집단(population) 생성
2) 초기 염색체들에 대한 적응도 계산
3) 현재 염색체들로부터 자손 생성 → 룰렛(selection), 교차(crossover), 돌연변이(mutation)
4) 생성된 자손들의 적응도 계산
5) 새로운 염색체로 대체될 때까지 반복
연산 정의
유전 알고리즘을 문제에 적용하기 위해서는 아래 5가지 연산을 정의하여야 한다.
- 초기 염색체 생성
- 적응도 계산
- 적응도를 기준으로 염색체 선택
- 선택된 염색체들로부터 자손 생성
- 돌연변이
🧬 초기 염색체 생성
초기에는 이전 염색체가 존재하지 않아 선택된 염색체들로부터 자손을 생성할 수 없다.
그렇기 때문에 초기 염색체를 생성할 때는 임의의 값으로 염색체를 생성한다.
🧬 적응도 계산
🧬 적응도를 기준으로 염색체 선택
- Roulette wheel selection - 각 염색체의 적합도에 비례하는 만큼 roulette의 영역을 할당한 다음, roulette을 돌려 화살표가 가리키는 영역의 염색체를 선택
- 엘리트주의 - 이전 세대에서 적합도가 가장 좋은 염색체를 다음 세대에 그대로 보존
🧬 선택된 염색체들로부터 자손 생성
앞에서 선택된 두 개의 부모 염색체들로부터 하나의 자손 염색체를 생성
주로 crossover라는 연산을 사용
🧬 돌연변이
local optimum에 빠지는 문제를 해결하기 위해 새롭게 생성된 염색체에 확률적으로 돌연변이가 발생하도록 하여 개체군의 다양성을 유지한다.
주로 0.1%, 0.005% 등 아주 낮은 확률로 돌연변이가 발생하도록 설정한다.
개선된 유전자 알고리즘
-
인코딩 기법 (Encoding) - 문제가 해가 될 가능성이 있는 것을 유전자로 표현한 것
- Binary Encoding, n-ary encoding
- Gray Encoding
- Permutation Encoding
- Value Encoding
- Variable Length Encoding
-
선택 연산자 (Selection)
- 룰렛 선택
- 토너먼트 선택
- SUS
- Expected-value selection
- Ranking selection
-
교배 연산자 (Crossover)
- single/multi point crossover
- uniform crossover
- arithmetic crossover
- Order-based crossover
- Position-based crossover
-
변이 연산자 (Mutation)
- Scramble Mutation
- Displacement Mutation
- Insertion Mutation
- Inversion Mutation
- Displaced Inversion
🧬 인코딩 기법
이진수 표현 - 0101011000 ...
- 교차시 자름 선 위치가 많아져 추가 변이 효과 발생
k진수 표현 - 5435653
- 의미 있는 스키마 보존 가능성이 높음
Gray Coding - 2진수 표현의 한 변형, 인접한 수는 단 한 비트만 차이가 나도록 하는 코드 체계
순열 표현 (Permutation Encoding) - 순열을 유전자형으로 가짐, 순서 기반형 표현
실수 표현
가변 표현
🧬 선택 연산자
Roulette wheel selection - 각 염색체의 적합도에 비례하는 만큼 룰렛의 영역을 할당한 다음, 룰렛을 돌려 화살표가 가리키는 영역의 염색체를 선택
Elitist preserving selection
토너먼트 선택 - 집단에서 n개의 개체를 임의로 선택하고 이들 중에서 가장 적응도가 높은 개체를 다음 세대의 집단에 포함시킴
SUS - 균등한 간격으로 바늘이 있는 바퀴를 한 번만 돌려서 다음 세대를 결정
Expected-value selection - 적합도에 대한 각 개체의 확률적인 재생 개체수를 구하여 선택
Ranking selection - 적합도의 크기 순서에 따라 순위를 매기고 순위에 따라 확률을 결정
🧬 교배 연산자
single/multi point crossover
uniform crossover
arithmetic crossover (산술적 교차) - 실수 표현일 경우 사용 가능
- 염색체의 각 위치에 대해 두 부모 염색체의 유전자의 평균값을 내어 자식 유전자로 삼는다
Order-based crossover - 순열을 이용한 인코딩인 경우 사용 가능
- 순서 기반, 부모의 임의의 유전자를 선택한 후 그 순서를 다른 쪽 부모에 적용함
Position-based crossover - 순열을 이용한 인코딩인 경우 사용 가능
- 부모 1에 선택된 위치는 자식 1에 그대로 복사됨, 그리고 부모2의 유전자를 중복을 피해가면서 하나씩 자식 1에 옮김
🧬 변이 연산자
Scramble Mutation - 임의의 두 지점을 선택한 후, 그 사이의 값들을 뒤섞는다
Displacement Mutation - 임의의 두 지점을 선택한 후, 그 영역의 유전자들을 임의의 지점으로 이동시킴
Insertion Mutation - 매우 효과적, 단지 하나의 유전자만 위치를 바꿈
Inversion Mutation - 임의의 두 지점을 선택한 후, 그 사이의 유전자들의 순서를 바꿈
Displaced Inversion - 임의의 두 지점을 선택한 후 IVM을 적용한 후 DM을 적용
🧬 Scaling
: 적응도를 가공
- Rank Scaling
- Sigma Scaling
- Boltzmann Scaling
알고리즘 제어 파라미터
-
개체군의 크기 (한 집단에 몇 개의 염색체가 있는지)
- 추천: 20-30, 50-100
-
교배 확률
- 추천: 80-95%
-
돌연변이 확률
- 추천: 0.1-1%
레퍼런스
https://untitledtblog.tistory.com/110
