패턴 검색(최적화)

패턴 검색(직접 검색, 파생상품 없는 검색 또는 블랙박스 검색이라고도 함)은 구배가 필요 없는 수치 최적화 방법의 계열이다.그 결과, 연속적이거나 차별화되지 않는 기능에 사용할 수 있다.그러한 패턴 검색 방법 중 하나가 '융합(conversence)'(아래 참조)인데, 이는 양성 기반 이론에 바탕을 두고두고 있다.최적화는 가능성의 다차원 분석 공간에서 최상의 일치(오류 값이 가장 낮은 솔루션)를 찾으려고 시도한다.

역사

'패턴 서치'라는 이름은 후크와 지브스가 만들었다.^[1]초기에는 단순한 변종이 로스 알라모스 국립 연구소에서 일했을 때 페르미와 메트로폴리스에 기인한다.다비던은 다음과 같이 기술하고 있다.^[2]

그들은 동일한 크기의 단계별로 한 번에 하나의 이론적 매개변수를 변화시켰고, 그러한 한 매개변수의 증가나 감소가 실험 데이터에 대한 적합성을 추가로 개선하지 않을 경우, 단계 크기를 절반으로 줄이고 단계가 충분히 작은 것으로 간주될 때까지 과정을 반복했다.

수렴

융합은 유 전 회장이 제안한 패턴 검색 방식으로, 양성 기반 이론을 이용해 수렴한다는 것을 증명했다.^[3]이후 토르크존, 라고리아스, 공저자는^[4][5] 양기준 기법을 사용하여 특정 종류의 함수에 대해 또 다른 패턴-탐색법의 정합성을 입증했다.이러한 등급 외에 패턴 검색은 일부 문제에 대해 유용한 대략적인 해결책을 제공할 수 있지만 다른 문제에서는 실패할 수 있는 경험적 발견이다.이러한 등급 외에 패턴 검색은 솔루션으로 수렴되는 반복적인 방법이 아니다. 실제로 패턴 검색 방법은 비교적 길들여진 일부 문제에 대해 비역점적 지점으로 수렴할 수 있다.^[6][7]

참고 항목

• 골든섹션 검색은 단차원 검색공간에 한해 검색범위가 좁아지는 PS와 개념적으로 닮았다.
• 넬더-미드 방법 aka.심플렉스 방식은 다차원 검색공간의 검색범위를 좁히는 점에서 개념적으로 PS와 유사하지만, n차원 검색공간의 경우 n+1점을 유지함으로써 그렇게 하는 반면, PS 방식은 2n+1점(각 차원의 중앙점과 2점)을 계산한다.
• 루우스-자콜라 샘플은 현재 위치를 둘러싼 균일한 분포에서 추출되며 샘플링 범위를 기하급수적으로 감소시키는 간단한 공식을 사용한다.
• 무작위 검색은 현재 위치를 둘러싸고 있는 하이퍼바이저에서 표본을 추출하는 최적화 방법의 관련 제품군이다.
• 무작위 최적화는 현재 위치를 둘러싼 정규 분포로부터 표본을 추출하는 최적화 방법의 관련 제품군이다.

참조