GA ( genetic algorithm )
- 다윈의 유전 법칙에 기반함.
- 자연 선택 or 적자 생존의 원칙에 입각한 알고리즘
- 진화의 결과를 염색체 형태로 저장한다. ( DNA : C.G.A.T )
- 개체군(population)중에서 환경에 대한 적합도(fitness)가 높은 개체일수록 재생산할 수 있게 되며, 개체군은 환경에 적응을 할 수 있게 된다. ( 적자 생존 )
- 개체군을 유지하면서, 세대를 거쳐서 점진적으로 성능이 향상되는 방식이다.
- 주요 개념:
- individual ( 개체 ) : 하나의 가능한 해를 의미하며, 유전자를 가지고 있음.
- chromosome ( 유전자 ) : 개체의 특성을 나타내는 유전 정보
- generation ( 세대 ) : 개체들이 변이와 교배를 거쳐서 진화하는 한번의 과정
- fitness ( 적합도 ) : 각 개체의 성능을 평가하는 함수
- selection ( 자연 선택 )
- crossover ( 교차 )
- mutation ( 돌연변이 )
- 장점
- 복잡한 연산( 미적분,지수함수 등 )을 사용하지 않움.
- 평가 함수가 불연속이더라도 적용 가능
- 유전 조작으로 개체간 상호협력적으로 병렬 탐색이 이루어지므로, 단순 병렬 탐색보다 좋은 해를 발견하기 쉬움.
- 단점
- 유전 연산자 설정을 위한 파라미터의 수가 많다.
- 유전자 알고리즘의 일반적인 해법이 없으며, 특히 문제를 유전자로 표현(coding)하는 방법은 설계자의 능력에 좌우됨.
- GA 적용시에 고려해야 할 것들
- 유전자를 어떻게 구성할 것인가? ==> 알고리즘 성공의 열쇠
- 적합도를 어떻게 정의할 것인가? ==> 최적화
- popultation을 얼마로 할 것인가? ==> 속도와 메모리 문제
- 종료 조건을 어떻게 줄 것인가? ==> 시간문제
Selection
- 적합도가 높은 개체가 다음 세대로 전달될 확률을 높힘
- 룰렛 휠 선택 ( roulette wheel selection )
fitness의 값을 이용해서, 백분율이 클수록 차지하는 범위가 넓음
Crossover
- 두 개체의 유전정보를 교환하여 새로운 개체를 생성
- 즉, 염색체상에서 임의의 위치를 저장해서 나뉜 부분의 위치를 서로 바꿈.
- ( crossover가 되지 않는다면, 부모가 그대로 복제됨. crossover는 0.7일때 좋은 결과를 냄. )
- ex) 10개의 chromosome 존재시 7개를 교차시키면 crossover=0.7이다...
crossover의 시각화
Mutation
- 유전자(chromosome)의 일부를 임의로 변화시켜서 다양성을 유시시킴
- 자연계에서는 드물게 발생하며, 바람직하지 않은 결과를 만드는 경우가 많다.
- 지역 최적점에 같히지 않도록 보장하는 역할
- ( 돌연변이 발생 확률은 낮아야하며, 그렇다고 돌연변이가 없다면 독특한 값이 안나옴 ==> 돌연변이는 대부분 도태됨 )
mutation
유전자 알고리즘의 동작 과정
일반적으로 유전자 알고리즘이 동작하는 과정
- 1. 초기 개체군 생성 ( initialization )
- popultation을 무작위로 생성하거나 특정한 초기 조건아래에서 생성한다.
- 일반적으로 이진 문자열 or 실수 벡터 or 순열 등으로 표현
- 2. popultation안에 존재하는 individual에 대해서 Fitness를 평가한다.
- 3. Selection
- fitness가 높은 individual이 높은 확률로 다음 generation에 선택된다.
- 4. crossover
- 두개의 individual의 chromosome을 조합하여, 새로운 individual(개채 , 자식 )을 생성
- 방법들...
- 1. single-point crossover ( 단일 지점 교차 ) : 특정 지점에서 절반씩 교환
- 2. multi-point crossover ( 다중 지점 교차 ) : 여러 지점에서 교환
- 3. unifirm crossover ( 균등 교차 ) : 각 비트마다 교차 여부를 랜덤하게 결정
- 5. mutation
- individual의 일부 chromosome을 확률적으로 변경해서 다양성을 유지
- 방법들...
- 비트 반전 ( bit flip mutation )
- 균등 변이 ( uniform mutation )
- 정규 분포 변이 ( gaussian mutation )
- 6. 종료 조건 검사
- 특정한 조건이 충족된다면 종료한다. ( 아래에서 다시 설명 )
상대방의 숫자 알아내기에 대한 GA의 예시
GA의 종료 조건
- 전형적인 종료 조건
- 만족할 만한 해를 찾을때까지 계속 해를 구한다.
대신에, 더 좋은 염색체가 나타나기 전까지 몇 세대 동안은 해집단의 fitness가 정체될수도 있음
- 적응적 종료 조건
- 정해진 세대수가 되면 GA알고리즘을 종료하고, 해집단에서 가장 좋은 염색체를 찾는다.
만약에 만족스러운 해를 찾지 못한다면 GA알고리즘을 다시 시작.
