求解非光滑優(yōu)化問題的改進(jìn)大洪水算法

張清葉,　高　巖,　馬　良

(上海理工大學(xué) 管理學(xué)院,上?！?00093)

?

求解非光滑優(yōu)化問題的改進(jìn)大洪水算法

張清葉,高巖,馬良

(上海理工大學(xué) 管理學(xué)院,上海200093)

摘要：應(yīng)用啟發(fā)式算法求解非光滑優(yōu)化問題,解決基于次梯度信息的確定性算法在求解時困難較大的問題.首先分析了基本大洪水算法的優(yōu)化機(jī)理及特征并給出其求解步驟,然后針對無約束及盒子約束問題分別設(shè)計了改進(jìn)的大洪水算法,將基本大洪水算法所依賴的參數(shù)up省去.對于無約束情形,提出了進(jìn)行鄰域搜索的隨機(jī)行走法;對于盒子約束情形,提出了選擇初始可行點的方法和進(jìn)行鄰域搜索的混沌優(yōu)化算法.最后通過算例進(jìn)行測試并與其他算法進(jìn)行對比,測試結(jié)果表明了改進(jìn)的大洪水算法在求解非光滑優(yōu)化問題時的有效性與優(yōu)越性,故其可作為求解非光滑優(yōu)化問題的一種實用方法.

關(guān)鍵詞：大洪水算法; 非光滑優(yōu)化; 隨機(jī)行走; 混沌

非光滑優(yōu)化廣泛應(yīng)用于經(jīng)濟(jì)、力學(xué)、工程和最優(yōu)控制等眾多領(lǐng)域,然而由于不具有連續(xù)可微性質(zhì),基于梯度信息的經(jīng)典優(yōu)化方法不再適用.目前,次梯度法和束方法是求解非光滑優(yōu)化問題最常用的兩種方法[1-2],但由于凸函數(shù)的次梯度與局部Lipschitz函數(shù)的廣義梯度計算困難較大,從而嚴(yán)重影響了非光滑優(yōu)化算法的應(yīng)用.鑒于非光滑優(yōu)化問題的普遍性及計算的困難性,本文擬引進(jìn)啟發(fā)式算法對其進(jìn)行處理.

大洪水算法(great deluge algorithm,GDA)是一種受自然界啟發(fā)的優(yōu)化算法,它通過模擬洪水的上漲過程來進(jìn)行全局尋優(yōu),該算法最早由Dueck于1993年提出[3].Dueck在利用threshold accepting(TA)算法進(jìn)行實驗時,發(fā)現(xiàn)了兩個行之有效的啟發(fā)式算法,其中之一便是大洪水算法.它與模擬退火算法[4](simulated annealing,SA)有著相似的結(jié)構(gòu),但在迭代過程中對劣解的接受規(guī)則不同,且比模擬退火算法依賴于更少的參數(shù).由于其遍歷過程與圣經(jīng)中諾亞方舟的大洪水有相似之處,故稱之為大洪水算法.其算法思想可描述為:設(shè)想有一塊崎嶇不平的空地,在這塊空地上一直不間斷地下雨從而產(chǎn)生洪水,空地上有一個人,他可以向任意方向移動,然而隨著水平面不斷上漲,為了生存,此人必須不斷地移至更高處,一段時間之后,此人最終將到達(dá)空地的最高點,即最大化問題的最優(yōu)解.對于最小化問題,有兩種處理方法:其一是將目標(biāo)函數(shù)取負(fù)值,從而將最小化問題轉(zhuǎn)化成最大化問題;其二是修改大洪水算法,不妨稱為干旱算法,尋找高處的人為尋找水的魚類代替.

Dueck首先將大洪水算法用于旅行商問題(traveling salesman problem,TSP)的求解,隨后國內(nèi)外一些學(xué)者對大洪水算法進(jìn)行了研究[5-10],如將其應(yīng)用于二次分配、電力調(diào)度、復(fù)雜系統(tǒng)可靠性等問題的求解中.然而,截至目前尚未有學(xué)者將其用于求解非光滑優(yōu)化問題.

本文接下來給出基本大洪水算法的求解步驟,然后針對無約束及盒子約束非光滑優(yōu)化問題分別設(shè)計改進(jìn)的大洪水算法,同時給出相應(yīng)的偽代碼,最后通過算例對所給算法進(jìn)行測試.

1基本大洪水算法的求解步驟

以最大化目標(biāo)函數(shù)f(x)為例,其中f(x)是n上的實值函數(shù),即求解f(x).

算法1基本大洪水算法(BGDA)

Step1初始化

給定初始可行解x0,計算f(x0);

設(shè)置初始水平面高度water_level,令water_level:=f(x0);

設(shè)置水平面上升速度up>0;

設(shè)置迭代次數(shù)上界count,置迭代因子i:=1;

fori=1:count,執(zhí)行Step2.

Step2優(yōu)化

在x0附近進(jìn)行鄰域搜索,得新解x,計算f(x).

執(zhí)行if判斷語句:

iff(x)>water_level,則

置x0:=x,water_level:=water_level+up.

Endif

迭代因子i增加1,即令i:=i+1.

Endfor

Step3輸出x0,f(x0).

2針對無約束優(yōu)化問題的算法

考慮問題

(1)

其中f(x)不一定連續(xù)可微.由于無約束,可在n中任選一點作為初始解x0,然后利用隨機(jī)行走法[11]進(jìn)行鄰域搜索.不妨設(shè)迭代進(jìn)行到第k步,當(dāng)前解為xk,設(shè)置迭代格式,令xk+1=xk+λkdk,其中λk為鄰域半徑,dk為規(guī)劃后的搜索方向.為使dk能遍歷所有方向,可隨機(jī)生成多個[-1,1]之間的n維向量,其中n為決策變量x的維數(shù).注意到在基本大洪水算法的求解步驟Step 2中,對water_level的更新準(zhǔn)則依賴于參數(shù)up,改進(jìn)算法將參數(shù)up省去,更新準(zhǔn)則采用water_level=f(x),這樣一方面可以減少參數(shù),另一方面通過大量測試發(fā)現(xiàn)運行效率可得到較大提高.下面給出求解問題(1)的具體步驟,按偽碼形式敘述如下.

算法2無約束優(yōu)化問題的改進(jìn)大洪水算法,(UCGDA)

Begin

給定x0,計算f(x0),設(shè)置初始水平面高度water_level,令water_level:=f(x0);

設(shè)置迭代次數(shù)上界count,設(shè)置鄰域搜索時生成搜索方向個數(shù)m,置迭代因子i:=1;

進(jìn)入for循環(huán),fori=1:count.

執(zhí)行if判斷語句:ifa

置x0:=x,water_level:=a.

Endif

迭代次數(shù)增加1,即令i:=i+1.

Endfor

輸出最優(yōu)解x0和最優(yōu)值water_level.

End

算例測試

為驗證算法的有效性,下面選幾個測試函數(shù)進(jìn)行求解,并將求解結(jié)果與用模擬退火算法、Matlab優(yōu)化工具箱命令fminsearch所得結(jié)果進(jìn)行對比.表1列出了當(dāng)前能找到的最優(yōu)解x**和對應(yīng)的最優(yōu)值f**=f(x**),表2列出了各種算法求得的最優(yōu)解x*與對應(yīng)的最優(yōu)值f*=f(x*).上述3種算法均在Win7系統(tǒng)Matlab2012a環(huán)境下實現(xiàn).參數(shù)設(shè)置如下:算法2(UCGDA)迭代上界count取1 000,鄰域半徑λ取0.1,鄰域搜索時搜索方向個數(shù)m取100;模擬退火算法與fminsearch的參數(shù)設(shè)置取工具包默認(rèn)值,初始點為相同初始點.

例1wolfe函數(shù)

初始點設(shè)為x0=(3,2)T.

例2Rosen-Suzuki函數(shù)

初始點設(shè)為x0=(0,0,0,0)T.

例3Spiral函數(shù)

f(x)=max{f1(x),f2(x)}

初始點x0=(1.411 831,-4.794 62)T.

表1　當(dāng)前最優(yōu)解

表2　求解結(jié)果

通過對表2的求解結(jié)果進(jìn)行分析可以發(fā)現(xiàn),UCGDA的求解精度均優(yōu)于SA.此外,由于fminsearch為局部搜索算法,其求解結(jié)果嚴(yán)重依賴于初始點的選取,當(dāng)初始點選取不太合適時,將產(chǎn)生較大誤差,如例2.而在實際問題中,由于最優(yōu)解是待求的,初始點的選取大都是盲目的,故為得到全局最優(yōu)解應(yīng)使用UCGDA.綜上,為得到質(zhì)量較好的全局最優(yōu)解,算法2不失為求解非光滑無約束優(yōu)化問題的一種實用方法.

為進(jìn)一步加快算法收斂速度,在對water_level進(jìn)行更新時,亦可令

water_level=min{water_level+up,f(x)},其中,up<0為水平面下降速度.

3針對盒子約束優(yōu)化問題的算法

考慮問題

(2)

式中,x,a,b均為n維向量,f(x)不一定光滑.

另一種方法則是不進(jìn)行轉(zhuǎn)化,直接對約束優(yōu)化問題進(jìn)行求解.本文擬設(shè)計專門針對約束優(yōu)化問題的改進(jìn)大洪水算法.

不妨在盒子G內(nèi)任取一點x0作為初始解,其函數(shù)值f(x0)作為初始水平面,設(shè)置up值及迭代次數(shù)上界count.在鄰域搜索時,所求解x不僅需在x0附近,還需在G內(nèi).為得到函數(shù)f(x)在盒子G內(nèi)的全局最優(yōu)解,希望鄰域搜索時能遍歷G內(nèi)的所有點且最好不重復(fù),而混沌恰好具有此性質(zhì),故在求解約束優(yōu)化問題時,可考慮采用Logistic映射產(chǎn)生混沌序列.

混沌是一種普遍的非線性現(xiàn)象,其行為復(fù)雜且類似隨機(jī),但有精致的內(nèi)在規(guī)律性.混沌優(yōu)化算法是一種全局優(yōu)化算法[9,12],其理論基礎(chǔ)是混沌的遍歷性.混沌優(yōu)化是通過混沌變量來實現(xiàn)的,混沌變量的產(chǎn)生有多種方法,如應(yīng)用廣泛的Logistic映射,其方程為ti+1=μti(1-ti),i=1,2,…,其中μ為控制參數(shù),0≤ti≤1,當(dāng)μ=4時處于完全混沌.

設(shè)函數(shù)優(yōu)化變量x(a≤x≤b)為n維向量,T={t1,t2,…}為Logical映射函數(shù)產(chǎn)生的混沌序列,其中ti(i=1,2,…)亦為n維向量且滿足

(3)

式中:.*表示兩個向量的對應(yīng)元素相乘,其結(jié)果為一n維向量;0表示元素全為0的n維向量;1表示元素全為1的n維向量.x與T取值的映射與逆映射公式為

(4)

(5)

即xiti→ti+1xi+1→ti+2xi+2→ti+3→…,其中,./表示兩個向量的對應(yīng)元素相除,其結(jié)果為一n維向量.

算法3(盒子約束優(yōu)化問題的改進(jìn)大洪水算法,BCGDA)

Begin

設(shè)置初始水平面高度為water_level,令water_level:=f0;

設(shè)置迭代次數(shù)上界count,置迭代因子i:=1;

進(jìn)入for循環(huán),fori=1:count.

按式(3)由ti生成ti+1,按式(5)將ti+1映成xi+1,計算f(xi+1).執(zhí)行if判斷語句:

iff(xi+1)

置x0:=xi+1,water_level:=f(xi+1).

Endif

迭代次數(shù)增加1,即置i:=i+1.

Endfor

輸出最優(yōu)解x0和最優(yōu)值water_level.

End

算例測試

同算法2一樣,為驗證其有效性,下面選幾個測試函數(shù)進(jìn)行求解,并將求解結(jié)果與用模擬退火算法、Matlab優(yōu)化工具箱命令fmincon所得結(jié)果進(jìn)行對比.表3列出了目前能找到的最優(yōu)解x**和最優(yōu)值f**=f(x**),表4列出了各種算法的求解結(jié)果x*和f*=f(x*).參數(shù)設(shè)置如下:算法3(BCGDA)迭代上界count取1 000,為加快收斂速度,在算法初始化階段,在可行域G內(nèi)隨機(jī)生成100個點,即取m=100;模擬退火算法與fmincon的參數(shù)設(shè)置取工具包默認(rèn)值,初始點為相同初始點.

表3　當(dāng)前最優(yōu)解

表4　求解結(jié)果

例4

曲面圖如圖1所示.

例5

s.t.-512≤x≤512,-512≤y≤512

曲面圖如圖2所示.

圖1　例4曲面圖

圖2　例5曲面圖

這里需要指出的是,模擬退火算法與fmincon的運行結(jié)果與初值關(guān)系非常密切,給定不同的初值將得到不同的結(jié)果.為了得到較好的結(jié)果,首先在G內(nèi)任取100個點,從中篩選出最優(yōu)點作為初始可行點,例4中取x0=(0,0)T,例5取x0=(-502.582 9,482.484 5)T.算法3對初值不敏感,給定不同初值,均能得到最優(yōu)解.

4結(jié)束語

本文針對無約束及盒子約束非光滑優(yōu)化問題提出了改進(jìn)的大洪水算法,去掉了大洪水算法所依賴的唯一參數(shù)up,對無約束情形在進(jìn)行鄰域搜索時提出了隨機(jī)行走算法;對約束優(yōu)化問題為加快算法收斂速度,給出了選擇初始可行點的方法,在進(jìn)行鄰域搜索時引入了混沌優(yōu)化算法.通過對大量算例進(jìn)行測試,發(fā)現(xiàn)本文提出的改進(jìn)大洪水算法是求解非光滑優(yōu)化問題的一種切實可行的方法.此外,雖然本文所提算法是針對非光滑函數(shù)給出的,但在實際應(yīng)用中,任何非線性規(guī)劃問題均可用之求解.為進(jìn)一步驗證算法的可行性及優(yōu)越性,對文獻(xiàn)[9]所給算例進(jìn)行了測試,結(jié)果發(fā)現(xiàn)本文所給算法能較快收斂到最優(yōu)解.如何將大洪水算法推廣至帶復(fù)雜非線性約束非光滑問題的求解上,以便進(jìn)一步擴(kuò)大其應(yīng)用范圍,是一個值得考慮的問題.

參考文獻(xiàn)：

[1]高巖.非光滑優(yōu)化[M].北京:科學(xué)出版社,2008.

[2]王偉偉,高巖.凸可行問題的一種次梯度投影算法[J].上海理工大學(xué)學(xué)報,2009,31(5):422-426.

[3]Dueck G.New optimization heuristics:the great deluge algorithm and the record-to-record travel[J].Journal of Computational Physics,1993,104(1):86-92.

[4]Eglese R W.Simulated annealing:a tool for operational research[J].European Journal of Operational Research,1990,46(3):271-281.

[5]魏欣,馬良,張惠珍.二次分配問題的大洪水算法求解[J].運籌與管理,2011,20(1):12-15.

[6]Lenin K,Reddy B R,Kalavathi M S.An improved great deluge algorithm(IGDA)for solving optimal reactive power dispatch problem[J].International Journal of Electronics and Electrical Engineering,2014,2(4):321-326.

[7]Ravi V.Optimization of complex system reliability by a modified great deluge algorithm[J].Asia-Pacific Journal of Operational Research,2004,21(4):487-497.

[8]Al-milli N.Hybrid genetic algorithm with great deluge to solve constrained optimization problems[J].Journal of Theoretical and Applied Information Technology,2014,59(2):385-389.

[9]盛虹平,馬良.混沌大洪水算法求解函數(shù)優(yōu)化問題[J].計算機(jī)應(yīng)用研究,2011,28(5):1626-1627.

[10]Kifah S,Abdullah S.An adaptive non-linear great deluge algorithm for the patient-admission problem[J].Information Sciences,2015,295:573-585.

[11]吳鵬.Matlab高效編程技巧與應(yīng)用:25個案例分析[M].北京:北京航空航天大學(xué)出版社,2010.

[12]王秀梅,秦體恒.基于混沌優(yōu)化算法的最小二乘圓參數(shù)估計[J].武漢理工大學(xué)學(xué)報,2008,30(8):101-104.

(編輯:丁紅藝)

Improved Great Deluge Algorithm for Nonsmooth Optimization Problems

ZHANG Qingye,GAO Yan,MA Liang

(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

Abstract：Since nonsmooth optimization problems are difficult to solve by deterministic algorithms based on subgradient information,the heuristic algorithm was considered.The optimization mechanism and characteristics of the basic great deluge algorithm(GDA)were analyzed and the solving steps were given as well.Then improved GDAs for unconstrained and box constrained problems were proposed respectively,where the parameter up was omitted.For the unconstrained case,the random walk algorithm with respect to neighborhood search was proposed.For the box constrained case,the method of choosing a feasible initial point and a chaos optimization algorithm with respect to neighborhood search were proposed.The improved GDAs were tested by taking several typical nonsmooth optimization problems as examples and were compared with other algorithms.The test results show that the improved GDAs are efficient and superior to other algorithms mentioned in the paper.So it can be used as a practical method for solving nonsmooth optimization problems.

Keywords：great deluge algorithm; nonsmooth optimization; random walk; chaos

中圖分類號：O 224

文獻(xiàn)標(biāo)志碼：A

通信作者：高巖(1962-),男,教授.研究方向:非光滑優(yōu)化、投資組合優(yōu)化、混雜系統(tǒng)控制.E-mail:gaoyan@usst.edu.cn

基金項目：國家自然科學(xué)基金資助項目(11171221);高等學(xué)校博士學(xué)科點專項科研資助項目(20123120110004);上海市一流學(xué)科建設(shè)資助項目(XTKX2012)

收稿日期：2014-12-01

DOI：10.13255/j.cnki.jusst.2016.01.008

文章編號：1007-6735(2016)01-0043-05

第一作者： 張清葉(1978-),女,博士研究生.研究方向:非光滑優(yōu)化、投資組合優(yōu)化.E-mail:zhangqingye123@163.com