7.125 유전 알고리즘과 진화 전략

1. 진화 연산의 개요

진화 연산(evolutionary computation)은 생물학적 진화의 원리(자연 선택, 유전적 변이, 재조합)를 모사하여 최적화 문제를 해결하는 메타휴리스틱 방법의 총칭이다. 모집단(population) 기반의 탐색으로 다수의 후보 해를 동시에 유지하고 진화시키며, 도함수 정보를 요구하지 않으므로 비매끄러운 함수, 이산 변수, 혼합 변수 문제에 적용 가능하다.

2. 유전 알고리즘(Genetic Algorithm, GA)

2.1 기본 구조

홀랜드(Holland, 1975)에 의해 제안된 유전 알고리즘은 다음의 주요 연산으로 구성된다.

초기화: $N$ 개의 개체(individual)로 구성된 초기 모집단을 무작위로 생성한다.
적합도 평가: 각 개체의 적합도(fitness)를 목적 함수값으로 평가한다.
선택(Selection): 적합도가 높은 개체를 부모로 선택한다.
교차(Crossover): 두 부모의 유전 정보를 재조합하여 자손을 생성한다.
돌연변이(Mutation): 자손의 유전 정보를 무작위로 변이시킨다.
대체(Replacement): 새로운 모집단을 구성한다.
2~6단계를 종료 조건이 만족될 때까지 반복한다.

2.2 부호화(Encoding)

결정 변수를 유전자형(genotype)으로 표현하는 방식이다.

이진 부호화: 각 변수를 이진 문자열로 표현한다. 이산 문제에 자연스럽지만, 연속 변수의 정밀도가 문자열 길이에 의존한다.

실수 부호화: 연속 변수를 직접 실수 벡터로 표현한다. 로봇 공학의 연속 파라미터 최적화에 적합하다.

2.3 선택 연산

룰렛 휠 선택: 적합도에 비례하는 확률로 개체를 선택한다.

토너먼트 선택: 모집단에서 $k$ 개의 개체를 무작위로 추출하고, 그 중 가장 적합한 개체를 선택한다. 선택 압력의 조절이 용이하다.

2.4 교차 연산 (실수 부호화)

산술 교차: $\mathbf{x}_{child} = \alpha \mathbf{x}_{p1} + (1-\alpha)\mathbf{x}_{p2}$ , $\alpha \in [0, 1]$ .

시뮬레이티드 이진 교차(SBX): 이진 교차의 분포를 실수 공간에서 모사한다.

2.5 돌연변이 연산 (실수 부호화)

가우시안 돌연변이: $\mathbf{x}' = \mathbf{x} + \sigma \boldsymbol{\epsilon}$ , $\boldsymbol{\epsilon} \sim \mathcal{N}(\mathbf{0}, \mathbf{I})$ .

다항식 돌연변이: 유계 분포에 기반한 변이로, 변수의 범위를 존중한다.

3. 진화 전략(Evolution Strategy, ES)

3.1 $(\mu, \lambda)$ -ES와 $(\mu + \lambda)$ -ES

레헨베르크(Rechenberg, 1973)와 슈벨펠(Schwefel, 1977)에 의해 개발된 진화 전략은 연속 최적화에 특화되어 있다.

$(\mu, \lambda)$ -ES: $\mu$ 개의 부모로부터 $\lambda$ 개의 자손( $\lambda > \mu$ )을 생성하고, 자손 중 최선의 $\mu$ 개를 다음 세대의 부모로 선택한다. 부모는 생존하지 않는다.

$(\mu + \lambda)$ -ES: 부모와 자손을 합산한 $\mu + \lambda$ 개 중 최선의 $\mu$ 개를 선택한다. 최선의 개체가 항상 보존되는 엘리트주의(elitism)이다.

3.2 자기 적응적 돌연변이

ES의 핵심 특성은 돌연변이 매개변수(스텝 크기 $\sigma$ )를 함께 진화시키는 자기 적응(self-adaptation)이다.

$\sigma' = \sigma \cdot \exp(\tau \cdot \mathcal{N}(0, 1))$

$\mathbf{x}' = \mathbf{x} + \sigma' \cdot \mathcal{N}(\mathbf{0}, \mathbf{I})$

여기서 $\tau \propto 1/\sqrt{n}$ 은 학습률이다. 이를 통해 탐색의 스케일이 문제의 지형에 적응적으로 조절된다.

3.3 CMA-ES

공분산 행렬 적응 진화 전략(Covariance Matrix Adaptation Evolution Strategy, CMA-ES)은 현대 진화 전략의 대표적 알고리즘이다. 다변량 정규 분포 $\mathcal{N}(\mathbf{m}, \sigma^2\mathbf{C})$ 에서 자손을 샘플링하고, 평균 $\mathbf{m}$ , 스텝 크기 $\sigma$ , 공분산 행렬 $\mathbf{C}$ 를 적응적으로 갱신한다.

CMA-ES의 공분산 행렬 적응은 자연 그래디언트(natural gradient)에 대응하며, 회전 불변성(rotation invariance)과 스케일 불변성을 갖는다. 도함수를 사용하지 않는 방법 중 가장 효율적인 것으로 알려져 있으며, 도함수가 불가능한 $n \leq 100$ 정도의 연속 최적화 문제에서 표준적으로 사용된다.

4. 다목적 진화 알고리즘

유전 알고리즘은 다목적 최적화(multi-objective optimization)에 자연스럽게 확장된다. NSGA-II(Non-dominated Sorting Genetic Algorithm II)는 비지배 정렬(non-dominated sorting)과 혼잡도 거리(crowding distance)를 이용하여 파레토 최적 전선의 다양한 해를 동시에 탐색한다.

5. 로봇 공학에서의 응용

로봇 구조 최적화: 링크 길이, 관절 유형, 관절 배치 등의 이산적 설계 변수가 포함된 로봇 기구학적 구조의 최적화에 유전 알고리즘이 적용된다.

보행 패턴 최적화: 보행 로봇의 걸음 매개변수(보폭, 보행 주기, 관절 궤적 매개변수)를 CMA-ES나 유전 알고리즘으로 최적화한다. 실물 로봇에서의 도함수 계산이 불가능한 경우 특히 유용하다.

신경 진화(Neuroevolution): 로봇 제어를 위한 신경망의 구조와 가중치를 진화 알고리즘으로 동시에 최적화하는 방법이다. NEAT(NeuroEvolution of Augmenting Topologies)가 대표적이다.

6. 참고 문헌

Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
Hansen, N. (2016). “The CMA Evolution Strategy: A Tutorial.” arXiv:1604.00772.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.” IEEE Transactions on Evolutionary Computation, 6(2), 182–197.
Eiben, A. E., & Smith, J. E. (2015). Introduction to Evolutionary Computing (2nd ed.). Springer.

version: 1.0