一种快速构造多目标Pareto非支配集的方法_选举法则
收稿日期:2008204219;修回日期:2008207211 基金项目:国家自然科学基金资助项目(60773047);湖南省研究生科研创新资助项目
(x2008yjscx18);湖南省教育厅重点科研资助项目(06A074)
作者简介:杨平(19842),男,安徽怀宁人,硕士研究生,主要研究方向为进化计算、图像处理、计算智能;郑金华(19632),男,湖南邵阳人,教授,博导,主要研究方向为进化计算、并行处理等(jhzheng@xtu .edu .cn );李密青(19812),男,湖南常德人,硕士研究生,主要研究方向为进化计算;罗彪
(19842),男,湖南邵阳人,硕士研究生,主要研究方向为进化计算、计算智能.
一种快速构造多目标Pa re t o
非支配集的方法:选举法则
3
杨 平,郑金华,李密青,罗 彪
(湘潭大学信息工程学院,湖南湘潭411105)
摘 要:基于Paret o 的多目标优化问题是进化算法的一个重要研究方向,而如何构造Paret o 非支配集则是提高算法效率的关键所在。通过对选举现象的观察,同时针对多目标个体之间的特性,提出了一种快速求解多目标
Paret o 非支配集的方法:选举法则(electi on p rinci p le,EP ),分析了其时间复杂度为O (r mN ),并对其进行了正确
性证明。因为种群中实际的非支配个体数m 比进化群体规模N 小,所以与同类方法相比,EP 有更高的效率,并通过了实验验证。
关键词:多目标优化问题;进化算法;选举现象;Paret o 非支配集;选举法则
中图分类号:TP18 文献标志码:A 文章编号:100123695(2009)022*******
Fast method of constructing multi 2objective Paret o non 2dom inated set :electi on p rinci p le
Y ANG Ping,Z HE NG J in 2hua,L IM i 2qing,LUO B iao
(Institute of Infor m ation Engineering,X iangtan U niversity,X iangtan Hunan 411105,China )
Abstract:The multi 2objective op ti m izati on p r oblem based on paret o is a i m portant research directi on of the evoluti onary algo 2
rith m,and how t o i m p r ove the efficiency of constructing the Paret o non 2dom inated set is a key t o the algorith m.This paper p r o 2posed a quick method of constructing multi 2objective paret o non 2dom inated set thr ough observing the electi on phenomenon and understanding the mutual character of multi 2objective individual,na mely the electi on p rinci p le (EP ),analyzed that its com 2putati onal comp lexity was O (r mN ),p r oved the EP works correctly .Because the nu mber m of actual non 2dom inated individual is s maller than the populati on size N ,compared with fa m iliarmethods the EP has a high efficiency and p r oves it thr ough experi 2ment finally .
Key words:multi 2objective op ti m izati on p r oble m;evoluti onary algorith m;electi on phenomenon;Paret o non 2dom inated set;electi on p rinci p le (EP )
引言
在实际生活中,存在着很多多目标优化问题(MOP ),进化算法因具有解决高度复杂的非线性问题的能力,引起了专家学者们的极大兴趣。基于Paret o 的多目标优化是进化算法的一个重要研究方向。该方法最先由Goldberg 提出[1],其基本思想是利用基于Paret o 的适应度分配策略,从当前进化群体中找出所有的非支配个体,在进化过程中通过构造当前进化群体的
Paret o 非支配集,使其逐渐逼近真实的Paret o 前沿,但因其每
一代的进化都需找出所有非支配个体,因此构造Paret o 非支配集的效率则直接影响到整个进化算法的运行效率。目前构造
Paret o 非支配集的最典型方法主要有:郑金华等人
[2]
的擂台赛
法则;Deb 等人[3]提出的构造非支配集的方法,其时间复杂度为O (r N 2
),其中r 为目标数,N 为群体规模;Jensen [4]
提出的一种采用递归构造非支配集的方法,其时间复杂度为O (N
l og
(r -1)
N ),但是当目标数目r 很大时,其复杂度呈指数增加。
本文提出的选举法则(electi on p rinci p le,EP )是一种新的
构造Paret o 非支配集的方法,其思想来源于选举现象。西方国家存在多个政党,包括执政党和在野党。因此每当举行换届选举时,多个政党之间会发生激烈的竞争,一般情况下,只有两个实力较强且最为接近的政党之间产生激烈的争夺,如美国的民主党和共和党,英国的工党和保守党,日本的自民党和民主党等。当竞选时每个政党都需要产生一位候选竞选人,这个竞选人要有足够的实力,否则会就被竞争对手打败,由对手替代自己充当新的候选人。可以将此思想用到多目标优化中个体之间的支配性分析上,抉择产生最终的所有非支配个体。通过分析发现,EP 的时间复杂度仅为O (r mN ),而0 相关概念 定义1 多目标优化问题(MOP )。一般一个MOP 包括n 个决策变量,r 个目标函数,k 个约束条件。给定一个决策变量 第26卷第2期2009年2月 计算机应用研究 App licati on Research of Computers Vol .26No .2Feb .2009 x=(x1,x2,…,x n)。其中x∈X,满足以下约束条件: g i(x)≤0;i=1,2,…,k(1) X={x1,x2,…,x n)|l i≤x i≤u i}(2) l=(l1,l2,…,l n)(3) u=(u1,u2,…,u n)(4)其中:X为决策空间;l和u分别为上界和下界。假设有r个优化目标,且优化目标之间是相互冲突的,优化问题可表示为 m in f-(x)=(f1(x),f2(x),…,f r(x))(5)寻求x3=(x3 1 ,x32,…,x3n),使f-(x3)在满足以上约束条件的同时达到最优。 定义2 可行解。可行解是决策向量的集合,满足 x f={x∈X|g i(x)≤0}(6)定义3 Paret o最优解。给出m in f-(x),称x3为Paret o最 优解,若Πx∈x f ,满足下列条件 ∧i∈I (f i (x)=f i(x3))(7) 或者至少存在一个j∈I,使 f j(x)>f j(x3)(8)其中I={1,2,…,r},x f 是可行解。 定义4 设p和q是两个解个体,称p支配q,则必须满足 Πk,f k(p)≤f k(q);k∈{1,2,…,r}(9) ?l,f l(p) 定义5 不相关。若个体x与y之间不存在支配关系,则称x与y不相关或者无关。 定义6 对于给定个体x∈Pop,Pop为所有个体的集合,若不存在y∈Pop,使y:x,则称x为集合Pop的非支配个体。Pop的所有非支配个体组成的集合,称之为Pop的非支配集。 定义7 设Nds是Pop的非支配集,则NdsΑPop,Πx∈Pop,若x是Pop的非支配个体,必有x∈Nds,则称Nds是Pop 的最大非支配集。 定义8 任意两个个体p和q,若它们不相关,则定义它们的簇cluster(p,q)={x|not(p:x)&¬(q:x),x,p,q∈Pop},即集合Pop中不被p和q支配的所有个体集合。 定义9 若cluster(p,q)为个体p和q的簇,则称p和q为簇长。 定理1 支配关系具有传递性。 证明 Πx,y,z∈Pop,若有x:y,y:z,即证x:z。 因为x:y,由定义4有f k (x)≤f k (y)(k=1,2,…,r),且 ?l,f l(x) (y)≤f k (z)(k=1,2,…,r),且?l,f l (y) l (z),l∈{1,2,…, r}。综合以上两步,则有f k(x)≤f k(z),(k=1,2,…,r),且?l, f l(x) 采用选举法则(EP)构造非支配的基本思路是:每一轮比较时先从构造集中选出两个个体担任候选竞选个体,保证两个候选竞选个体互不相关;再依次从构造集中选取一个个体与两个候选竞选个体进行比较,败者被淘汰出局,胜者成为新的候选竞选个体,若竞选个体发生替换,则还要再次比较这两个候选竞选个体,淘汰弱者,以保证它们互不相关,并继续该轮比较;一轮比较后,两个候选竞选个体即为非支配个体。按照此方法进行下一轮比较,直至构造集为空。 1 用选举法则构造非支配集的方法 设Pop为r个目标的进化群体,Cs为构造集,令Cs=Pop, Nds为非支配集,初始时置为空。设B s为一个缓冲集,用来存储与当前竞选个体不相关但不能确定最终相关性的个体。X s 和Ys分别为两个竞选据点,用来存储竞选个体,X f和Yf分别用来表示当前Xs和Ys据点是否有竞选个体。当且仅当据点Xs(或Ys)内有个体时,Xf(或Yf)置为真,否则为假。首先从构造集Cs中任取一个个体p作为竞选个体,填充据点Xs,同时置Xf为真,置B s为空,依次与Cs中所有其他个体q进行比较,如果p支配q,则将个体q从Cs中清除;如果q支配p,则用q代替p(即替换产生了新的竞选个体);如果p和q不相关,判断Yf,当Yf为假时,则将q填充据点Ys;当Yf为真,则考虑Ys和q 的相关性,不相关时,则B s=B s∪{q},并继续进行剩余个体的比较。一轮比较后,将p和q并入非支配集N ds中,删除B s中被簇长q和p支配的个体,再将B s并入Cs中,重复以上步骤。依此下去,直至Cs为空。构造非支配集的具体过程如算法1所示。 算法1 用选举法则构造非支配集。 a)初始化:Nds= ,令Cs=Pop。 b)从构造集Cs中任选一个个体p,令X s=p,X f=1,Yf=0, Cs=Cs-{p},B s= 。 c)判断Cs是否为空,为空则转i);否则进行下一步操作。 d)依次从构造集Cs中取出一个个体q,Cs=Cs-{q},判断X s与q的支配关系,若Xs:q或者有Yf=1且Ys:q,则转c);否则进行下一步操作。 e)如果q与Xs不相关,转f);否则令Xs=q,若Yf=1&& q:Ys,则Yf=0,转c)。 f)判断Yf,若Yf=1,转g);否则Ys=q,Yf=1,转c)。 g)判断Ys与q的相关性,如果Ys与q无关,则令B s= B s∪{q},转c);否则进行下一步。 h)如果q:Ys,则令Ys=q,转c)。 i)如果Xf=1,Nds=Nds∪{X s}。 j)如果Yf=1,Nds=Nds∪{Ys}。 k)令Cs=Cs∪{w|w∈B s&¬(Xs:w)&¬(Ys: w)},即把集合B s中所有不被最后胜出竞选个体Xs和Ys所支配的个体并入集合Cs中。 l)判断Cs是否为空,若Cs= ,则转m);否则转b)。 m)保存集合Nds,即非支配集,结束。 以上是用选举法则构造非支配集的基本步骤。第一步初始化非支配集和构造集,接下来进行每一轮的比较,找出两个优秀的候选竞选个体。因为在每一轮比较过程中,会发生候选竞选个体被实力更强的个体打败的现象,即出现了替换操作。而将要被替换的那个候选竞选个体通过在前面的比较过程中积累了很多有用信息。此时,就需要记录下替换操作发生时的有用信息,如与候选竞选个体不相关的个体的集合。这是因为,在替换操作之前被保留下来的个体有可能是被最新的实力更强的候选竞选个体所支配,对于其中一些个体只被当前这个 ? 9 8 4 ? 第2期杨 平,等:一种快速构造多目标Paret o非支配集的方法:选举法则 最新候选竞选个体所支配而不被此前的任何其他候选竞选个体所支配的情况,这个最新的候选竞选个体必须返回去找出相同的被它所支配的个体并清除之。否则,只被某个新的候选竞选个体所支配的个体就会被保留下来,并被当成是非支配个体,所以要采取必要的措施排除这种情况的发生。 为此,在本算法中设置了一个缓冲集B s,用它来存储目前那些不相关个体,在每一轮的比较前,初始化B s为空,在竞选比较过程中B s积累了所有到目前为止判定为不相关的个体信息,而在这一轮的最后再用最终的优秀候选竞选个体对B s中被它所支配的个体进行删除。一般情况下,设在构造非支配集的某一轮的比较中,两个竞选据点Xs和Ys分别出现了m和n 个新的候选竞选个体,Xs据点的替换过程为X m:X m-1:X2: X1,Ys据点的替换过程为Y n:Y n-1:Y2:Y1。其中:X1表示据点Xs的第一个候选竞选个体;X i 表示第i次出现的新的候选 竞选个体;Y 1表示据点Ys的第一个候选竞选个体;Y j 表示据 点Ys的第j个候选竞选个体。B s k 表示据点X s(或Ys)第k+1 次出现新候选竞选个体X k+1(或Y k+1 )时,没有被此前的旧候 选竞选个体X k 和Y h (假设此时Ys据点的个体为Y h )在比较时 所清除的所有个体的集合。这样一来,当第k+1个新的候选 竞选个体出现时,X k+1(或Y k+1 )需要返回进行比较的个体的 集合为B s k 。因为由定理1,即支配关系的传递性可知,任何被 X k+1(或Y k+1 )所支配的个体q∈B s k ,1≤k 必然被X m 或者Y n (即最终的竞选个体)所支配。从而可知,当 多次出现新旧竞选个体的更替时,只需将最后的竞选个体与其前被保留下来的所有个体进行比较,并清除被它支配的所有个体即可。 1 构造方法的时间复杂性分析 现对算法1进行时间复杂度分析,设进化群体集合Pop的大小为N,Pop中共有m个非支配个体,则算法总共需要执行了m/2轮比较操作,每一轮产生两个非支配个体。产生第一轮非支配个体时最多需要做2×(N-2)次比较操作,假设清 除了k 1个Pop中的支配个体。其中k 1 ≥0。产生第二轮非支 配个体时最多要做2×(N-k 1 -4)次比较操作,设清除了k2 个Pop中的支配个体。其中k 2 ≥0。依此类推,产生第m/2轮 非支配个体时做了2×(N-k 1 -k2-…-k m/2-1-m)次比较操 作,设清除了k m/2个Pop的支配个体。其中k m/2 ≥0。由于m 个非支配个体全部产生后,所有的支配个体都已经被清除,(k 1 +k2+…+k m/2)=N-m。由以上分析可知算法1在最坏情况下的时间复杂度为 T(EP)=2×(N-2)+2×(N-k1-4)+…+2×(N-k1-k2- …-k m/2-1 -m)=2×[(N-2)+(N-4)+…+(N-m)]-2×[k1+ (k1+k2)+…+(k1+k2+…+k m/2-1)]<(N-1)+(N-2)+…+ (N-m)-[k1+(k1+k2)+…+(k1+k2+…+k m/2-1)]<(2N-m-1)m/2 即算法在最坏情况下的时间复杂度为O(r m N)。其中:r为MOP中目标的数目,m为实际的非支配的个体数目,N为进化种群大小。由于在一般情况下有m 选举法则的正确性证明 下面讨论用选举法则(EP)构造Paret o非支配集的正确性,这里从两个方面进行分析:a)证明算法1的合理性,即采用 EP所构造的Nds就是Pop的非支配集;b)证明算法1的完备性,即算法1结束时的Nds就是进化群体Pop的最大非支配集。 定理2 选举法则构造非支配集(即算法1)是合理的。 证明 假设算法执行了n轮循环,令x i 和y i 表示第i轮 产生的非支配个体,P i 表示第i轮的所有个体集合,D i 表示该 轮中被x i 或者y i 所支配的所有个体集合,Cs i 表示在个体集P i 中由簇长x i 和y i 所对应的簇cluster(x i ,y i),则n轮对应下列n 个关系式: P1=x1+y1+Cs1+D1 P2=x2+y2+Cs2+D2 … P n=x n+y n+Cs n+D n (11) 其中:p 1 =Pop,p i =Cs i-1 ;i=2,…,n,Cs n= 。 下面用归纳法进行证明: a)首先证明第一轮进入Nds的个体是Pop的非支配个体。 设第一轮进入Nds的个体为x 1 和y 1 ,易知它们不相关,否则由构造方法可知会发生替换,从据点中被消除,不会进入非 支配集。由构造方法可知,? z∈Pop,使z:x 1 或者z:y 1 ,即x1和y1不被Pop中任一个体所支配,否则会发生替换或者从 据点中被清除;同时由簇的定义8知:? m∈Cs 1 ,x1:m,y1: m,即x1和y1不支配Cs1中任一个体,故可知x1和y1与Cs1中 个体不相关。又D i 中全是被个体x i 或者y i 所支配的个体的 集合,故x 1 和y 1 不被P 1 中任一个体所支配,亦即第一轮进入Nds的个体是Pop的非支配个体。 b)假设前面s(1≤s≤n-1)轮进入Nds中的个体是Pop 的非支配个体,现证明第s+1轮进入Nds的个体是Pop的非支配个体。 设x s+1 和y s+1 是第s+1轮产生的两个个体,由构造方法可 知,x s+1 和y s+1 不相关,否则发生替换,从据点中被清除,由簇的 定义知,x s+1 和y s+1 与Cs s+1 中任何一个个体无关,又D s+1 中为 x s+1或y s+1所支配的个体集合,故知x s+1和y s+1不被P s+1中任 一个体所支配,是P s+1 中的非支配个体,而P s+1 =Cs s ,由归纳 假设可知是x s 和y s 是Pop中的非支配个体,而x s 和y s 与Cs s 中任何一个个体无关且集合D s 中所有个体都被x s 或y s 所支 配,故Cs s 中非支配个体就是Pop中的非支配个体,即x s+1 和 y s+1是Pop中的非支配个体,也就是说第s+1轮进入Nds的个体也是Pop的非支配个体。 综合a)和b),采用EP所构造的Nds就是Pop的非支配集,即选举法则构造非支配集是合理的,故得证! 定理3 选举法则构造的非支配集(即算法1)是完备的。 证明 即求证Nds是Pop的最大非支配集。根据最大非支配集的定义,这里采用反证法进行证明。 若?x∈Nds,但不是Pop的非支配个体,则必?y∈Nds,使 y:x。则由算法构造过程知,或者在y并入Nds之前,x被y从构造集Cs中清除,故不会被并入Nds中;或者在y并入Nds之后,x被簇长y从簇中清除并进入下一轮的比较,这种情况下x 也不可能被并入Nds中,这与x∈Nds发生矛盾。反之,若?x∈Pop-Nds,且是Pop的非支配个体,则? y∈Pop,使y: x,因此Pop中任一个体都不能将x清除,故x必定被并入Nds 中,这与x∈Pop-Nds发生矛盾。由此可知,按算法1所构造 ? 9 4 ?计算机应用研究第26卷 的非支配集Nds 是P 的最大非支配集,即选举法则构造的非支配集是完备的,故得证! 实验结果 这里做了两部分实验:a )基于标准测试函数,采用NSG A 2Ⅱ[3]测试进化过程中非支配个体在种群中所占的比例;b )在标准测试函数下,求解算法关键操作次数的比较实验。实验环境为:I ntel (R )Celer on (R )CP U 2140GHz,256MB 的内存。1 基于标准测试函数非支配个体比例的测试实验为统计多目标进化算法在求解标准测试函数问题时,进化过程中实际的非支配个体比例变化情况,本文选用NSG A 2Ⅱ求解DT LZ 系列标准测试函数[5],并记录下每代种群的非支配个体比例。在文献[6]中给出了建议的归档集大小,对每个函数,分别取目标数r =2,3,5,8进行测试,结果如图1所示,发现进化时实际的非支配个体数m 是动态变化的,初始时比较小,随进化而不断增大,进化到一定程度时趋于稳定 。 对于这些标准测试问题,当目标数较少时(r =2,3),群体中非支配个体比例在50%左右;在目标数较多的情况下(r = 5,8),群体中非支配个体的比例会有所上升,但是一般在65% 左右,以此验证了实际的非支配个体数目m 比种群N 确实小,即0 1 基于标准测试函数的算法关键操作次数的比较实验在这一节,再基于算法的关键操作次数来比较算法的效率,该算法关键操作次数就是个体的支配性比较次数。这里采用关键操作次数的比较而不采用时间的比较是因为它更能反映出算法的效率。将EP 集成到NSG A 2Ⅱ中,代替其中构造非支配集部分的算法,然后比较(EP +NSG A 2Ⅱ)与DE B 的NS 2 G A 2Ⅱ在标准测试函数上的关键操作次数,如图2所示。标准 测试函数采用上一节使用的DT LZ1～6,进化参数设置如表1所示。 表1 进化参数设置 nu mber of objectives 2358populati on size 200200300500generati on 200 250 400 600 从图2可以看出,通过对DT LZ 系列标准测试函数的实验,无论是在低维还是在高维问题上,(EP +NSG A 2Ⅱ)比Deb 的NSG A 2Ⅱ的关键操作次数都要少,即个体的比较次数要少,所以算法EP 的效率更高 。 从前面两部分的实验可以得出:EP 受非支配个体比例的影响,而实际测试问题中每代的非支配个体比例不会达到 100%,这由第一部分实验进行了验证。由此可知,EP 要比Deb 的算法要好,而第二部分的实验正是验证了这一点。 结束语 因为基于Paret o 的多目标优化是通过在每一代进化过程中构造进化群体的非支配集,并使之不断逼近真实Paret o 前沿来实现的。因此,构造非支配集的方法,直接影响MOE A 的运行效率。本文提出了一种新的快速构造Paret o 非支配集的方法———选举法则,给出并讨论了用选举法则构造多目标进化群体的Paret o 非支配集的方法,同时进行了时间复杂度的分析,论证了构造方法的正确性。实验分为两部分,因为分析表明选举法则受非支配个体比例(即m /N )的影响,所以实验第一部 分是进行非支配个体比例的测试实验,验证了0 Paret o 非支配集上有自己的特色。 参考文献: [1] G OLDBERG D E .Genetic algorithm s in search,op ti m izati on,and machine learning,reading [M ].Massachusetts:Addis on 2W esley, 1989. [2]郑金华,蒋浩,邝达,等.擂台赛法则构造多目标Paret o 最优解集 的方法研究[J ].软件学报,2007,18(6):128721297. [3]DEB K,PRAT AP A ,AGRAWAL S,et al .A fast and elitist multi 2ob 2 jective genetic algorithm:NSG A 2Ⅱ[J ].I EEE Tran s on Evo l u ti o 2na ry Com p uta ti o n,2002,6(2):1822197.[4] JENSE N M T .Reducing the run 2ti m e comp lexity of multi 2objective E A s:the NSG A 2Ⅱand other algorithm s[J ].I EEE Tran s o n Evo l u 2ti o na ry Com p uta ti o n,2003,7(5):5032515. [5]DEB K,TH I ELE L,LAUMANNSM ,et al .Scalable evoluti onary multi 2 objective op ti m izati on test p r oblem s[C ]//Pr oc of Congress on Evolu 2ti onary Computati on .Ne w Jersey:I EEE Service Center,2002.[6] K NOWLES J D,CORNE D W ,F LE I SCHER M.Bounded archiving using the lebesgue measure [C ]//Pr oc of Congress on Evoluti onary Computati on .Piscata way,NJ:I EEE Press,2003. ? 194?第2期杨 平,等:一种快速构造多目标Paret o 非支配集的方法:选举法则 多目标规划 multiple objectives programming 数学规划的一个分支。研究多于一个目标函数在给定区域上的最优化。又称多目标最优化。通常记为VMP。在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方面的研究。1896年法国经济学家V.帕雷托最早研究不可比较目标的优化问题，之后，J.冯·诺伊曼、H.W.库恩、A.W.塔克尔、A.M.日夫里翁等数学家做了深入的探讨，但是尚未有一个完全令人满意的定义。求解多目标规划的方法大体上有以下几种：一种是化多为少的方法，即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法等；另一种叫分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。对多目标的线性规划除以上方法外还可以适当修正单纯形法来求解；还有一种称为层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。 1947年，J.冯·诺伊曼和O.莫根施特恩从对策论的角度提出了有多个决策者在彼此有矛盾的情况下的多目标问题。1951年，T.C.库普曼斯从生产和分配的活动中提出多目标最优化问题，引入有效解的概念，并得到一些基本结果。同年，H.W.库恩和A.W.塔克尔从研究数学规划的角度提出向量极值问题，引入库恩-塔克尔有效解概念，并研究了它的必要和充分条件。1963年，L.A.扎德从控制论方面提出多指标最优化问题，也给出了一些基本结果。1968年，A.M.日夫里翁为了排除变态的有效解，引进了真有效解概念，并得到了有关的结果。自70年代以来，多目标规划的研究越来越受到人们的重视。至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。 化多为少 即把多目标规划问题归为单目标的数学规划（线性规划或非线性规划）问题进行求解，即所谓标量化的方法，这是基本的算法之一。 ①线性加权和法对于多目标规划问题（VMP），先选取向量 要求λi>0(i=1,2，…,m) 作各目标线性加权和 多目标线性规划的若干解法及MATLAB 实现 一．多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为： 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? （1） 约束条件为： 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? （2） 若（1）式中只有一个1122i i i in n z c x c x c x =+++ ，则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = ， 12(,,,)T r Z Z Z Z = . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx = 约束条件：0 Ax b x ≤?? ≥? （3） 二．MATLAB 优化工具箱常用函数[3] 在MA TLAB 软件中，有几个专门求解最优化问题的函数，如求线性规划问题的linprog 、求有约束非线性函数的fmincon 、求最大最小化问题的fminimax 、求多目标达到问题的fgoalattain 等,它们的调用形式分别为： ①.[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) f 为目标函数系数,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为x 的下 限和上限, fval 求解的x 所对应的值。 算法原理：单纯形法的改进方法投影法 ②.[x,fval ]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub ） fun 为目标函数的M 函数, x0为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束 柏拉圖(Pareto Chart)是品管工具裡不可或缺的工具之一，它利用80/20的趨勢原則幫助工程師們歸納出較重大的要因，然後讓工程師可以只針對少數的及個要因，集中火力並對症下藥，以收事半功倍之效。但好像沒有幾個人可以使用Excel 畫出正確的柏拉圖。 如果你還不瞭解何謂柏拉圖(Pareto Chart)，就參考這裡吧： 柏拉圖分析(Pareto Chart)介紹 本文就暫時跳開所有的工程問題，單純的只討論如何利用Excel2007來製作出完整的柏拉圖(Pareto chart)，我知所以強調完整，是因為很多人做出來的柏拉圖都有點似是而非，比較一下上面兩張柏拉圖的畫法，右邊的圖只要稍有Excel 經驗的人，應該很簡單就可以畫出來，左圖才是比較正去的柏拉圖的畫法，要畫出這樣的圖可得有點技巧。 心動了嗎？現在就來看看如何利用Excel2007畫出這樣的柏拉圖效果，不過得先說聲對不起，因為我只有英文版的Excel2007，所以解說中的指令也都是英文，可能得麻煩自己對照一下中文了。 Step 1. 輸入數據並將數據由大到小排列。 1. 如下圖輸入A1~D1標題及A3~B6的「現象」及「數量」。 2. 將D2~D6的各式設為「百分比」。 3. 在C3的地方輸入公式【=B3】，在C4的地方輸入公式【=C3+B3】，其餘的 C5~C6用複製貼上就可以，或者用拖拉的方式複製也可以。 4. 在D2的地方輸入【0%】，這是一定要的，因為柏拉圖都是從0%開始的。 5. 在D3的地方輸入【=C3/$C$6】，其他的D4~D6用複製貼上就可以，或者用拖拉的方式複製也可以。小撇步：當你要輸入【$C$6】時，其實可以把滑鼠點到 C6的欄位再按 <决策理论和方法>习题 第一章概论 一、什么是决策? 什么是决策分析? 决策问题的特点是什么? 决策问题有哪些要素? 二、用决策树表示下列问题: 1. 火灾保险 2. 易腐品进货问题 3. 油井钻探问题: 某公司拥有一块可能有油的土地, 该公司可以自己钻井,也可 以出租给其它公司开采; 若出租土地,租约有两种形式,①无条件出租,租金45万元②有条件出租,租金依产量而定: 产量在20万桶或以上时,每桶提成5元; 产量不足20万桶时不收租金. 设钻井费用为75万元,有油时需另加采油设备费25万元,油价为15元/桶.(为了简化,可以将油井产量离散化,分为4种状态: 无油,产油5万桶, 产油20万桶, 产油50万桶) 三、* 设油井钻探问题如下: 每次钻井费用10万元,有油时售油收入100万元,有油 的概率为0.2, 无油的概率为0.8.问无油时该继续钻井否? 若该, 钻几次仍无油时停止钻井? 第二章主观概率和先验分布(Subjective Probability & Prior Distribution) 一、为什么要引入主观概率? 试比较主、客观概率的异同. 如何设定先验分布? 二、1. 阅读<决策分析> §6.3.4 2. 两人一组,一人充当决策人, 一人充当决策分析人, 就来年国民经济增长率 的先验分布进行对话,并画出对话所得的图形曲线. 互换角色, 就就来年通 涨率的先验分布进行对话. 三、设某个决策人认为产品售出400件的可能性是售出800件的可能性的1/3, 是售 出1200件的可能性的1/2, 与售出1600件的可能性相同, 售出800件的可能性售出1200件的可能性的两倍, 是售出1600件的可能性的3倍; 售出1200件的可能性比售出1600件的可能性的大2倍. 求该决策人关于产品销售量的主观概 施工管理多准则决策模型实例分析 摘要本文概述了建筑施工项目管理中存在的决策问题。对施工中存在的主要管理问题进行了鉴定，并讨论了解决这些问题的可能性。施工管理决策模型是基于多准则管理方法建立的，并实际案例中进行应用。基于层次分析法与专家选择法原理编写程序，依据实例模型验证程序的可行性。 关键词施工管理；实例分析 引言 施工管理和技术是影响建筑业发展的两个关键因素。在过去的40年中，虽然一些新的和先进的技术已应用于建筑项目，但该行业的效率仍然很低。先前的研究人员认为数字技术能让项目组织形式更加快速、灵活。今天，移动硬件、云计算和集成软件正在被广泛应用于存储和检索、自动搜索、原型机制造和仿真模拟这些领域。项目管理的目标是完成一个可执行项目，项目需要在可接受的风险、质量、安全和安全级别范围内满足预算和工作进度的要求[1]。 1 施工管理存在的问题 选择合适的承包商是施工中最重要的任務之一。从当今市场上提供的大量申请人中选择合适的承包商对客户来说是一个复杂的问题。塞纳拉特纳和塞克斯顿强调，在信息时代，组织理论把解决问题当成一种信息处理活动。然而，在这个时代，随着以知识为基础的组织观念的实现，共同解决问题越来越被视为是知识创造的触发器[2]。 2 施工管理中的多准则决策模型 2.1 多准则方法和施工管理 多准则决策是指在存在多个标准的决策，而这些决策通常是冲突的。每一个不同的标准可能有不同的测量单位、质量特性和相对重量。使用低价中标法选择承包商的业主应意识到几种可能的后果。首先，竞标过程假定所有的公司（包括总承包商、分包商和材料供应商）投标成本低，这通常意味着这些投标者的详细设计和图纸成本很低。其次，对于不了解真实行业状况的从业者通常存在这样误解，即投标过程的专业化设计可以保证每个参加竞标的承包商每个承包商必须提供与其他投标人相同质量的竞标结果，其设计将会满足业主的最终期望。最后，值得一提的是，由于设计过程中并没有承包商实际的投入，最终的低投标金额指到设计完成和投标结束后是无法确切得知的。因此，业主和建筑师只能在设计阶段和投标阶段完成之后才能知道他们的项目是设计在预算内的，或在大多数情况下是超过预算。 2.2 多准则决策模型的建立 多目标优化方法 基本概述 几个概念 优化方法 一、多目标优化基本概述 现今，多目标优化问题应用越来越广，涉及诸多领域。在日常生活和工程中，经常要求不只一项指标达到最优，往往要求多项指标同时达到最优，大量的问题都可以归结为一类在某种约束条件下使多个目标同时达到最优的多目标优化问题。例如：在机械加工时，在进给切削中，为选择合适的切削速度和进给量，提出目标：1）机械加工成本最低2）生产率低3）刀具寿命最长；同时还要满足进给量小于加工余量、刀具强度等约束条件。 多目标优化的数学模型可以表示为： X=[x1,x2,…,x n ]T----------n维向量 min F(X)=[f1(X),f2(X),…,f n(X)]T----------向量形式的目标函数s.t. g i(X)≤0,(i=1,2,…,m) h j(X)=0,(j=1,2,…,k)--------设计变量应满足的约束条件多目标优化问题是一个比较复杂的问题，相比于单目标优化问题，在多目标优化问题中，约束要求是各自独立的，所以无法直接比较任意两个解的优劣。 二、多目标优化中几个概念：最优解，劣解，非劣解。 最优解X*：就是在X*所在的区间D中其函数值比其他任何点的函数值要小即f(X*)≤f(X)，则X*为优化问题的最优解。 劣解X*：在D中存在X使其函数值小于解的函数值，即f(x)≤f(X*), 即存在比解更优的点。 非劣解X*：在区间D中不存在X使f(X)全部小于解的函数值f(X*). 如图：在[0,1]中X*=1为最优解 在[0,2]中X*=a为劣解 在[1,2]中X*=b为非劣解 多目标优化问题中绝对最优解存在可能性一般很小，而劣解没有意义，所以通常去求其非劣解来解决问题。 Pareto: In the single objective case, one attempts to obtain the best solution, which is absolutely superior to all other alternatives. 在单目标的情况下，一个试图以获得最佳的解决方案，这是绝对优于所有其他的替代品。 In the multiple objective case, there does not necessarily exist a solution that is best with respect to all objectives because of incommensurability and conflict among objectives. 在多个目标的情况下，不存在必然存在着一个解决方案，最好是不可通约性和目标之间的的冲突，因为所 有的目标。 There usually exist a set of solutions; nondominated solutions or Pareto optimal solutions, for the multiple objective case which cannot simply be compared with each other. 通常存在的一整套解决方案;非支配的解决方案或帕累托最优的解决方案，为多个目标的情况下，不能简单 地互相比较。 For a given nondominated point in the criterion space Z, its image point in the decision space S is called efficient or noninferior. A point in S is efficient if and only if its image in Z is nondominated. 对于一个给定的的标准空间z的非支配点，其形象在决定空间S点是所谓的效率或劣。非支配当且仅当其 在Z的形象是一个S点是有效的。 Definition 1: For a given point z0€Z, it is nondominated if and only if there does not exist another point z€Z such that, for the maximization case,where, z0 is a dominated point in the criterion space Z. Definition 2: For a given point x0€S, it is efficient if and only if there does not exist another point x€S such that, for the maximization case,where, x0 is inefficient.定义1：对于一个给定的点Z0属于Z，它非支配当 且仅当不存在另一点于属于z的，最大化的情况下，其中，Z0是在标准空间Z.的主导点 定义2：对于一个给定的点x0属于S，它是有效的当且仅当不存在另一点x属于S，最大化的情况下，其 中，X0是低效的。 Example 1: Two-objective (bicriteria) linear programming 例1：两个目标（bicriteria）线性规划 m ax We can observe that both regions are convex and the extreme points of Z are the images of extreme points of S. 我们可以观察到，这两个地区是凸的并且极端点的Z是极值点S的的图像。 The extreme points in the feasible region S of the decision space are shown in Fig. 4.1: 在可行区域的决策空间小号的极端点如图.4.1： 多目标优化的求解方法 多目标优化(MOP)就是数学规划的一个重要分支,就是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下: 多目标优化方法本质就是将多目标优化中的各分目标函数,经处理或数学变换,转变成一个单目标函数,然后采用单目标优化技术求解。目前主要有以下方法: （1）评价函数法。常用的方法有:线性加权与法、极大极小法、理想点法。评价函数法的实质就是通过构造评价函数式把多目标转化为单目标。 (2)交互规划法。不直接使用评价函数的表达式,而就是使决策者参与到求解过程,控制优化的进行过程,使分析与决策交替进行,这种方法称为交互规划法。常用的方法有:逐步宽容法、权衡比替代法,逐次线性加权与法等。 (3)分层求解法。按目标函数的重要程度进行排序,然后按这个排序依次进行单目标的优化求解,以最终得到的解作为多目标优化的最优解。 而这些主要就是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法与蚁群算法、模拟退火算法及人工免疫系统等。 在工程应用、生产管理以及国防建设等实际问题中很多优化问题都就是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其她若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少与总的运输费用最低, 这就是含有两个目标的优化问题。利用首次适配递减算法与标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合 第六章 最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值 2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法 4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法 5．5 投资收益风险问题 第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X 表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设 Pareto图（柏拉图&排列图）详细制作教程 Hello，大家好！小编又来给大家写教程啦……如何直观表达问题的主要影响因素，亦或者展现主要收入来源呢？通常我们习惯性的会使用“二八定律”，筛选出80%的原因。今天给大家介绍Pareto图（柏拉图&排列图）就可以清晰直观的表达，小编也是经常会使用到。例子如下：从图中可以直观看出80%的原因是由于划伤、松脱、异响、生锈引起的，如果这张图给领导看，是不是很清晰呢？第一步首先建立一个如下的表格：注：“不良数”这一列按照从大到小的降序排列，“百分比”这一列是每一个“不良原因”占总不良数的百分比，“累积百分比”是从第一个不良原因的百分比依次累加而得。 第二步选中“不良原因”，“不良数”，“累积百分比”，插入柱状图，再选中“累积百分比”这个系列的柱状图，调整为次坐标轴，并更改图表类型为折线图。接着我们来设置左边坐标轴（主坐标轴）和右边坐标轴（次坐标轴）的刻度，使折线图的点在柱状图的顶端。具体设置为：主坐标轴最大值改为不良数的总数（例子为102），最小值设为0；次坐标轴最大值改为1（也就是100%），最小值设为0。至此，柏拉图基本成型了，接下来再进行一些调整，美化图表。第三步将图表布局调整一下，再将柱状图中的柱子每一个调整到一起，并且添加数据标签，图形就更加的直观了。最后为了更加直观， 可以设置每一个柱子的颜色，将数据标签调整到合适的大小和位置即可。小编调整出来的就是教程开头那样，再来看下：划重点：利用EXCEL制作柏拉图，主要是要利用次坐标轴将数据分开，再进行一些调整，原始表格需要按照一定的要求整理出来。第四步等等！教程开头有两个图，另外一个图是怎么制作出来的呢？由于EXCEL制作还是太复杂了，作为一个懒人小编，肯定还有更好的办法，再这里就给大家推荐一个软件，叫做Minitab，这是一个统计软件，制作柏拉图，简直so easy！来看下软件的界面：我们如何用Minitab 来制作柏拉图呢？按照上面界面图里，将“不良原因”和“不良数”相对应的填写到表格里（不用按照降序或者升序排列），具体路径如下：统计→质量工具→Pareto图做出来的图形可以直接复制黏贴到PPT或者EXCEL里，并且图形里的文字、图形的颜色均可以调整。相比较EXCEL，方便多了，而且图形下面多了一列“百分比”。小编平时会写一些办公软件（EXCEL/PPT）、PS、视频制作的教程，小编很懒，所以就会去摸索一些“懒人”的方法来提高工作效率，如果能得到您的关注，非常感谢…… 第六章最优化数学模型 §1最优化问题 1．1最优化问题概念 1．2最优化问题分类 1．3最优化问题数学模型 §2经典最优化方法 2．1无约束条件极值 2．2等式约束条件极值 2．3不等式约束条件极值 §3线性规划 3．1线性规划 3．2整数规划 §4最优化问题数值算法 4．1直接搜索法 4．2梯度法 4．3罚函数法 §5多目标优化问题 5．1多目标优化问题 5．2单目标化解法 5．3多重优化解法 5．4目标关联函数解法 5．5投资收益风险问题 第六章最优化问题数学模 §1最优化问题 1．1最优化问题概念 （1）最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值； ②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。 一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为x1,x2, , x n ；我们常常也用X （x1,x2, ,x n）表示。 3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设 第六章最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法5．5 投资收益风险问题 第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X =表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。 用数学语言描述约束条件一般来说有两种： 等式约束条件 m i X g i ,,2,1,0)( == 不等式约束条件 r i X h i ,,2,1, 0)( =≥ 或 r i X h i ,,2,1, 0)( =≤ 注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件0)(>X h 或0)( 多目标优化方法 基本概述几个概念优化方法 一、多目标优化基本概述 现今，多目标优化问题应用越来越广，涉及诸多领域。在日常生活和工程中，经常要求不只一项指标达到最优，往往要求多项指标同时达到最优，大量的问题都可以归结为一类在某种约束条件下使多个目标同时达到最优的多目标优化问题。例如：在机械加工时，在进给切削中，为选择合适的切削速度和进给量，提出目标：1)机械加工 成本最低2)生产率低3)刀具寿命最长；同时还要满足进给量小于加工余量、刀具强度等约束条件。 多目标优化的数学模型可以表示为： X=[x i,x 2,…,x n ] T ---------------------------------- n 维向量 min F(X)=[f i(X),f 2(X),…,f n(X)] T- --------- 向量形式的目标 函数 s.t. g i(X) < 0,(i=1,2,…,m) h j (X)=0,(j=1,2,…,k) ------ 设计变量应满足的约 束条件 多目标优化问题是一个比较复杂的问题，相比于单目标优化问题，在 多目标优化问题中，约束要求是各自独立的，所以无法直接比较任意两个解的优劣。 二、多目标优化中几个概念：最优解，劣解，非劣解。 最优解X*:就是在乂所在的区间D中其函数值比其他任何点的函数值要小即f(X *) 如图：在［0,1］ 中 X*=1为最优解 在［0,2］ 中X*=a为劣解 在［1,2］ 中X*=b为非劣解 多目标优化问 题中绝对最优解存 在可能性一般很 小，而劣解没有 意义，所以通常去 求其非劣解来解决 问题。 三、多目标优化方法 多目标优化方法主要有两大类： 1)直接法：直接求出非劣解，然后再选择较好的解 将多目标优化问题转化为单目标优化问题。 2)间接法女口：主要目标法、统一目标法、功效系数法等。 将多目标优化问题转化为一系列单目标优化问题。女口：分层系列法等。 1、主要目标法 求解时从多目标中选择一个目标作为主要目标，而其他目标只需满足一定要求即可，因此可将这些目标转化成约束条件，也就是用约束条件的形式保证其他目标不致太差，这样就变成单目标处理方法。 例如：多目标函数f 1(X),f 2(X),.?…,f n(X)中选择f k(X)作为主 要目标，这时问题变为求min f k(x) D={x|f min < f i(X)< f ma》,D为解所对应的其他目标函数应满足上下限。 2、统一目标法 通过某种方法将原来多目标函数构造成一个新的目标函数，从而将多目标函数转变为单目标函数求解。 ①线性加权和法 根据各目标函数的重要程度给予相应的权数，然后各目标函数与 活用柏拉图(Pareto Chart) 一何谓柏拉图 意大利经济学家柏拉图于1897年在研究国民所得时发现，大部分所得集中于少数几个人，而创出此法，故命名为柏拉图。 柏拉图的功用： 柏拉图在应用时假设：发生不良的原因有很多，但影响较大的只有一项、二项，不会超过三项，而此三项就占全部不良之60%~80%，只要能找出此三项关键点，就容易获得解决及改善，柏拉图就是找出此三项(关键的少数)的方法，80/20法则亦是指柏拉图之意。 二柏拉图的作法 要作柏拉图分析之前，必先设计好查检表，并收集数据，今以某零件之不良为例加以说明： 履历：(略) 1步骤一：将上列查检表之数据往右加，求出合计并记录于该查检表合计栏上。 2 2.1由合计栏数据最多者开始排列(排行榜)，但其它项必须在最末。 2.2将各项合计不良数除以总检查数，求出各项不良率并填入不良率栏内。 2.3将各项不良率逐项累计并填入累计不良率栏内。 2.4将各项不良数除以总不良数，求出影响度并填入影响度栏内。 2.5将各项影响度逐项累计并填入累计影响度栏内。 3步骤三：作图 4步骤四：结论 根据柏拉图分析，累计影响度占89.4%的前3项是：A.毛边、B.偏心C.内孔粗糙。因此，要将此3项作为分析改善的重点。 三制作柏拉图应注意之事项 1一定依数据大小开始排列，但其它项一定排在最末项。 2如果其它项数据太大时(与各项相对比较而论)，应将“其它项”细分出一个或数个较显着的项目来。 3左边之纵轴，必要时，应以损失金额表示。 4如用于改善前后柏拉图比较时，不应上下排列，应左右排列以利比较，此时，改善后柏拉图的左纵轴刻度应与改善前柏拉图的左纵轴一致，以利比较改善效果。 Pareto 图――解读 第 1 页 共 1 页 Pareto 图――解读 Pareto 图 Pareto 图将缺陷按影响从大到小分成若干等级，可帮助您将“少数严重”问题从“多数细小”问题中区分出来。 右侧的 Y 轴显示了合计缺陷的百分比，左侧的 Y 轴显示了缺陷的计数。红线表示累积百分比，可帮助您判断每个类别的额外贡献。直方图的条形显示每个类别的计数（和总计百分比）。为每个类别列出了计数、百分比和累计百分比。如果 Pareto 图中的最后一组标记为“其他”，则默认情况下它将包含其缺陷数小于总缺陷数 5% 的类别的所有缺陷数。在本例中，45.2% 的缺陷归因于缺少纽扣，23.3% 的缺陷归因于缝纫错误。缺少纽扣和缝纫错误的累计百分比为 68.5%，因此集中精力解决纽扣缺失和缝纫问题可使整个制衣过程得到最大程度的改进。 数据说明：一家服装制造商跟踪了一个服装系列的缺陷数量和类型。 Pareto 图的局限：Pareto 图容易理解和使用，但它存在一些需要注意的局限： ?在较短时间内收集的数据，特别是从不稳定过程收集的数据可能导致错误的结论。由于数据不可靠，因此获得的缺陷和原因分布图有可能不正确。当过程不受控制时，原因系统可能不稳定。少数严重问题可能每周都在变化。时间太短可能代表不了整个过程。 ?较长时间内收集的数据可能包含一些变化。检查数据以确定问题分布中随时间出现的分层或变化。 ?慎重选择类别。如果最初的 Pareto 分析没有获得有用的结果，则您可能需要确保类别是有意义的，而且“其他”类别没有过于庞大。 ?慎重选择加权标准。例如，对于确定优先顺序而言，成本可能比出现次数更有用，尤其是当各种缺陷的成本各不相同时。 ?重点解决出现频率最高的问题应该能够减少需要返工产品的总数。重点解决成本最高的问题应该能够增加改进的财务收益。 ?Pareto 分析的目标是从质量改进中获得最大程度的收益，但这并不意味着在解决较大问题之前可以忽略容易解决的小问题。 加权 Pareto 图：通过为缺陷指定属性（例如，成本、严重性或可检测性），可以为计数加权。加权 Pareto 图有助于您识别高成本缺陷很少发生的情况。加权 Pareto 图可能不会指向相同的错误或问题，而基于频率的 Pareto 图则可能会。下面的加权 Pareto 图使用了与主要 Pareto 主题中介绍的制衣数据相同的数据，但不同之处在于缺陷已被加权（将每种缺陷类型的成本与缺陷类型的数量相乘）。此处可以看到缝纫错误现在占到了总缺陷成本的 30.5%。在未加权的 Pareto 图中占缺陷的 45.2% 的缺少纽扣的问题现在只占总缺陷成本的 5.3%。 80/20 原则：Pareto 图（因意大利经济学家 Vilfredo Pareto 而得名）是 80/20 原则的图形表示。Pareto 注意到意大利的财富分配中存在这样一种模式：80% 的财富由 20% 的人所占有。其他领域同样存在这样的原则，即 80% 的结果往往来自 20% 的原因。例如，80% 的投诉往往来自 20% 的客户。 多目标优化的求解方法 多目标优化（MOP）是数学规划的一个重要分支，是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下： 多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。目前主要有以下方法： （1）评价函数法。常用的方法有:线性加权和法、极大极小法、理想点法。评价函数法的实质是通过构造评价函数式把多目标转化为单目标。 （2）交互规划法。不直接使用评价函数的表达式，而是使决策者参与到求解过程，控制优化的进行过程，使分析和决策交替进行，这种方法称为交互规划法。常用的方法有：逐步宽容法、权衡比替代法，逐次线性加权和法等。 （3）分层求解法。按目标函数的重要程度进行排序，然后按这个排序依次进行单目标的优化求解，以最终得到的解作为多目标优化的最优解。 而这些主要是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法和蚁群算法、模拟退火算法及人工免疫系统等。 在工程应用、生产管理以及国防建设等实际问题中很多优化问题都是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其他若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少和总的运输费用最低, 这是含有两个目标的优化问题。利用首次适配递减算法和标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合应用于汽车零件多工序冷挤压工艺的优化。Chung等人也成功应用遗传算法对锻件工艺进行了优化。 3)投资 假设某决策部门有一笔资金要分配给若干个建设项目, 在确定投资方案时, 决策者总希望做到投资少收益大。Branke等人采用基于信封的多目标进化算法成功地解决了计划投资地选择问题。 4)模拟移动床过程优化与控制 一个工业化模拟移动床正常运行时, 一般有七股物料进、出吸附塔, 其中起关键作用的物料口将作为决策量引起目标值的变化。根据实际生产要求通常包括生产率、产品纯度、吸附剂消耗量等多个目标。模拟移动床分离过程由于其过程操作变量的强耦合性、工艺机理的复杂性及分离性能的影响因素繁多性, 需要众多学者对其操作优化和过程控制进行深入的研究。Huang等人利用TPS 算法解决了模拟移动床多个冲突目标的最大最小的问题, 并与NSGA2 算法的结果进行了比较。吴献东等人运用粒子群算法开发出一种非线性模拟移动床( SMB )色谱分离过程的优化策略。 5)生产调度 在离散制造生产系统中, 一个工件一般经过一系列的工序加工完成, 每道工序需要特定机器和其他资源共同完成, 各工件在各机器上的加工顺序(称技术约束条件)通常是事先给定的。车间调度的作用 华东师范大学 硕士学位论文 广义Pareto分布 姓名：南新艳 申请学位级别：硕士专业：概率论与数理统计指导教师：王静龙 20050501 摘要 从Ｐａｒｃｔｏ分布的诞生到现在已有１５０多年的历史了．随着时间的推移、社会的发展，Ｐａｒｃｔｏ分布也在不断地完善、改进、推广，从而形成了多种形式的Ｐａｒｃｔｏ分布、广义Ｐａ＿ｒｃｔｏ分布乃至Ｐａｒｅｔｏ分布族．Ｐａｒｃｔｏ分布族由于其具有的优良性质得到诸多学科研究者的青睐．本文首先对Ｐａｒｅｔｏ分布的发展作了简单的介绍，并介绍＿ｒＰａｒｃｔｏ分布族在经济学、社会学、环境学、保险精算学中的广泛应用．Ｐａｒｅｔｏ分布族中的两个分布已被列入精算师常用的八大分布之中，由此可见Ｐａｒｅｔｏ分布族的实际应用价值，也说明了我们对Ｐａｒｃｔｏ分布族研究的重要意义． 本文第二章分别介绍了Ｐａｒｅｔｏ分布族中各个分布的密度函数、矩、众数、Ｆｉｓｈｅｒ信息阵、次序统计量、参数估计等一些性质，并介绍了Ｐａｒｃｔｏ分布族内各个分布之间以及它们与其它分布之间的相互关系．从而可以比较清楚地了解到Ｐａｒｃｔｏ分布族中的各个分布是如何发展而来的，它们之间有何关系，它们之间有什么区别．同时还可以了解到Ｐａｒｅｔｏ分布族中的各个分布与均匀分布、Ｆ分布、Ｂｃｔａ分布以及ｚ分布之间的关系．第三章是本文的重点。也是本文的重要创新之处．本章主要包括四部分内容，第一部分主要描述广义Ｐａｒｅｔｏ分布的一些基本性质，给出广义Ｐａｒｃｔｏ分市的两种特殊形式，并对广义Ｐａｒｅｔｏ分布的一些数字特征进行研究．用图的形式描述了不同参数取值对分布形状及位性的不同影响，当参数ｐ取正整数时，采用数学归纳的方法推导出广义Ｐａｒｃｔｏ分布的分布函数，这是本文的创新点之一．第二部分主要是参数的估计，包括矩估计、极大似然估计、区间估计，以及基于正态逼近的一些推断．本文证明了矩估计和极大似然估计的同变性，这是本文的又一创新点．对次序统计量的部分相关性质也作了研究．第三部分主要研究假设检验，区间估计是一种参数的估计方法但同时也是一种参数假设检验的方法，该部分对区间估计的检验方法进行了探讨．似然比方法足很重要的一种假设检验方法，同样在本文中似然比检验方法发挥了其强大的威力．第四部分主要讨论了广义Ｐａｒｃｔｏ分布在实际中的应用，并通过棒球运动员收入的例子和飓风损失的例子进行了说明． ５ Pareto 分布――2010-2-6 Pareto 分布： 由意大利的经济学家economist Vilfredo Pareto发现的，它是一个冥指概率分布，与社会学、自然科学、地球物理学及精算及其他许多可以观察到的现像相一致，在经济领域它有时也叫Bradford distribution(布拉福德分布)。 Pareto分布常用于描绘在社会中财富的分布情况，因为任何社会中，社会中大量的财富是被少数人所掌握着的。这个道理可以简单的理解为 Pareto原理或者是： 80－20原理，也就是说：20％的人控制着一个社会 80％的财富。从图1 Pateto分存的概率密度函数(probability density function，简记为 pdf)图可以看出，拥有少量财富的人口占总人口的相当一大部分，拥有大量财富的人所占的比率是趋于稳定的很小一部分，Pareto 分布不只局限于描述财富，同样可以用于很多拥有这样情形的场合：从 small小分布到 large大分布要寻找一个平衡点，比如下面出现的情形可以近似看作为 Pareto分布： (1)The sizes of human settlements (few cities, many hamlets/villages) (2)File size distribution of Internet traffic which uses the TCP protocol (many smaller files, few larger ones).(这个要注意， 重点研究对像) (3)Clusters of Bose–Einstein condensate near absolute zero (4)The values of oil reserves in oil fields (a few large fields, many small fields) (5)The length distribution in jobs assigned supercomputers (a few large ones, many small ones) (6)The standardized price returns on individual stocks (7)Sizes of sand particles (8)Sizes of meteorites (9)Numbers of species per genus (There is subjectivity involved: The tendency to divide a genus into two or more increases with the number of species in it) (10)Areas burnt in forest fires (11)Severity of large casualty losses for certain lines of business such as general liability, commercial auto, and workers compensation.MOP多目标规划
多目标线性规划的若干解法及MATLAB实现
柏拉图(Pareto Chart)
决策理论和方法习题
施工管理多准则决策模型实例分析
多目标优化问题
多目标规划帕累托解算例
多目标优化的求解方法
多目标最优化模型
Pareto图(柏拉图
多目标最优化模型
多目标最优化数学模型
多目标优化问题
活用柏拉图(Pareto Chart)
Pareto 图――解读
多目标优化的求解方法
广义Pareto分布
Pareto 分布