爬山算法简介和Python实现实例

一、爬山法简介

爬山法（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取值最小的解。

代码如下：

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
某次运行结果如下：
[[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]

三、如何找到全局最优

爬山法获取的最优解的可能是局部最优，如果要获得更好的解，多次使用爬山算法（需要从不同的初始解开始爬山），从多个局部最优解中找出最优解，而这个最优解也有可能是全局最优解。

另外，模拟退火算法也是一个试图找到全局最优解的算法。

到此这篇关于爬山算法简介和Python实现实例就介绍到这了。人这一生能力有限，但是努力无限，努力做一个的人，做一个心态阳光的人，做一个积极向上的人，用正能量激发自己，也感染身边的，你阳光，世界也会因你而精彩！一辈子要记住三句话：看人长处、帮人难处、记人好处，做一个充满正能量的人！更多相关爬山算法简介和Python实现实例内容请查看相关栏目，小编编辑不易，再次感谢大家的支持！