MCS 알고리즘

MCS algorithm
A cartoon centipede reads books and types on a laptop.
그림 1: 2차원 로젠브록 기능에 적용된 MCS 알고리즘(로컬 검색 제외)글로벌 최소 m = 0 은, y)=( ,) )}에 위치한다 MCS는 21개 기능 평가에서 약의 위치를 식별한다.21개의 추가 평가 후 최적 값은 개선되지 않고 알고리즘은 종료된다.잠재적 미니마 주위에 표본의 밀집 군집화를 관찰하십시오. 이 효과는 현지 검색을 적절히 사용함으로써 크게 감소할 수 있다.
no alt
그림 2: 4개의 로컬 미니마(x 로 Himmelblau 기능에 적용된 MCS(로컬 검색 제외) 여기서 )= 0

다단계 좌표 검색(MCS)은 함수 값만 사용하여 바운드 제약 글로벌 최적화를 위한 효율적인[1] 알고리즘이다.[2]

이를 위해 n차원 검색 공간은 비절연 하이퍼큐브(상자) 집합으로 표현된다.그런 다음 박스(및 그 이웃들)의 대표 지점에 있는 함수의 값과 상자의 크기에 따라 축 평면을 따라 상자들을 반복적으로 분할한다.이 두 가지 분할 기준이 합쳐져 큰 상자를 분할하여 글로벌 검색을 형성하고, 함수 값이 좋은 영역을 분할하여 로컬 검색을 형성한다.

또한 함수의 (다차원) 2차적 보간물과 라인 검색을 결합한 로컬 검색을 사용하여 알고리즘의 성능을 높일 수 있다(로컬 검색이 포함된 MCS). 이 경우 일반 MCS는 시작(초기) 포인트를 제공하는 데 사용된다.로컬 검색에서 제공하는 정보(목표 함수의 로컬 미니마)는 최적기에 다시 공급되고 분할 기준에 영향을 미침으로써 로컬 미니마 주변의 샘플 클러스터링이 감소하고 수렴 속도가 빨라지며 정밀도가 높아진다.

단순화된 워크플로우

MCS 작업흐름은 그림 1과 2에 시각화되어 있다.알고리즘의 각 단계는 네 단계로 나눌 수 있다.

  1. 분할할 수 있는 잠재적 후보(마그네타, 두껍음)를 식별하십시오.
  2. 분할점의 최적 분할 방향과 예상 최적 위치(녹색)를 확인한다.
  3. 분할 지점에서 목표 기능을 평가하거나 이미 계산된 집합에서 복구하십시오. 인접한 상자를 분할할 때 현재 분할점에 이미 도달한 경우 후자가 적용된다.
  4. 분할점에서 목표 함수의 값을 기준으로 새 상자(마젠타, 얇음)를 생성한다.

각 단계에서 임시 노란색 후광이 있는 녹색 지점은 박스의 고유한 기준점이며, 각 박스는 목적의 연관 가치, 즉 박스의 기준점에서 그것의 가치를 가진다.

상자를 분할할지 여부를 결정하기 위해 두 개의 분리된 분할 기준을 사용한다.첫 번째 것은 등급별로 나누어서, 너무 자주 쪼개지지 않은 큰 상자들이 결국 쪼개지게 된다.만약 그것이 적용된다면, 분할점은 분할되는 옆면 길이의 고정된 부분에서 쉽게 결정된다.두 번째 것은 기대 이득에 의해 분할되며, 단일 좌표를 따라 국소적인 1차원 포물선 2차 모델(대략선)을 사용한다.이 경우 분할점은 라인 세그먼트를 따라 대리모의 최소치로 정의되며 보간 값(목적의 참 값에 대한 대리 역할)이 현재 가장 잘 추출된 함수 값보다 낮은 경우에만 상자가 분할된다.

수렴

알고리즘은 글로벌 미니마이저의 인접 지역에서 객관적인 기능이 지속되는 경우 장기적으로 글로벌 최소치(즉, 함수 평가 횟수와 검색 깊이가 임의로 큰 경우)로 수렴할 것을 보장한다.이는 어떤 박스가 결국 임의로 작아질 것이라는 사실에서 따르며, 따라서 함수 평가의 횟수가 무한대로 증가함에 따라 표본 사이의 간격은 0이 되는 경향이 있다.

재귀적 구현

MCS는 나무의 도움을 받아 효율적인 재귀적 방식으로 구현되도록 설계되었다.이 접근방식으로 필요한 메모리 양은 샘플링 포인트가 명시적으로 저장되지 않기 때문에 문제 치수성과 무관하다.대신 각 표본의 좌표 하나만 저장되고 상자의 이력을 다시 루트(초기 상자)로 추적하여 나머지 좌표를 복구할 수 있다.이 방법은 저자들에 의해 제안되어 원래의 구현에 사용되었다.[2]

참조

  1. ^ Rios, L. M.; Sahinidis, N. V. (2013). "Derivative-free optimization: a review of algorithms and comparison of software implementations". Journal of Global Optimization. 56 (3): 1247–1293. doi:10.1007/s10898-012-9951-y. hdl:10.1007/s10898-012-9951-y.
  2. ^ a b Huyer, W.; Neumaier, A. (1999). "Global Optimization by Multilevel Coordinate Search". Journal of Global Optimization. 14 (4): 331–355. doi:10.1023/A:1008382309369.

외부 링크