Python實(shí)現(xiàn)隨機(jī)爬山算法
隨機(jī)爬山是一種優(yōu)化算法。它利用隨機(jī)性作為搜索過程的一部分。這使得該算法適用于非線性目標(biāo)函數(shù)，而其他局部搜索算法不能很好地運(yùn)行。它也是一種局部搜索算法，這意味著它修改了單個解決方案并搜索搜索空間的相對局部區(qū)域，直到找到局部最優(yōu)值為止。這意味著它適用于單峰優(yōu)化問題或在應(yīng)用全局優(yōu)化算法后使用。
在本教程中，您將發(fā)現(xiàn)用于函數(shù)優(yōu)化的爬山優(yōu)化算法完成本教程后，您將知道：
- 爬山是用于功能優(yōu)化的隨機(jī)局部搜索算法。
- 如何在Python中從頭開始實(shí)現(xiàn)爬山算法。
- 如何應(yīng)用爬山算法并檢查算法結(jié)果。
教程概述
本教程分為三個部分：他們是：
- 爬山算法
- 爬山算法的實(shí)現(xiàn)
- 應(yīng)用爬山算法的示例
爬山算法
隨機(jī)爬山算法是一種隨機(jī)局部搜索優(yōu)化算法。它以起始點(diǎn)作為輸入和步長，步長是搜索空間內(nèi)的距離。該算法將初始點(diǎn)作為當(dāng)前最佳候選解決方案，并在提供的點(diǎn)的步長距離內(nèi)生成一個新點(diǎn)。計算生成的點(diǎn)，如果它等于或好于當(dāng)前點(diǎn)，則將其視為當(dāng)前點(diǎn)。新點(diǎn)的生成使用隨機(jī)性，通常稱為隨機(jī)爬山。這意味著該算法可以跳過響應(yīng)表面的顛簸，嘈雜，不連續(xù)或欺騙性區(qū)域，作為搜索的一部分。重要的是接受具有相等評估的不同點(diǎn)，因?yàn)樗试S算法繼續(xù)探索搜索空間，例如在響應(yīng)表面的平坦區(qū)域上。限制這些所謂的“橫向”移動以避免無限循環(huán)也可能是有幫助的。該過程一直持續(xù)到滿足停止條件，例如最大數(shù)量的功能評估或給定數(shù)量的功能評估內(nèi)沒有改善為止。該算法之所以得名，是因?yàn)樗鼤S機(jī)地）爬到響應(yīng)面的山坡上，達(dá)到局部最優(yōu)值。這并不意味著它只能用于最大化目標(biāo)函數(shù)。這只是一個名字。實(shí)際上，通常，我們最小化功能而不是最大化它們。作為局部搜索算法，它可能會陷入局部最優(yōu)狀態(tài)。然而，多次重啟可以允許算法定位全局最優(yōu)。步長必須足夠大，以允許在搜索空間中找到更好的附近點(diǎn)，但步幅不能太大，以使搜索跳出包含局部最優(yōu)值的區(qū)域。
爬山算法的實(shí)現(xiàn)
在撰寫本文時，SciPy庫未提供隨機(jī)爬山的實(shí)現(xiàn)。但是，我們可以自己實(shí)現(xiàn)它。首先，我們必須定義目標(biāo)函數(shù)和每個輸入變量到目標(biāo)函數(shù)的界限。目標(biāo)函數(shù)只是一個Python函數(shù)，我們將其命名為Objective（）。邊界將是一個2D數(shù)組，每個輸入變量都具有一個維度，該變量定義了變量的最小值和最大值。例如，一維目標(biāo)函數(shù)和界限將定義如下：
# objective function def objective(x): return 0 # define range for input bounds = asarray([[-5.0, 5.0]])
接下來，我們可以生成初始解作為問題范圍內(nèi)的隨機(jī)點(diǎn)，然后使用目標(biāo)函數(shù)對其進(jìn)行評估。
# generate an initial point solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0]) # evaluate the initial point solution_eval = objective(solution)
現(xiàn)在我們可以遍歷定義為“ n_iterations”的算法的預(yù)定義迭代次數(shù)，例如100或1,000。
# run the hill climb for i in range(n_iterations):
算法迭代的第一步是采取步驟。這需要預(yù)定義的“ step_size”參數(shù)，該參數(shù)相對于搜索空間的邊界。我們將采用高斯分布的隨機(jī)步驟，其中均值是我們的當(dāng)前點(diǎn)，標(biāo)準(zhǔn)偏差由“ step_size”定義。這意味著大約99％的步驟將在當(dāng)前點(diǎn)的（3 * step_size）之內(nèi)。
# take a step candidate = solution + randn(len(bounds)) * step_size
我們不必采取這種方式。您可能希望使用0到步長之間的均勻分布。例如：
# take a step candidate = solution + rand(len(bounds)) * step_size
接下來，我們需要評估具有目標(biāo)函數(shù)的新候選解決方案。
# evaluate candidate point candidte_eval = objective(candidate)
然后，我們需要檢查此新點(diǎn)的評估結(jié)果是否等于或優(yōu)于當(dāng)前最佳點(diǎn)，如果是，則用此新點(diǎn)替換當(dāng)前最佳點(diǎn)。
# 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))
就是這樣。我們可以將此爬山算法實(shí)現(xiàn)為可重用函數(shù)，該函數(shù)將目標(biāo)函數(shù)的名稱，每個輸入變量的范圍，總迭代次數(shù)和步驟作為參數(shù)，并返回找到的最佳解決方案及其評估。
# 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]
現(xiàn)在，我們知道了如何在Python中實(shí)現(xiàn)爬山算法，讓我們看看如何使用它來優(yōu)化目標(biāo)函數(shù)。
應(yīng)用爬山算法的示例
在本節(jié)中，我們將把爬山優(yōu)化算法應(yīng)用于目標(biāo)函數(shù)。首先，讓我們定義目標(biāo)函數(shù)。我們將使用一個簡單的一維x ^ 2目標(biāo)函數(shù)，其邊界為[-5，5]。下面的示例定義了函數(shù)，然后為輸入值的網(wǎng)格創(chuàng)建了函數(shù)響應(yīng)面的折線圖，并用紅線標(biāo)記了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()
運(yùn)行示例將創(chuàng)建目標(biāo)函數(shù)的折線圖，并清晰地標(biāo)記函數(shù)的最優(yōu)值。
接下來，我們可以將爬山算法應(yīng)用于目標(biāo)函數(shù)。首先，我們將播種偽隨機(jī)數(shù)生成器。通常這不是必需的，但是在這種情況下，我想確保每次運(yùn)行算法時都得到相同的結(jié)果（相同的隨機(jī)數(shù)序列），以便以后可以繪制結(jié)果。
# seed the pseudorandom number generator seed(5)
接下來，我們可以定義搜索的配置。在這種情況下，我們將搜索算法的1,000次迭代，并使用0.1的步長。假設(shè)我們使用的是高斯函數(shù)來生成步長，這意味著大約99％的所有步長將位于給定點(diǎn)（0.1 * 3）的距離內(nèi)，例如 三個標(biāo)準(zhǔn)差。
n_iterations = 1000 # define the maximum step size step_size = 0.1
接下來，我們可以執(zhí)行搜索并報告結(jié)果。
# perform the hill climbing search
best, score = hillclimbing(objective, bounds, n_iterations, step_size)
print('Done!')
print('f(%s) = %f' % (best, score))
結(jié)合在一起，下面列出了完整的示例。
# 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))
運(yùn)行該示例將報告搜索進(jìn)度，包括每次檢測到改進(jìn)時的迭代次數(shù)，該函數(shù)的輸入以及來自目標(biāo)函數(shù)的響應(yīng)。搜索結(jié)束時，找到最佳解決方案，并報告其評估結(jié)果。在這種情況下，我們可以看到在算法的1,000次迭代中有36處改進(jìn)，并且該解決方案非常接近于0.0的最佳輸入，其計算結(jié)果為f（0.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
以線圖的形式查看搜索的進(jìn)度可能很有趣，該線圖顯示了每次改進(jìn)后最佳解決方案的評估變化。每當(dāng)有改進(jìn)時，我們就可以更新hillclimbing（）來跟蹤目標(biāo)函數(shù)的評估，并返回此分?jǐn)?shù)列表
# 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]
然后，我們可以創(chuàng)建這些分?jǐn)?shù)的折線圖，以查看搜索過程中發(fā)現(xiàn)的每個改進(jìn)的目標(biāo)函數(shù)的相對變化
# line plot of best scores
pyplot.plot(scores, '.-')
pyplot.xlabel('Improvement Number')
pyplot.ylabel('Evaluation f(x)')
pyplot.show()
結(jié)合在一起，下面列出了執(zhí)行搜索并繪制搜索過程中改進(jìn)解決方案的目標(biāo)函數(shù)得分的完整示例。
# 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()
運(yùn)行示例將執(zhí)行搜索，并像以前一樣報告結(jié)果。創(chuàng)建一個線形圖，顯示在爬山搜索期間每個改進(jìn)的目標(biāo)函數(shù)評估。在搜索過程中，我們可以看到目標(biāo)函數(shù)評估發(fā)生了約36個變化，隨著算法收斂到最優(yōu)值，初始變化較大，而在搜索結(jié)束時變化很小，難以察覺。
鑒于目標(biāo)函數(shù)是一維的，因此可以像上面那樣直接繪制響應(yīng)面。通過將在搜索過程中找到的最佳候選解決方案繪制為響應(yīng)面中的點(diǎn)，來回顧搜索的進(jìn)度可能會很有趣。我們期望沿著響應(yīng)面到達(dá)最優(yōu)點(diǎn)的一系列點(diǎn)。這可以通過首先更新hillclimbing（）函數(shù)以跟蹤每個最佳候選解決方案在搜索過程中的位置來實(shí)現(xiàn)，然后返回最佳解決方案列表來實(shí)現(xiàn)。
# 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]
然后，我們可以創(chuàng)建目標(biāo)函數(shù)響應(yīng)面的圖，并像以前那樣標(biāo)記最優(yōu)值。
# 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')
最后，我們可以將搜索找到的候選解的序列繪制成黑點(diǎn)。
# plot the sample as black circles pyplot.plot(solutions, [objective(x) for x in solutions], 'o', color='black')
結(jié)合在一起，下面列出了在目標(biāo)函數(shù)的響應(yīng)面上繪制改進(jìn)解序列的完整示例。
# 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()
運(yùn)行示例將執(zhí)行爬山搜索，并像以前一樣報告結(jié)果。像以前一樣創(chuàng)建一個響應(yīng)面圖，顯示函數(shù)的熟悉的碗形，并用垂直的紅線標(biāo)記函數(shù)的最佳狀態(tài)。在搜索過程中找到的最佳解決方案的順序顯示為黑點(diǎn)，沿著碗形延伸到最佳狀態(tài)。
以上就是Python實(shí)現(xiàn)隨機(jī)爬山算法的詳細(xì)內(nèi)容，更多關(guān)于Python 隨機(jī)爬山算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
python pyg2plot的原理知識點(diǎn)總結(jié)
在本篇文章里小編給大家整理的是一篇關(guān)于python pyg2plot的原理知識點(diǎn)總結(jié)內(nèi)容，有興趣的朋友們可以參考下。2021-02-02
從DataFrame中提取出Series或DataFrame對象的方法
今天小編就為大家分享一篇從DataFrame中提取出Series或DataFrame對象的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-11-11
這篇文章主要介紹了簡單的編程0基礎(chǔ)下Python入門指引,包括從各個系統(tǒng)的Python安裝和簡單的語句知識，需要的朋友可以參考下2015-04-04
這篇文章主要介紹了獲取numpy array前N個最大值的操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-05-05
Pandas DataFrame中的tuple元素遍歷的實(shí)現(xiàn)
這篇文章主要介紹了Pandas DataFrame中的tuple元素遍歷的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10
Python列表去重復(fù)項的N種方法(實(shí)例代碼)
這篇文章主要介紹了Python列表去重復(fù)項的N種方法,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-05-05
這篇文章主要介紹了關(guān)于python類SortedList詳解，可以幫大家鞏固一下python類的基礎(chǔ)知識，有需要的朋友可以借鑒參考下，希望可以對廣大讀者有所幫助2021-09-09
這篇文章主要介紹了Python collections模塊使用方法詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-08-08
python的thread模塊是底層的模塊,python的threading模塊是對thread做了一些包裝的,可以更加方便的被使用。本文詳細(xì)的講述了threading模塊的用法2021-06-06
YOLOv5部署到web端詳細(xì)過程(flask+js簡單易懂)
YOLOv5是一個目標(biāo)檢測模型,Flask是一個Python的Web框架,下面這篇文章主要給大家介紹了關(guān)于YOLOv5部署到web端(flask+js簡單易懂)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-04-04