胡毓達(dá)

教授，上海交通大學(xué)數(shù)學(xué)系，上海 200240

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

胡毓達(dá)

教授，上海交通大學(xué)數(shù)學(xué)系，上海 200240

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

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

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

1 單峰問題與對稱試驗(yàn)方法

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

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

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

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

圖2 n次對稱試驗(yàn)方法

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

圖3 不對稱試驗(yàn)方法

2 斐波那契數(shù)列和黃金分割數(shù)

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

1202年，意大利數(shù)學(xué)家列奧納多(Leonardo)在署名為斐波那契(Fibonacci L.)的一本《算盤冊(Liber Abaci)》的書中[2]，曾提出下面的兔子繁殖問題：兔子出生后兩個(gè)月可生小兔，設(shè)1對兔子每月恰生一雄一雌兩只小兔，現(xiàn)若飼養(yǎng)了1對初生的小兔，問一年后共有多少對兔子？

對于此問題，我們可以按圖4(a)(黑色的為成熟兔子，白色的為未成熟兔子)推算如下：

第0個(gè)月后(第1個(gè)月中)，有1對未成熟小兔；

第1個(gè)月后，小兔成熟，仍只有1對兔子；

第2個(gè)月后，這對老兔子生了1對小兔，共有2對兔子；

第3個(gè)月后，老兔子又生了1對小兔，而上月出生的小兔成熟，這時(shí)共有3對兔子；

第4個(gè)月后，老兔子和第2個(gè)月后出生的兔子(已成熟)各生1對，連同它們本身計(jì)有4對，加上上月出生的小兔成熟，這時(shí)共有5對兔子；

圖4 斐波那契數(shù)列的實(shí)例

…………

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

表1 兔子繁殖問題

此外，如樹木分枝問題的年份和分枝數(shù)(圖4(b))，以及蜜蜂家系問題的傳代數(shù)和祖先數(shù)之間，等等，也都遵循上述規(guī)律。

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

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

另外，設(shè)ω是正實(shí)數(shù)，若它具有關(guān)系：

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

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

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

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

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

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

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

先給出由斐波那契數(shù)列來構(gòu)造的方法。

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

(ii)逐步按對稱試驗(yàn)方法進(jìn)行。

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

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

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

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

(ii)逐步按對稱試驗(yàn)方法進(jìn)行。

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

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

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

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

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

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

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

(ii)逐步按對稱試驗(yàn)方法進(jìn)行。

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

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

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

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

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

(2013年10月22日收稿)

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

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

[3] 胡毓達(dá). 非線性規(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]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 1973, 2: 34-41.

[6] 胡毓達(dá). 論異側(cè)對稱策略的最優(yōu)性[J]. 上海交通大學(xué)學(xué)報(bào), 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