[인공지능/최적화/AI] 휴리스틱 알고리즘 DE(Differential Evolution)란? 벡터 차이로 해를 진화시키는 전역 최적화 방법

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

 

최적화 문제를 풀다 보면, 해 공간이 너무 넓어서 어디부터 찾아야 할지 막막한 경우가 많습니다.
특히 목적함수가 비선형이거나, 매끄럽지 않거나, 미분 정보를 쓰기 어렵거나, 지역 최적해에 쉽게 갇히는 문제에서는 전통적인 방법만으로 답을 찾기 까다로운 경우가 있습니다. 이런 상황에서 자주 언급되는 대표적인 메타휴리스틱 중 하나가 바로 DE(Differential Evolution) 입니다. DE는 Storn과 Price가 제안한 확률적 개체군 기반 최적화 기법으로, 여러 후보 해 사이의 차이 벡터를 이용해 새로운 해를 만든다는 점이 핵심입니다.

핵심만 먼저 말하면, DE는 “좋은 해 주변을 무작정 흔드는 방식”이 아니라, 현재 개체군 안에 있는 해들 사이의 차이를 이용해 다음 후보를 만들어 가는 알고리즘입니다. 그래서 이름 그대로 “differential”, 즉 차이가 탐색의 동력이 됩니다. SciPy 공식 문서도 DE를 확률적(stochastic)이고, gradient를 사용하지 않으면서 넓은 탐색 공간을 다룰 수 있는 전역 최적화 방법으로 설명합니다.

---

DE 알고리즘은 무엇이 다른가?

유전 알고리즘(GA)도 개체군을 사용하고, PSO도 여러 후보를 동시에 움직입니다.
그런데 DE는 새 후보를 만드는 방식이 꽤 독특합니다.

보통 GA는 선택, 교차, 돌연변이를 통해 유전자를 섞는 느낌이 강합니다.
반면 DE는 현재 population 안에서 몇 개의 해를 뽑고, 그 해들 사이의 차이를 계산해 새 후보를 만듭니다. 다시 말해, 탐색 방향을 외부에서 정하는 것이 아니라, 현재 해 집단의 상대적 위치 관계로부터 만든다는 점이 DE의 가장 큰 특징입니다. pymoo 문서에서도 DE의 고전적인 형태를 바로 이 벡터 차 기반 수식으로 설명합니다.

---

DE는 어떻게 동작할까?

DE의 기본 흐름은 생각보다 단순합니다.

1. 초기 후보 해 집단(population)을 만든다.
2. 각 후보에 대해 목적함수 값을 계산한다.
3. 몇 개의 다른 후보를 골라 차이 벡터를 만든다.
4. 그 차이를 이용해 donor vector를 만든다.
5. 기존 해와 donor를 섞어 trial vector를 만든다.
6. trial이 더 좋으면 기존 해를 대체한다.
7. 종료 조건까지 반복한다.

SciPy 문서 기준으로도 DE는 population 기반으로 각 후보를 순회하면서, 다른 후보들을 섞어 trial candidate를 만들고, 성능이 더 좋으면 교체하는 방식으로 설명됩니다.

여기서 중요한 것은 항상 현재 해보다 좋은 후보만 남기는 greedy selection 구조가 자주 사용된다는 점입니다.
즉, 매 반복마다 “새 후보가 더 좋으냐?”만 비교하므로 구조는 단순하지만, 개체군 전체가 계속 조금씩 더 나은 방향으로 이동하게 됩니다.

 

---

DE의 핵심 수식: 왜 ‘차이 벡터’가 중요할까?

DE를 대표하는 가장 유명한 형태 중 하나는 아래와 같습니다.

v = x_r1 + F(x_r2 - x_r3)

이 식은 donor vector를 만드는 전형적인 예입니다.
여기서 x_r2 - x_r3 는 두 해 사이의 차이이고, F 는 그 차이를 얼마나 크게 반영할지를 정하는 계수입니다. 그리고 그 결과를 x_r1 에 더해서 새로운 방향의 후보를 만드는 것입니다. pymoo 문서와 SciPy 문서 모두 이 계열의 수식을 DE의 중심 구조로 설명합니다.

이 구조가 중요한 이유는,

DE가 무작위 노이즈만 넣는 것이 아니라 현재 population이 가진 기하학적 정보를 활용한다는 데 있습니다.
어떤 해들끼리 멀리 떨어져 있으면 큰 탐색이 일어나고, 해들이 서로 비슷해지면 움직임도 작아집니다. 그래서 탐색 초반에는 넓게 움직이고, 후반에는 점차 수렴하는 경향을 보일 수 있습니다. 이것이 DE가 단순해 보이면서도 강력한 이유입니다.

---

Mutation, Crossover, Selection은 각각 무슨 역할을 할까?

1) Mutation

DE에서 mutation은 일반적인 “랜덤 흔들기”와 조금 다릅니다.
차이 벡터를 이용해 donor vector를 만들기 때문에, 탐색 방향이 population 내부 구조에 의해 정해집니다. SciPy 문서에서는 mutation constant를 F(differential weight) 로 설명하며, 이 값이 커질수록 탐색 반경이 넓어지지만 수렴은 느려질 수 있다고 안내합니다.

2) Crossover

그다음에는 donor vector와 기존 target vector를 섞어서 trial vector를 만듭니다.
즉, 새 후보를 100% donor로 바꾸는 것이 아니라, 일부 좌표는 기존 해에서 유지하고 일부 좌표만 donor에서 받아옵니다. SciPy 문서에서는 이 recombination 값이 문헌상 CR(crossover probability) 로 불리며, 값이 커질수록 더 많은 mutant 정보가 다음 세대로 들어갈 수 있지만 population 안정성은 떨어질 수 있다고 설명합니다.

3) Selection

마지막은 selection입니다.
trial vector를 평가해서 기존 target보다 좋으면 교체하고, 아니면 버립니다.
구조 자체는 단순하지만, 이 비교가 세대마다 반복되면서 성능이 점진적으로 개선됩니다. SciPy 문서도 trial candidate의 fitness를 평가한 뒤 기존 후보보다 좋으면 대체한다고 설명합니다.

 

---

DE가 실무에서 자주 언급되는 이유

DE는 다음과 같은 상황에서 특히 검토할 가치가 있습니다.

• 목적함수가 복잡하고 비선형일 때
• gradient를 구하기 어렵거나 의미가 약할 때
• 탐색 공간이 넓고 지역 최적해가 많은 문제일 때
• 여러 설계 변수를 동시에 조정해야 할 때
• 시뮬레이션 기반 최적화처럼 “평가 함수는 있지만 해석적 구조는 약한” 문제일 때

SciPy 공식 문서도 DE가 gradient를 쓰지 않고 넓은 candidate space를 탐색할 수 있다고 설명하고, 원 논문 역시 비선형·비미분 연속 공간 최적화 문제를 주요 대상으로 제시합니다.

그래서 DE는 단순한 수학 함수 최적화뿐 아니라, 파라미터 튜닝, 설계 자동화, 공정 조건 탐색, 회로 사이징, 엔지니어링 최적화 같은 영역에서 꾸준히 언급됩니다. 특히 목적함수 평가가 시뮬레이션 기반일 때 “미분은 없지만 비교는 가능한” 구조와 잘 맞는 편입니다.

---

DE의 장점

DE의 장점은 꽤 분명합니다.

첫째, 구조가 단순합니다.
핵심 아이디어가 차이 벡터 기반 생성 + 교차 + 더 좋은 해 선택이기 때문에 이해와 구현이 비교적 직관적입니다. 원 논문도 DE를 few control variables, robust, easy to use라고 설명합니다.

둘째, gradient가 없어도 동작합니다.
그래서 미분 불가능하거나 noisy한 함수에도 적용을 검토할 수 있습니다.

셋째, 전역 탐색 성향이 강합니다.
population 전체를 기반으로 움직이기 때문에 한 점에서만 갱신하는 방식보다 넓게 보는 편입니다.

넷째, 병렬화와도 잘 맞습니다.
원 논문은 병렬 계산과 잘 맞는다고 설명했고, SciPy 역시 workers 옵션을 통해 병렬 평가를 지원합니다.

---

DE의 한계도 분명하다

물론 DE도 만능은 아닙니다.

가장 큰 한계는 평가 비용이 비싸면 전체 계산량이 커질 수 있다는 점입니다.
population 기반 알고리즘이므로 한 세대마다 여러 후보를 평가해야 하고, 목적함수 계산 자체가 무거우면 실행 시간이 빠르게 증가합니다. SciPy 문서도 gradient 기반 기법보다 더 많은 함수 평가가 필요할 수 있다고 설명합니다.

또 하나는 하이퍼파라미터에 민감할 수 있다는 점입니다.
F, CR, population size, strategy 설정에 따라 탐색 성향이 꽤 달라집니다. 즉, “그냥 넣으면 무조건 잘 된다”기보다는 문제 성격에 맞는 설정이 중요합니다.

그리고 DE는 전역 최적화를 잘 노리는 알고리즘이지만,
항상 수학적으로 전역 최적해를 보장하는 것은 아닙니다.
확률적 방법이기 때문에 시드나 설정, 문제 구조에 따라 결과가 달라질 수 있습니다.

---

실무에서 자주 보는 하이퍼파라미터

DE를 사용할 때 특히 자주 보는 값은 다음과 같습니다.

Population Size

후보 해를 몇 개 유지할지 정하는 값입니다.
너무 작으면 다양성이 부족하고, 너무 크면 계산량이 커집니다. SciPy에서는 popsize가 전체 population 크기를 결정하는 계수로 설명됩니다.

F (Mutation Factor)

차이 벡터를 얼마나 크게 반영할지 정합니다.
값이 크면 더 과감하게 움직이고, 값이 작으면 더 조심스럽게 움직입니다. SciPy 문서에 따르면 F를 키우면 search radius는 커지지만 convergence는 느려질 수 있습니다.

CR (Crossover Rate)

기존 해와 donor를 얼마나 많이 섞을지 정합니다.
값이 크면 donor 성분이 많이 들어가고, 값이 작으면 기존 해 성격을 더 유지합니다.

Strategy

DE/rand/1, DE/best/1/bin 같은 전략 이름으로 자주 표현됩니다.
SciPy는 best1bin, rand1bin, rand2bin, currenttobest1bin 등 여러 전략을 지원합니다.

Initialization

초기 population을 어떻게 뿌릴지도 중요합니다.
SciPy는 기본값으로 latinhypercube를 사용하며, 이는 parameter space를 넓게 덮도록 돕는다고 설명합니다.

 

---

언제 DE를 고려하면 좋을까?

아래와 같은 상황이라면 DE를 한 번쯤 검토할 만합니다.

• 블랙박스 함수 최적화
• 시뮬레이션 기반 파라미터 튜닝
• 비선형 연속 변수 최적화
• 지역 최적해가 많은 전역 탐색 문제
• gradient 정보가 약하거나 없는 설계 문제

반대로,
문제가 매끄럽고 convex에 가깝고 gradient를 정확히 쓸 수 있다면, 전통적인 gradient 기반 최적화가 더 빠르고 효율적일 수도 있습니다. 결국 중요한 것은 “DE가 유명한가?”가 아니라, 내 문제의 구조에 맞는가 입니다.

---

마무리

DE(Differential Evolution)는 이름은 조금 어렵지만, 핵심 아이디어는 꽤 직관적입니다.
현재 후보 해들 사이의 차이를 이용해 새로운 해를 만들고, 더 좋은 해만 남기면서 점점 해를 개선해 가는 방식입니다.

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

DE는 “개체군 내부의 차이 벡터를 이용해 새로운 후보를 만들고, 더 나은 해만 선택하며 전역 탐색을 수행하는 휴리스틱 최적화 알고리즘”이라고 이해하면 가장 쉽습니다.

최적화 문제를 다뤄야 하는데 gradient 기반 접근이 잘 맞지 않거나, 해 공간이 너무 복잡해서 넓게 탐색해야 한다면, DE는 한 번쯤 진지하게 검토할 만한 알고리즘입니다.

 

 

2026.04.08 - [기억하고 싶은 지식/python] - [scipy / pymoo] Python으로 Differential Evolution 시작하기: DE 패키지 사용법과 하이퍼파라미터 완전 정리

[scipy / pymoo] Python으로 Differential Evolution 시작하기: DE 패키지 사용법과 하이퍼파라미터 완전 정리