黄金分割搜索

✍ dations ◷ 2025-04-26 12:35:07 #算法

黄金分割搜索是一种通过不断缩小单峰函数的最值的已知范围,从而找到最值的方法。它的名称源于这个算法保持了间距具有黄金分割特性的三个点。这个算法与斐波那契搜索和二分查找关系紧密。黄金分割搜索是由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}} ,则必须使:

而φ就是黄金比例:

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

相关

  • J01BA·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码J01(抗菌药)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO Collaboratin
  • 弗雷格弗里德里希·路德维希·戈特洛布·弗雷格(德语:Friedrich Ludwig Gottlob Frege,宽式IPA:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","S
  • 土 (消歧义)土,即土壤,是一种自然体,由数层不同厚度的土层所构成,主要成分是矿物质。土还可以指:
  • 霍华德·休斯小霍华德·洛巴德·休斯(英语:Howard Robard Hughes, Jr.,1905年12月24日-1976年4月5日),是美国著名商业大亨、投资人、飞行员、航空工程师、电影制片人、慈善家,当时世界上最富有
  • 质体醌质体醌(英语:Plastoquinone,简称:PQ)是一种醌分子,与光合作用中光反应的电子传递链有关。质体醌被还原(得到叶绿体基质中的两个质子(H+),并与来自光系统 II的两个电子(e-)相结合),形成质体
  • 虎鲸虎鲸(学名:Orcinus orca, 英文:Killer whale 或 Orca)为齿鲸小目海豚科下体型最大的物种,又称杀手鲸、杀人鲸、逆戟鲸。地球上的所有大洋中都有虎鲸生活,且为全球性分布,除了在波罗
  • 约瑟夫·玛罗德·威廉·透纳约瑟夫·玛罗德·威廉·特纳(英语:Joseph Mallord William Turner,1775年4月23日-1851年12月19日),简称J·M·W·特纳(J. M. W. Turner)或威廉·特纳(William Turner),又译透纳,英国浪漫
  • 幸福的黄手绢《幸福的黄手绢》(日语:《幸福の黄色いハンカチ》,罗马字:Shiawase no kīroi han kachi),又译名《幸福的黄手帕》,改编自彼得·汉密尔(英语:Pete Hamill)(Pete Hamill)的公路小说《回家
  • 伊尔姆·赫尔曼伊尔姆·赫尔曼(德语:Irm Hermann,1942年10月4日-2020年5月26日),德国女演员,曾参演160余部电影和电视剧作品,两次获得德国电影奖最佳女演员奖。她曾长期与德国新浪潮知名导演法斯宾
  • 遥控战车遥控战车(Teletank)为一系列由苏联于1930年代至1940年代初期生产的遥控式(英语:remotely controlled vehicle)坦克的泛称,以“T”开头表示其战车型号。 它们首次于第二次世界大战