파이썬으로 stochastic hill climbing

stochastic hill climbing은 최적화 알고리즘입니다.

검색 프로세스의 일부로 임의성을 사용합니다. 따라서 알고리즘은 다른 로컬 검색 알고리즘이 제대로 작동하지 않는 비선형 목적 함수에 적합합니다.

또한 로컬 검색 알고리즘으로, 단일 솔루션을 수정하고 로컬 최적값을 찾을 때까지 검색 공간의 상대적으로 로컬 영역을 검색합니다. 이는 단일 모드 최적화 문제 또는 전역 최적화 알고리즘 적용 후 사용하기에 적합하다는 것을 의미합니다.

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

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

  • hill climbing은 함수 최적화를 위한 확률적 로컬 검색 알고리즘입니다.
  • Python에서 hill climbing 알고리즘을 처음부터 구현하는 방법.
  • hill climbing 알고리즘을 적용하고 알고리즘의 결과를 검사하는 방법.

튜토리얼 개요

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

  1. hill climbing 알고리즘
  2. hill climbing 알고리즘 구현
  3. hill climbing 알고리즘 적용 예

hill climbing 알고리즘

확률적 hill climbing 알고리즘은 확률적 로컬 검색 최적화 알고리즘입니다.

초기 지점을 입력으로 사용하고 단계 크기를 사용하며, 여기서 단계 크기는 검색 공간 내의 거리입니다.

알고리즘은 초기 점을 현재 최상의 후보 솔루션으로 사용하고 제공된 점의 단계 크기 거리 내에 새 점을 생성합니다. 생성된 점이 평가되고 현재 점과 같거나 같으면 현재 점으로 간주됩니다.

새로운 포인트의 생성은 종종 확률적 hill climbing이라고 하는 무작위성을 사용합니다. 이는 알고리즘이 검색의 일부로 반응 표면의 울퉁불퉁하거나, 잡음이 있거나, 불연속적이거나, 기만적인 영역을 건너뛸 수 있음을 의미합니다.

확률적 hill climbing은 오르막 동작 중에서 무작위로 선택합니다. 선택 확률은 오르막 이동의 가파른 정도에 따라 달라질 수 있습니다.

— 페이지 124, 인공 지능: 현대적인 접근 방식, 2009.

동일한 평가를 가진 여러 점을 수용하는 것이 중요한데, 이는 알고리즘이 반응 표면의 평평한 영역과 같이 검색 공간을 계속 탐색할 수 있도록 하기 때문입니다. 무한 루프를 피하기 위해 이러한 소위 “옆으로“움직임에 제한을 두는 것도 도움이 될 수 있습니다.

오르막 이동이 없을 때 항상 옆으로 이동을 허용하면 알고리즘이 어깨가 아닌 평평한 로컬 최대값에 도달할 때마다 무한 루프가 발생합니다. 한 가지 일반적인 해결책은 허용되는 연속 옆 이동 횟수를 제한하는 것입니다. 예를 들어, 최대 100개의 연속 횡보 이동을 허용할 수 있습니다.

— 페이지 123, 인공 지능: 현대적인 접근 방식, 2009.

이 프로세스는 최대 기능 평가 횟수 또는 지정된 기능 평가 수 내에 개선 없음과 같은 중지 조건이 충족될 때까지 계속됩니다.

이 알고리즘은 응답 표면의 언덕을 (확률적으로) 로컬 최적으로 올라간다는 사실에서 그 이름을 따왔습니다. 이것은 목적 함수를 최대화하는 데만 사용할 수 있다는 것을 의미하지는 않습니다. 그것은 단지 이름 일뿐입니다. 사실, 일반적으로 함수를 최대화하는 대신 최소화합니다.

hill climbing 검색 알고리즘 (가장 가파른 오르막 버전) […] 단순히 가치가 증가하는 방향, 즉 오르막으로 지속적으로 이동하는 루프입니다. 더 높은 값을 갖는 이웃이 없는 “피크”에 도달하면 종료됩니다.

— 페이지 122, 인공 지능: 현대적인 접근 방식, 2009.

로컬 검색 알고리즘으로서 로컬 최적에 갇힐 수 있습니다. 그럼에도 불구하고 여러 번 다시 시작하면 알고리즘이 전역 최적값을 찾을 수 있습니다.

랜덤 재시작 hill climbing […] 목표는 발견될 때까지 무작위로 생성된 초기 상태에서 일련의 hill climbing 검색을 수행합니다.

— 페이지 124, 인공 지능: 현대적인 접근 방식, 2009.

단계 크기는 검색 공간에서 더 나은 주변 지점을 찾을 수 있을 만큼 충분히 커야 하지만 검색이 로컬 최적이 포함된 영역 밖으로 이동할 정도로 크지 않아야 합니다.



hill climbing 알고리즘 구현

글을 쓰는 시점에서 SciPy 라이브러리는 확률적 hill climbing의 구현을 제공하지 않습니다.

그럼에도 불구하고 우리는 그것을 스스로 구현할 수 있습니다.

먼저 목적 함수와 각 입력 변수의 한계를 목적 함수로 정의해야 합니다. 목적 함수는 objective() 라는 이름을 지정할 파이썬 함수입니다. 범위는 변수의 최소값과 최대값을 정의하는 각 입력 변수에 대해 하나의 차원이 있는 2D 배열입니다.

예를 들어, 1차원 목적 함수와 범위는 다음과 같이 정의됩니다.

다음으로, 초기 솔루션을 문제 범위 내의 임의의 점으로 생성 한 다음 목적 함수를 사용하여 평가할 수 있습니다.

이제 “n_iterations“로 정의된 알고리즘의 미리 정의된 반복 횟수(예: 100 또는 1,000)를 반복할 수 있습니다.

알고리즘 반복의 첫 번째 단계는 단계를 수행하는 것입니다.

이를 위해서는 검색 공간의 경계에 상대적인 미리 정의된 “step_size” 매개 변수가 필요합니다. 평균이 현재 지점이고 표준 편차가 “step_size“로 정의되는 가우스 분포로 무작위 단계를 수행합니다. 즉, 수행 된 단계의 약 99 %가 현재 지점의 (3 * step_size) 이내에있게됩니다.

우리는 이런 식으로 조치를 취할 필요가 없습니다. 0과 단계 크기 사이의 균일 분포를 사용할 수 있습니다. 예를 들어:

다음으로 목적 함수를 사용하여 새 후보 솔루션을 평가해야 합니다.

그런 다음 이 새로운 포인트에 대한 평가가 현재 최고 포인트와 같거나 더 나은지 확인하고, 그렇다면 현재 최고 포인트를 이 새 포인트로 바꿔야 합니다.


이 hill climbing 알고리즘을 목적 함수의 이름, 각 입력 변수의 한계, 총 반복 및 단계를 인수로 사용하고 찾은 최상의 솔루션과 평가를 반환하는 재사용 가능한 함수로 구현할 수 있습니다.

이제 Python에서 hill climbing 알고리즘을 구현하는 방법을 알았으므로 이를 사용하여 목적 함수를 최적화하는 방법을 살펴보겠습니다.


hill climbing 알고리즘 적용 예

이 섹션에서는 hill climbing 최적화 알고리즘을 목적 함수에 적용합니다.

먼저 목적 함수를 정의해 보겠습니다.

경계 [-5, 5]가 있는 간단한 1차원 x^2 목적 함수를 사용합니다.

아래 예제에서는 함수를 정의한 다음 입력값 그리드에 대한 함수의 응답 표면의 선 플롯을 만들고 f(0.0) = 0.0에서 최적값을 빨간색 선으로 표시합니다.

예제를 실행하면 목적 함수의 선 그림이 생성되고 함수 optima가 명확하게 표시됩니다.

최적값이 빨간색 파선으로 표시된 목적 함수의 선 플롯

최적값이 빨간색 파선으로 표시된 목적 함수의 선 플롯

다음으로 hill climbing 알고리즘을 목적 함수에 적용 할 수 있습니다.

먼저 의사 난수 생성기를 시드합니다. 이것은 일반적으로 필요하지 않지만이 경우 알고리즘을 실행할 때마다 동일한 결과 (동일한 난수 시퀀스)를 얻도록하여 나중에 결과를 플롯 할 수 있도록하고 싶습니다.

다음으로 검색 구성을 정의할 수 있습니다.

이 경우 알고리즘을 1,000회 반복하고 단계 크기 0.1을 사용합니다. 단계를 생성하기 위해 가우스 함수를 사용하고 있다고 가정하면 이는 취해진 모든 단계의 약 99%가 주어진 지점의 (0.1 * 3) 거리 내에 있음을 의미합니다(예: 3개의 표준 편차).

다음으로 검색을 수행하고 결과를보고 할 수 있습니다.

이 모든 것을 함께 묶어 전체 예제가 아래에 나열되어 있습니다.

예제를 실행하면 반복 횟수, 함수에 대한 입력값, 개선이 감지될 때마다 목적 함수의 응답 변수 등 검색 진행률이 보고됩니다.

검색이 끝나면 최상의 솔루션이 발견되고 평가가보고됩니다.

이 경우 알고리즘의 1,000회 반복에 비해 약 36개의 개선 사항과 f(0.0) = 0.0으로 평가되는 최적 입력 0.0에 매우 가까운 솔루션을 볼 수 있습니다.

개선이 있을 때마다 최상의 솔루션 평가의 변화를 보여주는 선 그림으로 검색 진행률을 검토하는 것은 흥미로울 수 있습니다.

개선이있을 때마다 목적 함수 평가를 추적하고 이 점수 목록을 반환하도록 hillclimbing()을 업데이트 할 수 있습니다.

그런 다음 이러한 점수의 선 그림을 만들어 검색 중에 발견된 각 개선에 대한 목적 함수의 상대적 변화를 확인할 수 있습니다.

이를 함께 묶어 검색을 수행하고 검색 중에 향상된 솔루션의 목적 함수 점수를 플로팅하는 전체 예가 아래에 나열되어 있습니다.

예제를 실행하면 이전과 같이 검색이 수행되고 결과가 보고됩니다.

hill climbing 검색 중 각 개선에 대한 목적 함수 평가를 보여주는 선 그림이 생성됩니다. 검색 중에 목적 함수 평가에 대한 약 36개의 변경 사항을 볼 수 있으며, 알고리즘이 최적에 수렴함에 따라 처음에는 큰 변화가 있고 검색 끝으로 갈수록 매우 작거나 감지할 수 없는 변화가 있습니다.

언덕 오르기 검색 중 각 개선에 대한 목적 함수 평가의 선 그림

hill climbing 검색 중 각 개선에 대한 목적 함수 평가의 선 그림

목적 함수가 1차원이라는 점을 감안할 때 위에서 했던 것처럼 반응 표면을 플로팅하는 것은 간단합니다.

검색 중에 발견된 최상의 후보 솔루션을 응답 표면의 점으로 플로팅하여 검색 진행률을 검토하는 것은 흥미로울 수 있습니다. 반응 표면을 따라 최적 값으로 이어지는 일련의 점을 예상합니다.

이는 먼저 hillclimbing() 함수를 업데이트하여 검색 중에 있는 각 최상의 후보 솔루션을 추적한 다음 최상의 솔루션 목록을 반환하여 달성할 수 있습니다.

그런 다음 목적 함수의 응답 표면의 플롯을 만들고 이전과 같이 최적값을 표시할 수 있습니다.

마지막으로, 검색에서 찾은 후보 솔루션의 시퀀스를 검은 점으로 플로팅할 수 있습니다.

이를 함께 묶어 목적 함수의 응답 표면에 개선된 솔루션의 시퀀스를 플로팅하는 전체 예는 다음과 같습니다.