隨機環境下多目標設計優化問題的交互式算法＊

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

（1.中南大學 數學科學與計算技術學院，湖南 長沙 410083；2.中南大學 信息科學與工程學院，湖南 長沙 410083）

實際生產和生活中，許多問題都可以歸結為多目標設計優化問題.以通信網絡為例，不少業務具有多目標性，如時延最少，丟失率最低等.這時，QoS路由選擇問題的數學模型就是多約束條件下多目標參數設計優化問題[1]。在研究這類問題的模型和求解算法時，既要考慮問題中的多目標性，同時還要注意實際環境中存在的不確定性.因此，研究隨機環境下多目標設計優化問題的求解算法在計算機科學與工程、人工智能和管理科學與工程等科學與工程領域具有重要的理論價值和實際指導意義.近期相關研究成果可參看文獻[2－4]及其后所列參考文獻.

最近，文獻[4]研究了如下一類多目標設計優化模型：

其中：w為t維隨機變量，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.采用對目標函數和約束條件求期望的方法，該文得到原問題的如下確定型等價類：

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

1 確定型等價類的推導：方差期望綜合法

首先，針對雙目標問題（1），我們根據決策者對第二目標的期望水平ρ，將原問題轉化為單目標問題：

其次，考慮到期望方法能夠反映最優解的平均水平，方差能夠反映最優解的穩定性，不妨用E（·）表示期望，σ（·）表示方差，參數μ（0＜μ＜1）刻畫平均水平和穩定性的權重，將上述單目標隨機優化問題（3）轉化為如下確定型問題求解：

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

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

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

進一步假設

我們把上述推導多目標隨機優化問題的確定型等價類的方法叫做方差期望綜合法.下面我們將通過設計交互式算法證實：通過這種新的轉化方法在反映決策者喜好的同時，既能夠得到原隨機問題的平均意義上的最優解，又能夠保證解的穩定性好.

2 針對參數ρ，μ的交互式算法設計

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

算法1

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

步2 考慮以下模型：

代入相關數據，得到上述問題的最優解xiμρ，i＝1，2，…，n和目標函數值Fμρ.令Δρh＝Δρh＋0.5，h＝h＋1.

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

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

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

步6 詢問決策者是否想要改變Δμt的大小，若決策者不想改變，則轉步2；若決策者希望將Δμt的取值改變為Δμt′，則令ΔμtΔμt′，轉步2.

步7xiμρ，i＝1，2，…，n和Fμρ即為模型的最優解和相應的目標函數值，算法終止.

3 數值實驗

首先，我們在Lingo9.0環境下執行上一節的交互式算法，以研究參數μ，ρ對最優解的影響.為此，假設

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

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

表1 參數μ，ρ對最優解的影響Tab.1 Effect of the parametersμandρon the optimal solution

表1中，F為相應目標函數的函數值.所得結果充分說明，交互式算法中通過調節參數μ和ρ能夠反映決策者的意愿.

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

表2 樣本及其對應模型的最優解Tab.2 Optimal solutions of models for the samples

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

4 小 結

基于通信網絡設計等實際工程問題常常能歸結為隨機環境下多目標優化問題，研究了一類帶有一個隨機線性和隨機二次目標函數，以及若干隨機線性約束的隨機雙目標優化問題.利用新的方差期望綜合法得到了此類優化問題的確定型等價類，并據此設計了這類問題的基于決策者偏好的交互式算法.數值實驗表明，新方法要優于已有方法，它既能夠反映決策者的滿意度，又能夠得到更穩鍵的最優解.因此，本文得到的研究結果在計算機科學與人工智能和管理科學與工程等科學與工程領域具有方法論意義和實際指導意義.

[1] 周海剛.一種基于多目標優化的QoS路由交互式算法[J].東南大學學報：自然科學版，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，FUENTE 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] 施保昌，陳廷.多目標規劃的一類基于精確罰函數的交互式方法[J].系統科學與數學，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.