DE-2LS: Differential Evolution with Late-Stage local-search for Unconstrained Single-Objective Numerical Optimization

기술 요약: 제약 없는 단일 목적 수치 최적화(UCOP)를 위한 DE-2LS

문제 정의
본 논문은 IEEE CEC 경진대회에서 흔히 발생하는 변수 범위가 있는 제약 없는 단일 목적 수치 최적화(UCOP) 문제를 다룹니니다. 핵심 과제는 전역 탐색(global exploration), 후기 단계의 국소 탐색(late-stage exploitation), 그리고 함수 평가 효율성 사이의 균형을 맞추는 것입니다. 구체적으로, RDEx(exploitation-biased branching이 적용된 Reconstructed DE)와 같은 차분 진화(Differential Evolution, DE) 변형들은 강력한 성능을 보여주지만, 탐색이 유망한 분지(basin)에 진입했을 때 기존 솔루션을 효율적으로 "다듬는(polish)" 정밀도가 부족할 수 있습니다. 이러한 한계는 최종 솔루션의 품질과 수렴 속도를 공동으로 평가하는 U-score 평가 지표 하에서 매우 중요합니다. 목표는 기본 알고리즘의 견고한 진화 탐색 동작을 저해하지 않으면서 두 지표를 모두 개선하는 것입니다.

방법론
제안된 방법인 DE-2LS는 RDEx 프레임워크를 보수적으로 강화한 모델입니다. DE-2LS는 RDEx의 핵심 진화 엔진을 교체하는 대신, 고정된 함수 평가 예산 내에서 작동하도록 설계된 두 가지 후기 단계 정밀화 기법을 도입합니다.

1. 매끄러운 탐색 편향(Exploitation-Biased, EB) 분기율 업데이트:
   탐색의 후기 단계(평가 예산의 75%가 소비된 후)에서, 탐색 편향 분기를 선택할 확률을 업데이트하는 메커니즘입니다. 즉각적인 분기 성능에 반응하여 급격하게 변화하는 대신, 업데이트 규칙은 이전의 비율과 현재의 가공되지 않은 추정치의 가중치 결합(weighted smoothing)을 적용합니다. 이는 탐색 전략의 급격한 변화나 조기 수렴을 방지하며, 집중적인 탐색으로의 전이를 안정화합니다.

2. 가드형 좌표 패턴 국소 탐색(Guarded Coordinate-Pattern Local Search, LS):
   특정 조건이 충족될 때만 활성화되는 경량 국소 탐색 모듈입니다. 이 모듈은 탐색 후기 단계(예산의 82% 이후)이고, 전역 최적해(global-best)가 정의된 횟수만큼 정체되었으며, 국소 탐색 호출 제한에 도달하지 않았을 때 실행됩니다.

• 메커니즘: LS는 현재 전역 최적해를 사용하여 좌표 패턴 방식으로 작동합니다. 변수 범위에 비례하는 초기 스텝 사이즈를 사용하여 한 번에 하나의 좌표 방향을 탐색합니다.
• 전략: "First-improvement" 전략을 채택합니다. 더 나은 지점이 발견되면 중심점을 즉시 업데이트하고, 개선된 지점을 찾지 못하면 스텝 사이즈를 절반으로 줄입니다.
• 제약 사항: 이 과정은 엄격하게 예산을 준수합니다. 호출당 할당된 평가 횟수의 비율과 최대 호출 횟수가 정의되어 있습니다. 변수 범위 외의 제약은 없으므로 목적 함수 값만을 기준으로 수락 여부를 결정하며, 성공 이력 메모리(success-history memory)나 모집단 구조를 재설정하지 않고 개선된 솔루션을 모집단에 다시 주입합니다.

주요 기여

• 알고리즘 설계: 매끄러운 EB-rate 업데이트와 가드형 예산 제어 국소 탐색 모듈을 통해 RDEx 베이스라인을 증강한 DE-2LS를 제안하였습니다.
• 절제 연구(Ablation Study): 최적의 구성을 결정하기 위해 엄격한 단계별 절제 분석을 수행했습니다. 여기에는 EB-rate 평활화의 타이밍 및 가중치, 표준 분기의 초기 EB-rate, 가우시안 샘플링 스케일, 선택 압력 파라미터, 그리고 국소 탐색 계수(타이밍, 예산, 스텝 사이즈)의 튜닝이 포함되었습니다.
• U-Score 최적화: 설계 단계부터 U-score 지표를 명시적으로 겨냥하여, 정확도(최종 오차)와 속도(수렴 궤적) 구성 요소를 동시에 개선하는 것을 목표로 했습니다.

실험 결과
실험은 29개의 UCOP 함수(D=30)에 대해 10,000D 함수의 평가 예산을 사용하여 25회의 독립적인 실행을 통해 수행되었습니다. 성능은 쌍별(pairwise) U-score 절차를 사용하여 평가되었습니다.

• RDEx와의 비교: DE-2LS는 기존 RDEx를 일관되게 능가했습니다. U-score는 33,602.0에서 37,448.0으로 증가하였으며, 이는 11.45%의 개선을 의미합니다. 이러한 이득은 속도 성분에서의 17.25% 개선과 정확도 성분에서의 5.95% 개선에 의해 주도되었습니다.
• 경쟁 알고리즘과의 비교: 여러 경쟁적이고 IEEE CEC 수상 경력이 있는 알고리즘들(LSRTDE, BlockEA, mLSHADE-RL, jSO, IEACOP 포함)과의 광범위한 비교에서, DE-2LS는 178,966.5라는 가장 높은 전체 U-score를 달립다. 이 결과는 두 번째로 우수한 알고리즘인 RDEx보다 3.17% 높았으며, 다른 경쟁자들의 평균보다 약 34.43% 더 높은 수치입니다.
• 함수별 성능: DE-2LS는 29개 함수 중 11개에서 최고의 U-score를 기록하여 비교된 모든 알고리즘 중 가장 많은 횟수를 달성했습니다. 특히 수렴 속도 측면에서 강점을 보였으며, 많은 함수에서 경쟁자들보다 더 빠르게 경쟁력 있는 오차 수준에 도달했습니다.

의의 및 주장
본 논문은 정교하게 설계된 후기 단계 국소 탐색 전략이 전역 탐색 능력을 해치지 않으면서도 강력한 베이스라인 DE 알고리즘의 성능을 크게 향상시킬 수 있음을 입증한다고 주장합니다. 저자들은 원래의 RDEx 엔진을 보존하면서 경량화된 예산 제어 방식의 다듬기 메커니즘을 추가하는 "해를 끼치지 않는(do no harm)" 설계 원칙이 수렴 속도와 최종 목적 품질을 모두 개선하는 데 효과적임을 강조합니다. 결과는 제안된 매끄러운 EB-rate 제어와 가드형 국소 탐색이, 특히 느린 수렴에 페널티를 부여하는 U-score 평가 체계 하에서 탐색(exploration)과 활용(exploitation) 사이의 견고한 균형을 제공한다는 것을 시사합니다. 재현성을 지원하기 위해 DE-2LS의 소스 코드는 공개되었습니다.