黄金分割搜索

✍ dations ◷ 2025-09-09 02:12:49 #算法

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

而φ就是黄金比例:

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

相关

  • 毒参毒参属(学名:Conium)是伞形目伞形科下的一个属,为二年生草本植物。该属约有4种,毒参(Conium maculatum)为模式种,分布于欧洲、亚洲、北非和北美洲。
  • 右旋苯丙胺右旋安非他命(英语:Dextroamphetamine)是强力中枢神经兴奋剂,也是苯丙胺(“安非他命”) 的对映异构体,是注意力不足过动症(ADHD)和发作性嗜睡病的处方药。此外,它也被用作提升运动员能
  • 五色五色可能是指:
  • 柴尔德里斯县柴尔德里斯县(Childress County, Texas)位美国德克萨斯州北部的一个县,东北邻奥克拉荷马州。面积1,848平方公里。根据美国2000年人口普查,共有人口7,688人。县治柴尔德里斯(Child
  • 奥地利经济学派奥地利经济学派(英语:Austrian School)是一种经济学派,源自19世纪末的奥地利,延续至20世纪的美国等地,代表人物包括了卡尔·门格尔、欧根·博姆-巴维克、弗里德里克·哈耶克、路德
  • 维斯理学院维斯理学院(英语:Wellesley College,又译卫斯理学院),美国女子文理学院,成立于1875年,地处马萨诸塞州波士顿城西的小镇韦尔斯利,为美国七姐妹学院之一。据《美国新闻与世界报道》杂
  • 欧洲旗目前欧洲联盟和欧洲委员会使用的旗帜以深蓝色为底色,十二颗五角金星环成一圆组成,是这两个组织的旗帜和徽章。两个组织都称它为“欧洲旗”代表整个大洲,但是在欧洲委员会中使用
  • 吉尔德里斯·蒂特尼斯吉尔德里斯·蒂特尼斯(立陶宛语:Giedrius Titenis;1989年7月21日-)是一位立陶宛游泳运动员。他擅长蛙泳项目。在2009年世锦赛上,他获得了200米蛙泳项目的铜牌。
  • EDVAC报告书的第一份草案《EDVAC报告书的第一份草案》(英语:First Draft of a Report on the EDVAC),一般简称为,是由约翰·冯·诺伊曼所撰写共101页未完成(英语:unfinished work)文件,于1945年6月30日,由ENIA
  • FictionJunctionFictionJunction(フィクション ジャンクション)是日本作曲家梶浦由记Solo Project的总称。(但不包含梶浦制作的原声音乐。)梶浦由记除担当键盘乐器,还不定期(几近于无,例如:synchron