多目标优化问题5.1多目标优化的基本概念大多数工程设计问题都具有多个目标,设计工作需要同时极大化(或极小化)这些目标,并且满足约束条件。
一般情况下,这些和被设计系统的性能相关的目标是内在冲突的。
这种多于一个的数值目标在给定区域上的最优化问题称为多目标优化(Multi-Objective Optimization,MO)问题。
解MO 问题通常的做法是根据某效用函数将多目标合成单一目标来进行优化。
但大多数情况下,在优化前这种效用函数是难以确知的。
另一方面单目标优化问题中的任意两个解都是可以比较其好坏的,因此说问题有一个最优解(如果存在最优解)是毫无争议的;而多目标优化问题中各目标之间通过决策变量相互制约,对其中一个目标优化必须以其它目标劣化作为代价,也就是说,要同时使这多个子目标都一起达到最优值是不可能的,而只能是在它们中间进行协调合折衷处理,使各个子目标函数都尽可能地达到最优。
而且各目标的单位又往往不一致,因此很难客观地评价多目标问题解的优劣性。
与单目标优化问题的本质区别在于,多目标优化问题的解不是唯一的,而是存在一个最优解集合,这是多目标优化问题与单目标优化问题最大的区别。
因此在多目标优化问题中往往有一些无法简单进行相互比较的解。
这种解称作非支配解或Pareto 最优解,5.1.1多目标优化问题的数学模型在工程实际中许多实际问题往往期望几项指标同时达到最优值,如在机型工程中,可能希望机器(或零部件)的强度、刚度、经济性、工艺性、使用性及动力性能都有最优。
一般的多目标优化问题,就是在可行设计空间中寻找一组设计变量以同时优化几个不同的设计目标。
多目标优化问题一般可描述为下面的数学模型:T p x f x f x f x f V )](,),(),([)(min21"=−(读作x 属于集合X 。
满足约束条件的解x 称为可行解) X x t s ∈.. (读作X 是m R X ⊆m R 的子集。
集合X 表示由所有满足约束条件的解所组成的一个集合,叫做可行解集合)多目标优化 多目标优化 多目标优化式中,表示向量极小化,即向量目标中的各个子目标函数都尽可能地极小min−V T p x f x f x f x f )](,),(),([)(21"=多目标优化问题的最优解与单目标优化问题有着本质的不同,为正确地求解多目标优化问题,对多目标最优解和Pareto 最优解进行定义。
定义 1 设是多目标优化模型的约束集,是多目标优化时的向量目标函数,。
若 m R X ⊆X x ∈2p R x f ∈)(),,2,p "X x ∈1,)()(21x f x f k k ≤1(k =∀ (对于所有的子目标)且 )()(21x f x f k k <),,2,1(p k "=∃ (表示存在) 则称解比解优越。
1x 2x 定义 2 设是多目标优化模型的约束集,是多目标优化时的向量目标函数。
若,并且比X 中的所有其它解都优越,则称是多目标优化模型的最优解。
m R X ⊆p R x f ∈)(X x ∈11x 1x x m R X ⊆p R x f ∈)(x 由该定义可知,多目标优化问题的最优解就是使函数的每一个子目标函数都同时达到最优点的解,如图所示。
显然在大多情况下,这样的最优解是不存在的。
1)(x f 定义 3 设是多目标优化模型的约束集,是多目标优化时的向量目标函数。
若X ∈~,并且不存在比更优越的x ,则称是多目标优化模型的Pareto 最优解,或称为非劣解。
多目标优化问题的最优解x ~x ~m R X ⊆X x t s ∈..由该定义可知,多目标优化问题的Pareto 最优解仅仅是它的一个可以接受的“不坏”的解,并且一般多目标优化问题都存在多个Pareto 最优解,如图所示。
多目标优化 多目标优化 多目标优化多目标优化问题的最优解由Pareto 解的定义可知:在可行解中没有比Pareto 解更优的解,即Pareto 最优解集中的元素就所有目标而言是彼此不可比较的。
对一个多目标优化的问题而言,其Pareto 解不是唯一的,而是一群,所有Pareto 解的集合形成Pareto 解集,而该解集中任何一个解都是可能的最优解。
解决多目标优化问题的最好方法,就是得到均匀分布的Pareto 最优解集后,根据不同的设计要求和意愿,从其中选择最满意的设计结果。
Pareto 方法是建立在Pareto 最优解基础上的一种处理多目标问题的方法,它不同于线性加权法的地方在于:线性加权法先决定各个目标的重要程度,将多目标问题转化为单目标问题求解,实质上是单目标的优化设计,而Pareto 方法是在多目标优化的基础上,找到优化问题的Pareto 最优解,然后才是选择最适当的设计点,所以能更客观的反映多目标优化问题的实质。
一个多目标优化问题的所有Pareto 解(有效解)构成的集合称为Pareto 曲面(有效域),多目标优化问题的最终解应该从Pareto 曲面中产生。
5.2多目标优化问题的基本求解方法多目标优化问题最终获得的解实际上是所有有效解(或称有效解集)中的一个解或确定全部非支配解。
多目标优化问题的基本求解方法如下:(1)约束法根据设计者的偏好,选择一个参考目标,如,而要求其他m -1个目标函数满足一定的约束要求即可。
具体地k f (5.2) ()k m inf x 多目标优化 多目标优化 多目标优化s .t .()()k k f x εk =1,2,...,m,k k ∈≠0 x S ∈ 其中参数为设计者事先设定的。
k ε约束法也称约束法。
约束法求得的最优解只能保证是原多目标优化问题的Pareto 弱有效解。
对于任一个Pareto 解εx ,都存在一组参数k ε(k =1,2,...,m ,k ≠使得0k )x 为相应的参数设置下用约束法求得的最优解。
约束法重点保证第0k 目标的效益,同时又适当照顾其他目标,这在许多实际设计问题的求解中颇受设计者的喜爱。
个(2)分层序列法根据各目标的重要程度不同,将m 个目标函数排序。
假设最重要,次之,依此类推,最不重要。
逐次求解下列m 个单目标优化问题。
1f 2f m f 用分层序列法求得的解是原多目标优化问题的一个Pareto 有效解。
分层序列法还融合了设计者进一步的偏好信息。
但它也存在不足之处,一是求解一个Pareto 解需要求解m 个优化问题,另一方面在不少场合设计者拒绝将m 个目标进行排序。
(3)评价函数法对于一个多目标优化问题,如果能根据设计者提供的偏好信息构造出一个实函数,使得求解设计者最满意的解等价于求解实函数,则称该多目标优化问题是可标量化的,多目标效用理论就是研究这样的实函数存在的条件和如何构造问题的。
效用理论的基础是:假定设计者的偏好可以用一个称为效用函数的实函数表示。
一旦效用函数能够被构造出来,则方案的最后选取即按效用函数值来决定。
虽然效用理论为多目标优化分析提供了一种工具,但在许多场合下,设计者所提供的偏好信息不足以确定这样的效用函数,估计或构造一个实际问题的效用函数是相当困难甚至是不可能的。
为了帮助设计者选择满意的解又克服效用理论存在的困难,于是出现了评价函数的概念。
评价函数是用来整体或局部逼进设计者心中常常是朦胧而难以构造出来的多属性效用函数,以评价方案的好坏。
它的基本思想是:针对多目标优化问题,构造出一个评价函数()()h f x ,然后求解问题min (5.3) ()(h f x )s .t .x S ∈用该问题的最优解作为多目标优化问题的最优解。
常用的评价函数有加权系数法(线性加权法)、理想点法、平方和加权法等,其中加权系数法和理想点法是最重要的也是当前应用最广的两种多目标优化方法。
1)加权系数法对多目标优化问题的m 个目标按其重要的程度给以适当的权系数,且,然后求解下面的线性加权问题。
()i λ0i =1,2,...,m ≥mmii =1λ=1∑()i ii =1m i n λf x ∑(5.4)s.t.x S ∈多目标优化 多目标优化 多目标优化用加权系数法求得的解是原多目标优化问题的一个Pareto 有效解。
加权系数法比较简单,应用得也非常广泛。
其缺点是权重系数没有一个实际的物理意义,在实际应用中难以合理地确定;而且如果多目标优化问题的有效解是凹有效域,则利用加权系数法不能得到所有的Pareto 解。
2)理想点法理想点法是求距离某个给定的理想点T1m f =(f ,...,f )在某种范数意义下距离最短的可行解,即在S 中寻找是f(x)与f 偏差最小的点x 。
一般情况下,(){}()k k f =min f x |x S k =1,...,m ∈。
常用的描述偏差的函数有(a )距离模评价函数()k2u f =f -f =i 为目标个数;(b )p 模函数,()()()1mpp k k k k=1h f x =λ|f x -f |⎡⎤⎢⎥⎣⎦∑,其中1p ≤≤+∞;上面式中权系数是由设计者设定的。
(i λ0i =1,2,...,m ≥)2222(4)Pareto 方法[24]Pareto 方法假设对目标值偏好的任何信息都不存在,我们知道的信息就是对于每个目标,k =1,2,...,m ,其值越小越好的偏好。
Pareto 偏好定义如下:对于判据空间Z 上两点和,当且仅当至少存在一个满足,其他目标,k =1,2,…,m 。
由Pareto 解的定义可以知道,任意两个Pareto 解和是不能满足的。
因此,在Pareto 偏好定义下的判据空间中存在偏好关系不明确的特点。
本课题采用Pareto 遗传进化方法解决多目标参数优化问题。
k z 1z 2z 1z z ;1r z >z 1z r 2z 1r z z ≥1z ;r z 5.3基于Pareto 排序的Pareto 遗传算法的实现5.3.1 Pareto排序方法Pareto 基于排序的适应值分配方法是由Goldbelg 提出的,Goldbelg 在Pareto 最优集的基础上,提出一种将各个目标值映射到适应度函数中的基于级的适应度函数。
本章在Goldbelg 提出的Pareto 适应值分配方法的基础上,采用Pareto 排序机制[25],应用Pareto 解集过滤器等技术,给出了求解有约束的多目标优化问题的Pareto 多目标遗传算法的有效方法。
下面介绍“优”与“劣”与“非劣”的概念:定义5.3 设,u v x x 为多目标优化问题的两个解,()()u12m x =u ,u ,...,u ,u =f()(v 12m x =v ,v ,...,v ,v =f )称u 优于v ,当且仅当{}i i 1,2,...,m ,u v i ≤∀∈ ∧ {}1,2,...,m i ∃∈i i <v u 。