盲人探路負(fù)梯度方向法

李春明

(中國(guó)石油大學(xué)(華東)勝利學(xué)院,山東東營(yíng) 257061)

盲人探路負(fù)梯度方向法

李春明

(中國(guó)石油大學(xué)(華東)勝利學(xué)院,山東東營(yíng) 257061)

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

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

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

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

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

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

在單峰假設(shè)(目標(biāo)函數(shù)在尋優(yōu)方向上有且只有一個(gè)極值點(diǎn))下,從當(dāng)前點(diǎn)開(kāi)始,每一步所得探測(cè)點(diǎn)如果優(yōu)于當(dāng)前點(diǎn),則將其置為當(dāng)前點(diǎn)。從初始當(dāng)前點(diǎn)出發(fā),以初始步長(zhǎng)向前探測(cè),如果探點(diǎn)不如當(dāng)前點(diǎn)好,則轉(zhuǎn)身探測(cè),如果探點(diǎn)仍不好,則說(shuō)明極值點(diǎn)在單步范圍之內(nèi),否則,每探一步加倍步長(zhǎng),直到探測(cè)點(diǎn)不如當(dāng)前點(diǎn)好為止。此時(shí),極值點(diǎn)在單位步長(zhǎng)范圍之內(nèi)。減半步長(zhǎng)探測(cè),如探測(cè)點(diǎn)不好,可轉(zhuǎn)身探測(cè),如果探測(cè)點(diǎn)還不好,則減半步長(zhǎng)探測(cè)與轉(zhuǎn)身探測(cè)交替進(jìn)行,直到探測(cè)點(diǎn)優(yōu)于當(dāng)前點(diǎn)為止,然后減半步長(zhǎng)探測(cè)。重復(fù)以上過(guò)程,直到步長(zhǎng)足夠小時(shí)結(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 基于盲人探路的折線負(fù)梯度方向法

2.1 尋優(yōu)思想

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

(1)考慮到在新的尋優(yōu)方向上探測(cè)點(diǎn)遠(yuǎn)未及極值點(diǎn)的情況,當(dāng)極值點(diǎn)可能在單步步長(zhǎng)之內(nèi)時(shí),暫采用上一個(gè)尋優(yōu)方向上的尋優(yōu)步長(zhǎng),如果探測(cè)點(diǎn)好則設(shè)置為當(dāng)前點(diǎn)。因?yàn)樾聦?yōu)方向上的極值點(diǎn)與前一尋優(yōu)方向上的極值點(diǎn)不會(huì)在以當(dāng)前點(diǎn)為圓心的同一個(gè)圓上,如果直接減半步長(zhǎng)則容易失去捕捉極值點(diǎn)的機(jī)會(huì)。

(2)在暫不減半步長(zhǎng)階段,更新當(dāng)前點(diǎn)之前,退半步探測(cè),以避免探測(cè)點(diǎn)遠(yuǎn)跨過(guò)極值點(diǎn)而降低尋優(yōu)效率。

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

尋優(yōu)算法可分四個(gè)階段:初始步長(zhǎng)檢驗(yàn)階段;步長(zhǎng)加倍探測(cè)階段;暫不減半步長(zhǎng)階段;步長(zhǎng)減半探測(cè)階段。由于尋優(yōu)方向?yàn)楫?dāng)前點(diǎn)的負(fù)梯度方向,只須步長(zhǎng)的減半和加倍,而不須尋優(yōu)方向的反向,所以,折線盲人探路法比一維盲人探路法的算法更加簡(jiǎn)潔。

2.2 算法流程圖

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

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

2.3 算法步驟

(1)選定初始點(diǎn)x(1)為當(dāng)前點(diǎn),初始步長(zhǎng)h＝h0,收斂精度值ε(＜h/10),計(jì)算當(dāng)前點(diǎn)的目標(biāo)函數(shù)值y1＝f(x(1)),令尋優(yōu)方向?yàn)楫?dāng)前點(diǎn)的負(fù)梯度方向s(1)。

(2)取探測(cè)點(diǎn)為x(2)＝x(1)＋hs(1),計(jì)算探測(cè)點(diǎn)的目標(biāo)函數(shù)值y2＝f(x(2))。

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

(4)令h＝h＋h,y1＝y(tǒng)2,x(1)＝x(2),令尋優(yōu)方向?yàn)楫?dāng)前點(diǎn)的負(fù)梯度方向s(1),取探測(cè)點(diǎn)x(2)＝x(1)＋hs(1),計(jì)算其目標(biāo)函數(shù)值y2＝f(x(2))。

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

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

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

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

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

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

2.4 計(jì)算子程序部分代碼

3 算例分析

對(duì)于無(wú)約束優(yōu)化問(wèn)題

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

[4] 劉麗華,馬昌鳳,唐嘉.求解廣義鞍點(diǎn)問(wèn)題的一個(gè)新的類SOR算法[J].計(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ī)方向法改進(jìn)及其驗(yàn)證[J].計(jì)算機(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-),男,山東夏津人,博士后,副教授,研究方向?yàn)閯?chuàng)新方法、優(yōu)化方法、機(jī)械工程等.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.[李春明.盲人探路負(fù)梯度方向法[J].甘肅科學(xué)學(xué)報(bào),2016,28(5):116-122.]

10.16468/j.cnkii.ssn1004-0366.2016.05.026.