진화 알고리즘

진화 알고리즘(Evolutionary algorithm, EA)은 전산 지능(CI)에서 일반적인 인구 기반 메타휴리스틱 최적화 알고리즘인 진화 계산의 부분집합이다. EA는 번식, 돌연변이, 재조합, 선택 등 생물학적 진화에서 영감을 받은 메커니즘을 사용한다. 최적화 문제에 대한 후보 솔루션은 모집단 내 개인의 역할을 하며 적합도 함수는 솔루션의 품질을 결정한다(손실 함수 참조). 인구의 진화는 위의 연산자를 반복적으로 적용한 후에 발생한다.

진화 알고리즘은 기본 적합성 환경에 대해 어떤 가정도 하지 않기 때문에 모든 유형의 문제에 대해 근사적인 솔루션을 수행하는 경우가 많다. 생물학적 진화의 모델링에 적용되는 진화 알고리즘의 기술은 일반적으로 소진화 과정의 탐구와 세포 과정에 기초한 계획 모델로 제한된다. 대부분의 실제 EA 분야에서 계산 복잡성은 금지 요소이다. 실제로 이러한 계산 복잡성은 적합성 함수 평가로 인해 발생한다. 이러한 어려움을 극복하기 위한 솔루션 중 하나가 적합성 근사법이다. 그러나 겉으로는 단순해 보이는 EA는 종종 복잡한 문제를 해결할 수 있다. 따라서 알고리즘 복잡성과 문제 복잡성 사이에는 직접적인 연관성이 없을 수 있다.

구현

다음은 일반적인 단일 목표 유전자 알고리즘의 예이다.

1단계: 초기 개인 모집단을 무작위로 생성한다. (첫 세대)

2단계: 종료될 때까지 다음 재생성 단계를 반복한다.

1. 모집단 내 각 개인의 적합성을 평가한다(시간 제한, 충분한 적합성 달성 등).
2. 재생산에 가장 적합한 개체를 선택한다. (부모)
3. 교배와 돌연변이 연산을 통해 새로운 개체를 번식시켜 자손을 낳는다.
4. 인구 중 가장 적합하지 않은 개인을 새로운 개인으로 교체한다.