約束處理技術(shù)及應(yīng)用*

雍龍泉，拓守恒，史加榮

1.陜西理工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西 漢中 723001

2.西安建筑科技大學(xué) 理學(xué)院，西安 710055

1 引言

約束優(yōu)化問(wèn)題（constrained optimization problem，COP）是工程應(yīng)用領(lǐng)域經(jīng)常出現(xiàn)的一類數(shù)學(xué)規(guī)劃問(wèn)題。目前求解約束優(yōu)化問(wèn)題的算法可分為兩類：梯度型算法和啟發(fā)式算法。梯度型算法要求所有函數(shù)可導(dǎo)，常見(jiàn)的梯度型算法有序列二次規(guī)劃法、拉格朗日法、簡(jiǎn)約梯度法、投影梯度法等。梯度型算法需要設(shè)置較好的初值點(diǎn)并需要函數(shù)的梯度信息，因此對(duì)于不可微以及沒(méi)有顯式數(shù)學(xué)表達(dá)式的問(wèn)題無(wú)能為力，且求得的多為局部最優(yōu)解。啟發(fā)式算法是一種模擬自然進(jìn)化過(guò)程的全局優(yōu)化方法，它借用了達(dá)爾文“物競(jìng)天擇、適者生存”的生物進(jìn)化觀點(diǎn)，通過(guò)選擇、交叉、變異等機(jī)制來(lái)提高個(gè)體的適應(yīng)性，進(jìn)而達(dá)到最優(yōu)。常見(jiàn)的啟發(fā)式算法有遺傳算法、模擬退火算法、禁忌搜索算法等。與梯度型算法相比，啟發(fā)式算法無(wú)需梯度信息，是一種基于群體的搜索技術(shù)（梯度型算法從一個(gè)點(diǎn)開(kāi)始搜索，而啟發(fā)式算法從一個(gè)群體即多個(gè)點(diǎn)開(kāi)始搜索），且對(duì)所優(yōu)化問(wèn)題的特征不敏感，具有魯棒性強(qiáng)，搜索效率高，不易陷入局部最優(yōu)等特點(diǎn)，已成功應(yīng)用于工程優(yōu)化問(wèn)題[1-7]。

求解約束優(yōu)化問(wèn)題的兩個(gè)難點(diǎn)在于：約束的處理和算法的選取。本文給出約束優(yōu)化問(wèn)題一種約束處理技術(shù)，將不等式約束轉(zhuǎn)化為等式約束，進(jìn)而通過(guò)構(gòu)造靜態(tài)罰函數(shù)將原問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化，采用全局和聲搜索算法求解。

2 約束處理

考慮如下約束優(yōu)化問(wèn)題：

這里，x∈Rn為決策變量；f(x)為目標(biāo)函數(shù)；hi(x)=0為等式約束條件，gj(x)≤0為不等式約束條件，且hi(x)、gj(x)均為Rn上的n元函數(shù)，i=1,2,…,m，j=1,2,…,l；xL和xU分別表示決策變量的下界和上界。

目前較為常見(jiàn)的是將約束優(yōu)化問(wèn)題轉(zhuǎn)換為無(wú)約束優(yōu)化問(wèn)題，采用啟發(fā)式算法進(jìn)行求解。而啟發(fā)式算法是一種無(wú)約束的搜索技術(shù)，缺乏明確的約束處理機(jī)制，這促使研究者開(kāi)發(fā)不同的方法來(lái)處理約束條件。

約束處理常給算法帶來(lái)一些額外的參數(shù)，這些參數(shù)選取不當(dāng)?shù)脑挄?huì)導(dǎo)致溢出或者不收斂。于是，設(shè)計(jì)具有較好性能的約束處理方法顯得尤為重要。較為流行的約束處理技術(shù)是將等式約束條件hi(x)=0轉(zhuǎn)換為不等式約束|hi(x)|-δ≤0來(lái)處理，利用約束違反程度函數(shù)構(gòu)造罰函數(shù)達(dá)到最優(yōu)。這里等式約束條件轉(zhuǎn)換為不等式約束條件使得可行域的拓?fù)浣Y(jié)構(gòu)發(fā)生了變化，而且這種變化與δ的取值有關(guān)。為了減少轉(zhuǎn)換給算法性能帶來(lái)的影響，可以考慮動(dòng)態(tài)調(diào)節(jié)δ。但是，如何有效地設(shè)置參數(shù)δ仍是一個(gè)值得研究的問(wèn)題[8-9]。

鑒于上述原因，本文利用絕對(duì)值函數(shù)的性質(zhì)給出一種約束處理方法：將不等式約束轉(zhuǎn)化為等式約束，且無(wú)需增加任何參數(shù)。考慮絕對(duì)值函數(shù)?(t)=|t|，當(dāng)t≥ 0,|t|=t；當(dāng)t≤ 0,|t|=-t。于是，不等式約束gj(x)≤ 0 等價(jià)于gj(x)+|gj(x)|=0，j=1,2,…,l。從而問(wèn)題（1）就等價(jià)于：

構(gòu)造適應(yīng)值函數(shù)：

這里，θ是罰因子，如果θ隨著迭代變動(dòng)，則稱式（3）為動(dòng)態(tài)罰函數(shù)；若θ是一個(gè)常數(shù)（例如，取θ=105），則稱式（3）為靜態(tài)罰函數(shù)。式（3）是一個(gè)不可微的優(yōu)化問(wèn)題，下面采用啟發(fā)式算法優(yōu)化minfitness(x)。

3 優(yōu)化算法

和聲搜索（harmony search，HS）算法是Geem等人通過(guò)類比音樂(lè)和最優(yōu)化問(wèn)題的相似性而提出的一種現(xiàn)代啟發(fā)式智能進(jìn)化算法[10]。類似于遺傳算法對(duì)生物進(jìn)化的模仿，模擬退火算法對(duì)物理退火機(jī)制的模仿，以及粒子群優(yōu)化算法對(duì)鳥(niǎo)群魚群的模仿等，和聲搜索模擬了音樂(lè)演奏的原理。和聲搜索算法模擬了音樂(lè)創(chuàng)作中樂(lè)師們憑借自己的記憶，通過(guò)反復(fù)調(diào)整樂(lè)隊(duì)中各樂(lè)器的音調(diào)，最終達(dá)到一個(gè)美妙的和聲狀態(tài)的過(guò)程。HS算法將樂(lè)器聲調(diào)的和聲類比于優(yōu)化問(wèn)題的解向量，評(píng)價(jià)即是對(duì)應(yīng)的目標(biāo)函數(shù)值。算法引入兩個(gè)主要參數(shù)，即記憶庫(kù)取值概率（harmony memory considering rate，HMCR）和微調(diào)概率（pitch adjusting rate，PAR）。算法首先產(chǎn)生 HMS（harmony memory size）個(gè)初始解（和聲）放入和聲記憶庫(kù)（harmony memory，HM）內(nèi)。然后，在和聲記憶庫(kù)內(nèi)隨機(jī)搜索新解，具體做法是：隨機(jī)產(chǎn)生0～1的隨機(jī)數(shù)rand，如果rand

3.1 經(jīng)典的和聲搜索算法

經(jīng)典和聲搜索算法的基本步驟如下所示。

算法1HS算法

1.設(shè)置初始參數(shù)：決策變量個(gè)數(shù)N；各決策變量的搜索空間[XL,XU]；和聲記憶庫(kù)的大小HMS；和聲記憶的保留概率HMCR；音調(diào)調(diào)節(jié)概率PAR與調(diào)整步長(zhǎng)bw；最大迭代次數(shù)Tmax。

2.在搜索空間內(nèi)隨機(jī)初始化和聲記憶庫(kù)HM，并計(jì)算每個(gè)和聲向量的適應(yīng)值。

3.利用和聲庫(kù)HM生成一個(gè)新的和聲Xnew。

5.如果迭代次數(shù)達(dá)到Tmax，則結(jié)束并輸出和聲記憶庫(kù)中最好和聲向量，否則轉(zhuǎn)至步驟3繼續(xù)。

3.2 改進(jìn)的和聲搜索算法

與其他智能算法一樣，和聲搜索算法也存在早熟現(xiàn)象。對(duì)和聲搜索算法的改進(jìn)主要集中在調(diào)節(jié)算法中的某些參數(shù)[12-15]。文獻(xiàn)[13]采用位置更新和小概率變異策略，給出了一種全局和聲搜索算法（novel global harmony search，NGHS），改進(jìn)后的算法如下所示，其中Xbest和Xworst分別表示當(dāng)前和聲記憶庫(kù)中最好和聲與最差和聲。

算法2NGHS算法

1.設(shè)置初始參數(shù)：決策變量個(gè)數(shù)N；各決策變量的搜索空間[XL,XU]；和聲記憶庫(kù)的大小HMS；最大迭代次數(shù)Tmax；變異概率pm。

2.在搜索空間內(nèi)隨機(jī)初始化和聲記憶庫(kù)HM，并計(jì)算每個(gè)和聲向量的適應(yīng)值。

3.利用和聲庫(kù)HM生成一個(gè)新的和聲Xnew。

NGHS與HS算法的區(qū)別見(jiàn)文獻(xiàn)[16]。已有文獻(xiàn)大多研究的是NGHS算法求解無(wú)約束優(yōu)化，下面結(jié)合本文約束處理方法，采用NGHS算法求解約束優(yōu)化問(wèn)題。

4 約束優(yōu)化數(shù)值實(shí)驗(yàn)結(jié)果

為了測(cè)試約束處理及算法的有效性，選取13個(gè)帶有約束的非線性規(guī)劃標(biāo)準(zhǔn)測(cè)試問(wèn)題（NLP_1~NLP_13）進(jìn)行測(cè)試。這些測(cè)試問(wèn)題是用進(jìn)化算法很難取得全局最優(yōu)解的一些具有代表性的函數(shù)，具體表達(dá)式見(jiàn)文獻(xiàn)[17]。算法程序用MatlabR2009a編寫，算法參數(shù)為HMS=15,HMCR=0.85,PAR=0.35，bw=(XU-XL)/1 000，算法終止的最大進(jìn)化代數(shù)Tmax=20 000，在NGHS算法中選取pm=0.005，罰參數(shù)θ=105。為了便于觀察NGHS算法的搜索性能，同時(shí)給出經(jīng)典和聲搜索算法（HS）、混沌和聲搜索算法（harmony search algorithm with chaos，HSCH）[18]、最壞最好和聲搜索算法（harmony search algorithm with worst and best strategy，HSWB）[19]的求解結(jié)果。為消除隨機(jī)數(shù)對(duì)算法的影響，HS、HSCH、HSWB、NGHS算法各運(yùn)行20次。表1給出了各算法運(yùn)行20次后的最優(yōu)適應(yīng)值（Best）、平均適應(yīng)值（Mean）、最差適應(yīng)值（Worst）、標(biāo)準(zhǔn)差（Std）及運(yùn)行時(shí)間（Mean_Time,取20次的平均值）。圖1給出了每一個(gè)測(cè)試問(wèn)題運(yùn)行20次后的最優(yōu)目標(biāo)值的分布盒圖。

由表1可看出：對(duì)于NLP_1、NLP_3、NLP_4、NLP_5、NLP_6、NLP_9、NLP_10，NGHS 優(yōu)于 HS；對(duì)于NLP_2、NLP_7，HS優(yōu)于NGHS；對(duì)于NLP_8和NLP_12，所有算法結(jié)果相當(dāng)。對(duì)于NLP_11，HSCH結(jié)果稍優(yōu)于其余算法；對(duì)于NLP_13，HSWB結(jié)果優(yōu)于其余算法。這些結(jié)果表明，本文約束處理方法針對(duì)大部分測(cè)試函數(shù)是有效的，這也符合“No free lunch”原理[20]。下面給出一個(gè)具體的應(yīng)用算例。

5 應(yīng)用于工程優(yōu)化問(wèn)題

伸縮繩設(shè)計(jì)是典型的帶有約束的工程優(yōu)化問(wèn)題，其數(shù)學(xué)描述如下：

取罰參數(shù)θ=108，求解伸縮繩設(shè)計(jì)問(wèn)題的計(jì)算結(jié)果如表2所示（運(yùn)行20次）。

NGHS算法最終求得的最優(yōu)解為：

Table 1 Statistical results for 20 runs表1 運(yùn)行20次的統(tǒng)計(jì)結(jié)果

續(xù)表1

Fig.1 Boxplot of optimal solutions for 20 runs圖1 運(yùn)行20次后的最優(yōu)目標(biāo)值分布盒圖

Table 2 Statistical results for 20 runs表2 運(yùn)行20次的統(tǒng)計(jì)結(jié)果

由表2可知，本文算法求出的結(jié)果優(yōu)于文獻(xiàn)[21]中的結(jié)果，且計(jì)算結(jié)果穩(wěn)定性好。

6 結(jié)束語(yǔ)

本文給出了一種約束處理方法，為各類工程優(yōu)化問(wèn)題約束處理提供了新的途徑。下一步可以考慮采用本文約束處理方法，結(jié)合其他啟發(fā)式算法求解可靠性優(yōu)化[13]、結(jié)構(gòu)優(yōu)化[22-24]等工程問(wèn)題。

:

[1]Lin Dan,Li Minqiang,Kou Jisong.A GA-based method for solving constrained optimization problems[J].Journal of Software,2001,12(4):628-632.

[2]Zhou Yuren,Li Yuanxiang,Wang Yong,et al.APareto strength evolutionary algorithm for constrained optimization[J].Journal of Software,2003,14(7):1243-1249.

[3]Huang Haiyan,Gu Xingsheng,Liu Mandan.Research on cultural algorithm for solving nonlinear constrained optimization[J].ActaAutomatica Sinica,2007,33(10):1115-1120.

[4]Huang Tianyun.Research advances on pattern searches in constrained optimization[J].Chinese Journal of Computers,2008,31(7):1200-1215.

[5]Liu Ruochen,Jiao Licheng,Lei Qifeng,et al.New differential evolution constrained optimization algorithm[J].Journal of Xidian University:Natural Science,2011,38(1):47-53.

[6]Saha C,Das S,Pal K,et al.A fuzzy rule-based penalty function approach for constrained evolutionary optimization[J].IEEE Transactions on Cybernetics,2014,46(12):2953-2965.

[7]Mun S,Cho Y H.Modified harmony search optimization for constrained design problems[J].Expert Systems with Applications,2012,39(1):419-423.

[8]Guo Guanqi,Wang Yong.Constraint-handling techniques based on evolutionary algorithms[J].Journal of Hunan Institute of Science and Technology:Natural Sciences,2006,19(4):15-18.

[9]Wang Yong,Cai Zixing,Zhou Yuren,et al.Constrained optimization evolutionary algorithms[J].Journal of Software,2009,20(1):11-29.

[10]Geem Z W,Kim J H,Loganathan G V.A new heuristic optimization algorithm:harmony search[J].Simulation,2001,76(2):60-68.

[11]Yong Longquan.Advances in harmony search algorithm[J].Computer Systems&Applications,2011,20(7):244-248.

[12]Mahdavi M,Fesanghary M,Damangir E.An improved harmony search algorithm for solving optimization problems[J].Applied Mathematics&Computation,2007,188(2):1567-1579.

[13]Zou Dexuan,Gao Liqun,Wu Jianhua,et al.A novel global harmony search algorithm for reliability problems[J].Computers&Industrial Engineering,2010,58(2):307-316.

[14]Siddique N,Adeli H.Harmony search algorithm and its variants[J].International Journal of Pattern Recognition andArtificial Intelligence,2015,29(8):1-22.

[15]Wang Gaige,Gandomi A H,Zhao Xiangjun,et al.Hybridizing harmony search algorithm with cuckoo search for global numerical optimization[J].Soft Computing,2016,20(1):273-285.

[16]Zou Dexuan.Heuristic algorithms and their applications in engineering optimization[D].Shenyang:Northeastern University,2011.

[17]Runarsson T P,Yao Xin.Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on Evolutionary Computation,2000,4(3):284-294.

[18]Yong Longquan,Liu Sanyang,Tuo Shouheng,et al.Improved harmony search algorithm with chaos for absolute value equation[J].Telecommunication Computing Electronics and Control,2013,11(4):835-844.

[19]Yong Longquan,Liu Sanyang,Tuo Shouheng,et al.Improved harmony search algorithm for absolute value equation[J].Journal of Natural Science of Heilongjiang University,2013,30(3):321-327.

[20]Wolpert D H,Macready W G.No free lunch theorems for optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67-82.

[21]Wang Ling,Qian Bin.Hybrid differential evolution and scheduling algorithm[M].Beijing:Tsinghua University press,2012.

[22]Zou D,Liu H,Gao L,et al.A novel modified differential evolution algorithm for constrained optimization problems[J].Computers&Mathematics with Applications,2011,61(6):1608-1623.

[23]Gandomi A H,Yang Xinshe.Benchmark problems in structural optimization[M]//Computational Optimization,Methods andAlgorithms.Berlin,Heidelberg:Springer,2011:259-281.

[24]Gandomi A H,Yang Xinshe,Alavi A H.Cuckoo search algorithm:a metaheuristic approach to solve structural optimization problems[J].Engineering with Computers,2013,29(1):17-35.

附中文參考文獻(xiàn)：

[1]林丹,李敏強(qiáng),寇紀(jì)凇.基于遺傳算法求解約束優(yōu)化問(wèn)題的一種算法[J].軟件學(xué)報(bào),2001,12(4):628-632.

[2]周育人,李元香,王勇,等.Pareto強(qiáng)度值演化算法求解約束優(yōu)化問(wèn)題[J].軟件學(xué)報(bào),2003,14(7):1243-1249.

[3]黃海燕,顧幸生,劉漫丹.求解約束優(yōu)化問(wèn)題的文化算法研究[J].自動(dòng)化學(xué)報(bào),2007,33(10):1115-1120.

[4]黃天云.約束優(yōu)化模式搜索法研究進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào),2008,31(7):1200-1215.

[5]劉若辰,焦李成,雷七峰,等.一種新的差分進(jìn)化約束優(yōu)化算法[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2011,38(1):47-53.

[8]郭觀七,王勇.基于進(jìn)化算法的約束處理技術(shù)[J].湖南理工學(xué)院學(xué)報(bào),2006,19(4):15-18.

[9]王勇,蔡自興,周育人,等.約束優(yōu)化進(jìn)化算法[J].軟件學(xué)報(bào),2009,20(1):11-29.

[11]雍龍泉.和聲搜索算法研究進(jìn)展[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2011,20(7):244-248.

[16]鄒德旋.啟發(fā)式算法及其在工程優(yōu)化中的應(yīng)用[D].沈陽(yáng):東北大學(xué),2011.

[19]雍龍泉,劉三陽(yáng),拓守恒,等.改進(jìn)的和聲搜索算法求絕對(duì)值方程[J].黑龍江大學(xué)自然科學(xué)學(xué)報(bào),2013,30(3):321-327.

[21]王凌,錢斌.混合差分進(jìn)化與調(diào)度算法[M].北京:清華大學(xué)出版社,2012.