적응은 발견한 해뿐 아니라 시스템이 해를 찾는 방식에도 적용됩니다. MetaDE는 연결된 두 진화 수준으로 이 생각을 EvoX에 도입합니다. 내부는 목표 문제를 해결하고, 외부는 탐색을 효과적으로 만드는 DE 구성을 평가합니다. 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초 동안 각 알고리즘이 달성한 FEs
GPU 가속 병렬 연산을 사용하는 동일한 EvoX 프레임워크 하에서, MetaDE는 평균적으로 10⁹ 수준의 FEs를 달성한 반면, 전통적인 DE 변형들은 약 10^6 FEs에 그쳤습니다. 이러한 이점은 개체들에 대한 대규모 병렬 평가를 수행하여 하드웨어 자원 활용을 더 효율적으로 만드는 MetaDE의 파라미터화된 접근 방식에서 비롯됩니다. 결과적으로 알고리즘은 동일한 시간 창 내에서 더 많은 솔루션을 탐색하여 솔루션 품질과 안정성을 모두 향상시킵니다.
진화적 강화 학습: 로봇 제어 작업
MetaDE의 로봇 제어 실험은 정책 매개변수를 무경사 탐색하며 정책 목적을 역전파하지 않습니다. 그러나 진화 강화학습에는 경사 기반 및 하이브리드 방법도 있으므로 PPO나 SAC의 어려움을 보편적으로 제거한다고 볼 수 없습니다.
Brax Swimmer, Hopper, Reacher에서 약 1,500개 매개변수의 3층 MLP 정책을 사용합니다. 내부 탐색은 정책 가중치, 외부 탐색은 DE 실행기의 매개변수와 전략을 조정합니다. 시뮬레이션 평가이며 실제 로봇 배치나 강화학습 안정성의 일반적 향상을 입증하지 않습니다.
세 가지 Brax 환경에 대한 수렴 곡선
그림에서 볼 수 있듯이, MetaDE는 Brax 기반 로봇 제어 작업에서 강력한 성능을 보여주며, Swimmer 작업에서는 최고의 결과를, Hopper와 Reacher에서는 최적에 가까운 결과를 달성했습니다. 주요 이점은 초기 개체군의 높은 품질에 있으며, 이는 빠른 초기 단계 수렴과 고품질 솔루션 생성으로 이어집니다. 이러한 결과는 MetaDE가 신경망 정책을 효율적으로 최적화할 수 있음을 시사하며, 복잡한 물리 시뮬레이션이 포함된 로봇 제어 작업에 적합하고 실제 응용 분야에 대한 광범위한 잠재력을 제공함을 보여줍니다.
결론 및 향후 방향
외부 설정 시도와 내부 목적 함수 평가를 모두 기록합니다. 총예산과 실제 경과 시간을 함께 사용해 방법을 비교합니다. iStratDE: 개체군 다양성을 병렬 탐색의 원리로 삼다