求解二層線性規(guī)劃問(wèn)題的交互式人工蜂群算法

張 濤 (長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023 水資源與水電科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué))，湖北 武漢 430072)

陳 忠，呂一兵 (長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

求解二層線性規(guī)劃問(wèn)題的交互式人工蜂群算法

張 濤 (長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023 水資源與水電科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué))，湖北 武漢 430072)

陳 忠，呂一兵 (長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

基于人工蜂群算法提出了一種求解二層線性規(guī)劃問(wèn)題的交互式人工蜂群算法, 即將求解二層規(guī)劃問(wèn)題轉(zhuǎn)化為交互求解下層單目標(biāo)規(guī)劃問(wèn)題和上層單目標(biāo)規(guī)劃問(wèn)題。數(shù)值試驗(yàn)表明,該算法能夠在較短的時(shí)間內(nèi)得到問(wèn)題的近似最優(yōu)解,說(shuō)明該算法是一種求解二層線性規(guī)劃問(wèn)題的有效方法。

人工蜂群算法；線性二層規(guī)劃；交互式

二層規(guī)劃問(wèn)題是一類遞階優(yōu)化問(wèn)題,它具有2個(gè)決策層, 2個(gè)決策層分別有各自的目標(biāo)函數(shù)和約束條件。進(jìn)行決策時(shí),上層決策者首先根據(jù)自己的目標(biāo)給定一個(gè)決策,下層決策者根據(jù)上層決策者的決策進(jìn)行自身目標(biāo)決策, 并將最優(yōu)決策反饋到上層,上層決策者再根據(jù)下層的反饋修正自己的決策,最終找到使上層目標(biāo)達(dá)到最優(yōu)的決策。

二層規(guī)劃模型的求解十分困難,原因之一就是由于雙層規(guī)劃問(wèn)題是一個(gè)NP-難問(wèn)題。即使是很簡(jiǎn)單的二層線性規(guī)劃問(wèn)題也是NP-難問(wèn)題,不存在多項(xiàng)式求解算法[1]。二層規(guī)劃的非凸性也是造成二層規(guī)劃問(wèn)題求解異常復(fù)雜的另一重要原因。目前，國(guó)內(nèi)外一些學(xué)者提出的求解算法或求解方法,但大多數(shù)都是針對(duì)特定的二層規(guī)劃模型提出的。設(shè)計(jì)求解二層規(guī)劃算法的主要難點(diǎn)在于：上層問(wèn)題的可行解一定是下層問(wèn)題的最優(yōu)解。這就要求只能將下層問(wèn)題的精確最優(yōu)解反饋給上層。大量實(shí)踐表明，下層問(wèn)題的近似最優(yōu)解通?？梢宰鳛樽顑?yōu)響應(yīng)反饋給上層，從而通過(guò)上層問(wèn)題的求解得到整個(gè)問(wèn)題的近似最優(yōu)解，然后再通過(guò)預(yù)設(shè)的迭代次數(shù)，可以使整個(gè)問(wèn)題的近似最優(yōu)解任意精度的逼近精確解[2]。為此，筆者基于人工蜂群算法提出了一種求解二層線性規(guī)劃問(wèn)題的交互式人工蜂群算法。

1 線性二層規(guī)劃模型

假設(shè)x∈X?Rn,y∈Y?Rm,F:X×Y→R,andf:X×Y→R,則線性二層規(guī)劃可以寫(xiě)為：

(1)

式中，F(xiàn)(x,y)和f(x,y)分別為上層目標(biāo)函數(shù)和下層目標(biāo)函數(shù)；c1,c2∈Rn；d1,d2∈Rm；b1∈Rp；b2∈Rq,A1∈Rp×n,B1∈Rp×m,A2∈Rq×n,B1∈Rq×m。

假設(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是下層問(wèn)題的一個(gè)最優(yōu)Pareto最優(yōu)解，則(x,y)為問(wèn)題(1)的可行解。

定義2如果(x*,y*)是問(wèn)題(1)的可行解, 對(duì)于任意的(x,y)∈IR, 都有F(x*，y*)≤F(x,y), 則(x*,y*)是問(wèn)題(1)的一個(gè)最優(yōu)解。

2 人工蜂群算法

人工蜂群算法是Karaboga提出的一種模仿蜜蜂覓食的新型啟發(fā)式算法[3]，與遺傳、模擬退火、粒子群等算法相比，人工蜂群具有控制參數(shù)少、計(jì)算簡(jiǎn)潔、易于實(shí)現(xiàn)等優(yōu)點(diǎn)，且有較好的平衡探索與開(kāi)發(fā)能力，已被越來(lái)越多的學(xué)者所關(guān)注并已成功的應(yīng)用于解決函數(shù)的數(shù)值優(yōu)化問(wèn)題[4-6]。在優(yōu)化問(wèn)題求解時(shí)，食物源的位置對(duì)應(yīng)優(yōu)化問(wèn)題的可行解，食物源的收益度對(duì)應(yīng)優(yōu)化問(wèn)題的適應(yīng)度值，最大收益度食物源對(duì)應(yīng)優(yōu)化問(wèn)題的最優(yōu)解。

一般地，人工蜂群通過(guò)方程(1)隨機(jī)產(chǎn)生P個(gè)解：

(2)

(3)

式中，vij代表在xij附近產(chǎn)生一個(gè)新解，k∈{1,2,…,s}，k和j都是隨機(jī)選取，k是i鄰域的一個(gè)解，且k≠i；rij∈rand[-1,1]。跟隨蜂對(duì)解的選擇是通過(guò)觀察引領(lǐng)蜂的搖擺舞來(lái)判斷解的適應(yīng)度值，并依據(jù)選擇概率大小來(lái)選擇跟隨哪個(gè)引領(lǐng)蜂。

適應(yīng)度值fitnesssi和選擇概率p計(jì)算公式如下：

在人工蜂群算法中，利用參數(shù)R來(lái)記錄某個(gè)解被更新的次數(shù)。如果某個(gè)解連續(xù)R次循環(huán)后沒(méi)有得改善，則證明該解陷入局部最優(yōu)，就要被放棄。假設(shè)被放棄的解是xi，則根據(jù)鄰域構(gòu)成規(guī)則隨機(jī)產(chǎn)生一個(gè)新解來(lái)代替原來(lái)解xi。人工蜂群算法(算法1)的計(jì)算步驟如下：

步1 產(chǎn)生初始解集xij,i=1,2,…,S,j=1,2,…,D。設(shè)置triali=0，triali表示非改進(jìn)解xi的數(shù)量。

步3 設(shè)置外循環(huán)初始值m=1。

步4 設(shè)置內(nèi)循環(huán)初始值l=1。

步7 如果解xi沒(méi)有改進(jìn)，則triali=triali+1；否則，triali=0。

步9 跟隨蜂根據(jù)概率pi選擇食物源(解)，然后進(jìn)行領(lǐng)域搜索產(chǎn)生新解，再計(jì)算其適應(yīng)度；轉(zhuǎn)步6～步7。

步10 設(shè)置i=i+1。

步11 如果l

步13 所有搜索完畢后，記錄當(dāng)前最好的解。

步14 設(shè)置m=m+1。

步15 如果m

3 求解線性二層規(guī)劃問(wèn)題的人工蜂群算法

利用人工蜂群算法求解線性二層規(guī)劃問(wèn)題,對(duì)上下層都采用人工蜂群群算法進(jìn)行求解。算法(算法2)步驟如下:

步1 根據(jù)方程(2)初始化上層決策變量xi,設(shè)置i=0，設(shè)置i的最大值為P。

步2 求解下層優(yōu)化問(wèn)題。固定xi，將xi帶入到問(wèn)題(1)的下層，利用算法1求解下層問(wèn)題的最優(yōu)解y*。

步3 求解上層優(yōu)化問(wèn)題。將步2中的y*反饋到上層，利用算法1求解上層問(wèn)題的最優(yōu)解x及最優(yōu)值F。令x*=x,y*=y,F*=F。

4 試驗(yàn)仿真與結(jié)果分析

算例1[7]設(shè)x∈R,y∈R,考慮如下線性二層規(guī)劃問(wèn)題：

算例2[8]設(shè)x∈R2,y∈R3，考慮如下線性二層規(guī)劃問(wèn)題：

根據(jù)算法2，利用c#進(jìn)行編程，算法中的具體參數(shù)設(shè)置如下：算法1中種群S=100，內(nèi)層循環(huán)次數(shù)l=40，外層循環(huán)次數(shù)m=80; 算法2中，p=50，最后得出的結(jié)果與文獻(xiàn)的結(jié)果比較見(jiàn)表1。從數(shù)值試驗(yàn)結(jié)果來(lái)看,利用筆者所設(shè)計(jì)算法的計(jì)算結(jié)果與最優(yōu)解的誤差很小，因此，該算法是有效的。數(shù)值試驗(yàn)還表明，人工蜂群算法對(duì)種群規(guī)模要求不是很大，節(jié)約了計(jì)算時(shí)間。

表1 仿真結(jié)果

[1]Bard J. Some properties of the bi-level linear programming[J]. Journal of Optimization Theory and Applications, 1991, 32: 146-164.

[2] Zhang T, Hu T S，Zheng Y.An Improved Particle Swarm Optimization for Solving Bilevel Multiobjective Programming Problem[J]. Journal of Applied Mathematics, doi:10.1155/2012/626717, 2012.

[3]Karaboga D, Basturk B.A powerful and efficient algorithm for numerical function optimization：artificial bee colony (ABC) algorithm[J].Journal of Global Optimization, 2007, 39(3):459-471.

[4]羅鈞，李研.具有混沌搜索策略的蜂群優(yōu)化算法[J].控制與決策，2010,25(12):1913-1916.

[5]胡珂，李迅波，王振林.改進(jìn)的人工蜂群算法性能[J].計(jì)算機(jī)應(yīng)用, 2011,31(4):1107-1110.

[6]王慧穎，劉建軍，王全洲.改進(jìn)的人工蜂群算法在函數(shù)優(yōu)化問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2011,7(13)：36-39..

[7]Anandalingam G， White D J. A solution method for the linear static stackelberg problem using penalty functions [J]. IEEE Transaction on Automatic Control, 1990,35(10):1170-1173.

[8]Bard J F. Partical Bilevel optimization Algorithm and Applications [M]. Kluwer Academic Publishers, USA, 1998.

2012-10-25

國(guó)家自然科學(xué)基金項(xiàng)目(11201039；61273179)；湖北省教育廳重點(diǎn)項(xiàng)目(D20101304)。

張濤(1978-)，男，講師，博士生，現(xiàn)主要從事復(fù)雜系統(tǒng)建模與智能計(jì)算方面的教學(xué)與研究工作。

O221.1

A

1673-1409(2013)01-0001-03

[編輯] 洪云飛