爬山算法簡(jiǎn)介和Python實(shí)現(xiàn)實(shí)例

更新時(shí)間：2014年04月26日 09:30:53 作者：

這篇文章主要介紹了爬山算法,爬山法（climbing method）是一種優(yōu)化算法，其一般從一個(gè)隨機(jī)的解開(kāi)始，然后逐步找到一個(gè)最優(yōu)解（局部最優(yōu)）然后用Python實(shí)現(xiàn)了這個(gè)算法,需要的朋友可以參考下

一、爬山法簡(jiǎn)介

爬山法（climbing method）是一種優(yōu)化算法，其一般從一個(gè)隨機(jī)的解開(kāi)始，然后逐步找到一個(gè)最優(yōu)解（局部最優(yōu)）。假定所求問(wèn)題有多個(gè)參數(shù)，我們?cè)谕ㄟ^(guò)爬山法逐步獲得最優(yōu)解的過(guò)程中可以依次分別將某個(gè)參數(shù)的值增加或者減少一個(gè)單位。例如某個(gè)問(wèn)題的解需要使用3個(gè)整數(shù)類型的參數(shù)x1、x2、x3，開(kāi)始時(shí)將這三個(gè)參數(shù)設(shè)值為(2,2,-2)，將x1增加/減少1，得到兩個(gè)解(1,2,-2), (3, 2,-2)；將x2增加/減少1，得到兩個(gè)解(2,3, -2)，(2,1, -2)；將x3增加/減少1，得到兩個(gè)解(2,2,-1)，(2,2,-3)，這樣就得到了一個(gè)解集：
(2,2,-2), (1, 2,-2), (3, 2,-2), (2,3,-2), (2,1,-2), (2,2,-1), (2,2,-3)
從上面的解集中找到最優(yōu)解，然后將這個(gè)最優(yōu)解依據(jù)上面的方法再構(gòu)造一個(gè)解集，再求最優(yōu)解，就這樣，直到前一次的最優(yōu)解和后一次的最優(yōu)解相同才結(jié)束“爬山”。

二、Python實(shí)例

設(shè)方程 y = x1+x2-x3，x1是區(qū)間[-2, 5]中的整數(shù)，x2是區(qū)間[2, 6]中的整數(shù)，x3是區(qū)間[-5, 2]中的整數(shù)。使用爬山法，找到使得y取值最小的解。

代碼如下：

復(fù)制代碼代碼如下:

import random

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
某次運(yùn)行結(jié)果如下：

[[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]

可以看到，最優(yōu)解是-2，對(duì)應(yīng)的x1、x2、x3分別取值-2、2、2。

三、如何找到全局最優(yōu)

爬山法獲取的最優(yōu)解的可能是局部最優(yōu)，如果要獲得更好的解，多次使用爬山算法（需要從不同的初始解開(kāi)始爬山），從多個(gè)局部最優(yōu)解中找出最優(yōu)解，而這個(gè)最優(yōu)解也有可能是全局最優(yōu)解。

另外，模擬退火算法也是一個(gè)試圖找到全局最優(yōu)解的算法。

您可能感興趣的文章: