最优化 单峰搜索算法

  • 更新时间: 2017-12-29
  • 来源: 原创或网络
  • 浏览数: 36次
  • 字数: 3451
  • 发表评论

f(x)在区间[a,b]内只有一个极小值点,要找到这个极小值点或者这个极小值点所在的区间[x1,x2],其中[x1, x2]要远远小于[a, b]

一个通用的结论

要缩小区间,必须计算两个点,如果所示,必须计算x1和x2,然后对函数值进行比较。如果f(x1)小于f(x2),那么就说明极小值点一定在a到x2之间,反之也是这个思路。途中后面的两个式子将在以后的方法中反复使用。注意这了仅仅指的是单峰函数

具体的方法基本都是基于以上的思路,不同的是怎么确定x1和x2

二分搜索(dichotomous search)

步骤一:首先找到[a,b]的中间点c,c=(a+b)/2,这就是“二分”的意思

步骤二:事先确定一个值sigma,在c左右各找二分之sigma,产生x1、x2。这个就是通用结论中的x1、x2

步骤三:按照通用结论中的方法来做

步骤四:循环确定区间[x1, x2],直到满足要求为止

查找速度:新区间的长度L(n+1),上一个区间的长度L(n),他们的关系是:L(n+1) = L(n)/2 + sigma/2

这个方法其实只是确定了x1和x2怎么找。

计算量:需要计算三个点

缺点:一是需要预先指定sigma,指定不好会有问题。二是得到x1、x2需要计算三个点

1 等分区间搜索(equal-interval search)

三点等分(也就是区间四等分)

算法跟上面的基本一致,下面通过一个计算题描述一下

第一步:根据题目要求,区间在[0, 1]之间

第二步:将区间三等分,得到三个点,x1、x2、x3

第三步:计算x1、x2、x3对应的函数值,比较大小,这个题目比较特殊,x2、x3点的函数值是一样的,所以如果认为x2是最小点,那么确定的函数区间为[0.25, 0.75],如果认为x3是最小点,那么选取的区间是[0.5, 1]。区间缩小为原先的1/2

查找速度:L(n+1) = L(n)/2

计算量:第一轮需要计算三个点的值,以后只需要计算两个点的值


单模函数求极值问题:(黄金分割在上,二分法在下),明显黄金分割更快
注意:用阴影表示的“可能区域”里面始终都有三个已经计算过的点。

最优化 单峰搜索算法,by 5lulu.com

单根函数求根问题:(黄金分割在上,二分法在下),明显二分法更快
注意:用阴影表示的“可能区域”里面始终都有两个已经计算过的点。

最优化 单峰搜索算法,by 5lulu.com

分割的越“均衡”,算法执行得就越快。求根问题中的二分法和求极值问题中的黄金分割法都满足每次更新的“可行区域”和上一个“可行区域”是相似的


标签: 搜索 分区 c 二分搜索

我来评分 :6
0

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议