함수 최적화를 위한 무작위 검색 및 그리드 검색

함수 최적화를 위해서는 검색 공간을 효율적으로 샘플링하고 좋은 솔루션 또는 최상의 솔루션을 찾기 위한 알고리즘 선택이 필요합니다.

선택할 수 있는 알고리즘은 많지만 문제에 대해 실현 가능하거나 가능한 솔루션 유형에 대한 기준을 설정하는 것이 중요합니다. 이것은 무작위 검색 또는 그리드 검색과 같은 Naive 최적화 알고리즘을 사용하여 달성할 수 있습니다.

Naive 최적화 알고리즘에 의해 달성된 결과는 보다 정교한 최적화 알고리즘을 위한 비교 지점을 생성하고 제공하는 데 계산적으로 효율적입니다. 때로는 Naive 알고리즘이 특히 시끄럽거나 매끄럽지 않은 문제와 도메인 전문 지식이 일반적으로 최적화 알고리즘 선택을 편향시키는 문제에서 최상의 성능을 달성하는 것으로 밝혀졌습니다.

이 튜토리얼에서는 함수 최적화를 위한 Naive 알고리즘을 발견하게 됩니다.

이 자습서를 완료하면 다음을 알 수 있습니다.

  • 함수 최적화 프로젝트에서 Naive 알고리즘의 역할.
  • 함수 최적화를 위한 무작위 검색을 생성하고 평가하는 방법.
  • 함수 최적화를 위한 그리드 검색을 생성하고 평가하는 방법.

튜토리얼 개요

이 자습서는 다음과 같이 세 부분으로 나뉩니다.

  1. 나이브 함수 최적화 알고리즘
  2. 함수 최적화를 위한 무작위 검색
  3. 함수 최적화를 위한 그리드 검색

나이브 함수 최적화 알고리즘

최적화에 사용할 수있는 알고리즘은 여러 가지가 있지만 얻은 결과가 좋은지 어떻게 알 수 있습니까?

이 문제를 해결하는 한 가지 방법은 Naive 최적화 알고리즘을 사용하여 성능의 기준을 설정하는 것입니다.

Naive 최적화 알고리즘은 최적화되는 목적 함수에 대해 아무 것도 가정하지 않는 알고리즘입니다.

아주 적은 노력으로 적용 할 수 있으며 알고리즘에 의해 달성 된 최상의 결과는보다 정교한 알고리즘을 비교하기위한 참조 지점으로 사용될 수 있습니다. 더 정교한 알고리즘이 평균적으로 Naive 알고리즘보다 더 나은 결과를 얻을 수 없다면 문제에 대한 기술이 없으므로 포기해야합니다.

다음과 같이 함수 최적화에 사용할 수 있는 두 가지 Naive 알고리즘이 있습니다. 

  • 무작위 검색
  • 그리드 검색

이러한 알고리즘은 기본적으로 최적화가 검색 문제로 구성될 수 있기 때문에 “검색” 알고리즘이라고 합니다. 예를 들어 목적 함수의 출력값을 최소화하거나 최대화하는 입력값을 찾습니다.

가능한 모든 입력을 열거하는 “철저한 검색“이라는 또 다른 알고리즘이 있습니다. 가능한 모든 입력을 열거하는 것이 가능하지 않기 때문에 실제로는 거의 사용되지 않습니다 (예 : 실행하는 데 너무 많은 시간이 필요함).

그럼에도 불구하고 모든 입력을 적절한 시간 내에 열거하고 평가할 수 있는 최적화 문제를 해결하려면 이것이 기본 전략이 되어야 합니다.

각각에 대해 차례로 자세히 살펴 보겠습니다.



함수 최적화를 위한 무작위 검색

무작위 검색은 무작위 최적화 또는 무작위 샘플링이라고도 합니다.

무작위 검색에는 목적 함수에 대한 무작위 입력값을 생성하고 평가하는 작업이 포함됩니다. 목적 함수의 구조에 대해 아무 것도 가정하지 않기 때문에 효과적입니다. 이는 최적화 전략에 영향을 미치거나 편향될 수 있는 많은 도메인 전문 지식이 있는 문제에 유용할 수 있으며, 직관적이지 않은 솔루션을 발견할 수 있습니다.

… 의사 난수 생성기를 사용하여 설계 공간에 대해 단순히 m 개의 무작위 샘플을 그리는 무작위 샘플링. 랜덤 표본 x를 생성하기 위해 각 변수를 분포와 독립적으로 표본을 추출할 수 있습니다.

— 236페이지, 최적화를 위한 알고리즘, 2019.

랜덤 검색은 또한 신뢰할 수 있는 그래디언트에 의존하는 알고리즘을 야기할 수 있는 검색 공간의 노이즈가 있거나 매끄럽지 않은(불연속적인) 영역을 갖는 매우 복잡한 문제에 대한 최상의 전략일 수 있습니다.

의사 난수 생성기를 사용하여 도메인에서 무작위 샘플을 생성할 수 있습니다. 각 변수에는 잘 정의된 경계 또는 범위가 필요하며 범위에서 균일하게 임의의 값을 샘플링한 다음 평가할 수 있습니다.

무작위 샘플을 생성하는 것은 계산적으로 사소하고 많은 메모리를 차지하지 않으므로 많은 입력 샘플을 생성한 다음 평가하는 것이 효율적일 수 있습니다. 각 샘플은 독립적이므로 공정을 가속화하기 위해 필요한 경우 샘플을 병렬로 평가할 수 있습니다.

아래 예제에서는 간단한 1차원 최소화 목적 함수의 예를 제공하고 100개 입력으로 구성된 무작위 샘플을 생성한 다음 평가합니다. 그런 다음 성능이 가장 좋은 입력이 보고됩니다.

예제를 실행하면 입력 값의 무작위 샘플이 생성되고 이 샘플이 평가됩니다. 그런 다음 가장 실적이 좋은 지점을 식별하고 보고합니다.

참고: 결과는 알고리즘 또는 평가 절차의 확률적 특성 또는 수치 정밀도의 차이에 따라 달라질 수 있습니다. 예제를 몇 번 실행하고 평균 결과를 비교하는 것이 좋습니다.

이 경우 결과가 최적 입력값 0.0에 매우 가깝다는 것을 알 수 있습니다.

목적 함수를 플로팅하고 샘플과 최상의 결과를 표시하도록 예제를 업데이트할 수 있습니다. 전체 예제는 다음과 같습니다.

예제를 다시 실행하면 랜덤 샘플이 생성되고 최상의 결과가 보고됩니다.

그런 다음 목적 함수의 모양, 랜덤 샘플 및 샘플에서 찾은 최상의 결과에 대한 빨간색 선을 보여주는 선 플롯이 생성됩니다.

랜덤 표본을 사용한 1차원 목적 함수의 선 그림

랜덤 표본을 사용한 1차원 목적 함수의 선 그림



함수 최적화를 위한 그리드 검색

그리드 검색은 그리드 샘플링 또는 전체 요인 샘플링이라고도 합니다.

그리드 검색에는 목적 함수에 대해 균일한 그리드 입력을 생성하는 작업이 포함됩니다. 1차원에서 이것은 선을 따라 균등하게 배치된 입력입니다. 2차원에서 이것은 표면을 가로질러 균일하게 간격을 둔 점의 격자가 되고 더 높은 차원의 경우 계속됩니다.

전체 요인 표본 추출 계획은 검색 공간 위에 균일한 간격의 점의 그리드를 배치합니다. 이 방법은 구현하기 쉽고 임의성에 의존하지 않으며 공간을 포함하지만 많은 수의 포인트를 사용합니다.

— 235페이지, 최적화를 위한 알고리즘, 2019.

무작위 검색과 마찬가지로 그리드 검색은 도메인 전문 지식이 일반적으로 특정 최적화 알고리즘의 선택에 영향을 미치는 데 사용되는 문제에 특히 효과적일 수 있습니다. 그리드는 더 많은 주의를 기울일 가치가 있는 검색 공간 영역을 빠르게 식별하는 데 도움이 될 수 있습니다.

샘플 그리드는 일반적으로 균일하지만 반드시 그럴 필요는 없습니다. 예를 들어, log-10 스케일을 균일한 간격으로 사용하여 샘플링을 수행할 수 있습니다.

단점은 그리드의 거칠기가 좋은 솔루션이있는 검색 공간의 전체 영역을 밟을 수 있다는 것인데, 이는 문제에 대한 입력 수 (검색 공간의 차원)가 증가함에 따라 악화되는 문제입니다.

샘플 그리드는 점의 균일 한 분리를 선택한 다음 각 변수를 차례로 열거하고 선택한 분리만큼 각 변수를 증가시켜 생성 할 수 있습니다.

아래 예제에서는 간단한 2차원 최소화 목적 함수의 예를 제공하고 두 입력 변수에 대해 간격이 0.1인 그리드 샘플을 생성한 다음 평가합니다. 그런 다음 성능이 가장 좋은 입력이 보고됩니다.

예제를 실행하면 입력 값의 그리드가 생성되고 이 그리드가 평가됩니다. 그런 다음 가장 실적이 좋은 지점을 식별하고 보고합니다.

참고: 결과는 알고리즘 또는 평가 절차의 확률적 특성 또는 수치 정밀도의 차이에 따라 달라질 수 있습니다. 예제를 몇 번 실행하고 평균 결과를 비교하는 것이 좋습니다.

이 경우 결과가 최적값을 정확히 찾는다는 것을 알 수 있습니다.

목적 함수를 플로팅하고 샘플과 최상의 결과를 표시하도록 예제를 업데이트할 수 있습니다. 전체 예제는 다음과 같습니다.

예제를 다시 실행하면 그리드 샘플이 생성되고 최상의 결과가 보고됩니다.

그런 다음 목적 함수의 형상, 그리드 표본을 검은색 점으로, 표본에서 찾은 최상의 결과를 위한 흰색 별을 보여주는 등고선도가 생성됩니다.

도메인 가장자리의 검은 점 중 일부는 플롯에서 벗어난 것처럼 보입니다. 이것은 우리가 점을 그리는 방법을 선택하는 방법에 대한 아티팩트 일뿐입니다 (예 : 샘플 중앙에 있지 않음).

그리드 표본을 사용한 1차원 목적 함수의 등고선도
그리드 표본을 사용한 1차원 목적 함수의 등고선도



추가 정보

이 섹션에서는 더 자세히 알아보려는 경우 주제에 대한 더 많은 리소스를 제공합니다.

기사


요약

이 자습서에서는 함수 최적화를 위한 Naive 알고리즘을 발견했습니다.

특히 다음 내용을 배웠습니다.

  • 함수 최적화 프로젝트에서 Naive 알고리즘의 역할.
  • 함수 최적화를 위한 무작위 검색을 생성하고 평가하는 방법.
  • 함수 최적화를 위한 그리드 검색을 생성하고 평가하는 방법.
네피리티
No Comments

Sorry, the comment form is closed at this time.