(이론) 유전 알고리즘 (Genetic algorithm)

정의

• 생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아내는 알고리즘
• 생물의 진화 과정, 즉 자연 선택과 유전 법칙 등을 모방한 알고리즘
• 수학적으로 명확하게 정의되지 않은 문제에도 적용할 수 있기 때문에 매우 유용하게 이용된다.
• 유전 알고리즘은 특정한 문제를 풀기 위한 알고리즘이라기 보다는 최적화 문제를 풀기 위한 방법론에 가깝다.
• 유전 알고리즘은 선택, 교차, 변이, 대치 연산 등으로 구성

[이미지 출처 : https://m.blog.naver.com/jerrypoiu/221281257452]

방법

[이미지 출처 : https://m.blog.naver.com/jerrypoiu/221281257452]

 

한계점

• 현실 세계에 존재하는 문제를 유전자형으로 바꾸는 과정이 간단하지 않다. 
• 개체 수, 선택 방법, 교차의 결정, 돌연변이 비율, 최적화 함수 등 결정해 줘야 하는 변수가 많고, 그에 따른 결과 차이가 크다.[
  
  

 

활용 

• 개미 집단 최적화 (ACO): 먹이를 찾아다니는 개미 집단의 행동에서 영감을 얻은 기법이다.
• 유전 프로그래밍: 교차와 변이를 사용하는 등 유전 알고리즘과 많이 닮은 기법이다. 
• 진화 연산: 생물의 진화에서 영감을 얻은 기법의 총칭이다. 현재는 진화 연산에 속하는 기법들의 차이가 점점 없어지고 있다.
• 진화 프로그래밍: 변이를 주로 사용하는 기법으로 진화 전략과 유사하다. 
• 미미틱 알고리즘: 지역 탐색 기법과 유전 알고리즘을 결합하여 빠른 시간 안에 좋은 해를 찾아내려고 하는 방법이다.
  
  [출처 : 위키백과]