黄金分割搜索

✍ dations ◷ 2025-10-15 04:17:31 #算法

黄金分割搜索是一种通过不断缩小单峰函数的最值的已知范围,从而找到最值的方法。它的名称源于这个算法保持了间距具有黄金分割特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由Kiefer提出的,而斐波那契搜索是由Avriel和Wilde所提出。

上图表示了算法中找最小值的一个步骤。 f ( x ) {\displaystyle f(x)} 的函数值位于垂直坐标轴上,参数x位于水平坐标轴。已经有三个位于函数 f ( x ) {\displaystyle f(x)} 上的点的值被计算出来。: x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} ,和 x 3 {\displaystyle x_{3}} 。可见 f 2 {\displaystyle f_{2}} 小于 f 1 {\displaystyle f_{1}} f 3 {\displaystyle f_{3}} ,所以很明显的,最小值处于 x 1 {\displaystyle x_{1}} x 3 {\displaystyle x_{3}} 之间。

接下来的步骤是通过计算函数位于另一个点 x 4 {\displaystyle x4} 的值。在最大的区间选择 x 4 {\displaystyle x4} 会更有效率,例如: x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} 之间。从图中我们可以看出,如果函数的值落在 f 4 a {\displaystyle f_{4a}} 的话,最小值落于 x 1 {\displaystyle x_{1}} x 4 {\displaystyle x_{4}} 之间,并且新的一组点将会是 x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 4 {\displaystyle x_{4}} 。然而如果函数的值为 f 4 b {\displaystyle f_{4b}} 的话,新的一组点将会是 x 2 {\displaystyle x_{2}} x 4 {\displaystyle x_{4}} x 3 {\displaystyle x_{3}} 。因此,无论是哪种情况,我们都可以建立一个新的更狭窄的区间,用于搜索函数的最小值。

由图可知,新的区间会介于 x 1 {\displaystyle x_{1}} x 4 {\displaystyle x_{4}} ,长度为a+c,或者介于 x 2 {\displaystyle x_{2}} x 3 {\displaystyle x_{3}} ,长度为 b {\displaystyle b} 。黄金分割搜索要求这些区间是相等的。若不是如此,较宽的区间会被使用很多次,降低了收敛率。为了确保 b {\displaystyle b} = a {\displaystyle a} + c {\displaystyle c} ,算法应确保 x 4 {\displaystyle x_{4}} = x 1 {\displaystyle x_{1}} - x 2 {\displaystyle x_{2}} + x 3 {\displaystyle x_{3}}

然而 x 2 {\displaystyle x_{2}} 的确定仍是一个问题。我们避免了 x 2 {\displaystyle x_{2}} 非常接近 x 1 {\displaystyle x_{1}} 或者 x 3 {\displaystyle x_{3}} 的情况,确保了每一次迭代区间宽度会缩小同样的比例。

为了确保计算 f ( x 4 ) {\displaystyle f(x_{4})} 后的值与之间的成比例,假设 f ( x 4 ) {\displaystyle f(x_{4})} 的值为 f 4 a {\displaystyle f_{4}a} ,且我们新的一组点为 x 1 {\displaystyle x_{1}} x 2 {\displaystyle x_{2}} x 4 {\displaystyle x_{4}} ,则必须使:

而φ就是黄金比例:

这就是这个算法被成为黄金分割搜索的原因。

相关

  • 齐民要术《齐民要术》是中国保存得最完整的一本古代农牧情况的钜著,由北魏官员贾思勰所著,成书于东魏武定二年(544年),另一说为533年至544之间。收录公元6世纪时中国黄河流域下游地区的农
  • Columbia University Press哥伦比亚大学出版社(英语:Columbia University Press)是哥伦比亚大学系统的一部分,创建于1893年。它是独立于哥伦比亚大学运作的非盈利出版机构,宗旨是促进历史学、文学、理学、
  • 蒙特利尔工程学院大屠杀蒙特利尔工程学院大屠杀(法语:Tuerie de l'École polytechnique de Montréal,英语:École Polytechnique massacre),又被称为蒙特利尔大屠杀,是1989年12月6日发生于加拿大蒙特利
  • 草脱净草脱净(亚脱净,英语:Atrazine,ATR)是一种三嗪类除草剂,在多国广泛使用。属于持久性有机污染物,因污染问题已经被欧盟禁止使用。中国大陆地区使用“莠去津”作为产品名称。无色粉末
  • NET653020538ENSG00000103546ENSMUSG00000055368P23975O55192XR_933403、NM_001043、NM_001172501、NM_001172502、NM_001172504、XM_006721263、XM_011523295、XM_011523296、
  • 济南育英中学济南育英中学,是山东省济南市一所初级中学,1913年3月由李允峰等人倡办,7月诞生,9月正式开学。建校初期校名为山东私立育英中学,首任校长系代表中国参加巴黎和会的孔祥柯。1921年,
  • 五虎唱片五虎唱片公司(1964年 -1970年代),是一家曾经活跃于1960年代的台语流行歌曲唱片公司,五虎成立之初是以“雷虎”为名。1964年至1970年之间发行大量台语流行歌曲唱片,捧红了郭大诚、
  • 安庆府安庆府,南宋时设置的府。清朝中期以后,与徽州府等府同属一个巡抚,两者所属巡抚即安徽巡抚,安徽省省名亦源于此。因安徽巡抚亦称安庆巡抚,时安徽省又称安庆省。南宋庆元元年(1195年
  • Google CardboardGoogle Cardboard是Google所开发、与智能手机配合使用的虚拟现实头戴式显示器。该平台以其折叠式纸板头盔命名,旨在以廉价成本,激发对VR应用的兴趣和发展。按照Google发布的规
  • 好氧法好氧生物处理法(Aerobic Bioremediation)是在有游离氧存在的条件下,好氧微生物降解有机物,使其无害化、稳定化的处理过程。微生物利用废水中存在的有机污染物,作为营养源进行好