数学建模社区-数学中国

标题: 多目标优化算法简介(zz) 1 [打印本页]

---

作者: renew    时间: 2006-6-16 22:50
标题: 多目标优化算法简介(zz) 1
实际的工程优化问题大多数是多目标优化问题，目标之间一般都是互相冲突的。多目标优化很早就得到了人们的重视，到目前已经发展了较多的求解多目标优化的方法。下面先介绍多目标优化最重要的关于非劣解以及非劣解集的定义。
定义1：若 （ 为多目标优化的可行域），不存在另一个可行点 ，使得 成立（ 为目标数），且其中至少有一个严格不等式成立，则称 是多目标优化的一个非劣解（Noninferior Solution）。所有非劣解构成的集叫非劣解集（Noninferior Set）。
" S# M* W6 e. U7 l& l" @3 S4 i( M一个多目标优化如果存在非劣解，往往存在无穷多个，形成非劣解集。在求解实际问题时，过多的非劣解是无法直接应用的。决策者只能选择令其最满意的一个非劣 解作为最终解。求最终解主要有三类方法，一类是求非劣解的生成法，即先求出大量的非劣解，构成非劣解的一个子集，然后按照决策者的意图找出最终解，另一类 . O7 f" ~ ^: K, L' b/ D8 p为交互法，不先求出很多的非劣解，而是通过分析者与决策者对话的方式，逐步求出最终解。最后一类是事先要求决策者提供目标之间的相对重要程度，算法以此为 : y1 n) r) i0 C& G/ X* N依据，将多目标问题转化为单目标问题进行求解，该类方法也可以被认为是第一类方法的一个子方法，该类方法的难点在于，如何得到决策者真实的权重信息，本章 U# [0 `% O, F# ]将提出一种基于模糊逻辑的，能比较好反映决策者权重的多目标遗传算法。
' O) P9 S9 o7 U5 {4 [0 {( s: v生成法主要有加权法﹑约束法﹑加权法和约束法结合的混合法以及多目标遗传算法。而交互法主要有用于求解线性约束多目标优化的Geoffrion法﹑求解线性多目标优化的逐步法（STEM）和Zionts-Wallenius方法以及代替价值交换法。
作者认为相对而言生成法对决策者更有吸引力，首先目前没有比较好的多目标非线性优化的交互法，其次在只给决策者有限信息的前提下，往往要求决策者回答一些 ) V! F. [7 K3 l似是而非的问题，决策者在交互过程中将会很被动，也就是说交互法在某种程度上将问题的矛盾转嫁给了决策者。如果我们能求得非劣解的一个较好的近似解集，决 , V" w1 P0 n, w" N3 O% V4 _策者就有了一个对问题比较全面的认识，从而能更好地进行决策和折衷。
生成法中，常用的加权法有其固有的缺点，对于非劣解集的某些区域不可能求出。如图4.1就是一个两个目标的例子，箭头所指非劣解曲线凹的部分无法用加权法 / a- f& M5 \3 ~1 Z# w求出，出现该现象的原因是，加权法实际上是优化各个目标函数正线性组合而成的单个目标。即采用正加权系数计算的单目标最优必然是非劣解，而某些非劣解可能 : ?0 w9 i, a& r- X找不到一组正加权系数来进行求解。采用约束法可以避免该现象，但是计算代价过大，且过程很繁杂，应用前景也不乐观。利用多目标遗传算法求解非劣解集是最近 . J( s" Z( |( f几年新出现的一种求解思路，目前还处在研究
# X6 B8 L+ c* o / E8 x8 z( m5 B, f. q' p
: w; f7 h: d/ ] % r+ v9 d ^; D4 z) s
7 n" z; U/ F/ A) _4 H, S' ^: M
) H4 _( C: ~1 k! I! u, X, [

0 Z$ y5 Q2 g2 D2 k& X : \% m0 V8 ~% m! j7 c! y* w
+ x W' S; t" o# r! E$ T
% J% ]( L( q. W' S. o图4.1 加权法无法求出全部非劣解的例子
的初始阶段，但是初步的计算结果非常令人振奋，故本章另一个研究重点就放在了多目标非劣解集算法的研究上。
c* v, k/ E* B* |5 v§4.2基于模糊逻辑的多目标遗传算法
§4.2.1 模糊逻辑简介
模 糊逻辑（Fuzzy Logic）是一种新型的分类方法（分类是集合论的基本概念之一）。模糊逻辑模仿人类的智慧，引入隶属度的概念，描述介于“真”与“假”中间的过渡过程。 在模糊逻辑中，事件不以集合的极限值分类，而是给每一个元素赋予一个介于0和1之间的实数，描述其属于一个集合的强度。具体的介绍可以参考文献 b- @+ u4 }! [; m4 K【116】。
2 r5 U& B- t; C$ q4 \' C§4.2.2 基于模糊逻辑的多目标遗传算法的思路和具体实现
通过前面的介绍，我们知道采用模糊逻辑是一种很好的反应决策 者主观意愿的工具。可以用模糊逻辑的方法反应决策者对于各个目标之间重要性的“权衡”信息。众所周知，遗传算法是依据个体的适应度进行，可以认为适应度就 是决策者对于个体的综合评价，因而可以依据模糊逻辑的方法，直接构造决策者对于遗传个体的适应度的取值，即决策者对个体的综合评价。并以此作为遗传进化的 % a' R; S) Y, w依据和动力。下面是初步的算法步骤：
% U9 o% U& a( f% J% W. w0 G（1）分别求出各单目标的最优解；
& x6 k3 }4 l9 z（2）以（1）中的单目标的最优解和决策者协商，给出各个目标满意度的隶属函数；
（3）通过模糊逻辑表达决策者的想法，将各目标的满意度和个体的适应度联系起来；
. Z- }. y7 R" Q/ O2 Q9 k8 i& g$ C, n（4）以（3）定义的适应度为基础采用遗传算法进行求解；
之所以首先求解各个单目标的最优解，是希望能给决策者一个比较清晰的概念，即如果单独优化某个目标，可能的最优解是多少。有了这个信息，决策者才能给出令人置信的关于不同目标的满意度的隶属曲线。如果求解单目标优化的难度很大，也可以给出对单目标最优的一个估计值。
6 c" j& @/ k- \; w( c5 e6 @具体的计算方法和模糊控制的计算方法基本相同，也分为模糊化（Fuzzification）﹑模糊推理（Fuzzy-Inference）和去模糊化 + g- X( b' Y) h B ]（Defuzzification）三部分组成。在作者算法中，模糊推理采用的是最大最小法，而去模糊化采用的是面积重心法。详见参考文献【116】。
$ G- U; n( A( j. t- x下面以十杆桁架双目标优化为例详细叙述算法过程。
3 E. _& Q9 \$ z0 n- T0 _参考图3.4，位移目标是指节点1﹑2﹑3﹑4的最大 向位移最小。这里最大 向位移指的是绝对值最大。
这样我们就有了两个目标，即同时极小化位移和重量，可以建立比较简单的模糊逻辑如下：
, d- g. U/ c9 P# T0 P+ H: U* d（1）如果重量轻并且位移小那么设计的适应度高；
/ C! t& z1 Z- n+ [# Q O3 u6 T8 K: ~显然上式同时对两个目标都提出了要求。而如果我们只关心重量则可以建立如下的模糊逻辑：
（2）如果重量轻不管位移大或小设计的适应度都应高；
% V/ X) i0 J5 l9 [9 [1 e我们可以将模糊逻辑表示得更加精细，更符合决策者实际的想法：
（3-1）如果重量轻而且位移小那么设计的适应度很高；
（3-2）如果重量轻而且位移中等那么设计的适应度高；
（3-3）如果重量轻而且位移大那么设计的适应度一般；
. E# C0 p0 }1 O: j* g S（3-4）如果重量中等而且位移小那么设计的适应度高；
（3-5）如果重量中等而且位移中等那么设计的适应度中等；
（3-6）如果重量中等而且位移大那么设计的适应度低；
（3-7）如果重量大而且位移小那么设计的适应度中等；
. p' i! `( M: ?4 b8 O（3-8）如果重量大而且位移中等那么设计的适应度低；
9 s& ~( s* F- Y6 n: X) Q* f（3-9）如果重量大而且位移大那么设计的适应度很低；
/ h, N2 _2 \0 [2 U9 M, [我们可以建立相应的表格表示以上逻辑：
重量
位移
→ ' X! }, i: F+ P设计适应度
/ a6 `% f+ b' \' SGood
Good
→ 8 T& C7 E0 Y/ ~5 OVery High
Good
Normal
→ High
Good
Bad
→ " z9 d6 E% f& _; lNormal
* ]! X: I0 n9 X" J. l; `" o+ @4 SNormal
Good
→ High
Normal
Normal
→ $ t* I8 `) v0 m% |; N; e% b1 gNormal
Normal
Bad
→ Low
2 i- H% O. F, l' W! ^Bad
Good
→ * K/ N) o) J, _" ]; p b9 s! LNormal
Bad
Normal
→ & j6 Q8 T4 s8 T* i5 E( gLow
) K" z5 ]9 p/ B4 a/ l g% dBad
Bad
→ Very Low
表4.1 模糊逻辑表
+ e( m6 ~) b; O7 t6 ~! X采用模糊逻辑的方法实际上将目标函数映射到决策者的效用函数上，一般来说决策者的效用函数的精确描述是很困难的，目前多目标优化研究的一个重要领域就是如 - r. X! n9 t3 p# T何合理构造决策者的效用函数。但是要决策者用带有模糊性的语言对自己的偏好加以描述却比较容易的。采用模糊逻辑的另外一个优点就是，决策者可以直观地观察 到自己如果改变了模糊逻辑后，决策的变化。即求出的解始终是与决策者的真实想法接近的。在非劣解集范围较大的情况下，采用模糊逻辑可能是唯一实际可行的办 9 C/ [' N: M5 j法。
0 j7 U( j* S- v6 k: e§4.2.3 算例
在上一章已经求得十杆问题的最轻重量为1598.93lb，相应的最大位移为7.171639 ，我们也可以求得最小位移为0.977492 ，相应的最大重量为15349.4496 。下面是是位移最小和重量最轻的设计点的比较。
; n; f/ H$ O4 u! Q 4 b7 T& N- F+ Y! q+ L# p% y位移最小设计（ ）
最轻设计（ ）
) R, S6 o6 \& U6 x' T g杆1
40.0000
7.9396
杆2
40.0000
0.1
杆3
40.0000
8.0956
: R' M/ r6 z2 u7 _杆4
40.0000
3.9613
杆5
0.1
0.1
: u# h, Y5 Q, s' \( [; ?杆6
40.0000
0.1
* ?; O) e* ]" y# }- z% [( W+ l杆7
40.0000
5.7554
杆8
40.0000
5.5994
杆9
40.0000
5.5994
/ f# W3 E/ K$ ?4 v2 C ?9 w杆10
40.0000
0.1
% ?* c7 e8 ^" T4 Z7 P5 r" t2 y( r重量（ ）
15349.4496
1598.93
7 c( S' y- u% m# z位移（ ）
0.977492
7.171639
, ?1 F% ]4 {3 Q1 [8 z/ L5 Q* M3 n 表4.2
' P7 z% J+ A2 X/ a2 J( \5 N0 `从上表可以很明显地看出，位移和重量是两个互相冲突的目标。
^5 x3 U7 L, n) E7 Z% d3 }在已知单目标极值的情况下我们采取一简单的模糊逻辑来确定个体的适应度，如果重量轻并且位移小那么适应度高。

---

作者: yicol    时间: 2006-10-24 22:11
怎么看不到图表

---

作者: shy_ness    时间: 2010-4-13 22:20
不懂              麻烦楼主解释清楚啊

---

作者: gssdzc    时间: 2010-6-15 00:12
非常感谢分享

---

作者: adamxz    时间: 2010-7-9 16:33
无图表，很伤心了

---

作者: mvmmvmmvm    时间: 2010-8-13 22:32
这是从哪儿抄来的？

---

作者: yellowaug    时间: 2010-8-14 09:48
哪转的啊？

---

作者: yi635897086    时间: 2011-12-17 14:03
学习了。。   

---

作者: 易Style    时间: 2012-4-10 22:00
ddddddddddddddddddddd

---

作者: 494515326    时间: 2013-4-29 17:55
dddddddddddd

---

作者: mattee444    时间: 2013-7-11 00:07
谢谢楼主的分享

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5