黄金分割搜索

✍ dations ◷ 2025-06-10 14:22:19 #算法

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

而φ就是黄金比例:

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

相关

  • 精神胜利法精神胜利法,也称为阿Q精神,是鲁迅所著的《阿Q正传》所批判的一个自我安慰法,这个方法侧面以讽刺的姿态描写了中国人的心态,也有贬义之意。精神胜利法其实是在讽刺当时中国人在精
  • 罐装食品罐装食品,是指用金属制的容器所包装的食品,俗称的罐头,是其中一种罐装食品,罐头食品是一种储存食物的方法。食物先被高温处理,再被放进以锡或其他金属制造的罐内,并进行真空处理。
  • 德靖壮语德靖壮语,又称央壮语,是壮语的一种,属中部台语支,通行于中国广西壮族自治区西南部的德保、靖西、那坡、天等和大新两县西部小部,在越南高平省境内也有少数人使用,使用总人数大约有
  • 凯恩舍姆坐标:51°24′49″N 2°29′48″W / 51.4135°N 2.4968°W / 51.4135; -2.4968凯恩舍姆(Keynsham)英格兰西南部的一个城镇和民政教区,属于索美塞特郡,靠近布里斯托尔和巴斯,人口约
  • 黄芝琪黄芝琪(Grace Huang,1983年1月26日-),是澳洲籍华裔模特儿兼演员,在澳洲出生。代表作品包括《名扬四海》、《超脑特工》、《寒战》、《开脑儆探》。
  • 马德琳·奥尔布赖特马德琳·亚娜·科贝尔·奥尔布赖特(英语:Madeleine Jana Korbel Albright;1937年5月15日-)原名玛丽·亚娜·科贝洛娃(捷克语:Marie Jana Korbelová),是一位捷克出生的美国政治人物和
  • 陈宇晖陈宇晖(英语:Danny Chen,1992年5月26日-2011年10月3日)是一名驻扎在阿富汗的华裔美军二等兵,2011年因不堪军中同袍凌虐而于阿富汗自杀身亡。1992年5月26日,陈宇晖生于美国纽约州纽
  • 博卡尔丹博卡尔丹(Bhokardan),是印度马哈拉施特拉邦Jalna县的一个城镇。总人口16950(2001年)。该地2001年总人口16950人,其中男性8903人,女性8047人;0—6岁人口2931人,其中男1570人,女1361人;识
  • 丹布勒丹布勒(僧伽罗语:දඹුල්ල,Dambulla,泰米尔语:தம்புள்ளை),或译丹布拉,是斯里兰卡中央省马特莱区的一个城镇。位于斯里兰卡最大城市科伦坡东北148km处,中部省省会康提以
  • 景禐景禐(1860年-1911年),又名景瑗,字锦云,号佩珂、闽生,兀扎拉氏,满洲镶蓝旗人,清朝末年政治人物。光绪己卯举人,二十年(1894年),景禐中进士,同年五月,改翰林院庶吉士。光绪二十一年四月,散馆,以