차분 진화(Differential Evolution, DE)는 진화 연산의 핵심 알고리즘 중 하나로, 단순성과 높은 효율성 덕분에 블랙박스 최적화 문제에 널리 사용되어 왔습니다. 그러나 그 성능은 하이퍼파라미터와 전략의 선택에 크게 의존하며, 이는 연구자들에게 지속적인 과제였습니다. 이러한 문제를 해결하기 위해 EvoX 팀은 최근 *IEEE Transactions on Evolutionary Computation (IEEE TEVC)*에 “MetaDE: Evolving Differential Evolution by Differential Evolution(MetaDE: 차분 진화를 통한 차분 진화의 진화)“라는 제목의 연구를 발표했습니다. DE를 활용하여 자체 하이퍼파라미터와 전략을 진화시키는 메타 진화 방법인 MetaDE는 GPU 가속 병렬 컴퓨팅을 통합하면서 파라미터와 전략의 동적 조정을 가능하게 합니다. 이러한 설계는 최적화 성능과 함께 계산 효율성을 크게 향상시킵니다. 실험 결과에 따르면 MetaDE는 CEC2022 벤치마크 제품군과 로봇 제어 작업 모두에서 뛰어난 성능을 발휘합니다. MetaDE의 소스 코드는 GitHub(https://github.com/EMI-Group/metade)에 오픈 소스로 공개되어 있습니다.
배경
진화 연산(Evolutionary Computation) 분야에서 알고리즘의 성능은 종종 하이퍼파라미터의 선택에 의해 크게 좌우됩니다. 특정 문제에 가장 적합한 파라미터 설정을 결정하는 것은 오랫동안 연구 과제였습니다. 차분 진화(DE)는 고전적인 진화 알고리즘으로서 단순성과 강력한 전역 탐색 능력으로 널리 사랑받고 있지만, 그 성능은 하이퍼파라미터 선택에 매우 민감합니다. 기존 방법들은 성능을 향상시키기 위해 경험 기반 튜닝이나 적응형 메커니즘에 의존하는 경우가 많습니다. 그러나 다양한 문제 시나리오에 직면했을 때, 이러한 접근 방식은 효율성과 광범위한 적용 가능성 사이의 균형을 맞추는 데 어려움을 겪곤 합니다.
“메타 진화(Meta-Evolution)“라는 개념은 지난 세기부터 도입되었으며, 진화 알고리즘 자체를 사용하여 해당 알고리즘의 하이퍼파라미터 구성을 최적화하는 것을 목표로 합니다. 메타 진화는 수년 동안 존재해 왔지만, 높은 계산 요구량으로 인해 실제 적용에는 제약이 있었습니다. 최근 GPU 컴퓨팅의 발전은 이러한 제약을 완화하여 진화 알고리즘에 강력한 하드웨어 지원을 제공했습니다. 특히 분산 GPU 가속 EvoX 프레임워크의 도입은 GPU 기반 진화 알고리즘의 개발을 크게 촉진했습니다. 이러한 배경에서 우리 연구팀은 DE를 활용하여 자체 하이퍼파라미터와 전략을 진화시키는 새로운 메타 진화 접근 방식을 제안함으로써, 진화 알고리즘의 오랜 파라미터 튜닝 문제를 해결할 수 있는 새로운 길을 제시했습니다.
메타 진화(Meta-Evolution)란 무엇인가?
메타 진화의 핵심 아이디어는 “진화 알고리즘을 사용하여 스스로를 진화시키는 것”(Evolving an Evolutionary Algorithm by an Evolutionary Algorithm)으로 요약할 수 있습니다. 이 개념은 진화 알고리즘을 사용하여 문제의 최적해를 탐색할 뿐만 아니라, 자체 진화 과정을 통해 알고리즘의 하이퍼파라미터와 전략을 조정함으로써 전통적인 진화 연산 방법을 초월합니다.
즉, 메타 진화는 “자가 진화(self-evolution)” 패러다임을 도입하여 알고리즘이 문제 해결을 위한 탐색 공간을 탐색함과 동시에 스스로를 최적화할 수 있게 합니다. 진화 과정 중에 지속적으로 자신을 개선함으로써 알고리즘은 더 높은 적응력을 갖게 되며 다양한 문제 시나리오에서 높은 효율성을 유지할 수 있습니다.
MetaDE를 예로 들면, 그 설계는 이러한 철학에 뿌리를 두고 있습니다. 2계층 구조에서 하위 계층(“executor”, 실행기)은 파라미터화된 DE를 사용하여 주어진 최적화 문제를 해결합니다. 상위 계층(“evolver”, 진화기)은 동시에 DE를 사용하여 실행기의 하이퍼파라미터 구성을 최적화합니다. 이 프레임워크를 통해 DE는 솔버(solver) 역할을 할 뿐만 아니라, 다양한 문제를 더 효과적으로 해결하기 위해 자신의 파라미터와 전략을 어떻게 조정하는 것이 최선인지 “탐색”합니다. 이러한 과정은 시스템이 점진적으로 자신을 이해하고 개선하는 것과 유사하며, “수동적인 문제 해결”에서 “능동적인 자가 진화”로의 전환을 의미합니다. 결과적으로 다양한 작업에 더 잘 적응할 수 있습니다. DE를 복잡한 시스템으로 간주한다면, MetaDE는 이 시스템 내에서 자기 이해와 자기 개선의 “재귀적(recursive)” 방식을 효과적으로 가능하게 합니다.
컴퓨터 과학에서 “재귀(recursion)“라는 용어는 일반적으로 자기 자신을 호출하는 함수나 프로시저를 설명합니다. MetaDE 내에서 이 개념은 새로운 의미를 갖습니다. 즉, DE를 사용하여 DE의 하이퍼파라미터를 진화시키는 내부적으로 재귀적인 최적화 메커니즘입니다. 이 자기 참조 방식은 강력한 적응성을 구현할 뿐만 아니라 “공짜 점심은 없다(no free lunch)” 정리에 대한 새로운 관점을 제공합니다. 모든 문제에 대해 보편적으로 최적화된 단일 파라미터 세트는 없기 때문에, 알고리즘이 스스로 자율적으로 진화하도록 하는 것이 주어진 작업에 대한 최적의 파라미터 구성을 찾는 열쇠입니다.
이러한 재귀적 메타 진화 접근 방식을 통해 MetaDE는 다음과 같은 이점을 얻습니다:
1. 자동화된 파라미터 튜닝
노동 집약적인 수동 튜닝 과정이 제거됩니다. 알고리즘 자체가 하이퍼파라미터를 조정하는 방법을 학습하여 인간의 개입을 줄이고 효율성을 향상시킵니다.2. 향상된 적응성
MetaDE는 변화하는 문제 특성과 조건에 동적으로 반응하며, 실시간으로 전략을 수정하여 성능을 개선합니다. 이는 알고리즘의 유연성을 크게 높입니다.3. 효율적인 탐색 내재된 병렬성을 활용하여 MetaDE는 대규모 최적화 문제에서 탐색 속도를 크게 가속화합니다. 고차원의 복잡한 문제에 대해 합리적인 시간 내에 실행 가능한 솔루션을 제공합니다.
알고리즘 구현
MetaDE는 텐서 기반 기술과 GPU 가속을 사용하여 효율적인 병렬 컴퓨팅을 가능하게 합니다. 많은 개체군(population)을 동시에 처리함으로써 전체적인 계산 효율성이 현저히 향상되며, 이는 단일 목적 블랙박스 최적화 및 대규모 최적화 문제에서 특히 유리합니다. 주요 파라미터와 데이터 구조(예: 개체군, 적합도, 전략 파라미터)의 텐서화를 통해 MetaDE는 더 높은 계산 효율성을 달성할 뿐만 아니라 복잡한 최적화 문제를 해결하는 능력도 강화합니다. 고전적인 DE 및 다른 진화 알고리즘(EAs)과 비교할 때, MetaDE는 대규모 문제 해결에서 우수한 성능을 보여줍니다. 텐서 기반 접근 방식 덕분에 MetaDE는 계산 자원을 더 효과적으로 활용하여 기존 방법보다 더 빠른 솔루션과 더 정밀한 최적화 결과를 산출합니다.
PDE 아키텍처
연구팀은 먼저 파라미터와 전략의 수정이 완전히 지원되는 파라미터화된 DE 알고리즘 프레임워크(PDE)를 제안했습니다. 이 프레임워크에서 F와 CR은 연속 파라미터인 반면, 다른 파라미터들은 이산적입니다. 점선 상자는 허용 가능한 파라미터 값의 범위를 나타냅니다. 변이(mutation) 함수는 왼쪽과 오른쪽의 기본 벡터(base vectors)와 차분 벡터(difference vectors)의 수를 제어하는 파라미터로부터 도출됩니다.
MetaDE 아키텍처
MetaDE는 하나의 진화기(evolver)(상위 계층)와 여러 실행기(executors)(하위 계층)로 구성된 2계층 구조를 채택합니다. 진화기는 DE(또는 잠재적으로 다른 진화 알고리즘)이며, PDE의 파라미터를 최적화하는 역할을 합니다. 진화기의 개체군 내 각 개체 
x_i는 고유한 파라미터 구성 θ_i에 해당합니다. 이러한 구성은 PDE로 전달되어 서로 다른 DE 변형(variant)을 인스턴스화하며, 각 변형은 주어진 최적화 작업에서 독립적으로 실행되는 실행기에 의해 관리됩니다. 각 실행기는 최적의 적합도 값 y^*를 진화기에게 반환하고, 진화기는 해당 적합도 값 y_i를 대응하는 개체 x_i에 할당합니다.
실험 성능
MetaDE의 효과를 종합적으로 평가하기 위해 연구팀은 여러 벤치마크 테스트와 실제 시나리오에 걸쳐 체계적인 실험을 수행했습니다. 각 실험은 진화기(rand/1/bin 전략을 사용하는 DE)와 실행기(개체군 크기 100인 PDE)를 사용했습니다. 주요 실험 구성 요소는 다음과 같습니다:
CEC2022 벤치마크
단일 목적 최적화 작업에서 MetaDE를 다양한 DE 변형들과 비교.
CEC2022 상위 4개 알고리즘과의 비교
동일한 함수 평가 횟수(FEs) 예산 하에서 CEC2022 대회에서 가장 우수한 성과를 낸 4개의 알고리즘과 MetaDE를 평가.
고정된 실제 소요 시간(Wall-Clock Time) 하에서의 함수 평가(FEs)
GPU 가속 하에서 MetaDE의 계산 효율성 분석.
로봇 제어 작업
Brax 플랫폼 환경의 로봇 제어 작업에 MetaDE를 적용하여 실용적 유용성 검증.
CEC2022 벤치마크: 주류 DE 변형들과의 비교
팀은 CEC2022 벤치마크 제품군에서 MetaDE를 다음과 같은 대표적인 DE 변형들과 비교했습니다:
- Standard DE (rand/1/bin)
- SaDE 및 JaDE (적응형 DE 알고리즘)
- CoDE (전략 통합형 DE)
- SHADE 및 LSHADE-RSP (성공 이력 기반 적응형 DE)
- EDEV (통합형 DE 변형)
모든 알고리즘은 EvoX 플랫폼에서 구현되었으며, 공정성을 위해 개체군 크기 100으로 GPU 가속을 활용했습니다. 실험은 동일한 계산 시간 제약(60초) 하에 서로 다른 차원(10D 및 20D)에서 수행되었습니다.
10D CEC2022 최적화 결과
20D CEC2022 최적화 결과
MetaDE는 대부분의 테스트 함수에서 전반적으로 더 빠르고 안정적인 수렴을 달성합니다. 상위 계층 최적화와 결합된 파라미터화된 DE(PDE)는 다양한 문제 공간에 대한 동적 적응을 가능하게 하여 전반적인 견고성과 탐색 성능을 향상시킵니다.
CEC2022 상위 4개 알고리즘과의 비교 (동일한 FEs 하에서)
MetaDE의 최적화 능력을 더욱 평가하기 위해, 우리는 동일한 함수 평가 예산 내에서 CEC2022 대회의 상위 4개 알고리즘과 비교했습니다:
- EA4eig: 다중 EA를 통합한 하이브리드 방법
- NL-SHADE-LBC: 개선된 적응형 DE
- NL-SHADE-RSP-MID: 중간점 추정이 포함된 향상된 SHADE
- S-LSHADE-DP: 동적 섭동(dynamic perturbation)을 통해 개체군 다양성을 유지하는 DE 변형
이 알고리즘들은 각각 공식 파라미터 설정과 소스 코드를 사용하여 동일한 FE 제약 하에서 실행되었습니다. MetaDE와 각 기준 알고리즘 간의 통계적 비교(Wilcoxon 순위 합 검정, 유의 수준 0.05)가 CEC2022 테스트 제품군에서 수행되었습니다. 표의 마지막 행은 다양한 테스트 함수에서 MetaDE와 비교한 각 알고리즘의 성능을 보여줍니다: + (상당히 더 좋음), ≈ (유의미한 차이 없음), − (상당히 더 나쁨).
10D CEC2022 대회 알고리즘 비교 (동일 FEs)
20D CEC2022 대회 알고리즘 비교 (동일 FEs)
MetaDE는 특히 강력한 수렴이 요구되는 복잡한 문제에서 일관되게 강력한 성능을 보여줍니다. 자가 적응 메커니즘 덕분에 MetaDE는 다양한 탐색 환경에 맞춰 전략을 효과적으로 조정하여 탐색 효율성과 전역 최적화 능력을 향상시킵니다. 이러한 결과는 MetaDE가 주류 DE 변형들을 능가할 뿐만 아니라 최상위권 대회 알고리즘들과 비교해도 강력한 경쟁력을 갖추고 있음을 나타냅니다.
계산 효율성: 고정된 시간(60초) 내의 FEs
연구팀은 **동일한 고정 실행 시간(60초) 내에 서로 다른 알고리즘이 완료한 함수 평가 횟수(FEs)**를 추가로 기록했습니다.
60초 동안 각 알고리즘이 달성한 FEsGPU 가속 병렬 연산을 사용하는 동일한 EvoX 프레임워크 하에서, MetaDE는 평균적으로 10****⁹ 수준의 FEs를 달성한 반면, 전통적인 DE 변형들은 약 10^6 FEs에 그쳤습니다. 이러한 이점은 개체들에 대한 대규모 병렬 평가를 수행하여 하드웨어 자원 활용을 더 효율적으로 만드는 MetaDE의 파라미터화된 접근 방식에서 비롯됩니다. 결과적으로 알고리즘은 동일한 시간 창 내에서 더 많은 솔루션을 탐색하여 솔루션 품질과 안정성을 모두 향상시킵니다.
진화적 강화 학습: 로봇 제어 작업
강화 학습(Reinforcement Learning, RL)에서는 정책 최적화의 효율성과 안정성이 매우 중요합니다. PPO나 SAC와 같은 경사(Gradient) 기반 방법은 고차원 환경에서 경사 소실(gradient vanishing)이나 폭발(exploding) 문제를 겪을 수 있습니다. 대조적으로, 진화적 강화 학습(EvoRL)은 정책 파라미터를 직접 최적화하기 위해 경사 없는(gradient-free) 탐색을 사용하여 이러한 문제를 우회합니다.
진화적 강화 학습 프로세스
EvoRL 프레임워크 내에서 MetaDE는 다음과 같은 역할을 합니다:
- 신경망 파라미터 자동 최적화: 정책 모델의 적응성을 높입니다.
- 하이퍼파라미터 동적 조정: 훈련 안정성을 향상시킵니다.
- GPU 가속 활용: 정책 최적화 속도를 높입니다.
복잡한 최적화 작업에 대한 MetaDE의 성능을 평가하기 위해, 우리는 Brax 시뮬레이션 플랫폼에서 GPU 가속 최적화를 사용하여 로봇 제어 문제에 이를 적용했습니다. 연구에는 Swimmer, Hopper, Reacher의 세 가지 작업이 포함되었으며, 각 작업은 보상을 최대화하는 것을 목표로 하는 3층 완전 연결 신경망(MLP)으로 모델링되었습니다. 특히 각 MLP는 약 1,500개의 파라미터를 포함하고 있어, 진화 알고리즘(EAs)에 1,500차원의 최적화 과제를 생성합니다. 이는 탐색 능력과 계산 효율성 모두에 엄격한 요구 사항을 부과합니다.
세 가지 Brax 환경에 대한 수렴 곡선
그림에서 볼 수 있듯이, MetaDE는 Brax 기반 로봇 제어 작업에서 강력한 성능을 보여주며, Swimmer 작업에서는 최고의 결과를, Hopper와 Reacher에서는 최적에 가까운 결과를 달성했습니다. 주요 이점은 초기 개체군의 높은 품질에 있으며, 이는 빠른 초기 단계 수렴과 고품질 솔루션 생성으로 이어집니다. 이러한 결과는 MetaDE가 신경망 정책을 효율적으로 최적화할 수 있음을 시사하며, 복잡한 물리 시뮬레이션이 포함된 로봇 제어 작업에 적합하고 실제 응용 분야에 대한 광범위한 잠재력을 제공함을 보여줍니다.
결론 및 향후 방향
MetaDE는 최적화 작업을 해결하는 데 탁월할 뿐만 아니라 자체 전략을 자율적으로 튜닝하고 개선하는 혁신적인 메타 진화 접근 방식입니다. 차분 진화의 장점을 활용한 MetaDE는 적응형 파라미터 구성 및 전략 진화에서 강력한 잠재력을 보여줍니다. 실험 결과는 다양한 벤치마크 테스트에서 우수한 견고성을 보여주며, 진화적 강화 학습을 통한 로봇 제어 작업에서의 성공은 실제 적용 가능성을 강조합니다. 핵심 과제는 일반화와 전문화 사이의 최적 균형을 유지하는 것입니다. 즉, 알고리즘이 다양한 작업에 적응하면서도 특정 문제에 대해 효과적으로 최적화할 수 있도록 보장하는 것입니다. 이 연구는 자가 적응형 진화 알고리즘에 대한 새로운 관점을 제공하며 복잡한 시스템을 위한 메타 진화의 추가적인 발전을 촉진할 수 있습니다.
오픈 소스 코드 및 커뮤니티
논문: https://arxiv.org/abs/2502.10470
GitHub: https://github.com/EMI-Group/metade
업스트림 프로젝트 (EvoX): https://github.com/EMI-Group/evox
QQ 그룹: 297969717
QQ 그룹 | Evolving Machine Intelligence
MetaDE는 EvoX 프레임워크를 기반으로 구축되었습니다. EvoX에 관심이 있으시다면 EvoX 1.0에 대한 기사를 확인하여 자세한 내용을 알아보세요.
(https://mp.weixin.qq.com/s/uT6qSqiWiqevPRRTAVIusQ)