笔记多目标规划

1、处理多目标规划的方法1.约束法1.1原理约束法又称主要目标法，它根据问题的实际情况确定一个目标为主要目标，而把其余目标作为次要目标，并根据决策者的经验给次要的目标选取一定的界限值，这样就可以把次要目标作为约束来处理，从而就将原有多目标规划问题转化为一个在新的约束下，求主要目标的单目标最优化问题。假设在p个目标中，为主要目标，而对应于其余（p-1）个目标函数均可以确定其允许的边界值：。这样我们就可以将这个目标函数当做最优化问题的约束来处理，于是多目标规划问题转化称为单目标规划问题SP问题：公式1上述问题的可行域为2.评价函数法其基本思想就是将多目标规划问题转化为一个单目标规划问题来求解，而且该单

2、目标规划问题的目标函数是用多目标问题的各个目标函数构造出来的，称为评价函数，例如若原多目标规划问题的目标函数为F(x)，则我们可以通过各种不同的方式构造评价函数h(F(x)，然后求解如下问题：求解上述问题之后，可以用上述问题的最优解x*作为多目标规划问题的最优解，正是由于可以用不同的方法来构造评价函数，因此有各种不同的评价函数方法，下面介绍几种常用的方法。评价函数法中主要有：理想点法、平方和加权法、线性加权和法、乘除法、最大最小法2.1理想点法考虑多目标规划问题：，首先分别求解p个单目标规划问题：令各个问题的最优解为，而其目标函数值可以表示为：其中：一般来说，不可能所有的均相同，故其最优值组成

3、的向量并不属于多目标规划的象集，所以是一个几乎不可能达到理想点。那么，理想点法就是在多目标规划的可行域R中找到一点X*，使其对应的与理想点最为接近，即当已知理想点时，在目标空间中适当引进某种度量标准来确定和之间的距离，并在这个度量标准的意义下，使得多目标规划问题集合R上某点的目标函数与理想点之间的“距离”尽可能小。而距离的度量可以利用向量的某种模，当我们给模赋予不同的意义是，便可以得到不同的理想点法。下面我们给出最短距离理想点法，这种方法是将取为中的的形式，即构造如下的单目标规划问题：公式1&&这里的评价函数是到的距离。当然我们也可以采用其他评价函数的方式，例如更一般的将(8-

4、7)进行推广，得到评价函数为：公式2或者是如下形式：公式32.2基于加权的方法如果p个非负实数满足其和为1，则称为一组权向量，或者将称为一组权系数。若所有权系数，则称这组权系数为正权，正权的全体可以记为：；若所有权系数，则称这组权系数为非负权，非负权的全体可以记为：上述对权向量和权系数的定义适用于下面所介绍的各种加权和的方法。先求出各个单目标规划问题的一个尽可能好的下界，即满足：然后构造评价函数：一般情况下，权系数的值由各目标函数的重要程度给出。2.3.1平方和加权法平方和加权法是求解如下单目标规划问题：公式1将其最优解作为多目标规划的解。2.3.2线性加权和法线性加权和法是一种最常用的方法，

5、而且在理论上有重要意义，该方法是按照p个目标的重要程度，分别乘以一组权系数，然后相加作为目标函数，再对此目标函数在多目标规划问题的约束集合R上求最优解，即构造如下单目标规划问题：公式1求此单目标规划问题的最优解，并把它叫做多目标规划问题在线性加权意义下的最优解，且该问题中的或者，设p=2，则多目标规划问题具有两个目标函数，取如图所示，目标函数的等值线是一条直线。求的过程就是在中找一点，使得取最小值，从图上可以看出，是目标函数的等值线与在左下角的切点，即的有效点。对应于，存在使得，则为多目标规划问题的有效解。当时，可能是弱有效解。加权因子wi确定的方法:(1).将各分目标转化后加权 为消除各分目

6、标在量级上的差别，先将分目标函数fi(x)转化为无量纲等量级目标函数再组成统一目标函数:wi按各分目标的重要程度来决定如各分目标有相同的重要性，则取wi =1 (i=1,2,l) 称为均匀计权，否则取各分目标不同的加权因子，取将fi(x)转换为无量纲的等量级目标函数的方法 :设各分目标函数值的变动范围为：即将各单目标函数的最优值的倒数作为权系数，它反映了各单目标函数离开各自最优值的程度。另外相当于各分目标函数进行了无量纲的处理，而消除了各分目标在数量级上的差别。(2) 直接加权法将加权因子分成两部分: wi=w1i·w2i (i=1,2,l)其中，w1i本征权因子，反映各分目标的重要

7、程度w2i校正权因子，调整各分目标间量级差别的影响一般取：一个分目标函数fi(x)变化越快，的值越大，加权因子w2i愈小，反之，亦然。这样可调整不同的目标函数值同步下降。 2.4乘除法（存疑：乘除法原理即乘幂指数有变化，1或-1，为何不是2或-2？按照重要性幂指数应变大！）假如我们的目标可以分为两组：一组要求的值越小越好；另一组要求越大越好。而且对于任意的，均满足函数值非负的条件，此时可以令： (8-12)这样就可以把多目标规划问题统一为：乘除法的原理就是构造如下目标函数：公式1则多目标规划问题已经转化为单目标规划问题。在乘除法中我们是把求最大的目标作为分母，把求最小的目标作为分子，如此化为单

8、目标问题后再求最小。2.5最大最小法X = FMINIMAX(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)在对策论中，人们经常遇到这样的问题：在最不利的条件下如何寻求最有利的策略。因此，求解极小化的多目标规划，也就是要在R中求出各个目标函数的最大值中的最小值。这就是极大极小法的基本思想。基于上述基本思想，极大极小法是构造评价函数：，从而求解下述单目标规划问题P的最优解：，有时也给每个配上权系数，即考虑如下问题：，其中或者。当时极大极小法的几何意义如图所示，x是在R中的极小点。2.6结论（看不懂。，。）以上我们借助于不同形式的评价函数将多目标规划问题转化为单

9、目标规划问题。现在我们将要讨论：上述问题的最优解在什么条件之下才是多目标规划问题的的有效解或弱有效解。为此，给出两个定义：如果对于，当满足时均满足，则称为F的严格单调增函数。如果对于，当满足时均满足，则称为的单调增函数。在上述定义下，转化后的单目标规划问题是多目标规划问题的有效解或者弱有效解的条件由下面两个定理描述：若是的严格单调增函数，则转化后的单目标规划问题的最优解是多目标规划问题的有效解。若是的单调增函数，则转化后的单目标规划问题的最优解是多目标规划问题的弱有效解。可以证明，评价函数法中所给的评价函数都是严格单调增函数或单调增函数，因而其最优解是多目标规划问题的有效解或弱有效解。3.功效

10、系数法我们知道，多目标规划的任意一个可行解，对每个目标的相应值是有好有坏的。一个对某个的相应值的好坏程度，称为X对的功效。为了便于对每个比较它对某个的功效大小，可将以作一个函数变换，即令：。并规定：对产生功效最好的X，评分为；功效最坏的X，评分为；对不是最好也不是最坏的中间状态，评分为。换句话说，我们用一个值在0与1之间的功效函数来反映的好坏。下面介绍最常用的两种评分方法：线性型和指数型。3.1线性功效系数法这种方法是用功效最好与最坏的两点之间的直线来反映功效程度的，考虑如下的多目标规划问题：求出的最大值和最小值：(1) 由于当时，要求越小越好，故可取：公式1其中式选取作为函数值，主要是因为过

11、两点和可作一条直线，其方程为：由上式得：，的图形见图所示。显然，越靠近的功效越好，越靠近的功效越坏，所以便可以反映诸越小越好。(2) 对于当时，要求越大越好，故可取：公式2其中式选取作为函数值，主要是因为过两点和可作一条直线，其方程为：于是可得：，的图形见图所示。由(1)(2)可知，对所有的均给出了相应的功效系数，用(1)(2)所推导出的的公式中，当诸时便可以同时保证前k个目标越小越好，而后个目标越大越好。为了求解一个实际问题，我们不会寻求目标函数功效最坏的解，即我们不会求使得的解，因此我们不妨假设，对于，我们作其几何平均数：公式3称为功效函数，并以单目标规划的最优解作为多目标规划的解：对于上

12、述解法我们有如下定理：设对于若是式(8-24)的最优解，则必为多目标规划问题的有效解。3.2指数功效系数法线性型功效系数法实际上是把功效系数取作线性函数，当我们把功效系数取作指数函数时，便得到指数型功效系数法。由于指数函数的几何特征与直线不同，因为指数函数最大值的，而是趋近于0，故无法象线性功效系数法那样利用的最小值和最大值来定义，而是利用估计出的的不合格值（或者称为不满意值）和勉强合格值（或称最低满意值）来定义。(1) 对于越大越好的，考虑如下的指数型功效系数：公式1其中以及为待定的常数，其图形如图所示可见，是的严格单调增函数，而且当充分大时，。为了确定和，规定：，可以得到：(8-26)由此

13、可得：，故从而有：公式1(2) 对于越小越好的，可以类似的求得：公式2这时，的图形如图所示，图中，是的严格单调减函数，而且当充分小时，类似线性功效系数法，在得到了各功效系数之后，我们构造单目标规划问题：公式3同样可以证明，最优解为多目标规划问题的有效解。最后指出功效系数法显然也适用于统一的极小化模型，只需要在相应的评价函数中取即可。多目标规划的MATLAB求解由于多目标规划中的求解涉及到的方法非常多，故在MATLAB中可以利用不同的函数进行求解，例如：1.在评价函数法中我们所得最后的评价函数为一线性函数，且约束条件也为线性函数，则我们可以利用MATLAB优化工具箱中提供的linprog函数进行

14、求解；2.如果我们得到的评价函数为非线性函数，则可以利用MATLAB优化工具箱中提供的fmincon函数进行求解；FMINCON finds a constrained minimum of a function of several variables. FMINCON attempts to solve problems of the form: min F(X) subject to: A*X <= B, Aeq*X = Beq (linear constraints) X C(X) <= 0, Ceq(X) = 0 (nonlinear constraints) LB &l

15、t;= X <= UB (bounds) X = FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB) defines a set of lower and upper bounds on the design variables, X, so that a solution is found in the range LB <= X <= UB. Use empty matrices for LB and UB if no bounds exist. Set LB(i) = -Inf if X(i) is unbounded below; set UB(i)

16、= Inf if X(i) is unbounded above. X = FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON) subjects the minimization to the constraints defined in NONLCON. The function NONLCON accepts X and returns the vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. FMINCON minimizes FU

17、N such that C(X) <= 0 and Ceq(X) = 0. (Set LB = and/or UB = if no bounds exist.) X = FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) minimizes with the default optimization parameters replaced by values in the structure OPTIONS, an argument created with the OPTIMSET function. See OPTIMSET for d

18、etails. For a list of options accepted by FMINCON refer to the documentation. 3.如果我们采用最大最小法进行求解，则可以利用MATLAB优化工具箱中提供的fminimax函数进行求解。下面我们就结合前面各小节中所分析的几种方法，讲解一下典型多目标规划问题的MATLAB求解方法。1.例 利用理想点法求解我们首先根据评价函数法中的理想点法的理论基础，按照理想点法的求解思路分别对两个单目标规划问题进行求解： 求解该线性规划的MATLAB的代码和相应的运行结果为：c=2;-3;A=3 2;1 1;b=12;8lb=0;0x,

19、fval=linprog(c,A,b,lb,)Optimization terminated.x = 0.0000 6.0000fval = -18.0000于是可知。当时，单目标线性规划的最优函数值为。c=-5;-3;A=3 2;1 1;b=12;8lb=0;0x,fval=linprog(c,A,b,lb,)Optimization terminated.x = 4.0000 0.0000fval =-20.0000于是可知，当时，单目标线性规划的最优函数值为。由上述两个单目标线性规划的求解结果可知，因而是一个不可能达到的理想点，因而我们构造如下评价函数：评价函数：构造描述该评价函数的M-

20、函数文件objfun.m如下：function f=objfun(x)f=sqrt(2*x(1)-3*x(2)+18)2+(5*x(1)+3*x(2)-20)2);然后用非线性规划的方式求解上述问题的代码为：A=3 2;1 1;b=12;8;lb=0;0;x0=0;0;x,fval,exitflag=fmincon(objfun,x0,A,b,lb,)由运行结果可知在该评价函数标准之下，问题的最优解为：此时，各目标函数的取值为：。它与理想点在评价函数标准下的最小距离为1.9941。2.例 利用评价函数中的线性加权和法求解如下多目标规划问题：其中权系数为建立线性加权和法的评价函数为：将相应的权系

21、数代入上式即整理出目标函数为：于是建立目标函数的M-函数文件objfun.m：function f=objfun(x)f=x(1)2+1.2*x(2)2+1.4*x(3)2;由于目标函数非线性函数且具有线性等式约束和边界约束，因而我们调用MATLAB中求解非线性规划的fmincon函数对此问题进行求解，同时注意如果只考虑第一个目标函数，由这种特殊形式，即在设计变量的和为一定值，需要求其平方和的最小值时，最优解必然是当这几个设计变量的值相等时取得，于是我们可以将这个解设为问题的初始点，开始迭代，故求解该问题的代码为：Aeq=1 1 1;beq=3;lb=0;0;0;x0=1;1;1;x,fval

22、=fmincon(objfun,x0,Aeq,beq,lb,)结果说明，问题的最优解为：我们在求解多目标规划问题时，可以采用评价函数法中的最大最小法，而MATLAB也为这种方法提供了专门的求解函数fminimax，在讲解这方面的例题之前，我们首先介绍一下MATLAB优化工具箱中所提供的最大最小法的求解函数fminimax。最大最小法问题的MATLAB标准形式为：函数fminimax的调用方式和其他的最优化函数类似，其中所涉及的输入参数和输出参数的含义与非线性规划的求解函数fmincon类似，使用方法也基本相同，细节问题读者可以参考MATLAB的帮助文件。3.例 求解最大最小问题：首先建立描述目

23、标函数的M-函数文件objfun.m，注意到一共有五个目标函数，所求目标为这五个函数最大值中的最小值，代码如下：function f = objfun(x)f(1)= 2*x(1)2+x(2)2-48*x(1)-40*x(2)+304; f(2)= -x(1)2 - 3*x(2)2;f(3)= x(1) + 3*x(2) -18;f(4)= -x(1)- x(2);f(5)= x(1) + x(2) - 8;然后设置求解的初始点为x0=0;0，调用fminimax求解该问题的代码为：x0 = 0; 0;x,fval,maxfval = fminimax(objfun,x0)运行结果为：Loca

24、l minimum possible. Constraints satisfied.fminimax stopped because the predicted change in the objective functionis less than the default value of the function tolerance and constraints were satisfied to within the default value of the constraint tolerance.<stopping criteria details>Active ine

25、qualities (to within options.TolCon = 1e-006): lower upper ineqlin ineqnonlin 1 5x = 4.0000 4.0000fval = 0.0000 -64.0006 -1.9999 -8.0000 -0.0000maxfval = 2.6897e-008上述结果说明当时，目标函数的最大值达到最小，这一组的函数值为0.0000，-64.0006，-1.9999，-8.0000，-0.0000，于是最大值为0。4.例 利用最大最小法求解根据最大最小法评价函数的建立方法：仍然选择与上例相同的权值，故可知最大最小法的两个目标函

26、数为：于是我们在MATLAB中建立描述目标函数的M-函数文件objfun.m如下：function f=objfun(x)f(1)=0.8*(x(1)2+x(2)2+x(3)2);f(2)=0.2*(x(1)2+2*x(2)2+3*x(3)2);之后调用fminimax函数进行求解，同样设置初始点为1;1;1，代码为：Aeq=1 1 1;beq=3;lb=0;0;0;x0=1;1;1;x,fval=fminimax(objfun,x0,Aeq,beq,lb,)运行结果为：Local minimum possible. Constraints satisfied.fminimax stopped

27、 because the size of the current search direction is less thantwice the default value of the step size tolerance and constraints were satisfied to within the default value of the constraint tolerance.<stopping criteria details>Active inequalities (to within options.TolCon = 1e-006): lower uppe

28、r ineqlin ineqnonlin 1x = 1.0000 1.0000 1.0000fval = 2.4000 1.2000上述结果说明该问题的最优解为：，可见最大最小法与前面的线性加权和法所求得的结果不同，这主要是因为所采取的评价标准不同，即评价函数形式的不同，在实际应用中，我们应当按照实际的需求采用合适的评价函数，这样才能取得较为可行的结果。线性目标规划的MATLAB求解6212263700005128766MATLAB优化工具箱中提供了求解多目标规划问题的函数fgoalattain，针对本节中的线性目标规划问题，可以利用该函数进行求解。同时我们还可以将线性目标规划问题推广至一般的

29、多目标规划问题，调用此函数进行求解。MATLAB所定义的多目标规划的标准形式为：其中、为相应维数的向量，、为矩阵，、为返回向量的函数，它们可以是线性函数，也可以是非线性函数。1.函数fgoalattain的调用格式x = fgoalattain(fun,x0,goal,weight)x = fgoalattain(fun,x0,goal,weight,A,b)x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)x = fgoalattain(fun

30、,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,. options)x = fgoalattain(problem)x,fval = fgoalattain(.)x,fval,attainfactor = fgoalattain(.) x,fval,attainfactor,exitflag = fgoalattain(.)x,fval,attainfactor,exitflag,output = fgoalattain(.)x,fva

31、l,attainfactor,exitflag,output,lambda = fgoalattain(.)2.输入参数 在函数fgoalattain的输入参数中，fun为目标函数，x0是求解的初始值，goal是目标函数的期望值，nonlcon是非线性约束函数，weight是目标权重。下面对这些参数作一个介绍。fun输入参数之一fun为需要最小化的目标函数，在fun函数中需要输入设计变量x，为一个列向量，结果返回x处的目标函数值。fun可以是一个在M函数中定义的函数句柄，例如：x = fgoalattain(myfun,x0,goal,weight)M-函数文件myfun.m必须有下面的形式：

32、function f = myfun(x)f = . % 目标函数.fun还可以是匿名函数句柄和字符串，例如：x = fgoalattain(x)sin(x.*x),x0,goal,weight);如果用户定的x和f为矩阵的话，MATLAB会用线性索引的方式以列的方式将矩阵转化为向量，例如将矩阵A转换成为向量：A = 2 6 9; 4 2 8; 3 5 1A = 2 6 9 4 2 8 3 5 1实际上内存中的存储为：2, 4, 3, 6, 2, 5, 9, 8, 1如果我们希望目标函数值能够尽可能接近设定的期望值，也就是说目的是准确达到，而非大于也非小于，我们可以使用optimset设置控制

33、参数GoalsExactAchieve的值为相应的目标函数的序号。需要注意的是，这类目标函数必须安排在参数fun返回的函数向量的F的最前面。如果函数一阶可微，则该函数具有梯度向量，如果此时优化参数GradObj的值为'on'，设置方法为：options = optimset('GradObj','on')则fun必须在函数的第二个输出参数中返回函数在x处的梯度向量g。goal输入参数中的goal变量是指希望目标函数达到的向量值。该向量的长度与fun函数返回的目标数f相等。fgoalattain函数试图通过最小化向量f中的值来达到goal参数给定的

34、目标。nonlcon输入参数中的nonlcon参数则代表多目标规划中的约束函数，它包括了不等式约束c(x)0和等式约束ceq(x)=0，它实际上是计算在x处约束函数的值。nonlcon必须是函数句柄，例如可以是以M-函数文件的形式出现或者以匿名函数的形式出现，例如：x = fgoalattain(x)sin(x.*x),x0,goal,weight);其中mycon.m是一个M-函数文件形式如下：function c,ceq = mycon(x)c = . % 计算x处非线性不等式约束函数的值.ceq = . % 计算x处非线性等式约束函数的值.如果约束函数存在梯度向量，通过如下方法设置控制参

35、数GradConstr的值为on：options = optimset('GradConstr','on')则nonlcon必须在第三个和第四个输出参数返回相应的梯度值，即不等式约束函数的梯度值GC和等式约束函数的梯度值GCeq。需要注意的是，只有当设置了控制参数GradObj的值为'on'时，将控制参数GradConstr的值为'on'才有效，同时，由于优化工具箱只接受double型数据的输入，故用户提供的目标函数和非线性约束函数必须返回的是double型数据。weight输入参数中的weight变量为权重向量，可以控制低于或超

36、过fgoalattain函数指定目标的相对程度。当goal的值都是非零值时，则算法为了保证有效的目标值超过或低于的比例相当，将权重函数设置为abs(goal)。需要注意的是，如果将weight向量中的任一元素设置为0时，则算法将把对应的目标约束当做是硬约束来处理，另一种设置硬约束的方式是通过参数nonlcon来设置相应的约束。当设置weight为不同的数值时，fgoalattain将对目标函数采取不同的处理方式：(1) 当权重weight设置为正时，fgoalattain函数则试图使目标函数值小于期望值；(2) 当权重weight设置为负时；fgoalattain函数则试图使目标函数值大于期望

37、值；(3) 当需要目标函数值尽可能等于期望值时，则应设置控制参数GoalsExactAchieve的值为相应的目标函数的序号。需要注意的是，这类目标函数必须安排在参数fun返回的函数向量的F的最前面。当然，输入参数还包括优化控制参数options，其具体的设置我们将在控制参数设置一节中给出。3.输出参数attainfactor输出参数attainfactor指明了目标达到的情况。当attainfactor为负时，说明目标函数值溢出期望值goal，当attainfactor为正时，说明目标函数还未达到期望值。attainfactor参数包含了最优解处的值，若值为负，则表明目标溢出。exitflag优化终止状态指示结