转载请注明出处:http://www.codelast.com/

在一维搜索(line search)中,Fibonacci搜索与黄金比例搜索是一对“亲兄弟”,因为它们都是用分割区间的方法来求极小值,所以过程是相似的。本文就随意聊一下它们的区别与联系。

从名字上看,Fibonacci搜索算法当然与Fibonacci数列有关。
Fibonacci数列用如下式子表达:
{F_0} = 0,\;{F_1} = 1,\;{F_n} = {F_{n - 1}} + {F_{n - 2}}
即:第1个数为0,第2个数为1,后面的每个数都是前两个数之和,例如 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
文章来源:http://www.codelast.com/
Fibonacci搜索算法就是利用了该数列进行区间的分割。与黄金比例搜索算法每次分割区间时使用固定的比例(0.618)不同,Fibonacci搜索算法的区间缩短率是不固定的 \frac{{{F_{i - 1}}}}{{{F_i}}}

Fibonacci搜索算法要先确定搜索点的个数,并且在用分割方法求一维极小化问题时,Fibonacci是最优的策略(袁亚湘的书上说这个是可以证明的,但我没看怎么证明)。但跟Golden Section Search相比,由于Golden Section Search简单,所以更常用。并且,在实际中,为了能达到更快的收敛速度,通常会让Golden Section Search配合使用逆抛物内插或其他超线性收敛技术(例如复杂的Brent算法,就是结合了黄金分割+逆抛物内插的可靠line search算法),所以,也不是非用Fibonacci不可。
文章来源:http://www.codelast.com/
最后,Fibonacci搜索算法是线性收敛的,它的极限形式正是Golden Section Search,即:
\mathop {\lim }\limits_{n \to \infty } \frac{{{F_{n - 1}}}}{{{F_n}}} = \frac{{\sqrt 5 - 1}}{2} \approx 0.618

[原创]漫谈line search中的Fibonacci搜索与黄金比例搜索

发表评论

电子邮件地址不会被公开。 必填项已用*标注