[최적화/AI] 유전 알고리즘(Genetic Algorithm)이란? 선택·교차·돌연변이로 이해하는 핵심 원리

안녕하세요.
“기억하고자 하는 모든 것”을 담아내는 “리멤버미” 입니다.

 

최적화 문제를 다루다 보면, 해를 한 번에 정확히 계산해서 찾기 어려운 경우가 많습니다.
특히 변수 조합이 너무 많거나, 함수가 매끄럽지 않거나, 미분이 어렵거나, 정수 조건과 제약조건이 함께 얽혀 있으면 전통적인 방법만으로는 풀기 까다로운 경우가 많습니다. 이런 상황에서 자주 등장하는 접근이 바로 유전 알고리즘(Genetic Algorithm, GA) 입니다. MathWorks는 GA를 확률적(stochastic) 이고 개체군 기반(population-based) 인 알고리즘으로 설명하며, 연속 변수뿐 아니라 정수 제약이 있는 문제와 비매끄러운 문제에도 적용할 수 있다고 설명합니다.

 

핵심만 먼저 말하면, 유전 알고리즘은 좋은 해를 가진 후보들을 남기고, 서로 섞고, 조금씩 변형시키면서, 세대를 거듭할수록 더 나은 해를 찾아가는 방식입니다. 이름은 생물학에서 왔지만, 실제로는 최적화 문제를 풀기 위한 계산 전략이라고 보면 됩니다. 유전 알고리즘의 고전적 기반은 John Holland의 연구로 정립되었고, 이후 다양한 최적화·탐색 문제로 확장되었습니다.

유전 알고리즘은 무엇을 흉내 낼까?

유전 알고리즘은 생물의 진화를 그대로 재현하려는 것이 아니라, 그 안에서 쓸 만한 메커니즘만 가져옵니다.
대표적으로는 다음 네 가지입니다.

• 개체(Individual): 하나의 해 후보
• 염색체(Chromosome): 해를 표현한 구조
• 적합도(Fitness): 그 해가 얼마나 좋은지 평가한 값
• 진화(Evolution): 좋은 후보를 남기고 새로운 후보를 만들어가는 과정

예를 들어 어떤 설계 문제에서 변수 10개를 최적화해야 한다면, 그 10개 값을 하나의 염색체처럼 표현할 수 있습니다. 그리고 여러 후보 해를 한 번에 모아둔 집합이 population(개체군) 이 됩니다. 유전 알고리즘은 이 개체군 전체를 보면서 다음 세대를 만들어 갑니다. 그래서 한 점만 따라가는 방식보다 탐색 폭이 넓다는 장점이 있습니다.

유전 알고리즘은 어떻게 동작할까?

유전 알고리즘의 기본 흐름은 생각보다 단순합니다.

1. 초기 후보 집단을 만든다.
2. 각 후보의 적합도를 계산한다.
3. 성능이 좋은 후보를 부모로 선택한다.
4. 부모끼리 정보를 섞어 자식 해를 만든다.
5. 일부는 무작위 변형을 준다.
6. 새 세대로 교체하고, 종료 조건까지 반복한다.

이 과정을 좀 더 기술적으로 보면, 다음 세대에는 보통 세 종류의 자식이 들어갑니다.
첫째는 elite child로, 현재 세대에서 성능이 좋은 개체를 그대로 살려두는 방식입니다.
둘째는 crossover child로, 두 부모의 유전자를 섞어서 만드는 방식입니다.
셋째는 mutation child로, 한 부모를 기준으로 일부 유전자를 무작위로 바꾸어 만드는 방식입니다. MathWorks 공식 설명도 바로 이 세 가지 구조를 중심으로 GA를 설명합니다.

선택(Selection), 교차(Crossover), 돌연변이(Mutation)는 왜 중요할까?

유전 알고리즘을 이해할 때 가장 중요한 것은 이 세 연산의 역할을 구분하는 것입니다.

선택(Selection) 은 “누구를 부모로 남길 것인가”를 결정합니다.

적합도가 높은 개체가 부모로 뽑힐 가능성이 커지기 때문에, 전체 성능은 점차 좋아지는 방향으로 움직입니다. MathWorks 문서에는 tournament, roulette, stochastic uniform 같은 선택 함수들이 제시되어 있습니다.

 

교차(Crossover) 는 “좋은 해의 일부를 섞어 더 좋은 해를 만들 수 있지 않을까?”라는 아이디어입니다.
두 부모의 유전자를 조합해서 자식을 만들기 때문에, 기존 후보들이 갖고 있던 장점을 결합할 수 있습니다. 기본 GA 설명에서도 자식은 부모 벡터의 각 좌표, 즉 gene 단위 정보를 받아 만들어진다고 설명합니다.

 

돌연변이(Mutation) 는 탐색이 너무 빨리 한쪽으로 몰리는 것을 막아줍니다.
만약 교차만 계속하면 개체들이 서로 너무 비슷해지고, 지역 최적점 근처에 갇힐 수 있습니다. 돌연변이는 일부 유전자를 랜덤하게 흔들어 주어서, 아직 가보지 않은 영역을 탐색하게 도와줍니다. 공식 문서에서도 mutation은 부모의 gene을 무작위로 바꾸어 새로운 자식을 만드는 과정으로 설명됩니다.

 

즉, 아주 거칠게 말하면
선택은 성능 향상,
교차는 조합,
돌연변이는 다양성 유지
를 담당한다고 보면 이해가 쉽습니다.

 

왜 유전 알고리즘이 실무에서 자주 거론될까?

유전 알고리즘의 강점은 해 공간이 복잡해도 여러 후보를 동시에 굴릴 수 있다는 점입니다.
특히 목적함수가 매끄럽지 않거나, 정수/연속 변수가 섞여 있거나, 제약이 복잡해서 미분 기반 접근이 불편할 때 검토할 가치가 있습니다. MathWorks 역시 GA를 smooth / nonsmooth 문제, constrained / unconstrained 문제, mixed-integer 문제에 적용할 수 있다고 설명합니다.

또 하나의 장점은 표현 유연성입니다.
문제에 따라 해를 비트 문자열로 표현할 수도 있고, 실수 벡터로 표현할 수도 있고, 사용자 정의 구조로 다룰 수도 있습니다. 실제 구현 도구들도 선택, 교차, 돌연변이 연산을 문제 성격에 맞춰 바꿔 쓸 수 있게 설계되어 있습니다.

그래서 유전 알고리즘은 단순 수치 최적화뿐 아니라, 레이아웃 최적화, 스케줄링, 설계 자동화, 조합 최적화 같은 영역에서 꾸준히 사용되어 왔습니다. Holland의 고전적 설명에서도 복잡한 장치 설계와 집적회로 같은 응용이 언급되고, 이후 레이아웃 최적화나 자원 제약 스케줄링 문제로도 이어졌습니다.

반대로, 한계도 분명하다

유전 알고리즘은 강력하지만 만능은 아닙니다.

가장 먼저, 정답을 보장하는 알고리즘은 아닙니다.
좋은 해를 찾을 가능성을 높이는 방식이지, 항상 전역 최적해를 증명해 주는 방식은 아닙니다. 그래서 문제에 따라 실행할 때마다 결과가 조금씩 달라질 수 있습니다. 확률적 알고리즘이라는 점 자체가 이런 성격을 말해줍니다.

또한 평가 비용이 비싼 문제에서는 부담이 커질 수 있습니다.
유전 알고리즘은 한 세대마다 population 전체의 fitness를 계산해야 하므로, 한 번의 해 평가가 무거운 시뮬레이션이라면 전체 계산량이 빠르게 커집니다. 특히 population size, generation 수, elite 수, selection/crossover/mutation 설정에 따라 계산 시간과 결과 품질이 크게 달라집니다.

즉, 유전 알고리즘은 “아무 문제에나 무조건 좋다”기보다는,
해 공간은 복잡하지만 평가 기준은 명확한 문제에서 특히 빛을 발하는 편입니다.

실무에서 특히 중요한 하이퍼파라미터

유전 알고리즘 성능은 구조보다도 설정값에 크게 좌우됩니다.

가장 많이 보는 항목은 다음 정도입니다.

• Population Size: 후보 해를 몇 개 유지할지
• Selection Function: 부모를 어떤 기준으로 뽑을지
• Crossover Function: 부모 정보를 어떤 방식으로 섞을지
• Mutation Function: 얼마나, 어떤 방식으로 흔들지
• Elite Count: 좋은 해를 몇 개 그대로 보존할지
• Stopping Condition: 몇 세대, 몇 초, 어느 정도 개선 정체에서 멈출지

보통 population이 너무 작으면 탐색 다양성이 부족해지고, 너무 크면 계산량이 커집니다.
mutation이 너무 약하면 수렴은 빠르지만 갇히기 쉽고, 너무 강하면 좋은 구조가 잘 보존되지 않습니다.
결국 유전 알고리즘은 탐색(exploration) 과 활용(exploitation) 사이의 균형을 맞추는 싸움이라고 볼 수 있습니다. MathWorks의 later generations 예시도 세대가 지나며 population이 점차 한 점 근처로 모여드는 모습을 보여줍니다.

언제 유전 알고리즘을 고려하면 좋을까?

다음과 같은 경우라면 유전 알고리즘을 한 번쯤 검토할 만합니다.

• 변수가 많고 조합이 복잡할 때
• 목적함수가 비선형, 비매끄럽거나 미분이 어려울 때
• 정수 변수와 연속 변수가 함께 있을 때
• 여러 후보를 동시에 비교하며 넓게 탐색하고 싶을 때
• 회로/배치/스케줄링처럼 “좋은 해”는 빠르게 찾고 싶지만 exact 해법은 부담스러울 때

반대로, 문제가 작고 구조가 잘 알려져 있으며 미분도 쉽다면, 더 전통적인 최적화 기법이 더 빠르고 안정적일 수 있습니다. 결국 중요한 것은 “유전 알고리즘이 좋은가?”가 아니라, “내 문제에 맞는가?” 입니다.

마무리

유전 알고리즘은 생물 진화의 아이디어를 빌려온 최적화 방법이지만, 본질은 꽤 공학적입니다.
여러 후보를 동시에 평가하고, 좋은 후보를 남기고, 서로 섞고, 일부를 변형하면서 점점 더 나은 해를 찾아갑니다. 그래서 복잡한 설계 문제나 조합 최적화 문제에서 지금도 여전히 유효한 선택지입니다.

한 줄로 정리하면 이렇습니다.

유전 알고리즘은 “좋은 해를 골라 남기고, 섞고, 흔들면서 점점 개선해 가는 개체군 기반 휴리스틱 최적화”라고 이해하면 가장 쉽습니다.

 

 

2026.04.07 - [기억하고 싶은 지식/python] - [PyGAD / DEAP] Python으로 Genetic Algorithm 시작하기: 유전 알고리즘 패키지 사용법과 하이퍼파라미터 완전 정리

[PyGAD / DEAP] Python으로 Genetic Algorithm 시작하기: 유전 알고리즘 패키지 사용법과 하이퍼파라미터 완