극값 최적화(EO)는 조합 최적화를 위한 메타휴리스틱 알고리즘으로, 1999년 슈테판 뵈트허(Stefan Boettcher)와 앨런 G. 퍼커스(Allon G. Percus)가 도입했다. 이는 자기조직화 임계성에 대한 박-스네펜(Bak-Snppen) 모델에서 영감을 얻었으며, 이 모델은 자연계의 시스템이 가장 적합하지 않은 구성 요소를 반복적으로 제거함으로써 임계 상태로 진화하는 방식을 설명한다. 최적화에서 EO는 이진 또는 값이 있는 변수 집합에서 후보 해를 구성한 다음, 지역 적합도가 가장 낮은 변수를 반복적으로 선택하여 무작위 값으로 대체함으로써 문제를 해결하며, 편향된 극값 과정을 통해 해 공간을 탐색한다.
이 알고리즘은 단순성과 기울기 정보에 의존하지 않고 어려운 문제에 대해 고품질의 해를 얻는 능력으로 주목할 만하다. 이는 진화 계산 방법의 더 넓은 부류에 속하지만, 개체군 재생산과 교차를 사용하는 유전 알고리즘과는 다르다. 대신 EO는 단일 해를 사용하고 멱법칙 선택 확률을 통해 작동하여 해 공간에서 때때로 큰 도약을 가능하게 한다. 이러한 확률적 행동은 지역 최적점을 벗어나는 데 도움이 되며, 특히 외판원 문제, 그래프 분할, 스핀 유리 바닥 상태 문제와 같은 문제에서 최적에 가까운 결과를 자주 발견한다.
역사적 발전
이 방법은 1999년 뵈트허와 퍼커스에 의해 처음 발표되었으며, Physical Review Letters 저널에 "극값 최적화: 공진화에서 파생된 방법"이라는 제목으로 게재되었다. 그들의 연구는 모래 언덕과 생물학적 생태계와 같은 자연계의 시스템이 성과가 낮은 요소를 제거함을 통해 임계 상태로 자기 조직화한다는 관찰에서 동기 부여되었다. 이는 더 복잡하고 개체군 중심적인 접근 방식과 대조되는 단순하고 돌연변이 기반의 휴리스틱 개발로 이어졌다. 초기 실험은 EO가 대규모 NP-난해 문제에서 담금질(시뮬레이티드 어닐링)의 성능과 일치하거나 능가할 수 있음을 입증하여 최적화 문헌에서 그 위치를 확립했다.
도입 이후 EO는 양방향 그래프 분할, 그래프 채색, 그리고 최근에는 기계 학습에서 특징 선택을 포함한 다양한 영역으로 확장되고 적용되었다. 변형들은 제약이 있는 문제를 처리하고 적응형 확률 분포를 통해 수렴을 개선하는 방법을 제안했다. 또한 EO를 자기조직화 임계성의 역학과 연결하여 그 행동에 대한 이론적 정당성을 제공하는 연구도 있다.
핵심 알고리즘 및 메커니즘
기본 EO 알고리즘은 다음과 같이 작동한다:
- 각 가능한 해가 값이 할당된 변수(또는 스핀) 집합으로 구성된 탐색 공간으로 문제를 정의한다.
- 각 변수에 대해 전체 비용 또는 적합도에 대한 기여도를 기반으로 지역 적합도 값을 계산한다.
- 각 반복에서 지역 적합도가 가장 낮은(최악인) 변수, 즉 극값 변수를 선택한다. 그런 다음 가능한 할당 도메인에서 선택될 수 있는 새 무작위 값을 부여한다.
- 업데이트할 변수를 선택하기 위해 멱법칙에 비례하는 확률 분포가 자주 사용되며, 최악만 선택하는 방식이 과정을 함정에 빠뜨릴 수 있으므로 이를 피한다. 순위 r(여기서 r=1이 최악)인 변수의 일반적인 선택 확률은 p(r) ~ r^-τ이며, τ는 일반적으로 약 1 정도의 값으로 설정된다.
- 각 업데이트 후 영향을 받는 변수의 지역 적합도를 다시 계산하고, 고정된 반복 횟수 또는 중지 기준이 충족될 때까지 과정을 반복한다.
주목할 만한 특징은 EO가 명시적인 지역 탐색 단계나 언덕 오르기를 사용하지 않는다는 점이다. 대신 단일 돌연변이와 타우 매개변수가 탐험과 활용 사이의 균형을 제공한다. τ가 작을수록 더 무작위적인 변화를 유도하고, τ가 클수록 최악 중에서도 가장 나은 것을 선택하는 데 편향되어 소수의 나쁜 구성 요소만 문제를 일으킬 때 유용할 수 있다. 최종 해의 품질은 실행 중 어느 시점에서든 관찰된 가장 높은 지역 적합도 값이며, 이는 종종 추적된다.
컴퓨팅 시스템에서의 응용
EO는 다양한 최적화 문제에 적용되어 왔다. Artificial intelligence 분야에서는 신경망 토폴로지를 진화시키고 하이퍼파라미터를 조정하는 데 사용되어 기울기 기반 방법에 대한 대안을 제공했다. Machine learning에서는 특징 선택에 적용되었으며, 여기서 목표는 예측 변수의 최상의 하위 집합을 선택하는 것이다. EO는 특징을 검증 정확도에 대한 기여도를 기반으로 한 지역 적합도를 가진 구성 요소로 취급할 수 있기 때문에 잘 작동한다.
또한 EO는 빈 포장 문제, 작업장 일정 계획, 오류 정정 코드 구축과 같은 조합 최적화 인스턴스를 해결하는 데 자주 사용된다. 또한 병렬 및 분산 시스템 설계, 예를 들어 메이크스팬을 최소화하기 위해 프로세서에 작업을 할당하는 데에도 사용된다. 기울기 정보가 없기 때문에 목적 함수가 불연속적이거나 이산적인 문제에 적용할 수 있다. 그래프 이분할에 적용될 때 EO는 우수한 커뮤니티 탐지 결과를 생성하여 선도적인 그래프 분할 알고리즘과 일치하는 것으로 나타났다.
다른 메타휴리스틱과의 관계
EO는 유전 알고리즘 및 담금질과 가족 유사성을 공유하지만 독특한 메커니즘을 사용한다. 유전 알고리즘은 해의 개체군을 유지하고 재조합과 돌연변이를 사용하는 반면, EO는 단일 해를 사용한다. 담금질은 무작위 섭동으로 전체 해를 수정하고 온도에 따라 변경을 수락하는 반면, EO는 지역 적합도에 따라 최악의 구성 요소만 수정한다. 중요한 차이점은 EO가 수정할 구성 요소를 선택하는 것이 전체 해의 목적 함수 값이 아닌 순위에 기반하여 결정적(또는 멱법칙 무작위)이라는 점이다.
자기조직화 임계성(SOC)과의 이론적 연결은 EO가 자연계에서 볼 수 있는 멱법칙 변동을 재현한다는 것을 의미하며, 이는 다양한 경관 유형에 대한 견고성을 제공한다. 고전적인 벤치마크(외판원 문제) 비교에서 EO는 담금질과 경쟁력이 있지만 종종 더 적은 함수 평가를 요구한다. 실질적으로 구성 요소 적합도의 순위로 이웃이 정의되는 문제의 경우 EO는 간단한 구현으로도 효율적일 수 있다.
확장 및 변형
연구는 많은 변형을 만들어 냈다. 가장 일반적인 것은 타우-EO로, 매개변수 tau가 더 높은 순위의 변수를 선택할 확률을 제어한다. tau의 값과 멱법칙 꼬리의 범위는 일관성을 개선하기 위해 조정될 수 있다. 또 다른 변형은 꼬리에 지터를 도입한 확률적 언덕 오르기이다. 또 다른 접근 방식인 공진화는 상호 작용하는 구성 요소가 있는 문제를 처리하며, 공동 적응에 기반하여 둘 이상의 변수를 돌연변이시킨다. 최근에는 EO가 지역 탐색 휴리스틱과 결합되어 EO 탐색 단계 후 추가 미세 조정을 수행하는 하이브리드 EO를 생성했다.
Deep learning 응용에서 EO의 한 형태는 특히 Neural network 탐색에서 모델 아키텍처를 자동으로 조정하는 데 사용되었지만, 더 복잡한 방법으로 대체되었다. EO는 기울기를 요구하지 않으므로 기울기를 사용할 수 없거나 비용이 많이 드는 모델(예: 미분 불가능한 손실)에 적용할 수 있다. 또한 강화 학습 문제에서 이산 공간을 탐색하는 데 적합하다.
한계 및 공개 연구
EO의 주요 과제 중 하나는 타우 매개변수와 멱법칙의 값 범위를 설정하는 것이다. 잘못 선택된 tau는 수렴 불량이나 혼돈으로 이어질 수 있다. 또한 한 번에 하나의 변수만 수정하기 때문에 매우 제약이 많은 문제나 변수 간 의존성이 있는 문제는 높은 계산 비용을 피하기 위해 적합도를 신중하게 공식화해야 한다.
공개 연구는 EO를 더 적응적으로 만드는 데 초점을 맞추고 있으며, 예를 들어 실행 중에 tau를 추정하거나 tau에 대한 담금질 일정을 사용하는 방법이 있다. 또한 변수에 대한 무작위 값 대체를 선택하는 더 고급 방법을 사용하거나 분산 환경에서 EO를 사용하는 연구도 있다.
EO의 이론적 이해는 다른 메타휴리스틱만큼 성숙하지 않지만, 구현이 간단하고 다양한 어려운 문제에 견고하기 때문에 조합 최적화 및 자연에서 영감을 얻은 컴퓨팅 도구 세트에서 주목할 만한 개념이다. 미래에는 전문 최적화 도구와의 통합이 더 많아지고 실용적인 일정 계획 및 설계를 위한 멱법칙 통계에 대한 추가 연구가 이루어질 가능성이 높다.
주요 연구자 및 영향
원저자인 슈테판 뵈트허와 앨 퍼커스(둘 다 당시 산타페 연구소에 있었음)는 SOC 관점을 최적화에 도입했다. 제록스 팔크 및 버클리 AI 연구를 포함한 다른 그룹의 후속 연구는 이 방법의 프레임워크와 분석을 확장했다. 현대 기계 학습 도구의 최전선에 있지는 않지만 자연에서 영감을 얻은 휴리스틱의 참고 자료로 남아 있으며 진화 계산에 관한 강의 자료에 자주 포함된다.
요약하면, 극값 최적화는 어려운 조합 문제를 근사화하기 위한 미니멀하고 비기울기적이며 확률적인 프레임워크를 제공하며, 구성 요소로 분해될 수 있고 고유한 적합도 값을 가진 문제에 대한 이론적 연구와 응용 모두에서 지속적인 가치가 있다.
한계 및 참고 사항
실용적인 사용을 위해 이 방법을 시도하는 사람들은 이 방법이 전역 최적성을 보장하지 않으며 일부 문제는 선택 확률 분포의 조정이 필요할 수 있음을 인지해야 한다. 적절한 설정으로 간단하면서도 효과적인 최적화 도구가 될 수 있다.