优选法的对称试验最优性

胡毓达

教授，上海交通大学数学系，上海 200240

优选法的对称试验最优性

胡毓达

教授，上海交通大学数学系，上海 200240

优选法；斐波那契数列；黄金分割数

在实际应用中，通过试验的办法尽快求得只有一个最优方案问题的近似最优方案的方法，统称为优选法。利用斐波那契数列和黄金分割数来构建的近似黄金分割法类，是优选法中最重要和常用的一类方法。本文给出了近似黄金分割法类的第一个试验点与相应试验方法具有最大对称试验最优性次数之间的关系，据此可以判定任一近似黄金分割法的最大对称试验最优性次数。

20世纪60—70年代，中国数学家华罗庚提倡在全国推广被称为“优选法”的应用，在工矿企业取得了普遍成效。于是，在这类“尽可能少做试验、尽快地找到生产最优方案的方法”[1]中，使用最多的“0.618法”在民众中曾广为传播。鉴于“0.618法”的最优性常常会与理论上的“黄金分割法”的最优性相混淆，特别是在不少著作中甚至就将“0.618法”等同于“黄金分割法”。为此，本文将对优选法中最典型的“n次斐波那契法”“黄金分割法”和“0.618法”等黄金分割法类，在搜索最优方案时的最优性问题作出统一综述和澄清。

1 单峰问题与对称试验方法

在现实世界中，许多事物都会具有某种意义下的最优性问题。例如，一些化工产品有原材料的最优配比问题，机床上的刀具加工零部件有最优切削角问题，加工某些食品时则有最优温度问题，等等。这些要寻求最优配比、最优切削角和最优温度的问题的共同点，都是要在它们的所有可能方案中，求得其最优方案的问题。在数学上，则都归结为在区间[0，1]上，寻求只有一个峰(最大)值函数φ(x)，使其函数值达到最优(大)的最优(大)点的问题(求最小值可转化为求其负数的最大值）。一般地，设φ(x)是区间[a,b](a＜b)上的单值(只有一个值的)函数，如存在一点x*∈(a,b)，使得φ(x)在[a,x*]上严格递增，同时在[x*,b]上严格递减，则称φ(x)是[a,b]上的单峰函数，[a,b]是φ(x)的单峰区间。在单峰区间[a,b]上，求使单峰函数φ(x)取得最优(大)值的最优(大)点x*的问题，称为单峰问题。

由于在实际应用中出现的单峰问题，一般都无法写出其单峰函数的解析表达式。因此，对于这类问题的实用求解方法是：通过直接试验取得试验点处的函数值，然后经试验函数值的比较，淘汰掉最优点不在其中的“废区间”，逐次缩小单峰区间来求得其近似最优点。此类方法统称为淘汰废区间方法。

设x*是[0, 1]中单峰函数φ(x)的最优点。为更快地求得x*的近似点，通常采用如下在单峰区间[0, 1]中逐步进行“对称试验”的淘汰废区间方法。具体做法是：第1步，在第1级单峰区间[0, 1]中，取第1个(次)试验点x1(＞0.5)和与它对称的第2个试验点x2=1－x1(＜0.5)，然后比较φ(x1)和φ(x2)的值。这时有以下3种可能：①若φ(x1)＞φ(x2)，必有x*∈[x2,1]和x*∈/ [0,x2]，故可淘汰掉废区间[0,x2]，留下缩小了的第2级单峰区间[t1,t2]=[x2, 1]和留下第2次试验点=x1(图1(a))；②若φ(x1)＜φ(x2)，必有x*∈[0,x1]，同理淘汰掉废区间[x1, 1]，留下第2级单峰区间[t1,t2]= [0,x1]和第2次试验点=x2(图1(b))；③若φ(x1)=φ(x2)，因有x*∈[x1,x2]，则可随意淘汰掉[0,x2]或者[x1, 1]，留下第2级单峰区间[t1,t2]=[x2, 1]或[0,x1]和第2次试验点=x1或x2(图1(c))。如此，不论发生哪一种情况，都可以将第1级单峰区间[0, 1]缩小成第2级单峰区间[t1,t2]。这时，完成了第1步对称试验。第2步，在第2级单峰区间[t1,t2]中，再选取第2次试验点的对称试验点x3，经同样的函数值比较之后，又可淘汰掉废区间，得到又缩小了的第3级单峰区间[t2,t3]和留下第3次试验点(图2)，等等。按照以上做法，在单峰区间[0, 1]上连续取n(≥2)个试验点和做n-1步对称试验的方法，称为[0, 1]上的n次对称试验方法，简记“x1法”。

图1 淘汰废区间方法

图2 n次对称试验方法

上述采取对称试验方法来缩小单峰区间，以逐步寻求问题的近似最优点，其原因是由于事先人们并不知道所考虑问题中单峰函数的性态。事实上，不论所考虑单峰函数的性态如何，只要用对称试验方法，不管淘汰掉哪一个废区间，所留下单峰区间的长度都是相等的。如若采用两个试验点在单峰区间中是不对称的试验方法，经函数值比较之后，可能会留下较长的单峰区间(图3)。因此，使用对称试验方法总要比用不对称的试验方法好。

图3 不对称试验方法

2 斐波那契数列和黄金分割数

本节介绍优选法中两个重要概念：斐波那契数列和黄金分割数。

1202年，意大利数学家列奥纳多(Leonardo)在署名为斐波那契(Fibonacci L.)的一本《算盘册(Liber Abaci)》的书中[2]，曾提出下面的兔子繁殖问题：兔子出生后两个月可生小兔，设1对兔子每月恰生一雄一雌两只小兔，现若饲养了1对初生的小兔，问一年后共有多少对兔子？

对于此问题，我们可以按图4(a)(黑色的为成熟兔子，白色的为未成熟兔子)推算如下：

第0个月后(第1个月中)，有1对未成熟小兔；

第1个月后，小兔成熟，仍只有1对兔子；

第2个月后，这对老兔子生了1对小兔，共有2对兔子；

第3个月后，老兔子又生了1对小兔，而上月出生的小兔成熟，这时共有3对兔子；

第4个月后，老兔子和第2个月后出生的兔子(已成熟)各生1对，连同它们本身计有4对，加上上月出生的小兔成熟，这时共有5对兔子；

图4 斐波那契数列的实例

…………

按此推算，可得表1。由此可知，答案是：一年(第12个月)后共有兔子233对。

表1 兔子繁殖问题

此外，如树木分枝问题的年份和分枝数(图4(b))，以及蜜蜂家系问题的传代数和祖先数之间，等等，也都遵循上述规律。

将表1中的月份数记作n(=0, 1, 2,…)，相应的兔子对数记作Fn，则有：{Fn}={1，1，2，3，5，8，13，21，34，55，89，144，233，377，…}。从兔子繁殖的规律，不难得知在数列{Fn}中，首两项为F0=1和F1=1，3个相连项之间有如下递推关系：

人们将具有上述性质的数列{Fn}，称为斐波那契数列，其中的Fn称为斐波那契数[2]。

另外，设ω是正实数，若它具有关系：

则称ω是[0, 1]中的黄金分割数，它在单位区间中的对应点叫黄金分割点，它把单位长度分割为两部分叫黄金分割或黄金分割比。根据式(2)可知，黄金分割的几何意义是：黄金分割点ω在单位区间[0, 1]中的位置，相当于它在[0,1]中的对称点1-ω在区间[0, ω]中的位置。

在现实世界中，黄金分割现象普遍存在。特别是在建筑艺术中，人们认为使用黄金分割比的设计是最美的，因此在许多著名建筑中窗户的宽与高之比常取黄金分割比(图5(a))。又如，“标准”人体的肚脐高与身高之比，以及手肘到指尖与臂长之比，也都是黄金分割数(图5(b))，等等。

从(2)可知，黄金分割数ω满足二次方程ω2+ω-1=0。求解此方程，得其正根即黄金分割数：

由(1)和(3)，可以证明斐波那契数和黄金分割数之间有如下关系[1,3]：

图5 意大利建筑大师阿尔伯蒂(A lberti L. B., 1404－1472)用黄金分割比建造的代表作——鲁奇兰府邸(左图)；人体中的黄金分割比(右图)

3 斐波那契法和黄金分割法

现在，分别利用斐波那契数列和黄金分割数来构造优选法中寻求[0, 1]上单峰问题近似最优点的两个典型方法。

先给出由斐波那契数列来构造的方法。

n次斐波那契法设φ(x)是[0, 1]上的单峰函数。

(ii)逐步按对称试验方法进行。

(iii)直至给出第n次试验点后，取最后留下的点作为问题的近似最优点。

下面介绍利用黄金分割数来构造求单峰问题近似最优点的方法。

黄金分割法设φ(x)是[0, 1] 上的单峰函数。

(i)在第1级单峰区间[0, 1]中，取第1个试验点为x1=ω和与它对称的第2个试验点x2=1-ω。比较φ(x1)和φ(x2)的值之后淘汰掉废区间，留下第2级单峰区间和留下第2次试验点=ω或1-ω。

(ii)逐步按对称试验方法进行。

(iii)直至最后得到足够小的留下的单峰区间，取其中点(或其中任意一点)，作为问题的近似最优点。

这种利用黄金分割数ω来确定第1个试验点，连续做n次试验(n-1步对称试验)的方法，叫做n次黄金分割法，简记“ω法”。

黄金分割法的最优性[5]：对于[0, 1]上的单峰问题，记Δn[ω法]是“ω法”做n次试验后最后留下区间的长度，则对于任意一个淘汰废区间方法U≠“ω法”，总存在一个正整数N(≥2)，当n≥N后必有Δn[ω法]＜Δn[U]，其中Δn[U]是U做n次试验后最后留下区间的长度。

黄金分割法的这一性质说明，对于[0, 1]上任意一个单峰问题，用[0, 1]上的其他任何一个淘汰废区间方法来寻求它的最优点时，总存在一个试验次数，在这个次数之后，黄金分割法最后留下的n次区间精度与该淘汰废区间方法的n次区间精度相比是“最小的”。通常人们把黄金分割法的这一性质叫做黄金分割法具有无穷远处最优性。由黄金分割法的第1个试验点ω和寻优步骤，利用(2)可以推得Δn[ω法]=ωn-1。另外，从黄金分割法的试验步骤还可得知，使用它来寻求单峰问题的近似最优点时，并不受试验次数的限制。但是，黄金分割法的不足是，黄金分割数ω是一个无理数，因此这一方法只具有理论上的意义。在应用中，实际上是无法使用它来寻求单峰问题的最优点的。

4 近似黄金分割法及其对称试验最优性

从上一节的介绍，我们知道，用n次斐波那契法来寻求单峰问题的最优点，要受到试验次数的限制；而黄金分割法中的黄金分割数是一无理数，在应用中又无法用它来进行数值计算。为了克服这两个方法的不足，我们来考虑在对称试验方法中，取第1个试验点为有理近似黄金分割数的方法，同时，考察此类方法是否具有某种最优性？若有，则它具有怎样的最优性？

近似黄金分割法设φ(x)是[0, 1] 上的单峰函数。

(ii)逐步按对称试验方法进行。

(iii)直至得到足够小的留下的单峰区间，取其中点(或其中任意一点)作为问题的近似最优点。

近似黄金分割法的最优性[6]对于[0, 1]上的单峰问题，记有理数≈ω是近似黄金分割法的第1个试验点。若n是使

成立的m的最大值，则其n次区间精度Δn[法] ＜Δn[x法](其中当n是偶数时，x∈(0.5,1)/当n是奇数时，x∈(0.5,1)/

上述近似黄金分割法的最优性的意义是，对于[0, 1]上任意一个单峰问题，当n是满足(5)的m的最大值时，由“法”做n次试验后，其最后留下的n次区间精度Δn[法]与其他任何“x法”(n是偶数时，x∈(0.5,1)/(]；n是奇数时，x∈(0.5,1)/[)的n次区间精度相比是“最小的”。近似黄金分割法的这一性质，称为“法”具有n次对称试验最优性，其中的n是“法”的最大对称试验最优性次数。从近似黄金分割法的第1个试验点，由(1)用数学归纳法可以推得它的n次区间精度

表2 前5个近似黄金分割法以及n次斐波那契法和黄金分割法对应的最大对称试验最优性次数及其区间精度

(2013年10月22日收稿)

[1] 华罗庚. 优选学[M]. 北京: 科学出版社, 1981.

[2] Β о р о б ъëв НН. Ч и с л а Ф и б о н а ч ч и [M]. М о с к в а: С о в е т с к и х Н а ц и о н а л ь н ы х Т е х н и ч е с к и хК н и г Т е о р и и и П у б л и к а ц и й Б ю р о, 1951.

[3] 胡毓达. 非线性规划[M]. 北京: 高等教育出版社, 1990.

[4] KIEFER J. Sequential m inimax search for a m aximun [J]. Proc Amer Math Soc, 1953, 4: 502-506.

[5] 洪加威. 论黄金分割法的最优性[J]. 数学的实践与认识, 1973, 2: 34-41.

[6] 胡毓达. 论异侧对称策略的最优性[J]. 上海交通大学学报, 1979, 3: 67-77.

(编辑：沈美芳)

The optimality of symmetry trial on optimum seeking methods

HU Yu-da
Professor, Department of Mathematics, Shanghai Jiaotong University, Shanghai 200240, China

Optimum seeking methods are those that in practice seek to obtain approximate optimal alternatives through trials for problem s w ith one optimum value. Approximate golden section methods, which use Fibonacci sequence or golden section number, constitute a class of methods that are most important and most often used. This paper gives the relationships of the fi rst trial point and the maximal number of the optimality of symmetry trials of approximate golden section methods. With these relationships, the maximal number of the optimality of symmetry trials can be determined for any approximate golden section method.

optimum seeking method, Fibonacci sequence, golden section number

10.3969/j.issn.0253-9608.2014.04.008