유전 알고리즘(Genetic Algorithms, GA)은 진화적 접근법에 기반한 AI 기법으로, 주어진 문제에 대한 최적의 해를 찾기 위해 개체군의 진화 과정을 모방합니다. 이 알고리즘은 1975년 John Henry Holland에 의해 제안되었습니다.
유전 알고리즘은 다음과 같은 아이디어에 기반합니다:
- 문제의 유효한 해를 **유전자(genes)**로 표현할 수 있다.
- **교차(Crossover)**를 통해 두 가지 해를 결합하여 새로운 유효한 해를 얻을 수 있다.
- **선택(Selection)**은 특정 **적합도 함수(fitness function)**를 사용하여 더 나은 해를 선택하는 데 사용된다.
- **돌연변이(Mutations)**는 최적화 과정을 불안정하게 만들어 지역 최솟값에서 벗어날 수 있도록 한다.
유전 알고리즘을 구현하려면 다음이 필요합니다:
- 유전자(genes) g∈Γ를 사용하여 문제의 해를 코딩하는 방법을 찾아야 합니다.
- 유전자 집합 Γ에서 적합도 함수 fit: Γ→R를 정의해야 합니다. 함수 값이 작을수록 더 나은 해를 나타냅니다.
- 두 유전자를 결합하여 새로운 유효한 해를 생성하는 교차 메커니즘 crossover: Γ²→Γ를 정의해야 합니다.
- 돌연변이 메커니즘 mutate: Γ→Γ를 정의해야 합니다.
많은 경우, 교차와 돌연변이는 숫자 시퀀스나 비트 벡터와 같은 유전자를 조작하는 간단한 알고리즘으로 구현됩니다.
유전 알고리즘의 구체적인 구현은 상황에 따라 다를 수 있지만, 전체적인 구조는 다음과 같습니다:
- 초기 개체군 G⊆Γ를 선택합니다.
- 이 단계에서 수행할 작업(교차 또는 돌연변이)을 무작위로 선택합니다.
- 교차:
- 두 유전자 g₁, g₂ ∈ G를 무작위로 선택합니다.
- 교차를 계산하여 g=crossover(g₁, g₂)를 얻습니다.
- fit(g)<fit(g₁) 또는 fit(g)<fit(g₂)인 경우, 해당 유전자를 g로 대체합니다.
- 돌연변이 - 무작위로 유전자 g∈G를 선택하고 mutate(g)로 대체합니다.
- 적합도 값이 충분히 작아지거나, 단계 수 제한에 도달할 때까지 2단계부터 반복합니다.
유전 알고리즘으로 주로 해결하는 작업은 다음과 같습니다:
- 일정 최적화
- 최적의 포장 문제
- 최적의 절단 문제
- 완전 탐색 속도 향상
다음 노트북에서 학습을 이어가세요:
이 노트북에서 유전 알고리즘을 사용하는 두 가지 예제를 확인하세요:
- 보물의 공정한 분배
- 8퀸 문제
유전 알고리즘은 물류 및 탐색 문제를 포함한 다양한 문제를 해결하는 데 사용됩니다. 이 분야는 심리학과 컴퓨터 과학의 주제를 융합한 연구에서 영감을 받았습니다.
"유전 알고리즘은 구현이 간단하지만, 그 동작을 이해하기는 어렵다." 출처
유전 알고리즘의 구현 예(예: 스도쿠 퍼즐 해결)를 찾아보고, 이를 스케치나 흐름도로 설명해 보세요.
이 훌륭한 영상을 시청하여 유전 알고리즘으로 학습된 신경망이 슈퍼 마리오를 플레이하는 방법에 대해 알아보세요. 다음 섹션에서 이와 같은 게임 학습에 대해 더 배울 것입니다.
목표는 디오판토스 방정식(정수 해를 가지는 방정식)을 푸는 것입니다. 예를 들어, 방정식 a+2b+3c+4d=30을 고려해 보세요. 이 방정식을 만족하는 정수 해를 찾아야 합니다.
이 과제는 이 게시물에서 영감을 받았습니다.
힌트:
- 해는 [0;30] 구간에 있다고 가정할 수 있습니다.
- 유전자로 해 값의 리스트를 사용하는 것을 고려해 보세요.
Diophantine.ipynb를 시작점으로 사용하세요.