기술 요약: MO-ELA

문제 정의

자동 알고리즘 선택(Automated Algorithm Selection, AAS)은 단일 목적(single-objective, SO) 최적화 분야에서 성숙한 영역으로, 머신러닝 모델이 "탐색적 경관 분석(exploratory landscape analysis, ELA)" 특징을 기반으로 특정 문제 인스턴스에 대해 가장 성능이 좋은 알고리즘을 예측합니다. 그러나 연속 다목적(multi-objective, MO) 최로 최적화 영역에서는 가용 가능한 특징의 스펙트럼이 희소합니다. 기존 방식들은 각 목적 함수에 대해 개별적으로 SO 특징을 계산하는 데 의존하는 경우가 많은데, 이는 목적 함수 간의 복잡한 상호작용을 포착하지 못하거나, 제약이 없는(박스 제약이 있는) 연속 문제에 직접 적용할 수 없는 제약된 MO 특징에 의존한다는 한계가 있습니다. 따라서 박스 제약이 있는 연속 다목적 최적화 문제(MOP)의 경관을 특성화하기 위해 설계된 엄격하고 상호 보완적인 특징 세트가 필요합니다.

방법론

저자들은 이-목적(bi-objective) 문제를 위한 226개, 삼-목적(tri-objective) 문제를 위한 233개의 새로운 특징 세트인 MO-ELA를 제안합니다. 이 특징들은 결정 공간(decision space)과 목적 공간(objective space) 모두에서 무작лу(random) 샘플링된 점들을 활용하여 지배 관계(dominance relationships)와 다양한 구조적 분석을 통해 도출되었습니다. 특징들은 다섯 가지의 뚜렷한 그룹으로 분류됩니다:

1. 비지배 정렬(Non-Dominated Sorting, NDS) 기반 특징:

   • 비지배 정렬 절차(NSGA-II에서 영감을 얻음)를 사용하여 샘플을 계층($L_1, L_2, \dots$)으로 분할합니다.
   • 비지배 점의 개수, 계층의 수, 계층당 평균 점의 개수와 같은 메트릭을 계산합니다.
   • 첫 다섯 개 계층에 대해 하이퍼볼륨(Hypervolume, HV) 및 Solow-Polasky(SP) 측도를 계산합니다.
   • 계층에 따른 HV 값에 대해 다항 회귀(차수 1–4)를 적합시켜 파레토 프런트 분포의 비선형성을 포착하며, $R^2$를 특징으로 사용합니다.

2. 비지배 점의 기술 통계:

   • 첫 번째 비지배 계층($L_1$)의 목적 벡터에 대해 통계적 측정치(최솟값, 최댓값, 평균, 표준편차)를 적용합니다.
   • 목적 함수 간의 쌍별 스피어만 상관계수(Spearman correlations)와 이-목적 케이스에서의 표준편차 절대 차이를 포함합니다.

3. PCA 기반 특징:

   • 세 가지 세트(결정 공간 점 $X$, 목적 공간 점 $Y$, 그리고 비지배 계층의 결합 세트 $XY$)에 대해 주성분 분석(PCA)을 수행합니다.
   • 각 세트의 주성분으로부터 최소, 최대, 평균 설명 분산을 추출합니다.

4. 그래프 기반 특징:

   • 결정 공간과 목적 공간 모두에서 비지배 계층 $L_1$을 기반으로 그래프를 구축합니다.
   • MST 및 kNN 그래프: 결정 공간($G_D$)과 목적 공간($G_O$)에서 최소 신장 트리(Minimum Spanning Tree, MST) 및 k-최근접 이웃(k-Nearest Neighbor, kNN) 그래프($k=1$)를 구축합니다.
   • 에지 전이(Edge Transfer): 한 그래프의 에지 구조를 다른 그래프로 전이합니다 (예: 결정 공간의 MST 에지를 목적 공간의 점들에 적용, $G_{D \to O}$로 표기).
   • 메트릭: 에지 가중치(거리), 노드 근접 중심성(closeness centrality), 연결된 노드 간의 각도, 그리고 연결 성분(connected components)의 속성(성분의 수, 성분당 노드 수, 최장 경로)을 계산합니다.
   • 공간 간의 왜곡(distortion)을 포착하기 위해 결정 공간과 목적 공간 그래프 간의 특징 비율을 포함합니다.

5. 그래디언트(Gradient) 기반 특징:

   • 목적 공간의 MST($G^O_{ST}$) 내 연결된 노드들 사이의 변수별 절대 기울기를 계산합니다.
   • 이 기울기들을 모든 목적 함수와 에지에 대해 집계하여 다목적 그래디언트 벡터를 형성하고, 이로부터 최솟값, 최댓값, 표준편차, 평균값을 추출합니다.

실험 설정:

• 벤치마크: BiObjBBOB, ZDT, DTLZ, MPM2에서 유도된 1,165개의 문제 인스턴스로 구성된 포괄적인 세트를 사용하며, 이는 2개 및 3개의 목적 함수와 차원 $d \in \{2, 5, 10, 20\}$를 다룹니다.
• 알고리즘: 세 가지 솔버(NSGA-II, SMS-EMOA, MOEA/D)를 각 인스턴스당 20회씩 실행했습니다.
• AAS 프레임워크: 머신러닝 모델(SVM, XGBoost, Random Forest)을 학습시켜 최적의 솔버를 예측하도록 했습니다. 특징 선택은 가장 영향력 있는 부분 집합을 식별하기 위해 전방-후방 전수 탐색(forward-backward exhaustive search)을 사용하여 수행되었습니다.
• 메트릭: 정규화된 하이퍼볼륨(Normalized Hypervolume, HVN)과 단일 최적 솔버(Single Best Solver, SBS)와 가상 최적 솔버(Virtual Best Solver, VBS) 사이의 격차를 좁히는 상대적 개선도(Relative Improvement, RI)를 사용하여 성능을 평가했습니다.

주요 결과

• 알고리즘 선택 성능: 제안된 특징들은 AAS 성능을 유의미하게 향 향상시켰습니다. 이-목적 문제의 경우, 최적의 선택기(특징 선택이 적용된 XGBoost)는 0.963의 RI를 달성하여 VBS와의 격차를 효과적으로 좁혔습니다. 삼-목적 문제의 경우 0.272의 RI를 달셜성했습니다.
• 특징 기여도: 특징 선택 후, 새로 제안된 MO-ELA 특징들이 빈번하게 상위 기여 특징에 포함되었습니다.
  • 이-목적 문제의 경우, 선택된 32개 특징 중 14개가 새로운 특징이었습니다 (NDS 특징이 주를 이룸).
  • 삼-목적 문제의 경우, 선택된 36개 특징 중 17개가 새로운 특징이었습니다 (kNN 그래프 특징이 주를 이룸).
• 특징 안정성: 특징들은 서로 다른 무작위 샘플 및 샘플 크기에 대해 높은 안정성을 보였습니다. 모든 특징의 평균 쌍별 상관관계는 약 0.8이었으며, 선택된 부분 집합의 경우 거의 1.0에 달했습니다.
• 특징 표현력: 선택된 특징들은 낮은 상호 상관관계(이-목적 평균 ~0.30, 삼-목적 ~0.23)를 보였으며, 이는 이들이 문제 경관의 서로 다른 측면을 포착하고 있음을 나타냅니다.
• 샘플 크기 민감도: 차원 5, 10, 20에서는 샘플 크기 500이 최적의 결과를 냈습니다. 차원 2에서는 샘플 크기 200이 최적이었습니다. 특히, 솔버 실행을 위한 남은 예산이 줄어들더라도 더 큰 샘플 크기가 성능을 향상시킨다는 점은 주목할 만하며, 이는 특징의 표현력이 매우 중요하다는 것을 시사합니다.

의의 및 주장

본 논문은 MO-EDA가 연속 다목적 최적화를 위한 탐색적 경관 특징의 엄격한 확장을 제공한다고 주장합니다. 주요 의의는 다음과 같습니다:

1. 격차 해소: 목적 함수 간의 상호작용과 결정 공간 및 목적 공간의 기하학적 구조를 모두 포착하는 포괄적인 특징 세트를 도입함으로써 MO 문제의 특징 부족 문제를 해결합니다.
2. 유용성 입증: 이 특징들은 단순히 이론적인 것에 그치지 않고, 경험적으로 머신러닝 모델이 문제 인스턴스를 구분하고 최적에 가까운 정확도(이-목적 케이스의 경우 VBS에 근접)로 알고리즘을 선택할 수 있게 합니다.
3. 상호 보완성: 새로운 특징들은 기존의 MO-ELA 특징(Liefooghe et al., 2021)을 보완하며, 특징 선택 과정에서 두 종류가 일관되게 혼합되어 유지되는 것은 서로 다른 특징 그룹이 경관의 서로 다른 필수적 속성을 포착하고 있음을 시사합니다.
4. 실용성: 이 특징들은 비교적 작은 샘플 크기(예: 200–500개 포인트)에서도 안정적이고 효과적이어서, 계산 예산이 제한적인 실제 적용 환경에서도 실용적입니다.

저자들은 이 연구가 초기 단계에 있지만, 이러한 특징들이 문제 구조에 대한 의미 있는 통찰을 제공하며 연속 다목적 최적화를 위한 자동 알고리즘 선택의 최첨단 기술(state-of-the-art)을 유의미하게 향상시킨다고 결론짓습니다.