유전 알고리즘 간단 소개

유전 알고리즘 한 줄 요약

생물의 진화 과정인 자연 선별과 유전 법칙을 모방한 확률적 최적해 탐색 기법

https://engineering.purdue.edu/gekcogrp/methodology/GENES/

 

 

유전 알고리즘의 목적

특정 상황에서 내가 원하는 값을 찾기 위해 생물학적인 특성을 모방하여 "최적해"를 찾아내는 것이다. 유전자를 만들어서 세대를 만들고, 세대를 교배해서 자식을 만들고, 교배 방법에는 여러 가지가 있고, 돌연변이는 왜 필요하며 등등 생각보다 많이 복잡하다. 이 글은 간단 소개이기 때문에 최적화 알고리즘 중에 유전 알고리즘도 있다는 사실과 pseudo code, 모식도 정도만 짚고 넘어간다.

 

주요 용어

• 유전자(Gene): 각 해의 값(feature)
• 세대(Population): 최적해를 탐색하기 위한 후보해
  • 부모, 자식
• 적합도(Fitness): 후보해가 최적해인지 구하는 함수
  • ex) Find x s.t. f(x) = 10 → fitness(x) = | f(x) - 10 |
• 선택(Selection): 다음 세대에 유전자 정보를 넘길 후보해를 선택
  • Elitism: 적합도가 높은 N개를 선택
  • Roulette Wheel: 각 개체의 적합도를 확률로 사용하여 선택
  • Tournament: 세대를 N개로 균등 분리 후 그 안에서 Elitism/Roulette Wheel 적용하여 선택
• 교차(Crossover): 부모 유전자를 섞어 자식 유전자를 만드는 과정
  • Probabilistic Gene Selection: 확률 모수 θ에 따라 결정
  • Weighted Average: Weight 모수 θ로 계산된 가중 평균
  • θ 결정 방법: 1/2 또는 부모 각각의 적합도를 계산 후 그 비율에 따라 결정
• 변이(Mutation): local 최적해에서 벗어나기 위한 돌연변이 생성
• 대치(Update): 교차, 변이된 유전자를 해집단에 추가하고 기존 해 중 적합도가 좋지 않은 것들을 제외
• 종료 조건: 목표를 달성하거나(허용 범위 이내) 세대를 반복하여도 적합도가 좋아지지 않는 경우

 

Pseudo Code

 

 

모식도

 

 

 

 

 

상세 설명과 코드 구현은 추후 업로드할 예정이다.