一種求解二層多目標(biāo)規(guī)劃問題的改進模擬退火算法

張 濤 陳 忠，呂一兵

(長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北荊州434023 水資源與水電科學(xué)國家重點實驗室(武漢大學(xué))，湖北武漢430072) (長江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

一種求解二層多目標(biāo)規(guī)劃問題的改進模擬退火算法

張 濤 陳 忠，呂一兵

(長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北荊州434023 水資源與水電科學(xué)國家重點實驗室(武漢大學(xué))，湖北武漢430072) (長江大學(xué)信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

基于求解多目標(biāo)規(guī)劃問題的模擬退火算法，將求解二層多目標(biāo)規(guī)劃問題轉(zhuǎn)化為交互求解下層多目標(biāo)規(guī)劃問題和上層多目標(biāo)規(guī)劃問題，然后結(jié)合求解多目標(biāo)規(guī)劃的精英策略，提出了求解二層多目標(biāo)規(guī)劃的改進模擬退火算法。最后，通過數(shù)值試驗驗證了算法的可行性和有效性。

二層多目標(biāo)規(guī)劃；Pareto最優(yōu)解；模擬退火算法

二層多目標(biāo)規(guī)劃是二層規(guī)劃的子問題，其主要特征是上層和下層都具有多個目標(biāo)函數(shù)。求解二層多目標(biāo)規(guī)劃的主要難點在于：上層問題的可行解一定是下層問題的最優(yōu)解。這就要求只能將下層問題的精確最優(yōu)解反饋給上層。值得慶幸的是，大量實踐表明，下層問題的近似最優(yōu)解通?？梢宰鳛樽顑?yōu)響應(yīng)反饋給上層，從而通過上層問題的求解得到整個問題的近似最優(yōu)解，然后再通過預(yù)設(shè)的迭代次數(shù)，可以使整個問題的近似最優(yōu)解任意精度的逼近精確解?；谶@種觀念，模擬退火算法[1]對于求解二層多目標(biāo)規(guī)劃問題就有巨大的潛力。下面，筆者基于求解多目標(biāo)規(guī)劃問題的改進模擬退火算法，將求解二層多目標(biāo)問題轉(zhuǎn)化為交互求解下層多目標(biāo)規(guī)劃問題和上層多目標(biāo)規(guī)劃問題，再結(jié)合求解多目標(biāo)規(guī)劃的精英策略[2]，提出了求解二層多目標(biāo)規(guī)劃的模擬退火算法。

1 二層多目標(biāo)規(guī)劃模型

假設(shè)x∈Rn1,y∈Rn2,F:Rn1×Rn2→Rm1,f:Rn1×Rn2→Rm2,G:Rn1×Rn2→Rp,g:Rn1×Rn2→Rq，則二層多目標(biāo)規(guī)劃可以寫為：

(1)

式中，F(xiàn)(x,y)和f(x,y)分別為上層目標(biāo)函數(shù)和下層目標(biāo)函數(shù)；G(x,y)和g(x,y)分別表示上層約束條件和下層約束條件。

假設(shè)：

S={(x,y)|G(x,y)≥0,g(x,y)≥0}

X={x|?y,G(x,y)≥0,g(x,y)≥0}S(x)={y|g(x,y)≥0}

定義1固定x∈X, 如果y是下層問題的一個Pareto最優(yōu)解，則(x,y)為問題(1)的可行解。

定義2如果(x*,y*)是問題(1)的可行解, 并且不存在(x,y)∈IR, 使得F(x,y)F(x*,y*), 則(x*,y*)是問題(1)的一個Pareto最優(yōu)解, 其中 符號“” 表示Pareto偏好。

2 算法設(shè)計

2.1算法1

步1 根據(jù)當(dāng)前解Xk和擾動量εk產(chǎn)生備選解Yk=Xk+εk。

步3 計算轉(zhuǎn)移概率p(Yk|Xk,Tk)=min{1,exp(ΔE(Xk,Yk))}。

步4 選擇子代。若果p(Yk|Xk,Tk)≥η, 則Xk+1=Yk; 否則Xk+1=Xk。

2.2算法2

步1 對于第k(k=1,2,…,ns)個子群，在下層f空間給每個粒子分配非受控等級NDl以及擁擠度值CDl。然后將所有的子群合并成一個種群Pt，在F空間中對每個粒子分配非受控等級NDu以及擁擠度值NDu。

步2 將非受控等級NDu=1及NDl=1的粒子從Pt挑出，保存于精英集合At。

步3 對于第k個子群，更新下層決策變量。①設(shè)置下層循環(huán)變量tl=0；②對于固定的xj，利用算法1更新第j(j=1,2,…,Nl) 個粒子；③設(shè)置tl=tl+1；④如果tl≥Tl, 轉(zhuǎn) ⑤， 否則轉(zhuǎn)②；⑤對于第i個子群中的每個粒子在f空間中重新分配非受控等級NDl和擁擠度值CDl。然后將所有的子群合并成一個種群，重新命名為Qt，并在F空間中對其重新分配非受控等級NDu和擁擠度值CDu。

步 4 將Pt和Qt合并為Rt，并在F空間中分配非受控等級NDu，具有相同等級的粒子計算其擁擠度值。

步 5 從Rt中選擇一半粒子作為子代種群。 首先將NDu=1，NDl=1的粒子按照遞減的擁擠度值CDu所對應(yīng)的子群復(fù)制到中間種群St。然后考慮NDu=2的情況，依次類推直到St中包含ns個子群。

步6 根據(jù)精英策略更新精英集合At。

步7 在集合St中更新上層決策變量：①初始化上層循環(huán)次數(shù)tu=0；②對于固定的yi根據(jù)算法1更新第i個粒子 (i=1,2,…,Nu)；③ 設(shè)置tu=tu+1；④如果tu≥Tu, 轉(zhuǎn)步⑤， 否則轉(zhuǎn)②；⑤在F空間中，每個粒子分配非受控等級NDu和擁擠度值CDu。

步 9 如果Tk

3 數(shù)值試驗

根據(jù)算法2，利用c#進行編程(計算機配置：CPU:AMD 2.80GHz; RAM: 3.25GB)，所得數(shù)值結(jié)果如下。

參數(shù)設(shè)置如下:Nu=200，Tu=200,Nl=40,Tl=40,Tmax=106,Tf=10-3，m=3。根據(jù)算法2，利用c#進行編程(計算機配置：CPU: AMD 2.80GHz; RAM: 3.25GB)，所得數(shù)值結(jié)果如圖1和圖2所示。

圖1 算例1的最優(yōu)前沿面 圖2 算例1的最優(yōu)Pareto解集

算例2[4]:

圖3 算例3的最優(yōu)前沿面

參數(shù)設(shè)置如下:Nu=400，Tu=200,Nl=80,Tl=40,Tmax=107,Tf=10-3,m=3。根據(jù)算法2，利用c#進行編程(計算機配置：CPU: AMD 2.80GHz; RAM: 3.25GB)，所得數(shù)值結(jié)果如圖3所示。

從算例1的結(jié)果可以很清楚的看到，利用改進的模擬退火算法所求得的問題的最優(yōu)前沿面非常接近理論前沿面，并且可以均勻的分布于理論前沿面上；對于理論前沿面未知的算例2，利用改進的模擬退火算法所求的最優(yōu)前沿面與文獻[5]中所求解的最優(yōu)前沿面非常的相似，從而說明該算法是可行并且是有效的。

[1]汪定偉，王俊偉，王洪峰，等. 智能優(yōu)化算法[M]. 北京：高等教育出版社，2006.

[2] Deb K, Agrawalan S, Pratap A,et al. A fast and elitist multi-objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002(6):182-197.

[3] Eichfelder G. Solving nonlinear multi-objective bi-level optimization problems with coupled upper level constraints[A]. Technical Report Preprint No. 320, Preprint-Series of the Institute of Applied Mathematics[C].Univ. Erlangen-Nrnberg, Germany, 2007.

[4] Eichfelder G.Multiobjective bilevel optimization[J]. Mathematical Programming, 2010, 123:419-449.

[編輯] 洪云飛

10.3969/j.issn.1673-1409(N).2012.11.001

O224

A

16731409(2012)11N00103