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

雍龍泉，拓守恒，史加榮

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

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

1 引言

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

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

2 約束處理

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

這里，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分別表示決策變量的下界和上界。

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

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

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

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

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

3 優(yōu)化算法

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

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

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

算法1HS算法

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

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

3.利用和聲庫HM生成一個新的和聲Xnew。

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

3.2 改進的和聲搜索算法

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

算法2NGHS算法

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

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

3.利用和聲庫HM生成一個新的和聲Xnew。

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

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

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

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

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

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

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

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

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

續(xù)表1

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

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

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

6 結(jié)束語

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

:

[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.

附中文參考文獻：

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

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

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

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

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

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

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

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

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

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

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