優(yōu)選法的對稱試驗最優(yōu)性

胡毓達

教授，上海交通大學數學系，上海 200240

優(yōu)選法的對稱試驗最優(yōu)性

胡毓達

教授，上海交通大學數學系，上海 200240

優(yōu)選法；斐波那契數列；黃金分割數

在實際應用中，通過試驗的辦法盡快求得只有一個最優(yōu)方案問題的近似最優(yōu)方案的方法，統(tǒng)稱為優(yōu)選法。利用斐波那契數列和黃金分割數來構建的近似黃金分割法類，是優(yōu)選法中最重要和常用的一類方法。本文給出了近似黃金分割法類的第一個試驗點與相應試驗方法具有最大對稱試驗最優(yōu)性次數之間的關系，據此可以判定任一近似黃金分割法的最大對稱試驗最優(yōu)性次數。

20世紀60—70年代，中國數學家華羅庚提倡在全國推廣被稱為“優(yōu)選法”的應用，在工礦企業(yè)取得了普遍成效。于是，在這類“盡可能少做試驗、盡快地找到生產最優(yōu)方案的方法”[1]中，使用最多的“0.618法”在民眾中曾廣為傳播。鑒于“0.618法”的最優(yōu)性常常會與理論上的“黃金分割法”的最優(yōu)性相混淆，特別是在不少著作中甚至就將“0.618法”等同于“黃金分割法”。為此，本文將對優(yōu)選法中最典型的“n次斐波那契法”“黃金分割法”和“0.618法”等黃金分割法類，在搜索最優(yōu)方案時的最優(yōu)性問題作出統(tǒng)一綜述和澄清。

1 單峰問題與對稱試驗方法

在現實世界中，許多事物都會具有某種意義下的最優(yōu)性問題。例如，一些化工產品有原材料的最優(yōu)配比問題，機床上的刀具加工零部件有最優(yōu)切削角問題，加工某些食品時則有最優(yōu)溫度問題，等等。這些要尋求最優(yōu)配比、最優(yōu)切削角和最優(yōu)溫度的問題的共同點，都是要在它們的所有可能方案中，求得其最優(yōu)方案的問題。在數學上，則都歸結為在區(qū)間[0，1]上，尋求只有一個峰(最大)值函數φ(x)，使其函數值達到最優(yōu)(大)的最優(yōu)(大)點的問題(求最小值可轉化為求其負數的最大值）。一般地，設φ(x)是區(qū)間[a,b](a＜b)上的單值(只有一個值的)函數，如存在一點x*∈(a,b)，使得φ(x)在[a,x*]上嚴格遞增，同時在[x*,b]上嚴格遞減，則稱φ(x)是[a,b]上的單峰函數，[a,b]是φ(x)的單峰區(qū)間。在單峰區(qū)間[a,b]上，求使單峰函數φ(x)取得最優(yōu)(大)值的最優(yōu)(大)點x*的問題，稱為單峰問題。

由于在實際應用中出現的單峰問題，一般都無法寫出其單峰函數的解析表達式。因此，對于這類問題的實用求解方法是：通過直接試驗取得試驗點處的函數值，然后經試驗函數值的比較，淘汰掉最優(yōu)點不在其中的“廢區(qū)間”，逐次縮小單峰區(qū)間來求得其近似最優(yōu)點。此類方法統(tǒng)稱為淘汰廢區(qū)間方法。

設x*是[0, 1]中單峰函數φ(x)的最優(yōu)點。為更快地求得x*的近似點，通常采用如下在單峰區(qū)間[0, 1]中逐步進行“對稱試驗”的淘汰廢區(qū)間方法。具體做法是：第1步，在第1級單峰區(qū)間[0, 1]中，取第1個(次)試驗點x1(＞0.5)和與它對稱的第2個試驗點x2=1－x1(＜0.5)，然后比較φ(x1)和φ(x2)的值。這時有以下3種可能：①若φ(x1)＞φ(x2)，必有x*∈[x2,1]和x*∈/ [0,x2]，故可淘汰掉廢區(qū)間[0,x2]，留下縮小了的第2級單峰區(qū)間[t1,t2]=[x2, 1]和留下第2次試驗點=x1(圖1(a))；②若φ(x1)＜φ(x2)，必有x*∈[0,x1]，同理淘汰掉廢區(qū)間[x1, 1]，留下第2級單峰區(qū)間[t1,t2]= [0,x1]和第2次試驗點=x2(圖1(b))；③若φ(x1)=φ(x2)，因有x*∈[x1,x2]，則可隨意淘汰掉[0,x2]或者[x1, 1]，留下第2級單峰區(qū)間[t1,t2]=[x2, 1]或[0,x1]和第2次試驗點=x1或x2(圖1(c))。如此，不論發(fā)生哪一種情況，都可以將第1級單峰區(qū)間[0, 1]縮小成第2級單峰區(qū)間[t1,t2]。這時，完成了第1步對稱試驗。第2步，在第2級單峰區(qū)間[t1,t2]中，再選取第2次試驗點的對稱試驗點x3，經同樣的函數值比較之后，又可淘汰掉廢區(qū)間，得到又縮小了的第3級單峰區(qū)間[t2,t3]和留下第3次試驗點(圖2)，等等。按照以上做法，在單峰區(qū)間[0, 1]上連續(xù)取n(≥2)個試驗點和做n-1步對稱試驗的方法，稱為[0, 1]上的n次對稱試驗方法，簡記“x1法”。

圖1 淘汰廢區(qū)間方法

圖2 n次對稱試驗方法

上述采取對稱試驗方法來縮小單峰區(qū)間，以逐步尋求問題的近似最優(yōu)點，其原因是由于事先人們并不知道所考慮問題中單峰函數的性態(tài)。事實上，不論所考慮單峰函數的性態(tài)如何，只要用對稱試驗方法，不管淘汰掉哪一個廢區(qū)間，所留下單峰區(qū)間的長度都是相等的。如若采用兩個試驗點在單峰區(qū)間中是不對稱的試驗方法，經函數值比較之后，可能會留下較長的單峰區(qū)間(圖3)。因此，使用對稱試驗方法總要比用不對稱的試驗方法好。

圖3 不對稱試驗方法

2 斐波那契數列和黃金分割數

本節(jié)介紹優(yōu)選法中兩個重要概念：斐波那契數列和黃金分割數。

1202年，意大利數學家列奧納多(Leonardo)在署名為斐波那契(Fibonacci L.)的一本《算盤冊(Liber Abaci)》的書中[2]，曾提出下面的兔子繁殖問題：兔子出生后兩個月可生小兔，設1對兔子每月恰生一雄一雌兩只小兔，現若飼養(yǎng)了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))，以及蜜蜂家系問題的傳代數和祖先數之間，等等，也都遵循上述規(guī)律。

將表1中的月份數記作n(=0, 1, 2,…)，相應的兔子對數記作Fn，則有：{Fn}={1，1，2，3，5，8，13，21，34，55，89，144，233，377，…}。從兔子繁殖的規(guī)律，不難得知在數列{Fn}中，首兩項為F0=1和F1=1，3個相連項之間有如下遞推關系：

人們將具有上述性質的數列{Fn}，稱為斐波那契數列，其中的Fn稱為斐波那契數[2]。

另外，設ω是正實數，若它具有關系：

則稱ω是[0, 1]中的黃金分割數，它在單位區(qū)間中的對應點叫黃金分割點，它把單位長度分割為兩部分叫黃金分割或黃金分割比。根據式(2)可知，黃金分割的幾何意義是：黃金分割點ω在單位區(qū)間[0, 1]中的位置，相當于它在[0,1]中的對稱點1-ω在區(qū)間[0, ω]中的位置。

在現實世界中，黃金分割現象普遍存在。特別是在建筑藝術中，人們認為使用黃金分割比的設計是最美的，因此在許多著名建筑中窗戶的寬與高之比常取黃金分割比(圖5(a))。又如，“標準”人體的肚臍高與身高之比，以及手肘到指尖與臂長之比，也都是黃金分割數(圖5(b))，等等。

從(2)可知，黃金分割數ω滿足二次方程ω2+ω-1=0。求解此方程，得其正根即黃金分割數：

由(1)和(3)，可以證明斐波那契數和黃金分割數之間有如下關系[1,3]：

圖5 意大利建筑大師阿爾伯蒂(A lberti L. B., 1404－1472)用黃金分割比建造的代表作——魯奇蘭府邸(左圖)；人體中的黃金分割比(右圖)

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

現在，分別利用斐波那契數列和黃金分割數來構造優(yōu)選法中尋求[0, 1]上單峰問題近似最優(yōu)點的兩個典型方法。

先給出由斐波那契數列來構造的方法。

n次斐波那契法設φ(x)是[0, 1]上的單峰函數。

(ii)逐步按對稱試驗方法進行。

(iii)直至給出第n次試驗點后，取最后留下的點作為問題的近似最優(yōu)點。

下面介紹利用黃金分割數來構造求單峰問題近似最優(yōu)點的方法。

黃金分割法設φ(x)是[0, 1] 上的單峰函數。

(i)在第1級單峰區(qū)間[0, 1]中，取第1個試驗點為x1=ω和與它對稱的第2個試驗點x2=1-ω。比較φ(x1)和φ(x2)的值之后淘汰掉廢區(qū)間，留下第2級單峰區(qū)間和留下第2次試驗點=ω或1-ω。

(ii)逐步按對稱試驗方法進行。

(iii)直至最后得到足夠小的留下的單峰區(qū)間，取其中點(或其中任意一點)，作為問題的近似最優(yōu)點。

這種利用黃金分割數ω來確定第1個試驗點，連續(xù)做n次試驗(n-1步對稱試驗)的方法，叫做n次黃金分割法，簡記“ω法”。

黃金分割法的最優(yōu)性[5]：對于[0, 1]上的單峰問題，記Δn[ω法]是“ω法”做n次試驗后最后留下區(qū)間的長度，則對于任意一個淘汰廢區(qū)間方法U≠“ω法”，總存在一個正整數N(≥2)，當n≥N后必有Δn[ω法]＜Δn[U]，其中Δn[U]是U做n次試驗后最后留下區(qū)間的長度。

黃金分割法的這一性質說明，對于[0, 1]上任意一個單峰問題，用[0, 1]上的其他任何一個淘汰廢區(qū)間方法來尋求它的最優(yōu)點時，總存在一個試驗次數，在這個次數之后，黃金分割法最后留下的n次區(qū)間精度與該淘汰廢區(qū)間方法的n次區(qū)間精度相比是“最小的”。通常人們把黃金分割法的這一性質叫做黃金分割法具有無窮遠處最優(yōu)性。由黃金分割法的第1個試驗點ω和尋優(yōu)步驟，利用(2)可以推得Δn[ω法]=ωn-1。另外，從黃金分割法的試驗步驟還可得知，使用它來尋求單峰問題的近似最優(yōu)點時，并不受試驗次數的限制。但是，黃金分割法的不足是，黃金分割數ω是一個無理數，因此這一方法只具有理論上的意義。在應用中，實際上是無法使用它來尋求單峰問題的最優(yōu)點的。

4 近似黃金分割法及其對稱試驗最優(yōu)性

從上一節(jié)的介紹，我們知道，用n次斐波那契法來尋求單峰問題的最優(yōu)點，要受到試驗次數的限制；而黃金分割法中的黃金分割數是一無理數，在應用中又無法用它來進行數值計算。為了克服這兩個方法的不足，我們來考慮在對稱試驗方法中，取第1個試驗點為有理近似黃金分割數的方法，同時，考察此類方法是否具有某種最優(yōu)性？若有，則它具有怎樣的最優(yōu)性？

近似黃金分割法設φ(x)是[0, 1] 上的單峰函數。

(ii)逐步按對稱試驗方法進行。

(iii)直至得到足夠小的留下的單峰區(qū)間，取其中點(或其中任意一點)作為問題的近似最優(yōu)點。

近似黃金分割法的最優(yōu)性[6]對于[0, 1]上的單峰問題，記有理數≈ω是近似黃金分割法的第1個試驗點。若n是使

成立的m的最大值，則其n次區(qū)間精度Δn[法] ＜Δn[x法](其中當n是偶數時，x∈(0.5,1)/當n是奇數時，x∈(0.5,1)/

上述近似黃金分割法的最優(yōu)性的意義是，對于[0, 1]上任意一個單峰問題，當n是滿足(5)的m的最大值時，由“法”做n次試驗后，其最后留下的n次區(qū)間精度Δn[法]與其他任何“x法”(n是偶數時，x∈(0.5,1)/(]；n是奇數時，x∈(0.5,1)/[)的n次區(qū)間精度相比是“最小的”。近似黃金分割法的這一性質，稱為“法”具有n次對稱試驗最優(yōu)性，其中的n是“法”的最大對稱試驗最優(yōu)性次數。從近似黃金分割法的第1個試驗點，由(1)用數學歸納法可以推得它的n次區(qū)間精度

表2 前5個近似黃金分割法以及n次斐波那契法和黃金分割法對應的最大對稱試驗最優(yōu)性次數及其區(qū)間精度

(2013年10月22日收稿)

[1] 華羅庚. 優(yōu)選學[M]. 北京: 科學出版社, 1981.

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

[3] 胡毓達. 非線性規(guī)劃[M]. 北京: 高等教育出版社, 1990.

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

[5] 洪加威. 論黃金分割法的最優(yōu)性[J]. 數學的實踐與認識, 1973, 2: 34-41.

[6] 胡毓達. 論異側對稱策略的最優(yōu)性[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