진화 알고리즘(EA)은 생물학적 진화의 메커니즘(예: 번식, 돌연변이, 재조합, 선택)에서 영감을 얻은 모집단 기반 메타휴리스틱 최적화 기법의 한 부류이다. 이들은 정확하거나 만족스러운 방법이 알려지지 않은 어려운 최적화 문제에 대한 근사 해를 찾는 데 사용된다. 진화 연산 및 계산 지능의 일부로서, EA는 후보 해의 모집단을 대상으로 작동하며, 적합도 함수를 통해 품질을 평가하고 진화 연산자를 반복적으로 적용하여 세대를 거듭하며 모집단을 개선한다. 이들의 주요 장점은 기본 적합도 지형에 대해 거의 가정을 하지 않아 다양한 문제를 다룰 수 있다는 점이지만, 계산 복잡성은 종종 적합도 평가 비용에서 비롯된다.
일반 알고리즘
일반적인 진화 알고리즘은 다음과 같은 반복 과정을 따른다:
- 초기 모집단(첫 번째 세대)의 개체들을 무작위로 생성한다.
- 모집단 내 각 개체의 적합도를 평가한다.
- 목표에 도달했는지 확인하고, 도달했다면 종료한다.
- 가능하면 적합도가 높은 개체를 부모로 선택한다.
- 교차(번식 모방)와 선택적 돌연변이를 통해 자손을 생성한다.
- 자손에게 돌연변이 연산을 적용한다.
- 가능하면 적합도가 낮은 개체를 대체 대상으로 선택하여 다음 세대를 구성한다.
- 2단계로 돌아가 종료 조건까지 반복한다.
이 일반적인 프레임워크는 각각 특정 표현과 연산자를 가진 다양한 EA 유형에 맞게 조정된다.
진화 알고리즘의 유형
유전적 표현과 구현 세부 사항이 다른 여러 EA 변형이 존재한다:
- 유전 알고리즘(GA): 가장 널리 사용되는 유형으로, 해를 숫자(종종 이진수) 문자열로 표현한다. 재조합과 돌연변이 같은 연산자가 적용된다. GA는 최적화 문제에 널리 사용된다.
- 유전 프로그래밍(GP): 해가 컴퓨터 프로그램이며, 적합도는 계산 문제를 해결하는 능력에 따라 결정된다. 변형으로는 데카르트 유전 프로그래밍, 유전자 발현 프로그래밍, 문법 진화, 선형 유전 프로그래밍, 다중 표현 프로그래밍이 있다.
- 진화 전략(ES): 1960년대와 1970년대에 잉고 레헨베르크, 한스-파울 슈베펠과 동료들에 의해 개발되었으며, 수치 및 공학 최적화에 중점을 둔다. 실수 값 벡터를 대상으로 돌연변이, 재조합, 결정적 선택을 사용한다. 특징적인 점은 돌연변이 분포의 자기 적응이며, (1+1)-ES, (μ, λ)-ES, (μ+λ)-ES와 같은 형태가 있다. 이후 개발로는 공분산 행렬 적응(CMA-ES)과 자연 진화 전략이 있다.
- 차분 진화(DE): 벡터 차이에 기반하며, 주로 수치 최적화에 적합하다.
- 진화적 다중 목적 최적화: 여러 상충되는 목표를 가진 문제로 EA를 확장하며, 파레토 전선에서 절충 해를 근사하는 모집단을 유지한다.
- 공진화 알고리즘: 해가 다른 해와의 상호 작용을 기반으로 평가되며, 경쟁하거나 협력할 수 있다. 동적 또는 경쟁적 적합도 지형에 유용하다.
- 신경 진화: 게놈이 인공 신경망을 나타내며, 구조와 연결 가중치를 직접 또는 간접적으로 인코딩한다.
- 학습 분류자 시스템(LCS): 해가 분류자(규칙) 집합이다. 미시간-LCS는 개별 분류자를 진화시키는 반면, 피츠버그-LCS는 분류자 집합의 모집단을 진화시킨다. 적합도는 강화 학습 또는 지도 학습을 통해 결정된다.
- 품질-다양성(QD) 알고리즘: 고품질과 다양한 해를 동시에 목표로 하며, 문제 공간 전반에 걸쳐 다양한 해를 탐색한다.
이론적 배경
무료 점심 정리
최적화의 무료 점심 정리에 따르면, 가능한 모든 최적화 문제를 고려할 때 모든 최적화 전략은 동일하게 효과적이다. 이는 어떤 진화 알고리즘도 모든 문제에서 다른 알고리즘보다 근본적으로 우월하지 않다는 것을 의미한다. 그러나 실제로는 문제 집합이 제한되며, 적절한 표현과 연산자를 선택하는 등 문제 특정 지식을 활용하여 EA를 개선할 수 있다.
계산 복잡성
대부분의 실제 응용에서 EA의 계산 복잡성은 주로 적합도 함수 평가 비용 때문에 중요한 요소이다. 적합도 근사 기법은 이 문제를 완화할 수 있다. 흥미롭게도 단순한 EA가 복잡한 문제를 해결할 수 있는 경우가 많으며, 이는 알고리즘 복잡성과 문제 복잡성 사이에 직접적인 연관성이 없음을 시사한다.
응용 및 한계
진화 알고리즘은 공학 설계, 일정 계획, 기계 학습(예: 신경 진화), 다중 목적 최적화 등 다양한 분야에 적용된다. 탐색 공간이 크고 비선형이거나 잘 이해되지 않을 때 특히 유용하다. 그러나 성능은 매개변수 조정과 문제 표현에 따라 달라진다. EA의 기법은 생물학적 미시 진화 및 세포 과정 모델링에도 사용되지만, 한계가 있다.