Python 랜 덤 등산 알고리즘 구현

무 작위 등산 은 최적화 알고리즘 이다.그것 은 검색 과정의 일부분 으로 무 작위 성 을 이용한다.이 알고리즘 은 비 선형 목표 함수 에 적용 되 고 다른 부분 검색 알고리즘 은 잘 작 동 하지 않 습 니 다.이것 도 부분 검색 알고리즘 입 니 다.이것 은 하나의 해결 방안 을 수정 하고 검색 공간의 상대 적 인 부분 영역 을 검색 하여 부분 적 인 최 적 치 를 찾 을 때 까지 검색 한 다 는 것 을 의미 합 니 다.이 는 단 봉 최적화 문제 나 전체 최적화 알고리즘 을 응용 한 후에 사용 하 는 것 을 의미한다.
본 튜 토리 얼 에서 함수 최적화 에 사용 되 는 등산 최적화 알고리즘 이 본 튜 토리 얼 을 완성 하면 다음 과 같은 것 을 알 게 될 것 입 니 다.

 등산 은 기능 최적화 에 사용 되 는 랜 덤 국부 검색 알고리즘 이다.

 어떻게 Python 에서 처음부터 등산 알고리즘 을 실현 합 니까?

 어떻게 등산 알고리즘 을 응용 하고 알고리즘 결 과 를 검사 합 니까?

강좌 개설
본 튜 토리 얼 은 세 부분 으로 나 뉜 다.그들 은:

 등산 알고리즘

 등산 알고리즘 의 실현

 등산 알고리즘 을 사용 한 예제

등산 알고리즘
랜 덤 등산 알고리즘 은 랜 덤 국부 검색 최적화 알고리즘 이다.그것 은 시작 점 을 입력 과 보폭 으로 하고 보폭 은 검색 공간 내의 거리 이다.이 알고리즘 은 초기 점 을 현재 최 적 후보 솔 루 션 으로 하고 제 공 된 점 의 보폭 거리 에서 새로운 점 을 생 성 합 니 다.생 성 된 점 을 계산 합 니 다.현재 점 과 같 거나 좋 으 면 현재 점 으로 간주 합 니 다.새로운 점 의 생 성 은 랜 덤 으로 사용 되 며,일반적으로 랜 덤 등산 이 라 고 부른다.이 알고리즘 은 표면의 흔 들 림,시 끄 러 움,불 연속 또는 기만 적 인 영역 을 뛰 어 넘 어 검색 의 일부분 으로 사용 할 수 있다 는 뜻 이다.중요 한 것 은 똑 같은 평 가 를 가 진 차이 점 을 받 아들 이 는 것 이다.알고리즘 이 검색 공간 을 계속 탐색 할 수 있 기 때문이다.예 를 들 어 표면 에 응 하 는 평탄 한 지역 에서.무한 순환 을 피하 기 위해 이른바'가로'이동 을 제한 하 는 것 도 도움 이 될 수 있다.이 과정 은 최대 수량의 기능 평가 나 주어진 수량의 기능 평가 에서 개선 되 지 않 을 때 까지 계속 되 었 다.이 알고리즘 이 이름 을 얻 은 이 유 는 응답 면 의 언덕 에 올 라 가 국부 적 으로 가장 좋 은 값 에 이 르 기 때문이다.이것 은 결코 그것 이 목표 함 수 를 최대 화 하 는 데 만 사용 된다 는 것 을 의미 하지 않 는 다.이것 은 단지 하나의 이름 일 뿐이다.실제로 우 리 는 그것 을 최대 화 하 는 것 이 아니 라 기능 을 최소 화 하 는 경우 가 많다.국부 검색 알고리즘 으로서 국부 최 우선 상태 에 빠 질 수 있 습 니 다.그러나 여러 번 재 부팅 하면 알고리즘 포 지 셔 닝 전체 가 가장 좋 습 니 다.검색 공간 에서 더 좋 은 부근 점 을 찾 을 수 있 도록 걸음 길이 가 충분 해 야 하지만,걸음 폭 이 너무 크 면 안 되 며,검색 이 국부 적 으로 가장 좋 은 값 을 포함 하 는 구역 에서 벗 어 날 수 있 도록 해 야 한다.
등산 알고리즘 의 실현
본문 을 작성 할 때 Scipy 라 이브 러 리 는 무 작위 등산 의 실현 을 제공 하지 않 았 다.하지만 우 리 는 스스로 그것 을 실현 할 수 있다.우선,우 리 는 목표 함수 와 모든 입력 변 수 를 목표 함수 의 경계 로 정의 해 야 한다.대상 함 수 는 파 이 썬 함수 일 뿐 Objective()라 고 명명 합 니 다.경 계 는 2D 배열 이 될 것 입 니 다.모든 입력 변 수 는 하나의 차원 을 가지 고 이 변 수 는 변수의 최소 값 과 최대 값 을 정의 합 니 다.예 를 들 어 1 차원 목표 함수 와 경 계 는 다음 과 같이 정 의 됩 니 다.

# objective function  
def objective(x):  
 return 0   
# define range for input  
bounds = asarray([[-5.0, 5.0]]) 

그 다음 에 우 리 는 초기 해 를 문제 범위 내의 무 작위 점 으로 만 든 다음 에 목표 함 수 를 사용 하여 이 를 평가 할 수 있다.

# generate an initial point  
solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])  
# evaluate the initial point  
solution_eval = objective(solution) 

이제 우 리 는'n'으로 정의 할 수 있다.iterations'알고리즘 의 미리 정 의 된 교체 횟수,예 를 들 어 100 또는 1,000.

# run the hill climb  
for i in range(n_iterations): 

알고리즘 교체 의 첫 단 계 는 절 차 를 밟 는 것 이다.미리 정 의 된"step"가 필요 합 니 다.size'인자,이 매개 변 수 는 검색 공간의 경계 에 비해.우 리 는 고 스 분포 의 무 작위 절 차 를 채택 할 것 이다.그 중에서 평균 값 은 우리 의 현재 점 이 고 표준 편차 는"step"이다.size 정의이것 은 약 99%의 절차 가 현재 점(3*stepsize)내.

# take a step  
candidate = solution + randn(len(bounds)) * step_size 

우 리 는 이런 방식 을 채택 할 필요 가 없다.0 에서 걸음 사이 의 균일 한 분 포 를 원 하 실 수도 있 습 니 다.예 를 들 면:

# take a step  
candidate = solution + rand(len(bounds)) * step_size 

다음은 목표 함 수 를 가 진 새로운 후보 해결 방안 을 평가 해 야 한다.

# evaluate candidate point  
candidte_eval = objective(candidate) 

그 다음 에 우 리 는 이 새로운 평가 결과 가 현재 의 가장 좋 은 점 과 같 거나 좋 은 지 확인 해 야 한다.만약 그렇다면 이 새로운 점 으로 현재 의 가장 좋 은 점 을 교체 해 야 한다.

# check if we should keep the new point  
if candidte_eval <= solution_eval:  
 # store the new point  
 solution, solution_eval = candidate, candidte_eval  
 # report progress  
 print('>%d f(%s) = %.5f' % (i, solution, solution_eval)) 

그렇습니다.우 리 는 이 등산 알고리즘 을 다시 사용 할 수 있 는 함수 로 실현 할 수 있 습 니 다.이 함 수 는 목표 함수 의 이름,모든 입력 변수의 범위,총 교체 횟수 와 절 차 를 매개 변수 로 하고 찾 은 가장 좋 은 해결 방안 과 평 가 를 되 돌려 줍 니 다.

# hill climbing local search algorithm  
def hillclimbing(objective, bounds, n_iterations, step_size):  
 # generate an initial point  
 solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])  
 # evaluate the initial point  
 solution_eval = objective(solution)  
 # run the hill climb  
 for i in range(n_iterations):  
  # take a step  
  candidate = solution + randn(len(bounds)) * step_size  
  # evaluate candidate point  
  candidte_eval = objective(candidate)  
  # check if we should keep the new point 
  if candidte_eval <= solution_eval:  
   # store the new point  
   solution, solution_eval = candidate, candidte_eval  
   # report progress  
   print('>%d f(%s) = %.5f' % (i, solution, solution_eval))  
 return [solution, solution_eval] 

이제 우 리 는 Python 에서 등산 알고리즘 을 어떻게 실현 하 는 지 알 게 되 었 으 며,그것 을 어떻게 사용 하여 목표 함 수 를 최적화 하 는 지 보 여 주 었 다.
등산 알고리즘 을 사용 한 예제
이 절 에서 우 리 는 등산 최적화 알고리즘 을 목표 함수 에 응용 할 것 이다.우선 목표 함 수 를 정의 합 시다.우 리 는 간단 한 1 차원 x^2 목표 함 수 를 사용 할 것 이다.그 경 계 는[-5,5]이다.아래 의 예 는 함 수 를 정의 한 다음 에 입력 값 의 격자 에 함수 응답 면 의 접선 도 를 만 들 고 빨 간 선 으로 f(0.0)=0.0 곳 의 최 적 치 를 표시 합 니 다.

# convex unimodal optimization function  
from numpy import arange  
from matplotlib import pyplot   
# objective function  
def objective(x):  
 return x[0]**2.0   
# define range for input  
r_min, r_max = -5.0, 5.0  
# sample input range uniformly at 0.1 increments  
inputs = arange(r_min, r_max, 0.1)  
# compute targets  
results = [objective([x]) for x in inputs]  
# create a line plot of input vs result  
pyplot.plot(inputs, results)  
# define optimal input value  
x_optima = 0.0  
# draw a vertical line at the optimal input  
pyplot.axvline(x=x_optima, ls='--', color='red')  
# show the plot  
pyplot.show() 

예 시 를 실행 하면 목표 함수 의 접선 도 를 만 들 고 함수 의 최 적 화 된 값 을 선명 하 게 표시 합 니 다.

다음 에 우 리 는 등산 알고리즘 을 목표 함수 에 응용 할 수 있다.우선,우 리 는 가짜 난수 생 성 기 를 파종 할 것 이다.일반적으로 이것 은 필요 한 것 이 아니 지만,이러한 상황 에서 나 는 알고리즘 을 실행 할 때마다 같은 결과(같은 난수 서열)를 얻어 나중에 결 과 를 그 릴 수 있 도록 확보 하고 싶다.

# seed the pseudorandom number generator  
seed(5) 

다음은 검색 설정 을 정의 할 수 있 습 니 다.이런 상황 에서 우 리 는 검색 알고리즘 의 1,000 번 을 교체 하고 0.1 의 보폭 을 사용 할 것 이다.만약 에 우리 가 사용 하 는 것 이 고 스 함수 로 걸음 길 이 를 생 성 하 는 것 이 라 고 가정 하면 약 99%의 모든 걸음 길 이 는 지정 점(0.1*3)의 거리 에 있 을 것 이다.예 를 들 어 세 가지 기준 차이 등 이다.

n_iterations = 1000  
# define the maximum step size  
step_size = 0.1 

다음 에 우 리 는 검색 을 실행 하고 결 과 를 보고 할 수 있다.

# perform the hill climbing search  
best, score = hillclimbing(objective, bounds, n_iterations, step_size)  
print('Done!')  
print('f(%s) = %f' % (best, score)) 

한데 결합 하여 아래 에 완전한 예 시 를 열거 하 였 다.

# hill climbing search of a one-dimensional objective function  
from numpy import asarray  
from numpy.random import randn  
from numpy.random import rand  
from numpy.random import seed   
# objective function  
def objective(x):  
 return x[0]**2.0   
# hill climbing local search algorithm  
def hillclimbing(objective, bounds, n_iterations, step_size):  
 # generate an initial point  
 solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])  
 # evaluate the initial point  
 solution_eval = objective(solution)  
 # run the hill climb  
 for i in range(n_iterations): 
  # take a step  
  candidate = solution + randn(len(bounds)) * step_size  
  # evaluate candidate point  
  candidte_eval = objective(candidate)  
  # check if we should keep the new point  
  if candidte_eval <= solution_eval:  
   # store the new point  
   solution, solution_eval = candidate, candidte_eval  
   # report progress  
   print('>%d f(%s) = %.5f' % (i, solution, solution_eval))  
 return [solution, solution_eval]  
# seed the pseudorandom number generator  
seed(5)  
# define range for input  
bounds = asarray([[-5.0, 5.0]])  
# define the total iterations 
n_iterations = 1000  
# define the maximum step size  
step_size = 0.1  
# perform the hill climbing search  
best, score = hillclimbing(objective, bounds, n_iterations, step_size)  
print('Done!')  
print('f(%s) = %f' % (best, score)) 

이 예제 를 실행 하면 검색 진 도 를 보고 합 니 다.개선 할 때마다 교체 횟수,이 함수 의 입력 과 목표 함수 에서 온 응답 을 포함 합 니 다.검색 이 끝 났 을 때 가장 좋 은 해결 방안 을 찾 아 평가 결 과 를 보고 합 니 다.이러한 상황 에서 우 리 는 알고리즘 의 1,000 번 교체 에서 36 곳 이 개선 되 었 고 이 해결 방안 은 0.0 에 가 까 운 가장 좋 은 입력 을 볼 수 있 으 며 그 계산 결 과 는 f(0.0)=0 이다.

>1 f([-2.74290923]) = 7.52355  
>3 f([-2.65873147]) = 7.06885  
>4 f([-2.52197291]) = 6.36035  
>5 f([-2.46450214]) = 6.07377  
>7 f([-2.44740961]) = 5.98981  
>9 f([-2.28364676]) = 5.21504  
>12 f([-2.19245939]) = 4.80688  
>14 f([-2.01001538]) = 4.04016  
>15 f([-1.86425287]) = 3.47544  
>22 f([-1.79913002]) = 3.23687  
>24 f([-1.57525573]) = 2.48143  
>25 f([-1.55047719]) = 2.40398  
>26 f([-1.51783757]) = 2.30383  
>27 f([-1.49118756]) = 2.22364  
>28 f([-1.45344116]) = 2.11249  
>30 f([-1.33055275]) = 1.77037  
>32 f([-1.17805016]) = 1.38780  
>33 f([-1.15189314]) = 1.32686  
>36 f([-1.03852644]) = 1.07854  
>37 f([-0.99135322]) = 0.98278  
>38 f([-0.79448984]) = 0.63121  
>39 f([-0.69837955]) = 0.48773  
>42 f([-0.69317313]) = 0.48049  
>46 f([-0.61801423]) = 0.38194  
>48 f([-0.48799625]) = 0.23814  
>50 f([-0.22149135]) = 0.04906  
>54 f([-0.20017144]) = 0.04007  
>57 f([-0.15994446]) = 0.02558  
>60 f([-0.15492485]) = 0.02400  
>61 f([-0.03572481]) = 0.00128  
>64 f([-0.03051261]) = 0.00093  
>66 f([-0.0074283]) = 0.00006  
>78 f([-0.00202357]) = 0.00000  
>119 f([0.00128373]) = 0.00000  
>120 f([-0.00040911]) = 0.00000  
>314 f([-0.00017051]) = 0.00000  
Done!  
f([-0.00017051]) = 0.000000 

검색 진 도 를 선도 로 보 는 것 이 재 미 있 을 수 있 습 니 다.이 선 도 는 매번 개선 후 가장 좋 은 해결 방안 에 대한 평가 변 화 를 보 여 줍 니 다.개선 이 있 을 때마다 힐 클 라 임 빙()을 업데이트 하여 목표 함수 의 평 가 를 추적 하고 이 점수 목록 을 되 돌려 줍 니 다.

# hill climbing local search algorithm  
def hillclimbing(objective, bounds, n_iterations, step_size):  
 # generate an initial point  
 solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])  
 # evaluate the initial point  
 solution_eval = objective(solution)  
 # run the hill climb 
 scores = list()  
 scores.append(solution_eval)  
 for i in range(n_iterations):  
  # take a step  
  candidate = solution + randn(len(bounds)) * step_size  
  # evaluate candidate point  
  candidte_eval = objective(candidate)  
  # check if we should keep the new point  
  if candidte_eval <= solution_eval:  
   # store the new point  
   solution, solution_eval = candidate, candidte_eval  
   # keep track of scores  
   scores.append(solution_eval)  
   # report progress  
   print('>%d f(%s) = %.5f' % (i, solution, solution_eval))  
 return [solution, solution_eval, scores] 

그 다음 에 우 리 는 검색 과정 에서 발 견 된 모든 개 선 된 목표 함수 의 상대 적 인 변 화 를 보기 위해 이 점수 들 의 접선 도 를 만 들 수 있 습 니 다.

# line plot of best scores  
pyplot.plot(scores, '.-')  
pyplot.xlabel('Improvement Number')  
pyplot.ylabel('Evaluation f(x)')  
pyplot.show() 

결합 하여 검색 을 실행 하고 검색 과정 에서 해결 방안 을 개선 하 는 목표 함수 점 수 를 그 리 는 전체 예 시 를 보 여 줍 니 다.

# hill climbing search of a one-dimensional objective function  
from numpy import asarray  
from numpy.random import randn  
from numpy.random import rand  
from numpy.random import seed  
from matplotlib import pyplot   
# objective function  
def objective(x):  
 return x[0]**2.0  
# hill climbing local search algorithm  
def hillclimbing(objective, bounds, n_iterations, step_size):  
 # generate an initial point  
 solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])  
 # evaluate the initial point  
 solution_eval = objective(solution)  
 # run the hill climb  
 scores = list()  
 scores.append(solution_eval)  
 for i in range(n_iterations):  
  # take a step  
  candidate = solution + randn(len(bounds)) * step_size  
  # evaluate candidate point  
  candidte_eval = objective(candidate)  
  # check if we should keep the new point  
  if candidte_eval <= solution_eval:  
   # store the new point  
   solution, solution_eval = candidate, candidte_eval  
   # keep track of scores  
   scores.append(solution_eval)  
   # report progress  
   print('>%d f(%s) = %.5f' % (i, solution, solution_eval))  
 return [solution, solution_eval, scores]  
# seed the pseudorandom number generator  
seed(5)  
# define range for input  
bounds = asarray([[-5.0, 5.0]])  
# define the total iterations  
n_iterations = 1000  
# define the maximum step size  
step_size = 0.1  
# perform the hill climbing search  
best, score, scores = hillclimbing(objective, bounds, n_iterations, step_size)  
print('Done!')  
print('f(%s) = %f' % (best, score))  
# line plot of best scores  
pyplot.plot(scores, '.-')  
pyplot.xlabel('Improvement Number')  
pyplot.ylabel('Evaluation f(x)')  
pyplot.show() 

예 시 를 실행 하면 검색 을 실행 하고 이전 처럼 결 과 를 보고 합 니 다.등산 검색 기간 동안 개 선 된 목표 함수 평 가 를 보 여 주 는 선형 그림 을 만 듭 니 다.검색 과정 에서 우 리 는 목표 함수 평가 에 약 36 개의 변화 가 발생 한 것 을 볼 수 있다.알고리즘 이 최 우수 치 로 수렴 되면 서 초기 변화 가 비교적 크 고 검색 이 끝 날 때 변화 가 적어 알 아차 리 기 어렵다.

목표 함수 가 1 차원 임 을 감안 하여 위 처럼 응답 면 을 직접 그 릴 수 있 습 니 다.검색 과정 에서 찾 은 최 적 후보 솔 루 션 을 응답 면 의 점 으로 그 려 검색 진 도 를 되 돌아 보 는 것 이 재 미 있 을 것 으로 보인다.우 리 는 호응 면 을 따라 가장 장점 있 는 일련의 점 에 도달 하 기 를 기대한다.이 는 우선 hillclimbing()함 수 를 업데이트 하여 모든 최 적 후보 솔 루 션 이 검색 과정 에서 의 위 치 를 추적 한 다음 최 적 솔 루 션 목록 으로 돌아 갈 수 있 습 니 다.

# hill climbing local search algorithm  
def hillclimbing(objective, bounds, n_iterations, step_size):  
 # generate an initial point  
 solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])  
 # evaluate the initial point  
 solution_eval = objective(solution) 
 # run the hill climb  
 solutions = list()  
 solutions.append(solution)  
 for i in range(n_iterations):  
  # take a step  
  candidate = solution + randn(len(bounds)) * step_size  
  # evaluate candidate point 
   candidte_eval = objective(candidate)  
  # check if we should keep the new point  
  if candidte_eval <= solution_eval:  
   # store the new point  
   solution, solution_eval = candidate, candidte_eval  
   # keep track of solutions  
   solutions.append(solution) 
   # report progress  
   print('>%d f(%s) = %.5f' % (i, solution, solution_eval))  
 return [solution, solution_eval, solutions] 

그 다음 에 우 리 는 목표 함수 응답 면 의 그림 을 만 들 고 예전 처럼 최 적 화 된 값 을 표시 할 수 있 습 니 다.

# sample input range uniformly at 0.1 increments  
inputs = arange(bounds[0,0], bounds[0,1], 0.1)  
# create a line plot of input vs result  
pyplot.plot(inputs, [objective([x]) for x in inputs], '--')  
# draw a vertical line at the optimal input  
pyplot.axvline(x=[0.0], ls='--', color='red') 

마지막 으로 찾 은 후보 해 의 서열 을 검 은 점 으로 그 릴 수 있다.

# plot the sample as black circles  
pyplot.plot(solutions, [objective(x) for x in solutions], 'o', color='black') 

결합 하여 목표 함수 의 응답 면 에 개선 해 열 을 그 리 는 전체 예 시 를 보 여 줍 니 다.

# hill climbing search of a one-dimensional objective function  
from numpy import asarray  
from numpy import arange  
from numpy.random import randn  
from numpy.random import rand  
from numpy.random import seed  
from matplotlib import pyplot  
# objective function  
def objective(x):  
 return x[0]**2.0  
# hill climbing local search algorithm  
def hillclimbing(objective, bounds, n_iterations, step_size):  
 # generate an initial point  
 solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])  
 # evaluate the initial point  
 solution_eval = objective(solution)  
 # run the hill climb  
 solutions = list()  
 solutions.append(solution)  
 for i in range(n_iterations):  
  # take a step  
  candidate = solution + randn(len(bounds)) * step_size  
  # evaluate candidate point  
  candidte_eval = objective(candidate)  
  # check if we should keep the new point  
  if candidte_eval <= solution_eval:  
   # store the new point  
   solution, solution_eval = candidate, candidte_eval  
   # keep track of solutions  
   solutions.append(solution) 
    # report progress  
   print('>%d f(%s) = %.5f' % (i, solution, solution_eval))  
 return [solution, solution_eval, solutions]  
# seed the pseudorandom number generator  
seed(5)  
# define range for input  
bounds = asarray([[-5.0, 5.0]])  
# define the total iterations  
n_iterations = 1000  
# define the maximum step size  
step_size = 0.1  
# perform the hill climbing search  
best, score, solutions = hillclimbing(objective, bounds, n_iterations, step_size)  
print('Done!')  
print('f(%s) = %f' % (best, score))  
# sample input range uniformly at 0.1 increments  
inputs = arange(bounds[0,0], bounds[0,1], 0.1)  
# create a line plot of input vs result 
pyplot.plot(inputs, [objective([x]) for x in inputs], '--')  
# draw a vertical line at the optimal input  
pyplot.axvline(x=[0.0], ls='--', color='red')  
# plot the sample as black circles  
pyplot.plot(solutions, [objective(x) for x in solutions], 'o', color='black')  
pyplot.show() 

예 시 를 실행 하면 등산 검색 을 실행 하고 예전 처럼 결 과 를 보고 할 것 이다.이전 처럼 함수 에 익숙 한 그릇 모양 을 표시 하고 수직 으로 빨 간 선 으로 함수 의 최 적 상 태 를 표시 하 는 응답 면 도 를 만 듭 니 다.검색 과정 에서 찾 은 가장 좋 은 해결 방안 의 순 서 는 검 은 점 으로 나타 나 사발 모양 을 따라 가장 좋 은 상태 로 뻗 어 있다.

이상 은 파 이 썬 이 랜 덤 등산 알고리즘 을 실현 하 는 상세 한 내용 입 니 다.파 이 썬 랜 덤 등산 알고리즘 에 관 한 자 료 는 다른 관련 글 을 주목 하 세 요!