Genetic Algorithm (GA; 유전 알고리즘)

- 유전 알고리즘이란 자연계에 있어서 생물의 유전(Genetics)과 진화(Evolution)의 메카니즘을 공학적으로 모델화하는 것에 의해 생물이 갖는 환경에서의 적응 능력을 취급하는 것

- 1975년에 John Holland가 저서 "Adaptation on Natural and Artificial System'에 처음 소개한 자연도태의 원리를 기초로 한 최적화(Optimization) 방법

- 유전 알고리즘

- 자연계 생물의 유전과 진화의 메카니즘을 공학적으로 모델화 하는 일종의 확률 탐색 방법으로, 생물의 유전자 모양으로 탐색을 진행하며, 탐색(search), 최적화(optimization), 기계학습(machine learning)의 도구로서 많이 사용됨

- 근접한 최적 해를 찾기 쉽고 병렬적 탐색이 가능하며 지역 최적해(local maximum)에 빠지지 않음.

- 그러나 만약 탐색이 해의 사이로 진행되는 경우 결과를 찾지 못할 가능성이 있으며, 해를 찾는다 하더라도 찾는 과정을 알 수 없음.

- 적합한 분야

TSP, 고차함수의 근사최적해 문제, 신경망 최적화, 기타 NP-Hard 문제 중 일부

- 적합하지 않은 분야

1:N Shortest path 문제, Sorting, Finding

- 유전 알고리즘의 응용 예들

함수 근사, 신경망 최적화, 퍼지 시스템 최적화, 엘리베이터 그룹 스케줄링, TSP, 네트웍 배치, 그래프 분할, 회로 라우팅

- 기본 용어

염색체(Gene)

문제의 해를 나타냄

자연계의 염색체가 가변적인 것과 달리, 대부분의 경우 고정 길이를 가진다.

염색체 표현 방식 : 이진 표현, K진수 표현, 그레이 코드, 실수 표현, 트리 표현

평가 함수(Evaluation function)

염색체가 얼마나 Goal과 가까운지를 평가함

유전자의 품질을 결정하여 우수 유전자를 선별

적합 함수(Fitness function)

유전자가 유효한 해인지를 판단하는 함수

평가 함수가 적합 함수를 겸하는 경우도 있음

연산자

선택 연산(Selection)

품질 비례 룰렛휠 선택, 토너먼트 선택

교차 연산(Cross-Over)

1점 교차, 다점 교차, 균등 교차, 싸이클 교차, 순서 교차, PMX(Partially matched Crossover), 산술적 교차, 휴리스틱 교차, 간선 재결합

변이 연산(Mutation)

부모 해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산

지역 최적해에 빠지는 것을 완화시켜 준다.

대치 연산(reproduction; 재생산)

품질이 나쁜 유전자를 품질이 좋은 유전자로 바꾸는 연산

유전자의 수(해집단)의 수를 일정하게 유지하기 위한 연산

일반적으로 가장 우수한 해는 대치되지 않는다.(엘리트주의; Elitism)

- 정리에 도움을 준 김현식 군에게 감사드립니다.

블로그 내의 관련 글

2009/07/01 - [Study/Artificial Intelligence] - 유전 알고리즘(Genetic Algorithm)

2010/09/30 - [Study/Artificial Intelligence] - CSP vs BFS vs GA for N-Queen