유전 알고리즘
유전 알고리즘은 후보 해의 집단에 선택·교차·돌연변이를 적용해 탐색 공간을 반복적으로 조사한다 진화적 메타휴리스틱 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.
| 분류 | 알고리즘 · 진화적 메타휴리스틱 |
|---|---|
| 주요 목적 | 후보 해의 집단에 선택·교차·돌연변이를 적용해 탐색 공간을 반복적으로 조사한다 |
| 핵심 방법 | 적합도 함수로 개체를 평가하고 선택 연산으로 부모를 뽑아 교차·돌연변이로 다음 세대를 생성한다 |
| 복잡도 | 세대 수 × 개체 수 × 적합도 평가 비용에 의존하며 전역 최적 보장은 일반적으로 없다 |
| 적용 조건 | 해의 인코딩, 적합도 함수, 연산자의 유효성을 정의해야 한다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
유전 알고리즘은 후보 해의 집단에 선택·교차·돌연변이를 적용해 탐색 공간을 반복적으로 조사한다 진화적 메타휴리스틱 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 적합도 함수로 개체를 평가하고 선택 연산으로 부모를 뽑아 교차·돌연변이로 다음 세대를 생성한다. 엘리트 보존, 개체 다양성, 종료 기준과 제약 처리 방식을 설계해야 한다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 세대 수 × 개체 수 × 적합도 평가 비용에 의존하며 전역 최적 보장은 일반적으로 없다 실제 구현에는 해의 인코딩, 적합도 함수, 연산자의 유효성을 정의해야 한다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 비선형 최적화·스케줄링·설계 탐색에 사용한다. 생물학적 진화에서 영감을 받았지만 알고리즘의 선택 규칙은 별도의 수치적 절차다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]