一、爬山法簡介
爬山法（climbing method）是一種優化算法，其一般從一個隨機的解開始，然后逐步找到一個最優解（局部最優）。 假定所求問題有多個參數，我們在通過爬山法逐步獲得最優解的過程中可以依次分別將某個參數的值增加或者減少一個單位。例如某個問題的解需要使用3個整數類型的參數x1、x2、x3，開始時將這三個參數設值為(2,2,-2)，將x1增加/減少1，得到兩個解(1,2,-2), (3, 2,-2)；將x2增加/減少1，得到兩個解(2,3, -2)，(2,1, -2)；將x3增加/減少1，得到兩個解(2,2,-1)，(2,2,-3)，這樣就得到了一個解集：
(2,2,-2), (1, 2,-2), (3, 2,-2), (2,3,-2), (2,1,-2), (2,2,-1), (2,2,-3)
從上面的解集中找到最優解，然后將這個最優解依據上面的方法再構造一個解集，再求最優解，就這樣，直到前一次的最優解和后一次的最優解相同才結束“爬山”。
二、Python實例
設方程 y = x1+x2-x3，x1是區間[-2, 5]中的整數，x2是區間[2, 6]中的整數，x3是區間[-5, 2]中的整數。使用爬山法，找到使得y取值最小的解。
代碼如下：
def evaluate(x1, x2, x3):
return x1+x2-x3
if __name__ == '__main__':
x_range = [ [-2, 5], [2, 6], [-5, 2] ]
best_sol = [random.randint(x_range[0][0], x_range[0][1]),
random.randint(x_range[1][0], x_range[1][1]),
random.randint(x_range[2][0], x_range[2][1])]
while True:
best_evaluate = evaluate(best_sol[0], best_sol[1], best_sol[2])
current_best_value = best_evaluate
sols = [best_sol]
for i in xrange(len(best_sol)):
if best_sol[i] > x_range[i][0]:
sols.append(best_sol[0:i] + [best_sol[i]-1] + best_sol[i+1:])
if best_sol[i] < x_range[i][1]:
sols.append(best_sol[0:i] + [best_sol[i]+1] + best_sol[i+1:])
print sols
for s in sols:
el = evaluate(s[0], s[1], s[2])
if el < best_evaluate:
best_sol = s
best_evaluate = el
if best_evaluate == current_best_value:
break
print 'best sol：', current_best_value, best_sol
某次運行結果如下：
[[0, 5, 1], [-1, 5, 1], [1, 5, 1], [0, 4, 1], [0, 6, 1], [0, 5, 0], [0, 5, 2]]
[[-1, 5, 1], [-2, 5, 1], [0, 5, 1], [-1, 4, 1], [-1, 6, 1], [-1, 5, 0], [-1, 5, 2]]
[[-2, 5, 1], [-1, 5, 1], [-2, 4, 1], [-2, 6, 1], [-2, 5, 0], [-2, 5, 2]]
[[-2, 4, 1], [-1, 4, 1], [-2, 3, 1], [-2, 5, 1], [-2, 4, 0], [-2, 4, 2]]
[[-2, 3, 1], [-1, 3, 1], [-2, 2, 1], [-2, 4, 1], [-2, 3, 0], [-2, 3, 2]]
[[-2, 2, 1], [-1, 2, 1], [-2, 3, 1], [-2, 2, 0], [-2, 2, 2]]
[[-2, 2, 2], [-1, 2, 2], [-2, 3, 2], [-2, 2, 1]]
best sol： -2 [-2, 2, 2]
三、如何找到全局最優
爬山法獲取的最優解的可能是局部最優，如果要獲得更好的解，多次使用爬山算法（需要從不同的初始解開始爬山），從多個局部最優解中找出最優解，而這個最優解也有可能是全局最優解。
另外，模擬退火算法也是一個試圖找到全局最優解的算法。
新聞熱點
疑難解答
圖片精選
