극단적 최적화

Extremal optimization

극단적 최적화(EO)는 통계물리학 분야에서 자체 조직된 임계성의 Bak-Sneppen 모델에서 영감을 받은 최적화 휴리스틱이다.이 경험적 접근법은 처음에 최적화 영역에서 기능하는 것으로 입증되었지만, 여행 중인 판매원 문제 및 스핀 안경과 같은 조합 최적화 문제를 다루기 위해 설계되었다.

자기조직적 중요성과의 관계

자기조직적 중요성(SOC)은 유도체로서 임계점을 갖는 역동적 시스템의 종류를 기술하기 위한 통계물리학 개념이다.구체적으로는 시스템의 최고 규모에 이르는 변화와 소멸의 눈사태를 통해 진화하는 비균형 시스템이다.SOC는 경관 형성, 지진, 진화, 쌀과 모래 더미의 세분화된 역학 등 이러한 폭발적 현상을 가진 일부 자연 시스템의 역학을 지배한다고 한다.여기서 특별히 관심을 가지는 것은 SOC의 Bak-Sneppen 모델이 있는데, 이는 균형이 깨진 (멸종 사건)을 통해 진화를 설명할 수 있기 때문에 진화를 자체 조직화된 임계 과정으로 모델링할 수 있다.

계산 복잡성과의 관계

퍼즐의 또 다른 부분은 계산 복잡성에 관한 연구인데, 특히 NP 완성 문제에서 거의 최적인 해결책이 널리 분산되고 검색 공간의 장벽에 의해 분리되어 국소 검색 알고리즘이 막히거나 심각하게 방해되는 중요한 지점들이 존재한다는 것이 입증되었다.Stefan Boettcher와 Allon Percus에 의한 극단적 최적화의 발전으로 이어지는 것은 Bak과 Sneppen에 의한 진화적 자가 조직된 임계 모델과 결합 최적화 문제에서의 임계점에 대한 관찰이었다.

테크닉

EO는 조합 최적화 문제에 대한 로컬 검색 알고리즘으로 설계되었다.EO는 후보 솔루션 모집단과 함께 작동하는 유전 알고리즘과 달리 단일 솔루션을 진화시켜 최악의 구성요소를 국소적으로 수정한다.이를 위해서는 개별 솔루션 구성요소에 품질 측정("피트니스")을 할당할 수 있는 적절한 표현을 선택해야 한다.이것은 객관적 기능에 대한 집합적 평가에 기초하여 솔루션의 모든 구성요소에 동등성을 부여하는 개미 군집 최적화 및 진화적 계산과 같은 전체적인 접근방식과는 다르다.알고리즘은 임의로 생성하거나 다른 검색 프로세스에서 파생될 수 있는 초기 솔루션으로 초기화된다.

이 기술은 정교하게 다듬어진 탐색이며, 피상적으로 언덕 등반(현지 탐색) 기법과도 닮았다.좀 더 자세한 검사를 통해 몇 가지 흥미로운 원칙이 드러나며, 이는 적용가능성과 심지어 더 광범위한 모집단 기반 접근방식(진화 연산 및 인공 면역 시스템)과 유사성을 가질 수 있다.이 알고리즘의 지배 원리는 저품질 구성요소를 선별적으로 제거하고 무작위로 선택된 구성요소로 대체함으로써 개선되는 것이다.이것은 분명히 더 나은 해결책을 만들기 위해 좋은 해결책을 선택하는 필수적인 진화 연산 알고리즘인 유전 알고리즘과 상충된다.

이 간단한 원칙의 결과적 역학관계는 첫째, 강력한 힐 클라이밍 검색 행동이고, 둘째, 다중 리스타트 검색과 유사한 다양성 메커니즘이다.시간 경과에 따른 전체론적 솔루션 품질(알고리즘 반복)을 그래프로 표시하면, 품질 충돌(아발란치)에 따른 개선 기간을 구두점 평형에서 설명하는 방식으로 매우 많이 보여준다.알고리즘이 로컬 최적에서 벗어나 다른 로컬 검색 절차와 구별되도록 허용하는 것은 검색 공간의 이러한 충돌 또는 극적인 점프다.이러한 구두점-균형 행동은 "설계" 또는 "하드 코드화"될 수 있지만, 이는 알고리즘에 기초하는 음-구성요소-선택 원리의 긴급한 효과라는 점을 강조해야 한다.

EO는 주로 그래프 파티셔닝, 여행 세일즈맨 문제 등과 같은 결합 문제뿐만 아니라 스핀글라스 같은 통계 물리학의 문제에도 적용되어 왔다.

테마 및 응용 프로그램의 다양성

일반화 극한 최적화(GEO)는 비트의 절대 변화율이나 전체론적 솔루션 품질에 대한 비트 기여도에 의해 구성요소 품질이 결정되는 비트 문자열에서 작동하도록 개발되었다.이 작업에는 엔지니어링 문제 영역뿐만 아니라 표준 기능 최적화 문제에 대한 적용이 포함된다.EO와 유사한 또 다른 확장은 연속극단최적화(CEO)이다.

EO는 개미 군집 최적화를 사용한 후 국부적 검색으로 사용될 뿐만 아니라 이미지 래스터레이션에도 적용되었다.EO는 복잡한 네트워크의 구조를 식별하기 위해 사용되어 왔다.EO는 다중 표적 추적 문제에 사용되어 왔다.마지막으로, 선택을 제어하는 데 사용되는 확률 분포를 조사하는 작업이 수행되었다.

참고 항목

참조

외부 링크