Main Content

유전 알고리즘이란?

유전 알고리즘은 생물학적 진화를 유도하는 과정인 자연 선택에 기반한 것으로, 제약 조건이 있는 최적화 문제와 제약 조건이 없는 최적화 문제를 모두 풀 수 있는 방법입니다. 유전 알고리즘은 개별 해의 모집단을 반복적으로 수정합니다. 유전 알고리즘은 매 스텝마다 현재 모집단에서 부모가 될 개체를 선택하고 이 개체를 사용해서 다음 세대의 자식을 생성합니다. 모집단은 여러 세대를 거치면서 최적해를 향해 "진화"합니다. 목적 함수가 불연속적이거나, 미분 불가능하거나, 확률적이거나, 매우 비선형적인 경우처럼 표준적인 최적화 알고리즘에 적합하지 않은 다양한 최적화 문제를 풀어야 할 때 유전 알고리즘을 적용할 수 있습니다. 유전 알고리즘은 일부 성분이 정수 값으로 제한되는 혼합 정수 계획법 문제를 풀 수 있습니다.

다음 플로우 차트에는 주요 알고리즘 단계가 간략하게 설명되어 있습니다. 자세한 내용은 How the Genetic Algorithm Works 항목을 참조하십시오.

Flow chart: create initial population, score and scale population, retain elite, select parents, produce crossover and mutation children, return to score and scale

유전 알고리즘은 매 스텝마다 3개의 주요한 규칙 유형을 사용하여 현재 모집단에서 다음 세대를 만듭니다.

  • 선택 규칙부모라 불리는 개체를 선택하며, 이들 개체는 다음 세대의 모집단에 기여하게 됩니다. 선택은 일반적으로 확률적이며 개체의 점수에 따라 달라질 수 있습니다.

  • 교차 규칙은 두 부모를 결합하여 다음 세대의 자식을 형성합니다.

  • 변이 규칙은 개별 부모에게 무작위 변화를 적용하여 자식을 형성합니다.

An elite child is identical to its parent. A crossover child gets some of each parent. A mutation child comes from one parent, and includes a change.

유전 알고리즘은 고전적인 도함수 기반 최적화 알고리즘과 두 가지 점에서 다릅니다. 다음 표에 이 차이점이 요약되어 있습니다.

고전적 알고리즘유전 알고리즘

각 반복마다 단일 점을 생성합니다. 이러한 점들의 시퀀스가 최적해에 근접합니다.

각 반복마다 점들로 이루어진 모집단을 생성합니다. 모집단의 최적점이 최적해에 근접합니다.

결정적 계산을 통해 시퀀스에서 다음 점을 선택합니다.

난수 생성기를 사용하는 계산을 통해 다음 모집단을 선택합니다.

일반적으로 국소해로 빠르게 수렴합니다.

일반적으로 수렴하기 위해 많은 함수 실행이 필요합니다. 국소 최솟값 또는 전역 최솟값으로 수렴할 수도 있고 수렴하지 않을 수도 있습니다.

관련 항목