1、第十章第十章 多目标函数的最优化方法多目标函数的最优化方法 实际工程问题中，常希望有多项指标达到最优值，所以问题包含了多个目实际工程问题中，常希望有多项指标达到最优值，所以问题包含了多个目标函数。例如设计一个新的工艺过程，希望产量高、质量好、投资少、消标函数。例如设计一个新的工艺过程，希望产量高、质量好、投资少、消耗低、环境污染少、安全程度大等等。耗低、环境污染少、安全程度大等等。多目标函数最优化问题的数学模型：多目标函数最优化问题的数学模型：min f1(x)min f2(x)min fp(x)s.t.gi(x)0 i=1,2,l hj(x)=0 j=1,2,m V表示求向量函数的最优表示求
2、向量函数的最优引进向量函数引进向量函数 f(x)=f1(x),f2(x),fp(x)T，上式可改写为，上式可改写为 V-min f(x)x S 各目标函数之间往往是相互影响相各目标函数之间往往是相互影响相互制约的，有时是相互矛盾的，不互制约的，有时是相互矛盾的，不能同时达到最优，有时某一个点是能同时达到最优，有时某一个点是一个目标函数的最优点，但对另一一个目标函数的最优点，但对另一个目标函数却是最差点。因此，这个目标函数却是最差点。因此，这要求在各目标之间进行协调，相互要求在各目标之间进行协调，相互作出适当的作出适当的“让步让步”，以便取得整，以便取得整体最优方案。体最优方案。S（f）f2 f
3、1 S（x）映射映射多目标优化问题自变量空间中可行域与解空间中可行域的对映关系多目标优化问题自变量空间中可行域与解空间中可行域的对映关系10.1 多目标最优化问题的解多目标最优化问题的解 多目标问题与单目标问题的一个重要区别：单目标问题的任意两个解都是多目标问题与单目标问题的一个重要区别：单目标问题的任意两个解都是可以比较其优劣的，但对多目标问题就不一定能进行优劣性的简单比较。可以比较其优劣的，但对多目标问题就不一定能进行优劣性的简单比较。f2f112867453例如对如下的优化问题：例如对如下的优化问题：min f1(x)min f2(x)s.t.x0 在在“解空间解空间”中存在如图所示的中
4、存在如图所示的8个解个解 在图中，除解在图中，除解3、4、5之外，其它的解都可找到另一个比它更优。之外，其它的解都可找到另一个比它更优。对解对解3、4、5而言，它们之间无法比较优劣，而且也没有别的解比它们更而言，它们之间无法比较优劣，而且也没有别的解比它们更 优，这种解在多目标优化问题中有特殊意义。优，这种解在多目标优化问题中有特殊意义。定义：定义：设设x*S，若对任意的，若对任意的x S及及 i=1,2,P，都成立，都成立fi(x*)fi(x)，则称，则称x*为多目标为多目标 问题的问题的绝对最优解绝对最优解。x*=0是该问题的绝对最优解。是该问题的绝对最优解。例如例如 min f1=x2
5、min f2=x2+4 s.t.4x4 44xf1f20不存在绝对最优解不存在绝对最优解 又如又如 min f1=x2 min f2=(x2)2 s.t.4x4 44xf1f20可见，在研究多目标优化问题时，需要引入其它意义的解。可见，在研究多目标优化问题时，需要引入其它意义的解。先引入三个不等式符号：先引入三个不等式符号：设设 f(x(1)=f1(x(1),f2(x(1),fp(x(1)T,f(x(2)=f1(x(2),f2(x(2),fp(x(2)T（1）符号）符号“”:f(x(1)f(x(2)表示表示 fi(x(1)fi(x(2),i=1,2,p每个分量都严格小于每个分量都严格小于（2）
6、符号）符号“”:f(x(1)f(x(2)表示表示 fi(x(1)fi(x(2),i=1,2,p且至少有一个且至少有一个i0(1 i0 p)，成立，成立fi0(x(1)fi0(x(2)至少有一个分量严格小于至少有一个分量严格小于（3）符号）符号“”:f(x(1)f(x(2)表示表示 fi(x(1)fi(x(2),i=1,2,p可以都是全等于可以都是全等于 定义：定义：设设x*S，若不存在，若不存在x S 使使 f(x)f(x*)，则称则称x*为多目标问题的为多目标问题的非劣解。非劣解。(有效解有效解)即在即在“”意义下，找不到更好的解。意义下，找不到更好的解。定义：定义：设设x*S，若不存在，若
7、不存在x S 使使 f(x)f(x*)，则称则称x*为多目标问题的为多目标问题的弱非劣解弱非劣解(弱有效解弱有效解)。即在即在“”意义下，找不到更好的解。意义下，找不到更好的解。f2f1125433和和4是非劣解是非劣解3、4和和5是弱非劣解是弱非劣解例例10.1.3 分析下列问题的非劣解：分析下列问题的非劣解：min f1(x)=x22x min f2(x)=x st 0 x2a0-1-2xa 1b2单目标函数的最优解分别为单目标函数的最优解分别为 x1*=1,x2*=2,该多目标问题不存在绝对最优解。该多目标问题不存在绝对最优解。当当x0,1)时不可能是非劣解时不可能是非劣解,对任意的对任
8、意的x1,2都是非劣解都是非劣解,。对多目标问题，最好是找出绝对最优解，但大部分问题不存在绝对最优对多目标问题，最好是找出绝对最优解，但大部分问题不存在绝对最优 解，解，通常是求出非劣解。通常是求出非劣解。多目标问题的非劣解往往很多，甚至是无穷个，而最终付诸实施的一般多目标问题的非劣解往往很多，甚至是无穷个，而最终付诸实施的一般 只有只有 一个。一个。所以存在决策采用哪个非劣解的问题。所以存在决策采用哪个非劣解的问题。多目标问题的整个求解过程分为分析与决策两个部分，找出非劣解的人多目标问题的整个求解过程分为分析与决策两个部分，找出非劣解的人 为分析者，最终决定采用哪个非劣解的人为决策者。两者需
9、配合。为分析者，最终决定采用哪个非劣解的人为决策者。两者需配合。min f1=(x13)2+(x23)2 min f2=x12+(x2 3)2 s.t.g1=(x13)2+(x23)2 40g2=x12+(x2 3)2 40 x2x103pqabcdg1=0g2=0例：例：试分析下列问题的非劣解：试分析下列问题的非劣解：f2f10a,bcd分析：可行域为上图中分析：可行域为上图中acbda包围的区域包围的区域可行域各点在解空间中的对应点如下图所示。可行域各点在解空间中的对应点如下图所示。显然，解空间中显然，解空间中CD弧线上的解均为非劣解。弧线上的解均为非劣解。(两目标函数的等值线相切）两目标
10、函数的等值线相切）在可行域中的直线在可行域中的直线cd上，上，x23，1 x1 2，f1=(x13)2，f2=x12，所以在解空间中曲线所以在解空间中曲线cd的表达式为：的表达式为：f10.5f20.53，1 f1 4所以，非劣解在可行域及解空间的关系式分别为所以，非劣解在可行域及解空间的关系式分别为:1 x1 2，x23f10.5f20.53，1 f1 410.2 主要目标法（约束法）主要目标法（约束法）考虑到各个目标的重要程度不一样，抓住主要目标，兼顾次要目标。考虑到各个目标的重要程度不一样，抓住主要目标，兼顾次要目标。即选择一个作为主要目标，其他目标只要满足一定要求即可，于是将其转即选择
11、一个作为主要目标，其他目标只要满足一定要求即可，于是将其转换成约束条件换成约束条件 min f1(x)x S1=x|f jfjf”j,j=2,3,P,x S 其中其中f j 和和f”j 分别为分别为fj(x)的上下限。的上下限。10.3 评价函数法评价函数法首先构造称为评价函数的新目标函数首先构造称为评价函数的新目标函数,然后求解该单目标问题：然后求解该单目标问题：min hf(x)x S 用上述问题的最优解作为原多目标问题的近似最优解。用上述问题的最优解作为原多目标问题的近似最优解。关键是如何构造评价函数关键是如何构造评价函数.10.3.1 理想点法理想点法 先分别求解各个单目标问题，得先分
12、别求解各个单目标问题，得 P,1,2,.i (x),f fiSx*imin然后构造评价函数然后构造评价函数 P1i1/22*ii f(x)fhf(x)min 可以证明上述评价函数的最优解是原多目标问题的非劣解。可以证明上述评价函数的最优解是原多目标问题的非劣解。上述评价函数上述评价函数 hf(x)相当于在相当于在“解空间解空间”中中 f1(x),f2(x),fP(x)T与与f*1,f*2,f*PT之间的距离。之间的距离。f*1,f*2,f*PT是一个理想点，一般不能达到，此法的出发点就在于找出一是一个理想点，一般不能达到，此法的出发点就在于找出一个与理想点距离最近的点，即让各个单目标尽可能地接
13、近各自的理想值。个与理想点距离最近的点，即让各个单目标尽可能地接近各自的理想值。每个目标函数值都尽可每个目标函数值都尽可能接近各自的最小值能接近各自的最小值（单目标问题最优值）（单目标问题最优值）10.3.2 线性权和法线性权和法 此法简单易行，计算量少，是个常用方法。此法简单易行，计算量少，是个常用方法。（一）（一）基本思想基本思想构造评价函数构造评价函数P1iii(x)fhf(x)其中常数其中常数i称为加权因子，取值大小取决于目标称为加权因子，取值大小取决于目标 fi 的相对重要程度，要求的相对重要程度，要求i0,且且11Pii可以证明上述评价函数的最优解是原多目标问题的非劣解或弱非劣解。
14、可以证明上述评价函数的最优解是原多目标问题的非劣解或弱非劣解。此法的关键在于如何找到能反映此法的关键在于如何找到能反映 fi 相对重要程度的相对重要程度的i(二二)加权因子的选取加权因子的选取(1)老手法老手法请有关方面的专家、有经验的工人或干部（老手）对加权因子的选取各自独请有关方面的专家、有经验的工人或干部（老手）对加权因子的选取各自独立打分，然后计算每个加权因子的平均值以及每个专家对该因子的打分与平立打分，然后计算每个加权因子的平均值以及每个专家对该因子的打分与平均值的偏差，请偏差较大的专家发表意见，充分讨论修改后再最后确定。均值的偏差，请偏差较大的专家发表意见，充分讨论修改后再最后确定
15、。(2)方法方法 首先分别求解单目标问题首先分别求解单目标问题 min fi(x)i=1,2 x S设最优解分别为设最优解分别为x(1),x(2),令令 f11=f1(x(1)f21=f2(x(1)f12=f1(x(2)f22=f2(x(2)=f1*=f2*f(S)f11 f21f1(x*)f2(x*)f2 f1 f12 f22AB否则，否则，“解空间解空间”中弧中弧AB上的所有点均为非劣解。上的所有点均为非劣解。若若x(1)x(2)，为原问题的绝对最优解，为原问题的绝对最优解,则问题已解决。则问题已解决。方法的作法是连接方法的作法是连接AB，平移直线得，平移直线得x*2211 ff121将将
16、f11,f21和和f12,f22代入，可解得代入，可解得)()/()()()/()(22121121112122212112122121ffffffffffff代入评价函数代入评价函数 ，求解得，求解得x*先讨论先讨论P=2的简单情况。的简单情况。(x)f(x)fminhf(x)min 2211对于一般具有对于一般具有p(p2)个目标函数的情形，可用类似的步骤求出个目标函数的情形，可用类似的步骤求出i，i=1,2,p 求求p个单目标问题个单目标问题 min fi(x)i=1,2,p x S得最优解得最优解x(i),令令 fj(i)=fj(x(i),i=1,2,p;j=1,2,p设经过设经过p个点个点f1(i),f2(i),fp(i)T,i=1,2,p 的超平面方程为的超平面方程为ppfff2211121p将将p个点代入上述方程，可解出个点代入上述方程，可解出i，i=1,2,p作业：作业：P462 2 5
