萬 中，郝愛云，孟福真，王雅琳

（1.中南大學(xué) 數(shù)學(xué)科學(xué)與計(jì)算技術(shù)學(xué)院，湖南 長沙 410083；2.中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410083）

實(shí)際生產(chǎn)和生活中，許多問題都可以歸結(jié)為多目標(biāo)設(shè)計(jì)優(yōu)化問題.以通信網(wǎng)絡(luò)為例，不少業(yè)務(wù)具有多目標(biāo)性，如時(shí)延最少，丟失率最低等.這時(shí)，QoS路由選擇問題的數(shù)學(xué)模型就是多約束條件下多目標(biāo)參數(shù)設(shè)計(jì)優(yōu)化問題[1]。在研究這類問題的模型和求解算法時(shí)，既要考慮問題中的多目標(biāo)性，同時(shí)還要注意實(shí)際環(huán)境中存在的不確定性.因此，研究隨機(jī)環(huán)境下多目標(biāo)設(shè)計(jì)優(yōu)化問題的求解算法在計(jì)算機(jī)科學(xué)與工程、人工智能和管理科學(xué)與工程等科學(xué)與工程領(lǐng)域具有重要的理論價(jià)值和實(shí)際指導(dǎo)意義.近期相關(guān)研究成果可參看文獻(xiàn)[2－4]及其后所列參考文獻(xiàn).

最近，文獻(xiàn)[4]研究了如下一類多目標(biāo)設(shè)計(jì)優(yōu)化模型：

其中：w為t維隨機(jī)變量，C（w）＝（ci（w））T，i＝1，2，…，n，D（w）＝（dij（w））n×n，A（w）＝（aij（w））m×n，b（w）＝（bi（w））T，i＝1，2，…，m.采用對目標(biāo)函數(shù)和約束條件求期望的方法，該文得到原問題的如下確定型等價(jià)類：

上述期望值方法雖然被看成處理隨機(jī)優(yōu)化問題的一種最基本和最重要的方法，但由于該方法得到的最優(yōu)解只能是平均意義上的最優(yōu)，一般不能保證解的穩(wěn)定.鑒此，本文提出方差期望綜合法，目的在于保證解的均值達(dá)到最優(yōu)的同時(shí)，也保證最優(yōu)解的穩(wěn)定性.此外，本文還將研究求解這類問題的實(shí)用的交互式算法，以使最優(yōu)解既能夠反映決策者的滿意度，又能夠更穩(wěn)健.數(shù)值實(shí)驗(yàn)驗(yàn)證這些方法切實(shí)有效.

1 確定型等價(jià)類的推導(dǎo)：方差期望綜合法

首先，針對雙目標(biāo)問題（1），我們根據(jù)決策者對第二目標(biāo)的期望水平ρ，將原問題轉(zhuǎn)化為單目標(biāo)問題：

其次，考慮到期望方法能夠反映最優(yōu)解的平均水平，方差能夠反映最優(yōu)解的穩(wěn)定性，不妨用E（·）表示期望，σ（·）表示方差，參數(shù)μ（0＜μ＜1）刻畫平均水平和穩(wěn)定性的權(quán)重，將上述單目標(biāo)隨機(jī)優(yōu)化問題（3）轉(zhuǎn)化為如下確定型問題求解：

令Q表示隨機(jī)矩陣D（w）＝（dij（w））n×n的期望矩陣，R表示該矩陣的方差矩陣，即

這樣，模型（4）就可以寫成：

其中，x2＝ （x21，x22，…，x2n）T.

進(jìn)一步假設(shè)

我們把上述推導(dǎo)多目標(biāo)隨機(jī)優(yōu)化問題的確定型等價(jià)類的方法叫做方差期望綜合法.下面我們將通過設(shè)計(jì)交互式算法證實(shí)：通過這種新的轉(zhuǎn)化方法在反映決策者喜好的同時(shí)，既能夠得到原隨機(jī)問題的平均意義上的最優(yōu)解，又能夠保證解的穩(wěn)定性好.

2 針對參數(shù)ρ，μ的交互式算法設(shè)計(jì)

在使用方差期望綜合法轉(zhuǎn)化模型時(shí)，我們引入了兩個(gè)參數(shù)ρ和μ，這兩個(gè)參數(shù)的取值均由決策者根據(jù)其意愿給出，ρ和μ的取值將直接影響到該模型的最優(yōu)解.本文參考文獻(xiàn)[5－8]，在文獻(xiàn)[4]的基礎(chǔ)上，針對上述兩個(gè)參數(shù)（[4]中只有參數(shù)ρ）設(shè)計(jì)一種新的交互式算法.該種算法隨時(shí)考慮進(jìn)決策者的意愿，能夠得到使決策者滿意的最優(yōu)解.該算法的計(jì)算步驟如下.

算法1

步1 假設(shè)參數(shù)μ和ρ的取值是連續(xù)的，且0＜μ＜1，ρmin≤ρ≤ρmax.其中，ρmin和ρmax是決策者給出的ρ的最小取值和最大取值.令μ和ρ分別以Δμ，Δρ的幅度變化，同時(shí)引入計(jì)數(shù)變量t，h.令t＝0，h＝0，Δμt＝0，Δρh＝0，μ0＝0.05.

步2 考慮以下模型：

代入相關(guān)數(shù)據(jù)，得到上述問題的最優(yōu)解xiμρ，i＝1，2，…，n和目標(biāo)函數(shù)值Fμρ.令Δρh＝Δρh＋0.5，h＝h＋1.

步3 若（ρmin＋Δρh）＞ρmax，則轉(zhuǎn)步5；否則，轉(zhuǎn)步4.

步4 詢問決策者對上一步所得的解xiμρ，i＝1，2，…，n和Fμρ是否滿意，如果決策者對該解滿意，則轉(zhuǎn)步7；如果決策者對該解不滿意，則問決策者是否想要改變Δρh的大小，若決策者不想改變，則轉(zhuǎn)步2；若決策者希望將Δρh的取值改變?yōu)棣う裩′，則我們令Δρh＝Δρh′，轉(zhuǎn)步2.

步5 令Δμt＝Δμt＋0.05，t＝t＋1，Δρh＝0.若μ0＋Δμt≥1，轉(zhuǎn)步7；否則，轉(zhuǎn)步6.

步6 詢問決策者是否想要改變Δμt的大小，若決策者不想改變，則轉(zhuǎn)步2；若決策者希望將Δμt的取值改變?yōu)棣う蘴′，則令ΔμtΔμt′，轉(zhuǎn)步2.

步7xiμρ，i＝1，2，…，n和Fμρ即為模型的最優(yōu)解和相應(yīng)的目標(biāo)函數(shù)值，算法終止.

3 數(shù)值實(shí)驗(yàn)

首先，我們在Lingo9.0環(huán)境下執(zhí)行上一節(jié)的交互式算法，以研究參數(shù)μ，ρ對最優(yōu)解的影響.為此，假設(shè)

則D（w）的期望和方差分別為

將以上數(shù)據(jù)代入模型（2）可得到使用期望方法求解模型的最優(yōu)解為：x1＝（2.52，0，0，0）T.將數(shù)據(jù)代入模型（6），得到使用方差期望綜合法求解模型的最優(yōu)解為x2＝（1.855，0.065，0.034，0.422）T，目標(biāo)函數(shù)值為551.76.改變μ，ρ的取值，如μ＝0.7，ρ＝45，則 得 到 新 的 最 優(yōu) 解x3＝ （1.97，0，0.131，0.453）T，目標(biāo)函數(shù)值為548.44.執(zhí)行算法1，表1反映了參數(shù)μ，ρ對最優(yōu)解的影響.

表1 參數(shù)μ，ρ對最優(yōu)解的影響Tab.1 Effect of the parametersμandρon the optimal solution

表1中，F(xiàn)為相應(yīng)目標(biāo)函數(shù)的函數(shù)值.所得結(jié)果充分說明，交互式算法中通過調(diào)節(jié)參數(shù)μ和ρ能夠反映決策者的意愿.

接下來，我們比較文獻(xiàn)[4]中的期望方法與方差期望綜合法的優(yōu)劣.比較方法是用數(shù)值模擬的方法產(chǎn)生所有隨機(jī)參數(shù)的48個(gè)樣本值，并分別求解相應(yīng)的優(yōu)化問題（3）（我們稱之為樣本優(yōu)化問題），得到48個(gè)最優(yōu)解.然后考察這48個(gè)最優(yōu)解與期望方法和方差期望綜合法得到的最優(yōu)解之間的關(guān)系.一是考察樣本最優(yōu)解的均值是否等于期望方法和方差期望綜合法得到的最優(yōu)解；二是考察樣本最優(yōu)解均值離期望方法和方差期望綜合法得到的最優(yōu)解的距離哪一個(gè)更近.樣本優(yōu)化問題的解見表2.

表2 樣本及其對應(yīng)模型的最優(yōu)解Tab.2 Optimal solutions of models for the samples

由表2知，樣本最優(yōu)解的均值為：x0＝（1.317，0.341，0.142，0.342）T.定義兩點(diǎn)（x1，x2，x3，x4）和（y1，y2，y3，y4）之間的距離為：d＝｜x1－y1｜＋｜x2－y2｜＋｜x3－y3｜＋｜x4－y4｜，則樣本最優(yōu)解均值與期望方法得到的最優(yōu)解之間的距離dx0，x1＝2.028，與方差期望綜合法得到的最優(yōu)解之間的距離dx0，x2＝1.002.可見由樣本得到的最優(yōu)解離方差期望綜合法得到的最優(yōu)解更近一些.這表明，使用方差期望綜合法得到的最優(yōu)解穩(wěn)定性更好.

4 小 結(jié)

基于通信網(wǎng)絡(luò)設(shè)計(jì)等實(shí)際工程問題常常能歸結(jié)為隨機(jī)環(huán)境下多目標(biāo)優(yōu)化問題，研究了一類帶有一個(gè)隨機(jī)線性和隨機(jī)二次目標(biāo)函數(shù)，以及若干隨機(jī)線性約束的隨機(jī)雙目標(biāo)優(yōu)化問題.利用新的方差期望綜合法得到了此類優(yōu)化問題的確定型等價(jià)類，并據(jù)此設(shè)計(jì)了這類問題的基于決策者偏好的交互式算法.數(shù)值實(shí)驗(yàn)表明，新方法要優(yōu)于已有方法，它既能夠反映決策者的滿意度，又能夠得到更穩(wěn)鍵的最優(yōu)解.因此，本文得到的研究結(jié)果在計(jì)算機(jī)科學(xué)與人工智能和管理科學(xué)與工程等科學(xué)與工程領(lǐng)域具有方法論意義和實(shí)際指導(dǎo)意義.

[1] 周海剛.一種基于多目標(biāo)優(yōu)化的QoS路由交互式算法[J].東南大學(xué)學(xué)報(bào)：自然科學(xué)版，2003，33（3）：275－279.ZHOU Hai－gang.An interactive multi－objective optimization QoS routing algorithm[J].Journal of Southeast University：Natural Sciences，2003，33（3）：275－279.（In Chinese）

[2] KOFJAC D，KLJAJIC M.The anticipative concept in warehouse optimization using simulation in an uncertain environment[J].European Journal of Operational Research，2009，193：660－669.

[3] PARDO M J，F(xiàn)UENTE D de la.Design of a fuzzy finite capacity queuing model based on the degree of customer satisfaction：analysis and fuzzy optimization[J].Fuzzy Sets and Systems，2008，159：3313－3332.

[4] XU Jiu－ping，LI Jun.A class of stochastic optimization problems with one quadratic several linear objective functions and extended portfolio section model[J].Journal of Computational and Applied Mathematics，2002，146：99－113.

[5] WANG Ling，ZHANG Liang.Stochastic optimization using simulated annealing with hypothesis test[J].Applied Mathematics and Computation，2006，174：1329－1342.

[6] 施保昌，陳廷.多目標(biāo)規(guī)劃的一類基于精確罰函數(shù)的交互式方法[J].系統(tǒng)科學(xué)與數(shù)學(xué)，1999，1：106－110.SHI Bao－chang，CHEN Ting.An interactive algorithm for multi－objective problems based on a class of exact penalty function[J].System Science and Mathematics，1999，1：106－110.（In Chinese）

[7] ALREFAEI M H，ALAWNEH A J.Solution quality of random search methods for discrete stochastic optimization [J].Mathematics and Computers in Simulation，2005，68：115－125.

[8] KORHONEN P，LAASKO J.A visual interactive method for solving the multiple criteria problem [J].European Journal of Operational Research，1986，24：277－287.

[9] RHODE R，WEBER R.Multiple objective quadratic－linear programming[C]／／BRANS J P （Ed）.Operational Research，North－Holland，Amesterdam，IFOR，1981：405－420.