多目标优化问题(over)

1、第七章 多目标优化问题的求解优化问题按照目标函数的数量，可以分为单目标优化问题和多目标优化问 题，前面我们讲过的线性优化就是一个单目标优化问题， 对单目标优化问题进一 步突破， 将目标函数扩展为向量函数后， 问题就转化为多目标优化问题。 本节将 简要介绍多目标最优化问题的建模与求解方法。1、多目标优化模型多目标优化问题一般表示为J xs.tm.Gin(x) 0F(x)其中F(x) fi(x), f2(x), fi(x)T ,下面将通过例子演示多目标优化问题的建模。例1设某商店有A,A2,As三种糖果，单价分别为4,2.8和2.4元/kg,现在 要举办一次茶话会，要求买糖果的钱不超过 20 元，

2、但糖果的总重量不少于 6kg， A和A2两种糖果的总重量不低于3kg，应该如何确定最好的买糖方案。分析：首先应该确定目标函数如何选择的问题， 本例中， 好的方案意味着少 花钱多办事， 这应该是对应两个目标函数， 一个是花钱最少， 一个是买的糖果最 重，其他的可以认为是约束条件。当然，这两个目标函数有些矛盾，下面考虑如 何将这个问题用数学描述。设A,A2,Aa三种糖果的购买重量分别为 x.,X2,X3kg，这时两个目标函数分别为花钱： min fi(x) 4xi 2.8x2 2.4x3，糖果总重量： max f2(x)为 X2 X3，如果统一用最小值问题表示，则有约束的多目标优化问题可以表示为m

3、in4x12.8x22.4x3(- x1 x2 x3)4x12.8x22.4x320s.t.x1x2x3x1+x23x1+x23x1, x2, x30模型建立以后，可以考虑用后面的方法进行求解。x1+x232、无约束目标函数的最小二乘求解假设多目标优化问题的目标函数为 F(x) fi(x), f2(x), ,fi(x)T，则可以按 照下面的方式将其转化为单目标问题2 2 2minf1 (x) f2 (x)+ L +fn (x)x s.t. xm x Xm这样就可以用以前的单目标优化的方法直接求解该问题了。此外，Matlab还提供了 lsqnonlin()函数直接求解这类问题，该函数的调用格式为

4、x, nf, fopt,flag,clsqnonlin(F, x°,Xm,XM)其中，F为目标函数写的M函数、匿名函数或inline()函数，该函数为向量函数。X0为初始搜索点。最优化运算完成后，结果将在变量x中返回，最优化的目标函 数向量将在fopt中返回，其范数由nf返回，和其他优化函数一样，选项 OPT有 时候很重要。例2试求解下面无约束非线性多目标优化问题的最小二乘解。(x1min2x2 3x3)si n(x x2)e2.3e X2 x2 cos(4x1 X2)5x303x s.t. 0x05求解 写出向量型的目标函数，则可以调用下面的语句直接求解原问题。Program 1f

5、=(x)(x(1)+2*x (2)+3*x(3)*si n(x(1)+x(2)*exp(-x(1F2-x(3F2)+5*x(3); exp(-x (2) A2-4*x(2)A3)*cos(4*x(1)+x(2);xm=0;0;0;xM=3;pi;5;x=lsq non li n(f,xM,xm,xM)x, nf,fopt,flag,c=ls qnon li n(f,xM,xm,xM)则可以得到更为详细的输出。事实上，如果采用fmin co n()函数，则可以重新定得到x=3.00003.14160.0000，如果最后输出语句修改为义目标函数，调用该函数求解可以直接得到所需结果x x=3.000

6、03.14160.0000，值得注意的是，用后者(fmincon()可以求取含有约束条件的多目标优化最小二乘问题3、多目标问题转化为单目标问题求解多目标最优问题可以转化为单目标的优化问题， 例如对多目标函数进行加权 或最小二乘处理等。接下来对其简单介绍。3.1线性加权变换及求解显然，将多目标优化问题转化为单目标的优化问题的最简单的方法是根据指 标的侧重侧重不同引入加权，使得目标函数改写为标量形式f (x) Wifi(x) W2f2(x)Wnf n(X)其中w1w2wn 1，且 0 w-i, w2, ,wn 1。例3试在不同的加权的系数下，求出例 1的解。C=c;w1,w2,x',f1*

7、x,-f2*xC=c;w1,w2,x',f1*x,-f2*x解原问题可以重新修改为下面的线性优化问题min(w/4, 2.8,2.4)W2(1,1,1)x4x12.8x22.4X3 20s.t.X1X2X3x1 +x23C=c;w1,w2,x',f1*x,-f2*xX1, X2,氏 0程序如下:Program 2f1=4,2.8,2.4;f2=-1,-1,-1;Aeq=;beq=;xm=0;0;0;c=;A=4,2.8,2.4;-1,-1,-1;-1,-1,0;B=20;-6;-3;ww1=0:0.1:1;for w1=ww1,w2=1-w1;x=li nprog(w1*f1+

8、w2*f2,A,B,Aeq,beq,xm);end求解结果如下表1.C=c;w1,w2,x',f1*x,-f2*x表1不同加权系数下的最优方案w1w2x1x2x3总花费总重量016.3E-1334.8207.80.10.98.7E-1334.8207.80.20.81.2E-1134.8207.80.30.73.7E-153315.660.40.61.2E-093315.660.50.52.5E-093315.660.60.41.0E-123315.660.70.32.3E-113315.660.80.21.3E-113315.660.90.11.0E-123315.66102.7E-

9、113315.663.2线性优化问题的最佳妥协解考虑一类特殊的线性优化问题JmaxCxAxBx s.t.A eqXBeqXmX Xm和传统的线性优化问题不同，这里的目标函数不是一个向量，而是一个矩阵。每 一个目标函数f/x) qx, i 1,2, ,n，可以理解成第i个利益分配，所以这样的 最优问题可以认为是各方面利益的最大化分配，当然，在约束条件的限制和相互 制约下，不可能每一方的利益均能真正地最大化，这就需要各方面做出适当的妥协，得出唯一的最佳妥协解，最佳妥协解的求解步骤如下：(1)单独求解每一个单目标函数的最优化问题，得出最优解f, i 1, ,n。(2)通过规范化构造单独的目标函数f(

10、x)11CiXC2Xf1f2(3)最佳妥协解可以变换成下面的单目标线性优化问题的直接解J min f (x)Ax Bx s.t.AeqXBeqXmx Xm根据上述算法，可以编写出一个最佳妥协解的求解程序。 注意，该函数求解的是最大值问题的妥协解。Program 3function x,f,flag,cc=linprog_c(C,A,B,Aeq,Beq,xm,xM) n ,m=size(C);c=0;for i=1:nx,f=li nprog(C(i,:),A,B,Aeq,Beq,xm,xM); c=c-C(i,:)/f;end x,f,flag,cc=li nprog (c,A,B,Aeq,B

11、eq,xm,xM);例4试求出例1中的最佳妥协解解 由下面的语句可以立即得到最佳妥协解Program 4clcC=-4 -2.8 -2.4;1 1 1;A=4 2.8 2.4;-1 -1 -1;-1,-1,0;B=20;-6;-3;Aeq=;Beq=;xm=0;0;0;xM=;x,f,flag,cc=li nprog_c(C,A,B,Aeq,Beq,xm,xM)C*x最后的结果为x=0; 3; 4.833，总花费为20元，购买的糖果的总重量为 7.833kg,例5试求下面多目标优化问题的最佳妥协解3为 x2 6x4min10x2 7x42x1 x2 8X3X13x3 2x42x1 4x2 X4

12、1005x3 3x4180x s.t.捲 X2 6X3 5x4250利用上面的linprog_c()函数，可以编写M文件Program 5clcC=-3 1 0 6;0 10 0 7;2 1 8 0;1 1 3 2;A=2 4 0 1;0 0 -5 -3;1 1 6 5;B=110;-180;250;Aeq=;Beq=;xm=zeros(4,1);xM=;x,f,flag,cc=li nprog_c(C,A,B,Aeq,Beq,xm,xM)C*x求得的最佳妥协解为x =0.0000, 26.0870,32.6087,5.6522,各方妥协的目标函数值为60.0000,300.4348,286.

13、9565,135.2174。3.3线性优化的最小二乘解考虑下面多目标优化问题的的最小二乘表示min1 22|Cx-d|2Ax Bx s.t.AeqXBeqXmx Xm则最小二乘解可以由函数直接给出。例6考虑例5中的多目标优化问题，试求出最小二乘解。由于很容易得到C矩阵，并且写出其他约束条件，这样调用lsqlin()函数,就可以求解类似的问题。调用程序如下。Program 6clcC=3 1 0 6;0 100 7;2 1 8 0;1 1 3 2; d=zeros(4,1);A=2 4 0 1;0 0 -5 -3;1 1 6 5;B=110;-180;250;Aeq=; Beq=; xm=zer

14、os(4,1); xM=; x=lsqli n( C,d,A,B,Aeq,Beq,xm,xM)C*x求得结果为： x =0.0000, 0.0000, 28.4456, 12.5907，各方的目标函数为 75.5440， 88.1347，227.5648，110.5181，从结果中，我们可以看得，同是一个 问题，利用线性优化的最小二乘解求得的结果与妥协解的不同， 主要是由于求解 方法和目标函数发生了变换， 即求解方法的设计的不同， 目标函数也在不同的方 法下发生了改变。4、极小极大问题的求解多目标优化的一类重要的问题是极小极大问题，假设某一组p 个目标函数fi(x), i 1,2, , p，它

15、们中的每一个均可以提取出一个最大值max £(x)，而x s.t. G( x) 0这样得出的一组最大值仍然是关于 x的函数，现在想对这些最大值进行最小化搜 索，即minmaxx s.t . G ( x )fi(x)则这类问题成为极小极大问题， 话句话说， 极小极大问题是在最不利的条件下寻 求最有利决策方案的一种方法。考虑各类约束条件，极小极大问题可以更一般地写为Jmin max fi( x)Ax BAeq x Beqx s.t.xm x xMC(x) 0Ceq( x) 0Matlab 最优工具箱中的 fminimax() 函数，可以直接求解极小极大问题， 该函 数的调用格式为x, f

16、opt,flag,cfminimax(F, x0,A,B,Aeq,Beq,xm,xM,CF,OPT, p1, p2, )在调用的时候，目标函数为向量形式，当然，用匿名函数、inline()函数、M-函数都是可以的。例 7 求解下面的极小极大问题2为 sin x2 x2 3x1x2 cosx1min max2 x 2 xXi ex?eX1X2COSNX2022X X2 COS X X2x s.t4.3 x-i 3.8x2 4.9XiX2300解上述的最优化问题可以通过下面的语句直接求解，并选择随机数作为初始值，程序为Program 7f=(x)x(1F2*si n(x(2)+x (2)-3*x (1)*x(2)*cos(x(1);-x(1F2*exp(-x(2)+x(2)A2*exp(-x(1)+x (1)*x(2)*cos(x(1)*x