유전 알고리즘

최적설계 수치해석 시뮬레이션 마지막 수정: 2026-07-17 04:34:19

1. 개요[편집]

유전 알고리즘 Genetic Algorithm
약칭	GA
계열	진화 연산 / 메타휴리스틱
제창	John Holland (1975)
대표 구현	NSGA-II, SPEA2, DEAP, pymoo

미분이 안 되면? 자연에게 물어보면 된다. 다만 자연은 답을 40억 년 만에 준다.

유전 알고리즘(Genetic Algorithm, GA)은 생물의 진화 — 선택, 교차, 돌연변이 — 를 모방해 해 후보들의 집단(population)을 세대에 걸쳐 개선하는 확률적 전역 최적화 기법이다. 1975년 John Holland가 체계화했고, 그의 제자 David Goldberg가 1989년 저서로 공학 현장에 퍼뜨렸다.

GA의 존재 이유는 명확하다. 목적함수가 미분 불가능하거나, 불연속이거나, 설계 변수가 정수·범주형이거나, 국소 최적해가 지뢰밭처럼 깔려 있을 때 뉴턴-랩슨법이나 준-뉴턴법 같은 기울기 기반 방법은 시작조차 못 한다. GA는 목적함수를 블랙박스로 취급하고 “넣으면 점수가 나온다”는 것만 요구한다. CFD 솔버든 FEM 솔버든 엑셀 시트든 상관하지 않는다.

대가는 비싸다. 평가 횟수로 값을 치른다.¹

2. 알고리즘[편집]

초기화 — 설계 공간에 개체 $N$ 개를 뿌린다. 무작위보다 라틴 하이퍼큐브 같은 실험계획법 기법이 대개 낫다.
평가 — 각 개체의 적합도(fitness)를 계산한다. 여기서 시뮬레이션이 돈다. 시간의 99%가 여기다.
선택 — 적합도가 높은 개체가 부모가 될 확률을 높게 준다.
교차 — 부모 둘의 유전자를 섞어 자식을 만든다.
돌연변이 — 자식 유전자를 낮은 확률로 무작위 교란한다.
교체 — 새 세대를 구성하고 2로 돌아간다. 수렴하거나 예산이 떨어질 때까지.

2.1. 선택[편집]

룰렛 휠 — 적합도에 비례하는 확률. 교과서 단골이지만 실무에서는 잘 안 쓴다. 적합도 스케일에 민감해서, 초반에 튀는 슈퍼 개체 하나가 집단을 통째로 점령해버린다(조기 수렴).
토너먼트 선택 — 무작위로 $k$ 개(보통 2~3) 뽑아 그중 최고를 부모로. 적합도의 순위만 보므로 스케일에 무관하고 구현이 세 줄이다. 사실상 국룰.
엘리티즘 — 최고 개체 몇을 무조건 다음 세대에 복사. 이게 없으면 애써 찾은 최고해가 교차로 박살나는 걸 지켜봐야 한다. 대부분 켜둔다.

2.2. 교차와 돌연변이[편집]

이진 인코딩 시절에는 비트열을 자르고 붙이는 1점/2점 교차가 표준이었지만, 공학 설계 변수는 대개 실수다. 실수 인코딩에서는 SBX(Simulated Binary Crossover) 와 다항식 돌연변이(polynomial mutation) 조합이 사실상 기본값이다. SBX는 자식 $c_1, c_2$ 를 부모 $p_1, p_2$ 주위에 확률적으로 배치하되, 분포 지수 $\eta_c$ 로 “부모에 얼마나 붙일지”를 조절한다.

c_{1,2} = \tfrac{1}{2}\left[(1 \mp \beta)p_1 + (1 \pm \beta)p_2\right]

$\beta$ 는 난수 $u \sim U(0,1)$ 로부터 $\eta_c$ 가 지배하는 분포에서 뽑는다. $\eta_c$ 가 크면 자식이 부모에 딱 붙고(탐색 축소), 작으면 멀리 퍼진다.

돌연변이율 $p_m$ 은 관례적으로 변수 개수 $n$ 에 대해 $1/n$ 근처로 둔다. 즉 자식 하나당 평균 한 변수가 흔들린다. 이 값이 0이면 집단은 초기 유전자 풀 안에 갇히고, 너무 크면 그냥 무작위 탐색이 된다.

2.3. 탐색과 활용[편집]

GA 튜닝의 전부는 exploration vs exploitation 저울질이다. 선택압을 올리면(큰 토너먼트, 강한 엘리티즘) 빨리 수렴하지만 국소해에 처박힐 위험이 크고, 낮추면 다양성은 유지되지만 세대가 늘어난다. 담금질 모사가 온도 스케줄 하나로 이 저울을 조절하는 것과 달리, GA는 노브가 여럿이라 감이 필요하다.

3. 다목적 최적화[편집]

GA가 진짜 밥값을 하는 영역. 실제 설계는 “가볍게, 그런데 단단하게”처럼 상충 목적을 동시에 요구한다. 단일 최적해는 존재하지 않고, 파레토 프론트(어떤 목적도 다른 목적을 희생하지 않고는 개선할 수 없는 해들의 집합)를 구하는 것이 목표가 된다.

집단 기반이라는 GA의 성질이 여기서 결정적이다 — 한 번 돌리면 프론트 전체가 한꺼번에 나온다. 기울기 기반 방법으로 같은 걸 하려면 가중합을 바꿔가며 수십 번 돌려야 하고, 그마저 프론트가 비볼록이면 중간 구간을 통째로 놓친다.

NSGA-II(Deb 등, 2002)가 이 바닥의 표준이다. 두 가지 장치로 굴러간다.

비지배 정렬(non-dominated sorting) — 집단을 지배 관계에 따라 프론트 계층으로 분류하고, 앞쪽 프론트를 우선한다.
혼잡 거리(crowding distance) — 같은 프론트 안에서는 이웃과 멀리 떨어진 개체를 우대. 해가 프론트 한구석에 뭉치는 걸 막는다.

목적이 4개 이상으로 늘면 거의 모든 개체가 서로 비지배가 되어 정렬이 무력해진다. 이 영역을 따로 many-objective라 부르고 NSGA-III, MOEA/D 같은 후속 알고리즘이 나와 있다.

4. 시뮬레이션과의 결합[편집]

공학에서 GA는 거의 항상 해석 솔버 위에 얹힌다. 형상 최적화의 형상 파라미터, 복합재 해석의 적층 각도(값이 0/±45/90°로 이산적이라 GA 궁합이 최상이다), 난류 모델링 계수 보정, 배관 라우팅, 트러스 부재 선택 등.

여기서 평가 비용이 모든 것을 지배한다. 개체 100, 세대 200이면 해석 2만 번이다. CFD 한 케이스가 30분이면 단순 계산으로 1년이 넘는다. 그래서 실무는 예외 없이 다음 중 하나 이상을 쓴다.

병렬 평가 — 한 세대 안의 개체들은 서로 완전히 독립이다. 부끄러울 만큼 병렬(embarrassingly parallel)이라, 코어 수만큼 그대로 시간이 줄어든다. 병렬 컴퓨팅의 이상적 사례.
대리 모델 결합 — 진짜 솔버 대신 크리깅/RBF 근사에 GA를 돌리고, 유망한 후보만 실제 해석으로 검증해 대리 모델을 갱신한다. 평가 예산을 한두 자릿수 줄일 수 있어 사실상 필수.
축소차수모델 — 물리 기반 저차 모델로 초기 세대를 걸러낸다.
제약 처리 — 페널티 함수가 가장 흔하지만 계수 튜닝이 짜증난다. NSGA-II 계열은 제약 위반량으로 지배 관계를 정의하는 방식(constraint-domination)을 써서 계수 없이 처리한다.

5. 오해와 한계[편집]

GA는 전역 최적해를 보장하지 않는다. 무한 시간이면 확률 1로 찾는다는 정리는 있지만, 무한 시간을 가진 사람은 없다. 실무에서 GA는 “괜찮은 해를 합리적 시간에 찾는” 도구다.
공짜 점심은 없다. Wolpert와 Macready의 NFL 정리에 따르면, 모든 가능한 문제에 대해 평균하면 어떤 최적화 알고리즘도 무작위 탐색보다 낫지 않다.² GA가 잘 통하는 건 실제 공학 문제가 구조를 갖고 있기 때문이지, GA가 만능이어서가 아니다.
변수가 매끄럽고 미분 가능하면 GA를 쓰지 마라. 민감도 해석으로 기울기를 구할 수 있다면 기울기 기반이 수십~수백 배 빠르다. 위상 최적화가 변수 수십만 개를 다루면서도 GA를 안 쓰는 이유가 바로 이것이다. 수반법으로 기울기를 한 방에 뽑기 때문.
재현성 — 난수 시드를 안 박아두면 같은 결과가 다시 안 나온다. 보고서에 시드를 안 적었다가 재현 요청에 식은땀 흘리는 게 이 바닥의 통과의례.

6. 현업에서의 현실[편집]

“일단 GA 돌려놓고 퇴근”은 실존하는 워크플로다. 아침에 와서 보면 클러스터가 죽어 있거나 30세대에서 수렴이 멈춰 있다.
목적함수 설계가 알고리즘 선택보다 100배 중요하다. 잘못 정의된 목적함수에 GA를 붙이면, GA는 성실하게 그 정의의 허점을 파고들어 물리적으로 말도 안 되는 해를 들고 온다.³
파레토 프론트 그림 한 장은 의사결정 회의에서 슬라이드 열 장을 이긴다. GA를 쓰는 진짜 이유가 여기 있다는 말도 있다.

7. 관련 문서[편집]

Holland의 원래 관심은 최적화가 아니라 적응 시스템의 이론이었다. “스키마 정리(schema theorem)“로 GA가 왜 작동하는지 설명하려 했는데, 이 이론은 이후 여러 반례와 비판을 받았고 지금은 GA의 작동 원리에 대한 완전한 설명으로 받아들여지지 않는다. 즉 잘 되는 건 모두가 아는데 왜 잘 되는지는 아직도 논쟁 중이라는, 딥러닝과 비슷한 처지다. ↩
Wolpert & Macready (1997), “No Free Lunch Theorems for Optimization”. 이 정리를 근거로 “그러니 알고리즘 고민은 무의미하다”고 말하는 사람이 종종 있는데, 정리의 전제는 “모든 가능한 목적함수에 균등한 확률”이라는 현실에 없는 조건이다. 논문 인용은 정확하게, 해석은 조심스럽게. ↩
진화 알고리즘이 명세의 허점을 악용한 사례는 학계에 수집되어 있을 만큼 흔하다(Lehman 등의 “Surprising Creativity of Digital Evolution” 논문이 유명하다). 응력 제약을 안 걸면 재료를 지우다 못해 공중부양 부재를 내놓고, 진동 물리엔진 버그를 찾아내 추력 없이 날아가는 로봇을 만들어낸다. GA는 당신이 시킨 걸 한다. 당신이 원한 걸 하지 않는다. ↩