爬山算法简介和Python实现实例
发布时间:2023-08-10 04:56:29
一、爬山法简介
爬山法(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]
可以看到,最优解是-2,对应的x1、x2、x3分别取值-2、2、2。
三、如何找到全局最优
爬山法获取的最优解的可能是局部最优,如果要获得更好的解,多次使用爬山算法(需要从不同的初始解开始爬山),从多个局部最优解中找出最优解,而这个最优解也有可能是全局最优解。
另外,模拟退火算法也是一个试图找到全局最优解的算法。
猜你喜欢
- JS调试技巧技巧一:格式化压缩代码 技巧二:快速跳转到某个断点的位置右侧的Breakpoints会汇总你在JS文件所有打过的断点,点击跟ch
- 著名的老掉牙的IE6.0在我这里已经有六年工龄了,前几天朋友拿到个IE8.0新的Beta版本,我的Sever2003装不上,大为扫兴。Chr
- 导言作为web开发人员,我们的生活围绕着数据操作。我们建立数据库来存储数据,写编码来访问和修改数据,设计网页来采集和汇总数据。本文是研究在A
- 负责为网页编程语言提供标准化服务的W3C组织(World Wide Web Consortium)近日开始修改超文本标记语言的定义,计划为该
- ASCII码键盘ASCII 码键盘ASCII 码键盘ASCII 码键盘27ESC32SPACE33!34"35#36$37%38&
- 这个效果本身难度不大,主要在程序结构和扩展中下了些功夫,务求用起来更方便,能用在更多的地方。程序特点 1,同一个提示框用在多个触发元素时,只
- 核心代码function convert2utf8($string) { return iconv(&
- 背景:pony是公司的首席体验官、首席产品经理。这次在产品峰会上pony将自己平时经验的积累与大家交流,体验较细。这次分享研发管理部,设计中
- 我就废话不多说了,大家还是直接看代码吧~#aaa.py#version 3.5import os #这句是没用了,不知道为什么markdow
- 在软件项目实施的时候,数据导入一直是项目人员比较头疼的问题。其实,在SQL Server中集成了很多成批导入数据的方法。有些项目实施顾问头疼
- 在服务器上生成动态内容是使用ASP最主要的原因之一,所以我们选择的第一个测试项目是确定把动态内容发送到应答流使用什么方法最好。基本的选择有两
- 又从 James Padolsey 这里得到个好的点子。在实际写脚本过程中可能有段 Javascript 和 HTML 非常相关(比如实例化
- Create PROC P_viewPage
- 上一课:ACCESS入门教程:初识Access 2000窗口接口简介 通过上一课的学习,你是否感觉Access的窗口和接口还有点搞不清楚,对
- (5)SELECT (5-2) DISTINCT(5-3)TOP(<top_specification>)(5-1) <s
- 想到TDE(Transparent Data Encryption)。 TDE MSDN 说明: “透明数据加密”(TDE) 可对数据和日志
- python给数据加上高斯噪声一开始用MATLAB给数据加噪声很简单,就一句话:% 给数据加指定SNR的高斯噪声signal_noise =
- 1. document.form.item 问题 (1)现有问题:现有代码中存在许多 document.formName.item(&quo
- 当你的查询相对简单的时候,每次从头开始创建SQL语句也不费什么工夫,不过,复杂的查询就不同了,每次都从头来会产生很多开发错误。因此,一旦让S
- Dreamweaver 2004 除了可以插入 Flash SWF 動畫、Flash 文字和 Flash 按鈕以外,這次又新增加了一個叫做