유전 알고리즘(GA) 개요 및 하스스톤 적용 사례 분석
Source
Evernote/Inbox/유전 알고리즘에 대하여 하스스톤 논문을 중심으로.md
Summary
본 문서는 유전 알고리즘(Genetic Algorithm)의 기본 개념과 작동 원리를 설명하고, 이를 하스스톤(Hearthstone) 덱 최적화 연구에 적용한 사례를 분석한다. GA는 진화 과정을 모방하여 최적해를 탐색하는 알고리즘으로, 선택(Selection), 교차(Crossover), 변이(Mutation), 대치(Replacement) 연산으로 구성된다. 하스스톤 연구 사례에서는 30장 덱을 염색체로 표현하고 승률을 적합도(Fitness)로 사용하여 상위 덱을 선택·교차시켰으나, 선택압이 지나치게 높아 유전적 다양성 부족으로 조기 수렴(Early Convergence)될 위험이 있음을 지적한다. 또한 룰렛휠 선택, 교차 방법의 문제 의존성, 변이 연산의 탐색 공간 확장 역할 등 GA 설계 시 고려해야 할 요소들을 논의한다.
Key Points
- 유전 알고리즘은 생물의 진화(선택, 교차, 변이)를 모방한 최적화 탐색 알고리즘이다.
- 하스스톤 적용 사례: 30장 덱을 염색체, 카드 한 장을 유전자로 표현. 마나 비용 기반 정렬 후 교차 수행.
- 적합도(Fitness)는 절대적 수치보다 집단 내 상대적 우수성을 나타내며, 이를 기반으로 선택압을 조절한다.
- 하스스톤 연구의 한계: 상위 4개 덱만 선택하여 교차함으로써 선택압이 매우 높고, 유전적 다양성이 부족해 설익은 해에 수렴할 가능성이 있다.
- 룰렛휠 선택: 적합도 비례 확률로 부모를 선택하며, k 값을 조절하여 선택압을 제어할 수 있다.
- 교차 연산: 문제 정의에 따라 일점/다점 교차 또는 순서 무관 교차(하스스톤 사례)를 선택해야 한다.
- 변이 연산: 낮은 확률로 새로운 유전자를 도입하여 해집단의 다양성을 확보하고 지역 최적해(Local Optima) 탈출을 돕는다.
- 대치 연산: 자식 세대가 부모 세대를 대체하는 방식은 해집단의 다양성과 수렴 속도에 영향을 미친다.