랜덤 검색

Random search

랜덤 검색(RS)은 문제의 구배를 최적화할 필요가 없는 수치 최적화 방법의 집합이며, 따라서 RS는 연속적이지 않거나 미분할 수 없는 함수에 사용할 수 있다.이러한 최적화 방법은 직접 검색, 파생 없음 또는 블랙박스 방식이라고도 합니다.

1953년 앤더슨은 매개변수 검색 공간에서 특정 순서 또는 패턴으로 분포된 일련의 추측을 사용하여 최대 또는 최소 문제를 찾는 방법의 진행률을 검토했다. 예를 들어 기하급수적으로 분포된 간격/스텝이 [1]있는 교란 설계이다.이 검색은 각 파라미터에 대해 순차적으로 진행되며 마지막 시퀀스의 최적의 추측에 따라 반복적으로 조정됩니다.패턴은 모든 매개변수에 대한 그리드(요인) 검색, 각 매개변수에 대한 순차 검색 또는 이 둘의 조합일 수 있습니다.이 방법은 앤더슨의 논문에 기재된 여러 과학자들에 의해 화학 반응의 실험 조건을 선별하기 위해 개발되었다.예시적인 수학적 모델의 일반적인 비선형 회귀를 위한 순차적 절차를 재현하는 MATLAB 코드는 여기에서 찾을 수 있다(FitNGuess @ GitHub).[2]

"랜덤 검색"이라는 이름은 기본적인 수학적 분석과 함께 RS의 초기 프레젠테이션을 한 라스트리긴의[3] 이름에서 유래했다.RS는 현재 위치를 둘러싼 하이퍼스피어에서 샘플링된 서치 공간에서 더 나은 위치로 반복적으로 이동함으로써 작동합니다.

여기서 설명하는 알고리즘은 로컬 랜덤 검색의 일종으로, 모든 반복은 이전 반복의 후보 솔루션에 의존합니다.검색 공간 전체에서 샘플을 추출하는 대체 랜덤 검색 방법(예: 순수 랜덤 검색 또는 균일한 전역 랜덤 검색)이 있지만 이 문서에서는 이러한 방법에 대해 설명하지 않습니다.

랜덤 검색은 하이퍼 파라미터 [4]최적화를 위해 인공신경망에서 사용되어 왔다.

알고리즘.

f: → ℝ을n 최소화할 필요가 있는 적합성 또는 비용 함수라고 하자.서치공간에서 x ℝn a a a a a a a a a a a a a a in in in기본적인 RS 알고리즘은 다음과 같이 설명할 수 있습니다.

  1. 검색 공간에서 임의 위치를 사용하여 x를 초기화합니다.
  2. 종료 기준이 충족될 때까지(예: 수행된 반복 횟수 또는 적절한 적합성에 도달할 때까지) 다음을 반복합니다.
    1. 현재 위치 x를 둘러싼 주어진 반지름의 초공간에서 새 위치 y를 샘플링합니다(예: 참조).Marsaglia의 하이퍼스피어 샘플링 기술).
    2. f(y) < f(x)인 경우 x = y를 설정하여 새 위치로 이동합니다.

변종

비선형 회귀 문제를 예로 사용한 랜덤 검색 체계.목표는 패널티 함수의 값을 최소화하는 것입니다.오른쪽 하단에는 1. 비구조화 랜덤 검색, 2.구조화 랜덤 검색, 3.가우스-뉴턴 알고리즘 및 4.의 몇 가지 방법의 예가 나와 있습니다.Levenberg-Marquardt 알고리즘. 1,2는 구배를 알 필요가 없으며 3,4는 구배를 계산하고 보통 A와 k 파라미터 양쪽에서 동시에 최소화해야 한다(스킴은 k차원만 보여준다).

정말로 랜덤 검색은 순전히 운에 의한 것으로 매우 비용이 많이 드는 것부터 매우 운이 좋은 것까지 다양하지만, 구조화된 랜덤 검색은 전략적입니다.탐색 공간에서 구조화된 샘플링과 함께 많은 RS 변형이 문헌에 소개되었습니다.

  • Friedman-Savage 절차: 초기 추측과 [5]경계 사이에 공백 패턴이 있는 추측 세트를 사용하여 각 모수를 순차적으로 검색합니다.기하급수적으로 분산된 스텝의 예는 MATLAB 코드(그림NGuess @ GitHub)[2]에서 찾을 수 있습니다.이 예제 코드는 Levenberg-Marquardt 알고리즘보다 1~2배 느린 크기를 수렴하며 GitHub에도 예가 제공됩니다.
  • FSSRS(Fixed Step Size Random Search)는 Rastrigin의 기본 알고리즘으로 고정 반지름의 하이퍼스피어에서 표본을 추출합니다.
  • 슈머와 슈타이글리츠의 Optimum Step Size Random Search(OSSRS)는 최적화를 위한 신속한 수렴을 가능하게 하기 위해 하이퍼스피어의 반지름을 최적으로 조정하는 방법에 대한 이론적 연구이다.OSSRS의 실제 실장에서는 반복적인 샘플링에 의해 최적의 반경을 근사할 필요가 있기 때문에 실행에는 비용이 많이 듭니다.
  • 슈머와 Steiglitz의 Adaptive Step Size Random Search(ASSRS)는 하이퍼스피어의 반경을 경험적으로 조정하려고 시도합니다.하나는 현재 공칭 단계 크기를 가진 솔루션과 다른 하나는 더 큰 단계 크기를 가진 새로운 후보 솔루션이 생성됩니다.큰 스텝 사이즈가 새로운 공칭 스텝사이즈가 되는 것은 큰 스텝사이즈가 개선되는 경우 뿐입니다.두 단계가 모두 개선되지 않으면 공칭 단계 크기가 줄어듭니다.
  • Schrack 및 Choit의 ORSS(Optimized Relative Step Size Random Search)는 단순한 지수적 감소로 최적의 단계 크기를 근사합니다.그러나 감소율을 계산하는 공식은 다소 복잡하다.

「 」를 참조해 주세요.

  • 랜덤 최적화는 하이퍼스피어가 아닌 정규 분포에서 표본을 추출하는 최적화 방법 중 밀접하게 관련된 제품군입니다.
  • Luus-Jaakola는 샘플링에서 균일한 분포와 샘플링 범위를 기하급수적으로 감소시키는 간단한 공식을 사용하는 밀접하게 관련된 최적화 방법이다.
  • 패턴 검색은 기하급수적으로 감소하는 단계 크기를 사용하여 검색 공간의 축을 따라 단계를 수행합니다.

레퍼런스

  1. ^ Anderson, R.L. (1953). "Recent Advances in Finding Best Operating Conditions". Journal of the American Statistical Association. 48 (264): 789–798. doi:10.2307/2281072.
  2. ^ a b "GitHub - Jixin Chen/FigNGuess: A Random Search Algorithm for general mathematical model(s) fittings".
  3. ^ a b Rastrigin, L.A. (1963). "The convergence of the random search method in the extremal control of a many parameter system". Automation and Remote Control. 24 (11): 1337–1342. Retrieved 30 November 2021. 1964 translation of Russian Avtomat. i Telemekh pages 1467–1473
  4. ^ Bergstra, J.; Bengio, Y. (2012). "Random search for hyper-parameter optimization". Journal of Machine Learning Research. 13: 281–305.
  5. ^ Friedman, M.; Savage, L.J. (1947). Planning experiments seeking maxima, chapter 13 of Techniques of Statistical Analysis, edited by Eisenhart, Hastay, and Wallis. McGraw-Hill Book Co., New York. pp. 363–372. Retrieved 30 November 2021 – via Milton Friedman from Hoover Institution at Stanford University.
  6. ^ a b Schumer, M.A.; Steiglitz, K. (1968). "Adaptive step size random search". IEEE Transactions on Automatic Control. 13 (3): 270–276. CiteSeerX 10.1.1.118.9779. doi:10.1109/tac.1968.1098903.
  7. ^ Schrack, G.; Choit, M. (1976). "Optimized relative step size random searches". Mathematical Programming. 10 (1): 230–244. doi:10.1007/bf01580669.