随机环境下多目标设计优化问题的交互式算法＊

万 中，郝爱云，孟福真，王雅琳

（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.