李彩云，張著洪

(1.貴州大學(xué) 理學(xué)院 系統(tǒng)科學(xué)及信息技術(shù)研究所，貴州 貴陽 550025;2.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025)

由于人為干擾、環(huán)境影響、測量偏差等因素，使得大量實際工程優(yōu)化問題，如橋梁工程設(shè)計、城市公交車路線規(guī)劃、項目計劃管理等，均含有有界擾動參數(shù)，這類問題可描述為含有界擾動參數(shù)的區(qū)間數(shù)規(guī)劃［1］。約束區(qū)間數(shù)規(guī)劃是一種含約束條件的區(qū)間數(shù)規(guī)劃。由于參數(shù)的不確定性和有界性，加之優(yōu)化對象具有極高計算復(fù)雜性，使得對其求解具有極大挑戰(zhàn)性。通常需首先利用模糊規(guī)劃或嵌套式優(yōu)化的思想將其轉(zhuǎn)化為確定性的數(shù)學(xué)規(guī)劃模型，進而利用數(shù)學(xué)規(guī)劃方法［2－3］或智能優(yōu)化方法［1，4－11］尋求其有效解。

嵌套式優(yōu)化結(jié)構(gòu)是非線性區(qū)間數(shù)規(guī)劃問題的常規(guī)表現(xiàn)形式，求解方法通常有主從結(jié)構(gòu)法［1，4－8］和模型近似化法［9－10］。前者是一種較為流行的嵌套式優(yōu)化方法，其具有結(jié)構(gòu)簡單和搜索效果好的優(yōu)點，但計算復(fù)雜度較高，不宜在單臺PC 機上執(zhí)行尋優(yōu)過程。例如，文獻［1，6］把非線性區(qū)間數(shù)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)嵌套優(yōu)化問題，然后利用微種群遺傳算法設(shè)計主從式遺傳算法，求解原問題的解，但嵌套式優(yōu)化使得求解的計算復(fù)雜度很高。另一方面，后者在近年也得到許多研究，主要集中在研究替代不確定目標(biāo)函數(shù)和約束函數(shù)的近似函數(shù)，這種方法的優(yōu)點在于搜索效率高，但結(jié)構(gòu)復(fù)雜和尋優(yōu)效果不佳。例如文［9］將RBF 網(wǎng)絡(luò)的權(quán)值視為區(qū)間數(shù)，并用網(wǎng)絡(luò)的輸出區(qū)間值函數(shù)近似取代原優(yōu)化問題的不確定目標(biāo)函數(shù)和約束函數(shù)，獲得原問題的近似化模型，這種處理方法可極大提高尋優(yōu)效率，但獲得的解的精度較低。文［10］利用近似化模型替代嵌套式優(yōu)化模型，再用非線性區(qū)間數(shù)優(yōu)化方法進行求解，能提高尋優(yōu)效率。非主從結(jié)構(gòu)法是利用區(qū)間自然擴張和區(qū)間數(shù)的性質(zhì)，將嵌套式優(yōu)化模型轉(zhuǎn)化為區(qū)間自然擴張模型，進而設(shè)計智能優(yōu)化算法進行求解，但研究工作較為罕見。

鑒于求解非線性區(qū)間數(shù)規(guī)劃較難在搜索效果和效率之間作出合理權(quán)衡的問題，本文結(jié)合文化基因算法的思想，將經(jīng)典最速下降法和一種求解非約束區(qū)間數(shù)規(guī)劃的免疫優(yōu)化方法［11］有機結(jié)合，提出一種改進型約束免疫優(yōu)化算法(ICIOA :Improved Constrained Immune Optimization Algorithm)。在此，免疫優(yōu)化算法被用于執(zhí)行全局搜索，而最速下降法被用于增強算法的局部搜索能力和確定不確定函數(shù)的上下界，此有助于加速算法的尋優(yōu)過程和獲得高質(zhì)量的解。

1 問題描述與轉(zhuǎn)化

給定兩個區(qū)間A=［aL，aR］和B=［bL，bR］，依據(jù)區(qū)間的中點和半徑，A 和B 可表示為A=〈aC，aW〉和B=〈bC，bW〉其中aC=(aL+aR)/2，aW=(aR－aL)/2。

定義1［12－13］區(qū)間A 和B 的區(qū)間序關(guān)系和距離如下:

考慮如下非線性區(qū)間數(shù)規(guī)劃:

其中x為決策向量，x∈D，D為Rn中有界閉區(qū)域，u為不確定參數(shù)向量，u=(u1，u2，…，um)∈U，U是Rm中有界閉區(qū)域，，f 關(guān)于x是非線性的不確定目標(biāo)函數(shù)，gj為不確定約束函數(shù)，f 和gj關(guān)于x 和u 均連續(xù)。通常，人們期望尋找x*∈D，使得根據(jù)式(2)，滿足(P1)的不等式約束的所有候選解x 都有f(x*，u)≤f (x，u) ;然而這樣的x*一般不存在，為此，將該模型轉(zhuǎn)化為如下形式:

其中，

則(P2)的可行域為Σ={x ∈D| V(x)=0}，從而(P2)可重新表示為:

定義2 稱x*∈Σ為(P3)的有效解，如果不存在x ∈Σ，使得F(x*)＜CWF(x);特別，若存在x*∈Σ，使得在Σ 上同時達到最小，則稱x*為(P1)的最優(yōu)解，相應(yīng)的目標(biāo)區(qū)間值稱為最優(yōu)值間。

由于(P3)是一種嵌套式優(yōu)化問題，其計算復(fù)雜度較高，需將其轉(zhuǎn)化為如下區(qū)間值規(guī)劃問題，再進行求解:

其中Π(x)為f(x，u)關(guān)于u 的區(qū)間自然擴張函數(shù)。將定義2 中F(x)用Π(x)取代，可獲(P4)的有效解的含義。文獻［11］獲得如下結(jié)果:

定理1［11］1)(P4)的有效解集是Γ={z ∈D| fL(z)≤σ}，其中，σ=min fR(x)，x ∈D;2)(P3)的有效解必是(P4)的有效解。

基于定理1，本文求解(P1)的最優(yōu)解的思路是首先利用優(yōu)化方法求解(P4)的有效解集Λ，然后由Λ 確定(P3)的有效解集Γ，進而由Γ 確定(P1)的最優(yōu)解。

2 算法描述

為便于算法描述，對于(P4)，將決策空間D 中的候選解視為抗體，抗原視為求解問題本身。利用文化基因思想，將最速下降法和免疫優(yōu)化算法結(jié)合，求解含約束的區(qū)間數(shù)規(guī)劃(P1)。改進型約束免疫優(yōu)化算法(ICIOA)具體描述如下:

步1 參數(shù)設(shè)置:群體規(guī)模N，多項式變異概率Pm，柯西變異概率Pc，充分大的初始閾值σ0，最大迭代數(shù)Gmax，置n=0。

步2 產(chǎn)生初始抗體群An={x1，x2，…，xN}。

步3 利用區(qū)間運算規(guī)則，計算各抗體的目標(biāo)值區(qū)間［fL(xi)，fR(xi)］，i=1，2，…，N;借助最速下降法求解約束邊界:

利用式(4)計算各抗體的約束違背量，判斷是否為可行解。

步4 利用式(2)和(4)，對抗體進行排序，將η%的優(yōu)秀抗體在各自局部小鄰域內(nèi)利用最速下降法進行優(yōu)化，并替代原抗體。

步5 依據(jù)σn，將群體An劃分為劣質(zhì)群B1={x ∈An| fL(x)≥σn}和優(yōu)質(zhì)群B2={x ∈An| fL(x)＜σn}。

步6 對B1中抗體進行多項式變異，獲群體C1;對B2中抗體進行克隆繁殖，并進行柯西變異，獲群體C2。

步7 對C1、C2中的抗體，利用區(qū)間運算規(guī)則，計算其目標(biāo)值區(qū)間;借助最速下降法求解各抗體的約束邊界，進而依據(jù)式(4)，計算抗體的約束違背量。步8 將B2、C2中抗體組合為群體C3，借助抗體間的歐氏距離和抑制半徑將C3劃分為若干子群，進而利用式(2)抽取每個子群中最好抗體與C1組合為群體C，最后依據(jù)式(2)，選擇N 個抗體構(gòu)成群體An+1。

步9 若n ＜Gmax，則進行閾值更新σn+1=min{σn，fR(x)，x ∈C}，并置n=n+1，返回步3;否則，則確定(P4)的有效解集Λ={x ∈An+1| fL(x)≤σn+1}。

步10 對(P4)的每個有效解，利用最速下降法，計算目標(biāo)函數(shù)和約束函數(shù)的上下界，即

步11 依定義2 和Λ，確定(P3)的有效解Γ。

3 數(shù)值試驗

本實驗在Window XP/ CPU/3.30 GHz/RAM/2.98 GB/VC++環(huán)境下進行。將ICIOA 與IP-GA［1］進行比較;最大迭代數(shù)均為200.ICIOA 含有4 個參數(shù):Pm=Pc=0.9，η=20，N=10;IP-GA的參數(shù)設(shè)置由文獻［1］獲知。

考慮以下非線性區(qū)間數(shù)規(guī)劃問題:

這是一個由靜態(tài)約束優(yōu)化問題［14］轉(zhuǎn)化而來的非線性區(qū)間數(shù)規(guī)劃問題。在α=0.0，0.2，…，1.0 不同置信水平下，表1 給出各算法分別獨立運行30 次后，獲得的最好目標(biāo)值區(qū)間、平均運行時間以及目標(biāo)值區(qū)間的中點值統(tǒng)計結(jié)果。表1 ICIOA 與IPGA 執(zhí)行30 次后獲得的統(tǒng)計結(jié)果。

表1 ICIOA 與IP-GA 執(zhí)行30 次后獲得的統(tǒng)計結(jié)果

由表1 可以看出，除α=0.8 外，當(dāng)α 取其它值時，ICIOA 獲得的最好目標(biāo)值區(qū)間均優(yōu)于IP-GA獲得的結(jié)果。當(dāng)α=0.8 時，雖然ICIOA 搜索到的最好目標(biāo)值區(qū)間的寬度略大于IP-GA 的區(qū)間寬度，但依據(jù)區(qū)間序關(guān)系＜CW，ICIOA 獲得的最好解的質(zhì)量優(yōu)于IP-GA 的質(zhì)量。另外，從這兩種算法的目標(biāo)區(qū)間中點值的統(tǒng)計結(jié)果看，ICIOA 的搜索效果優(yōu)于IP-GA 的效果且相對穩(wěn)定。進一步，在給定的每種置信水平下，此兩種算法的平均運行時間表明，IP-GA 求解每種情形的最優(yōu)解，需要的平均運行時間是ICIOA 的2 倍多。因此，盡管IP-GA 是一種結(jié)構(gòu)簡單的小種群主從式進化算法，但它求解約束區(qū)間數(shù)規(guī)劃的計算復(fù)雜度仍然較高。

4 結(jié)論

針對具有主從式結(jié)構(gòu)的優(yōu)化算法求解約束區(qū)間數(shù)規(guī)劃問題存在搜索效率低的缺陷，基于文化基因思想、免疫優(yōu)化和最速下降法，設(shè)計改進型約束免疫優(yōu)化算法;利用免疫優(yōu)化方法執(zhí)行全局搜索，且利用最速下降法對優(yōu)秀抗體進行局部優(yōu)化和求解約束條件的邊界，加快尋優(yōu)的速度。數(shù)值實驗比較結(jié)果顯示:該方法尋優(yōu)效率高，搜索效果好且較為穩(wěn)定，有一定的應(yīng)用潛力。

［1］Jiang Chao，Han Xu，Liu Guirong，et al.A nonlinear interval number programming method for uncertain optimization problems［J］.European Journal of Operational Research，2008，188(1):1－13.

［2］Bhurjee AK，Panda G.Efficient solution of interval optimization problem［J］.Mathematical Methods of Operations Research，2012，76(3):273－288.

［3］Kamakar S，Bhunia AK.An alternative optimization technique for interval objective constrained optimization problems via multiobjective programming［J］.Journal of the Egyptian Mathematical Society，2014，22(2):292－303.

［4］鄭泳凌，馬龍華，錢積新.一類參數(shù)不確定規(guī)劃的三目標(biāo)規(guī)劃解決方法［J］.系統(tǒng)工程理論與實踐，2003，5(5):59－64.

［5］蔣崢，劉斌.自適應(yīng)主從式并行遺傳算法在區(qū)間非線性規(guī)劃問題求解中的應(yīng)用［J］.信息與控制，2006，35(3):314－318.

［6］Jiang Chao，Han Xu，Li Ding.A new interval comparison relation and application in interval number programming for uncertain problems［J］.Computers Materials and Continua，2012，27(3):275－303.

［7］Jiang C，Zhang ZG，Zhang QF，et al.A new nonlinear interval programming method for uncertain problems with dependent interval variables［J］.European Journal of Operational Research，2014，238(1):245－253.

［8］Hladík M.Optimal value bounds in nonlinear programming with interval data［J］.Top，2011，19(1):93－106.

［9］Okada H.Particle swarm optimization with interval-valued genotypes and its application to neuro evolution［J］.World Academy of Science，Engineering and Technology，2013，7(10):627－630.

［10］趙子衡，韓旭，姜潮.基于近似模型的非線性區(qū)間數(shù)優(yōu)化方法及其應(yīng)用［J］.計算力學(xué)學(xué)報，2010，27(3):451－456.

［11］張著洪，陶娟.求解非線性區(qū)間數(shù)規(guī)劃的微免疫優(yōu)化算法研究［J］.計算機研究與發(fā)展，2014，51(12):2633－2643.

［12］Ishibuchi H，Tanaka H.Multiobjective program-ming in optimization of the interval objective function［J］.European Journal of Operational Research，1990，48:219－225.

［13］Moore RE，Cloud MJ，Kearfott RB.Introduction to interval analysis［M］.Philadelphia:Society for Industrial and Applied Mathematics，2009.

［14］王凌.智能優(yōu)化算法及應(yīng)用［M］.北京:清華大學(xué)出版社，2001.