李春明

(中國石油大學(xué)(華東)勝利學(xué)院,山東東營 257061)

盲人探路負梯度方向法

李春明

(中國石油大學(xué)(華東)勝利學(xué)院,山東東營 257061)

負梯度方向法作為一個常用的優(yōu)化方法在機械工程領(lǐng)域發(fā)揮著重要作用,但是,因其鋸齒現(xiàn)象而具有計算量大、計算效率低的缺點。一維盲人探路尋優(yōu)思想總結(jié)為:根據(jù)探測點與極值點相對位置的三種情況采取三種處理方案。基于此,將負梯度方向法進行了改進,提出了新的尋優(yōu)方法——折線負梯度方向法。算法分為四部分:初始步長檢驗階段;步長加倍探測階段;暫不減半步長階段;步長減半探測階段。第三部分考慮了探測點遠未及極值點的情況。提供了尋優(yōu)思想流程圖和完整的C語言子程序。通過與負梯度方向法的比較,證明了折線負梯度方向法具有計算量小、尋優(yōu)效率大的特點?？紤]遠跨過極值點的情況,提出了走一步退半步探的算法。通過對不進行退半步探運算和退半步探時不減半步長兩種情況的比較,證明了折線負梯度方向法的適用范圍較廣。

優(yōu)化方法;負梯度方向法;盲人探路尋優(yōu)思想;計算量

目前,優(yōu)化方法在機械、冶金、石油、化工、電機、建筑、鐵路、交通、航空、航天、航宇、國防、造船、紡織、輕工、機床、汽車、自動控制系統(tǒng)、電力系統(tǒng)、電子、電器、管理等工程設(shè)計領(lǐng)域均發(fā)揮著重要的作用,在數(shù)值仿真等領(lǐng)域也體現(xiàn)出優(yōu)化理念,如三維數(shù)字化工藝模型、數(shù)字成像技術(shù)[1]、系統(tǒng)可靠性分析[2]等。即使是最簡單的一維優(yōu)化方法(單目標優(yōu)化),也在機械行業(yè)得到了廣泛的應(yīng)用,如淬火工藝參數(shù)的確定和以可靠性為中心的預(yù)防性維修計劃[3]?；谄渌碚摰膬?yōu)化方法也有較深入的研究,如遺傳算法、廣義鞍點問題[4]。

自外點懲罰函數(shù)法(土堆法)的有效性獲得認可以來,優(yōu)化方法已經(jīng)發(fā)展成一個理論性強、系統(tǒng)性強的學(xué)科,其理論體系主要包括一維優(yōu)化方法、多維無約束優(yōu)化方法、多維有約束優(yōu)化方法、線性優(yōu)化方法、多目標優(yōu)化方法、離散變量優(yōu)化方法、基于生理學(xué)理論的優(yōu)化方法、基于物理學(xué)理論的優(yōu)化方法等。其中一維盲人探路優(yōu)化方法[5]對一維優(yōu)化方法的補充和多維優(yōu)化方法的改進起到了重要作用[6]。

負梯度方向法利用當前點的局部信息獲得目標函數(shù)下降量最大的方向作為尋優(yōu)方向,當尋優(yōu)點接近于極值點時,由于相鄰尋優(yōu)方向相互垂直,在每個尋優(yōu)方向上所求得極值點與初始點的距離逐漸減小,并且每個尋優(yōu)方向仍須采用一維優(yōu)化方法獲得最優(yōu)點,須至少探測初始步長與收斂精度值之商的若干倍,也就是說,尋優(yōu)效率逐漸變小,這稱為鋸齒現(xiàn)象。目前國內(nèi)外的研究不僅應(yīng)用范圍較廣[7-9],而且多主要集中在共軛梯度上[10,11]。負梯度方向法的深入研究也較多。研究將一維盲人探路優(yōu)化方法的尋優(yōu)思想推廣應(yīng)用于多維優(yōu)化問題,根據(jù)負梯度方向法的尋優(yōu)方向確定方法,提出了折線負梯度方向法。

1 一維盲人探路優(yōu)化算法

在單峰假設(shè)(目標函數(shù)在尋優(yōu)方向上有且只有一個極值點)下,從當前點開始,每一步所得探測點如果優(yōu)于當前點,則將其置為當前點。從初始當前點出發(fā),以初始步長向前探測,如果探點不如當前點好,則轉(zhuǎn)身探測,如果探點仍不好,則說明極值點在單步范圍之內(nèi),否則,每探一步加倍步長,直到探測點不如當前點好為止。此時,極值點在單位步長范圍之內(nèi)。減半步長探測,如探測點不好,可轉(zhuǎn)身探測,如果探測點還不好,則減半步長探測與轉(zhuǎn)身探測交替進行,直到探測點優(yōu)于當前點為止,然后減半步長探測。重復(fù)以上過程,直到步長足夠小時結(jié)束尋優(yōu)。圖1為該算法的流程圖。圖2為該算法尋優(yōu)思想的流程圖。

圖1 一維盲人探路法的程序流程Fig.1 One-dimensional pathfinding program flow chart

圖2 盲人探路法尋優(yōu)思想流程Fig.2 Optimizing thoughts flow chart for blind person exploring way

2 基于盲人探路的折線負梯度方向法

2.1 尋優(yōu)思想

每一步探測均沿當前點的負梯度方向進行。在每一個尋優(yōu)方向上,均探測一個比當前點好的點,利用效率較大,符合漸進尋優(yōu)特點。在一維盲人探路法的基礎(chǔ)上增加以下三點:

(1)考慮到在新的尋優(yōu)方向上探測點遠未及極值點的情況,當極值點可能在單步步長之內(nèi)時,暫采用上一個尋優(yōu)方向上的尋優(yōu)步長,如果探測點好則設(shè)置為當前點。因為新尋優(yōu)方向上的極值點與前一尋優(yōu)方向上的極值點不會在以當前點為圓心的同一個圓上,如果直接減半步長則容易失去捕捉極值點的機會。

(2)在暫不減半步長階段,更新當前點之前,退半步探測,以避免探測點遠跨過極值點而降低尋優(yōu)效率。

(3)更新當前點之后,確定目標函數(shù)在該點處的負梯度方向,并將其單位化。尋優(yōu)方向單位化在優(yōu)化方法當中非常重要,可以保證在設(shè)計空間中探測點與當前點之間的距離為當前點步長。尋優(yōu)方向通常用方向向量表示,表現(xiàn)為列陣的形式。如果不進行方向單位化,則會出現(xiàn)初始步長過大或過小的情況,從而導(dǎo)致算法失效。

尋優(yōu)算法可分四個階段:初始步長檢驗階段;步長加倍探測階段;暫不減半步長階段;步長減半探測階段。由于尋優(yōu)方向為當前點的負梯度方向,只須步長的減半和加倍,而不須尋優(yōu)方向的反向,所以,折線盲人探路法比一維盲人探路法的算法更加簡潔。

2.2 算法流程圖

根據(jù)盲人探路尋優(yōu)思想及上述改進算法,改進的負梯度方向法流程如圖3所示。

圖3 折線負梯度方向法的尋優(yōu)思想流程圖Fig.3 Optimizing thoughts flow chart of broken line negative gradient direction method

2.3 算法步驟

(1)選定初始點x(1)為當前點,初始步長h＝h0,收斂精度值ε(＜h/10),計算當前點的目標函數(shù)值y1＝f(x(1)),令尋優(yōu)方向為當前點的負梯度方向s(1)。

(2)取探測點為x(2)＝x(1)＋hs(1),計算探測點的目標函數(shù)值y2＝f(x(2))。

(3)如y1＜y2,則令h＝0.5h,如果h足夠小,則取當前點為最優(yōu)點,結(jié)束尋優(yōu),否則轉(zhuǎn)步驟(2)。

(4)令h＝h＋h,y1＝y(tǒng)2,x(1)＝x(2),令尋優(yōu)方向為當前點的負梯度方向s(1),取探測點x(2)＝x(1)＋hs(1),計算其目標函數(shù)值y2＝f(x(2))。

(5)如y1≥y2,則轉(zhuǎn)步驟(4);否則,令h＝0.5h。

(6)產(chǎn)生新的探測點x(2)＝x(1)＋h,計算其目標函數(shù)值y2＝f(x(2))。如果滿足收斂條件則結(jié)束尋優(yōu)。

(7)如y1≥y2,則令y1＝y(tǒng)2,x(1)＝x(2),退半步探,根據(jù)探測點決定是否再次更新當前點,尋優(yōu)方向為當前點的負梯度方向s(1),轉(zhuǎn)步驟(6);否則,令h＝0.5h。

(8)產(chǎn)生新的探測點x(2)＝x(1)＋h,計算其目標函數(shù)值y2＝f(x(2))。如果h足夠小,并且x(2)與x(1)兩點的目標函數(shù)值之差滿足收斂準則,則取當前點與探測點的較好點為最優(yōu)點,結(jié)束尋優(yōu)。

(9)如y1≥y2,則令y1＝y(tǒng)2,x(1)＝x(2),h＝0.5h,令尋優(yōu)方向為當前點的負梯度方向s(1),轉(zhuǎn)步驟(6);否則,令h＝0.5h,轉(zhuǎn)步驟(8)。

上述算法步驟中,(1)、(2)、(3)為初始步長檢驗階段,(4)、(5)為步長加倍探測階段,(6)、(7)為暫不減半步長階段,(8)、(9)為步長減半探測階段。

2.4 計算子程序部分代碼

3 算例分析

對于無約束優(yōu)化問題

取收斂精度值ε為1.0×10－5,采用負梯度方向法尋優(yōu),以[－10 8]T為初始點,采用目標函數(shù)值落差收斂準則和目標函數(shù)梯度準則均獲得最優(yōu)點為[2.499 9 2.500 1]T,最優(yōu)解為7.207 9×10－8,最優(yōu)點梯度為[0.000 5 －0.000 6]T的尋優(yōu)結(jié)果,目標函數(shù)調(diào)用517次[12]。

取同樣的初始點和收斂精度值,采用目標函數(shù)值落差和尋優(yōu)步長均小于收斂精度值的收斂準則,采用基于盲人探路尋優(yōu)思想的折線負梯度方向法,不進行走一步退半步測的步驟,尋優(yōu)結(jié)果為:最優(yōu)點[2.500 0 2.500 0]T;最優(yōu)解3.326 0×10－10;最優(yōu)點處的梯度[－2.379 9×10－54.872 3×10－5]T;目標函數(shù)調(diào)用次數(shù)為68。與負梯度方向法相比,經(jīng)過47次尋優(yōu)方向確定和57次目標函數(shù)調(diào)用即超過其尋優(yōu)精度,可見,其計算量大大地減小,計算精度大大地提高。

圖4和圖5為尋優(yōu)過程,其中曲線及數(shù)字表示目標函數(shù)等值線及其目標函數(shù)值,折線表示尋優(yōu)過程,寶石形的點表示依次更新的當前點?？梢?合理地增倍和減半尋優(yōu)步長,有效地逼近了極值點。由于橫坐標與縱坐標的刻度不一致,尋優(yōu)步長并不代表實際長度。

圖4 不進行退半步探的尋優(yōu)過程Fig.4 Optimizing process of non back half step

圖5 接近于極值點的尋優(yōu)過程Fig.5 Optimizing process on the verge of extreme point

從尋優(yōu)過程可見,第三部分對于探測點在尋優(yōu)方向上遠未及極值點的情況可起到加大尋優(yōu)效率的作用,但是對于探測點在尋優(yōu)方向上越過極值點的情況考慮不足。如果在步長減半之前反向探半步,即走一步退半步探,則可以彌補上述不足。但是對于本例,其他條件不變,則增加了計算量;經(jīng)過58次尋優(yōu)方向確定、64次當前點更新和101次目標函數(shù)調(diào)用超過了負梯度方向法的尋優(yōu)精度;最終經(jīng)過69次尋優(yōu)方向確定、76次當前點更新和119次目標函數(shù)調(diào)用獲得尋優(yōu)結(jié)果為:最優(yōu)點[2.500 0 2.500 0]T、最優(yōu)解6.759 9×10－10、最優(yōu)點處的梯度[－3.209 5× 10－57.116 8×10－5]T。尋優(yōu)過程如圖6所示?？梢妼?yōu)方向過早地減半會影響尋優(yōu)效果。

圖6 增加“走一步退半步探”的尋優(yōu)過程Fig.6 Optimizing process of adding“up one step and back half step”

如果在退半步探之后步長不減半,則尋優(yōu)過程如圖7所示。

圖7 退半步探時不減半步長的尋優(yōu)過程Fig.7 Optimizing process without reduced half step length when backing half step

4 結(jié)論

通過對不進行退半步探運算和退半步探時不減半步長兩種情況的比較,驗證了以上所提出方法的有效性。對于具體問題,三種情況的計算量不同,在解決實際優(yōu)化問題時,可根據(jù)要求適當?shù)剡x用計算步驟,但是,尋優(yōu)結(jié)果將是相同的。雖然基于盲人探路思想的折線負梯度方向法比負梯度方向法的計算量小,但是仍然是越接近于極值點尋優(yōu)效果越差,這是由負梯度方向表示目標函數(shù)局部特性的事實所決定的。

[1] 趙娟娟.數(shù)字圖像邊緣檢測方法的對比分析及優(yōu)化[J].甘肅科學(xué)學(xué)報,2012,24(3):143-146.

[2] 李冬娜,張民悅,張霞.系統(tǒng)可靠性模糊方法優(yōu)化問題[J].甘肅科學(xué)學(xué)報,2013,25(2):28-30.

[3] 王靈芝,徐宇工,張家棟.基于設(shè)備有效度和可靠度的預(yù)防修經(jīng)濟優(yōu)化模型[J].機械工程學(xué)報,2010,46(4):163-168.

[4] 劉麗華,馬昌鳳,唐嘉.求解廣義鞍點問題的一個新的類SOR算法[J].計算數(shù)學(xué),2016,38(1):83-95.

[5] Li Chunming.Blind-walking Optimization Method[J].Journal of Networks,2010,5(12):1 458-1 466.

[6] 李春明.隨機方向法改進及其驗證[J].計算機仿真,2009,26 (1):189-192.

[7] Krejic,Nata?a.A Gradient Method for Unconstrained Optimization in Noisy Environment[J].Applied Numerical Mathematics,2013,70(1):1-21.

[8] Narushima,Yasushi.Global Convergence of a Memory Gradient Method for Unconstrained Optimization[J].Computational Optimization and Applications,2006,35(3):325-346.

[9] Zheng Yue.A New Variant of the Memory Gradient Method for Unconstrained Optimization[J].Optimization Letters, 2012,6(8):1 643-1 655.

[10] Ezzati,Ghasem.A New Reliability Analysis Method Based on the Conjugate Gradient Direction[J].Structural and Multidisciplinary Optimization,2015,51(1):89-98.

[11] Narushima,Yasushi.Conjugate Gradient Methods Based on Secant Conditions that Generate Descent Search Directions for Unconstrained Optimization[J].Journal of Computational and Applied Mathematics,2012,236(17):4 303-4 317.

[12] 李春明.優(yōu)化方法[M].南京:東南大學(xué)出版社,2009.

Negative Gradient Direction Method for Blind Person Exploring the Way

Li Chunming
(Shengli College,China University of Petroleum,Dongying257061,China)

Negative gradient direction method,a common used optimizing method,plays important effect in mechanical engineering field,but,it has the disadvantages of huge calculating amount and low calculating efficiency due to sawtooth phenomenon.One-dimensional blind person pathfingding and optimizing thoughts can be summed as:take three measurements according to 3 situations in relative position of probe point and extreme point.Based on this,improve the negative gradient direction method and give new optimizing method-broken line negative gradient direction method.The algorithm is classified into four parts: initial step length inspecting period;inspecting period for double step lengths;the period for temporarily not reducing step length;probing period for half step length.In third part,probe point far end and extreme point are considered.This text offers optimizing thought flow chart and complete C language subprogram.Compared with negative gradient direction method,broken line negative gradient direction method has the advantage of little calculating amount and high optimizing efficiency.Thinking about the situation of striding extreme point,this text gives the algorithm of up one step and back half step.By comparing algorithms of non back half step and non reduced length with back half step,it proves that broken line negative gradient direction method is widely used.

Optimizing method;Negative gradient direction method;Optimizing thoughts for blind person exploring way;Calculating amount

O224;TP202

:A

:1004-0366(2016)05-0116-07

2016-03-31;

:2016-05-04.

李春明(1971-),男,山東夏津人,博士后,副教授,研究方向為創(chuàng)新方法、優(yōu)化方法、機械工程等.E-mail:lchming＠126.com.

Li Chunming.Negative Gradient Direction Method for Blind Person Exploring the Way[J].Journal of Gansu Sciences,2016,28(5):116-122.[李春明.盲人探路負梯度方向法[J].甘肅科學(xué)學(xué)報,2016,28(5):116-122.]

10.16468/j.cnkii.ssn1004-0366.2016.05.026.