파이썬을 사용한 Dual Annealing 최적화

20 12월

파이썬을 사용한 Dual Annealing 최적화

Dual Annealing은 확률적 글로벌 최적화 알고리즘입니다.

이것은 일반화된 시뮬레이션된 annealing 알고리즘의 구현으로, 시뮬레이션된 annealing의 확장입니다. 또한 시뮬레이션된 annealing 절차가 끝날 때 자동으로 수행되는 로컬 검색 알고리즘과 쌍을 이룹니다.

효과적인 전역 및 로컬 검색 절차의 이러한 조합은 까다로운 비선형 최적화 문제를 위한 강력한 알고리즘을 제공합니다.

이 자습서에서는 Dual Annealing 전역 최적화 알고리즘을 발견합니다.

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

Dual Annealing 최적화는 로컬 검색 알고리즘도 사용하는 시뮬레이션된 annealing의 수정된 버전인 전역 최적화입니다.
파이썬에서 Dual Annealing 최적화 알고리즘 API를 사용하는 방법.
다중 최적으로 전역 최적화 문제를 해결하기 위해 Dual Annealing을 사용하는 예

튜토리얼 개요

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

Dual Annealing이란?
Dual Annealing API
Dual Annealing 예

Dual Annealing이란?

Dual Annealing은 글로벌 최적화 알고리즘입니다.

따라서 비선형 응답 표면을 갖는 목적 함수를 위해 설계되었습니다. 확률적 최적화 알고리즘으로, 검색 과정에서 임의성을 사용하고 검색을 실행할 때마다 다른 솔루션을 찾을 수 있습니다.

Dual Annealing은 시뮬레이션된 annealing 최적화 알고리즘을 기반으로 합니다.

시뮬레이션된 annealing은 후보 솔루션이 임의의 방식으로 수정되고 수정된 솔루션이 현재 후보 솔루션을 확률적으로 대체하도록 수용되는 확률적 hill climbing의 한 유형입니다. 이는 더 나쁜 솔루션이 현재 후보 솔루션을 대체할 수 있음을 의미합니다. 이러한 유형의 교체 확률은 검색 초기에 높으며 “온도”하이퍼 매개 변수에 의해 제어되는 각 반복마다 감소합니다.

Dual Annealing은 고전적인 CSA(시뮬레이션 annealing) 알고리즘의 구현입니다. 이는 1997년 논문 “일반화된 시뮬레이션 annealing 알고리즘과 Thomson 모델에 대한 적용”에 설명된 일반화된 시뮬레이션 annealing(GSA) 알고리즘을 기반으로 합니다.

“빠른 시뮬레이션 annealing”(FSA)의 annealing 일정 (알고리즘 반복에 걸쳐 온도가 감소하는 속도)과 저자의 이름을 딴 대체 통계 절차 “Tsallis 통계“의 확률 론적 수용을 결합합니다.

실험 결과에 따르면 이 일반화된 시뮬레이션된 annealing 알고리즘은 비교된 알고리즘의 클래식 또는 빠른 버전보다 더 나은 성능을 보이는 것으로 나타났습니다.

GSA는 FSA 및 CSA보다 빠르게 수렴할 뿐만 아니라 FSA 및 CSA보다 더 쉽게 로컬 최소값에서 벗어날 수 있습니다.

— 글로벌 최적화를 위한 일반화된 시뮬레이션 annealing: GenSA 패키지, 2013.

시뮬레이션된 annealing의 이러한 수정 외에도, 로컬 검색 알고리즘이 시뮬레이션된 annealing 검색에 의해 발견된 솔루션에 적용될 수 있다.

이는 전역 검색 알고리즘이 최적의 솔루션을 위해 유역(검색 공간의 영역)을 찾는 데 능숙하지만 유역에서 가장 최적의 솔루션을 찾는 데는 종종 부족하기 때문에 바람직합니다. 반면 지역 검색 알고리즘은 유역의 최적을 찾는 데 탁월합니다.

로컬 검색을 시뮬레이션된 annealing 절차와 페어링하면 검색이 찾은 후보 솔루션을 최대한 활용할 수 있습니다.

이제 높은 수준의 Dual Annealing 알고리즘에 익숙해졌으므로 Python에서 Dual Annealing을 위한 API를 살펴보겠습니다.

Dual Annealing API

듀얼 annealing 전역 최적화 알고리즘은 dual_annealing() SciPy 함수를 통해 파이썬에서 사용할 수 있습니다.

이 함수는 목적 함수의 이름과 각 입력 변수의 한계를 검색의 최소 인수로 사용합니다.

1
2
3
...
# perform the dual annealing search
result = dual_annealing(objective, bounds)

검색에 대해 기본값이 있는 여러 가지 추가 하이퍼파라미터가 있지만 검색을 사용자 지정하도록 구성할 수 있습니다.

“maxiter” 인수는 알고리즘의 총 반복 횟수(함수 평가의 총 횟수가 아님)를 지정하며 기본값은 1,000회입니다. 원하는 경우 “maxfun“을 지정하여 총 함수 평가 수를 제한할 수 있으며 기본값은 1,000만 개입니다.

검색의 초기 온도는 “initial_temp” 인수로 지정되며 기본값은 5,230입니다. annealing 공정은 온도가 (initial_temp * restart_temp_ratio) 이하의 값에 도달하면 다시 시작됩니다. 비율은 기본적으로 매우 작은 숫자 2e-05(즉, 0.00002)이므로 재annealing의 기본 트리거는 (5230 * 0.00002) 또는 0.1046의 온도입니다.

또한 이 알고리즘은 기반이 되는 일반화된 시뮬레이션된 annealing과 관련된 하이퍼파라미터에 대한 제어를 제공합니다. 여기에는 기본적으로 2.62(3보다 작은 값이 선호됨)인 “visit” 인수와 새 솔루션을 수락할 가능성을 제어하는 “accept” 인수(기본값은 -5)를 통해 검색 중에 수행할 수 있는 거리가 포함됩니다.

minimize()함수는 기본 하이퍼 매개 변수를 사용하여 로컬 검색을 위해 호출됩니다. 로컬 검색은 하이퍼 매개 변수 이름과 값의 사전을 “local_search_options” 인수에 제공하여 구성할 수 있습니다.

검색의 로컬 검색 구성 요소는 “no_local_search” 인수를 True로 설정하여 비활성화할 수 있습니다.

검색 결과는 사전처럼 속성에 액세스할 수 있는 OptimizeResult 개체입니다. 검색의 성공 여부는 ‘성공‘또는 ‘메시지’키를 통해 액세스 할 수 있습니다.

총 함수 평가 횟수는 ‘nfev‘를 통해 액세스할 수 있으며 검색을 위해 찾은 최적의 입력은 ‘x‘ 키를 통해 액세스할 수 있습니다.

이제 Python의 Dual Annealing API에 익숙해졌으므로 몇 가지 작업 예제를 살펴보겠습니다.

Dual Annealing 예

이 섹션에서는 다중 모드 목적 함수에서 Dual Annealing 알고리즘을 사용하는 예를 살펴보겠습니다.

Ackley 함수는 로컬 검색이 중단될 수 있는 단일 전역 최적값과 여러 로컬 최적값을 갖는 다중 모드 목적 함수의 예입니다.

따라서 전역 최적화 기술이 필요합니다. 이 함수는 전역 최적값이 [0,0]이고 0.0으로 평가되는 2차원 목적 함수입니다.

아래 예제에서는 Ackley를 구현하고 전역 최적값과 다중 국소 최적값을 보여주는 3차원 표면도를 생성합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# ackley multimodal function
from numpy import arange
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D
 
# objective function
def objective(x, y):
 return –20.0 * exp(–0.2 * sqrt(0.5 * (x**2 + y**2))) – exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20
 
# define range for input
r_min, r_max = –5.0, 5.0
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection=‘3d’)
axis.plot_surface(x, y, results, cmap=‘jet’)
# show the plot
pyplot.show()

예제를 실행하면 방대한 수의 국소 최적값을 보여주는 Ackley 함수의 표면도가 생성됩니다.

애클리 멀티모달 함수의 3D 표면도

Dual Annealing 알고리즘을 Ackley 목적 함수에 적용할 수 있습니다.

먼저 검색 공간의 경계를 각 차원에서 함수의 한계로 정의할 수 있습니다.

1
2
3
...
# define the bounds on the search
bounds = [[r_min, r_max], [r_min, r_max]]

그런 다음 목적 함수의 이름과 검색 범위를 지정하여 검색을 적용할 수 있습니다.

이 경우 기본 하이퍼 매개 변수를 사용합니다.

1
2
3
...
# perform the simulated annealing search
result = dual_annealing(objective, bounds)

검색이 완료되면 검색 상태와 수행된 반복 횟수 및 평가에서 찾은 최상의 결과를 보고합니다.

1
2
3
4
5
6
7
8
...
# summarize the result
print(‘Status : %s’ % result[‘message’])
print(‘Total Evaluations: %d’ % result[‘nfev’])
# evaluate solution
solution = result[‘x’]
evaluation = objective(solution)
print(‘Solution: f(%s) = %.5f’ % (solution, evaluation))

이를 함께 묶어 Ackley 목적 함수에 Dual Annealing을 적용하는 전체 예는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# dual annealing global optimization for the ackley multimodal objective function
from scipy.optimize import dual_annealing
from numpy.random import rand
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
 
# objective function
def objective(v):
 x, y = v
 return –20.0 * exp(–0.2 * sqrt(0.5 * (x**2 + y**2))) – exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20
 
# define range for input
r_min, r_max = –5.0, 5.0
# define the bounds on the search
bounds = [[r_min, r_max], [r_min, r_max]]
# perform the dual annealing search
result = dual_annealing(objective, bounds)
# summarize the result
print(‘Status : %s’ % result[‘message’])
print(‘Total Evaluations: %d’ % result[‘nfev’])
# evaluate solution
solution = result[‘x’]
evaluation = objective(solution)
print(‘Solution: f(%s) = %.5f’ % (solution, evaluation))

예제를 실행하면 최적화가 실행되고 결과가 보고됩니다.

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

이 경우 알고리즘이 입력값이 0에 매우 가깝고 목적 함수 평가가 실질적으로 0인 최적값을 찾았음을 알 수 있습니다.

총 4,136 개의 기능 평가가 수행되었음을 알 수 있습니다.

1
2
3
Status : [‘Maximum number of iteration reached’]
Total Evaluations: 4136
Solution: f([-2.26474440e-09 -8.28465933e-09]) = 0.00000

추가 정보

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

논문

증권 시세 표시기

기사

요약

이 자습서에서는 Dual Annealing 전역 최적화 알고리즘을 발견했습니다.

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

Dual Annealing 최적화는 로컬 검색 알고리즘도 사용하는 시뮬레이션된 annealing의 수정된 버전인 전역 최적화입니다.
파이썬에서 Dual Annealing 최적화 알고리즘 API를 사용하는 방법.
다중 최적으로 전역 최적화 문제를 해결하기 위해 Dual Annealing을 사용하는 예.

Tags:

Dual Annealing,Machine learning