间隔指标(spacing)
1 n (d d i ) 2 n 1 i 1
s
评价： 衡量解集的分布性。
S
MOPSO
SPEA
SOEA
Best
0.1200
0.1148
0.1675
Worst
0.1272
0.1599
0.1675
Mean
0.1228
0.1336
0.1675
Std
0.0026
TSC
Mopso: Spea
Mopso: Soea
Spea: Mopso
Soea: Mopso
Best
1.0
1.0
0.0114
0.0
Worst
0.8939
0.0
0.0
0.0
Mean
0.9710
1.0
0.0036
0.0
Std
0.0387
0.0
0.0056
0.0
Median
0.9857
1.0
0.0
0.0
3.2 一种多目标粒子群优化算法实例
3.2.1 自适应角度分区方法 提出了一种自适应角度 f 2 分区算法，该方法通过计 算档案中成员在目标空间 中的范围，调整角度分区 以覆盖档案中的所有成员。 通过角度分区对目标空间 中不同区域的拥挤程度进 行动态跟踪，以维护外部 档案的空间分布性。
a
b
i

particles
n id n 1 1 n id n id n 2 2 n gd n id
◆ PSO种群中任一粒子i的位置
x
n 1 id
x
n id
v
n 1 id
3.2 一种多目标粒子群优化算法实例
算法使用一个存储非劣解的精英档案，该 档案有两个作用。首先，它存储和更新粒子群 每轮迭代搜索到的所有非劣解集，在迭代结束 后，档案中的成员即为算法整个生命期搜索到 的非劣解集。其次，档案通过对当前非劣解前 沿的近似估计，从而辅助算法从档案中选择粒 子速度更新的全局极值。后者提供了选择压力， 通常促使粒子向多目标问题的全局非劣解前沿 方向搜索。如果没有这个过程，算法就不能分 辨好的和坏的解点，导致粒子在目标搜索空间 中漫无目的的飞行。
演讲主题
多目标问题及多目标进化算法研究
基于粒子群的一种多目标优化算法
报告人： 蒋庆 2004级博士研究生
演讲主题
1. 多目标优化问题 2. 多目标进化算法 3. 多目标粒子群优化算法实例
主题一
1 多目标问题(Multi-Objective Problem) 1.1 什么是多目标问题 1.2 多目标问题的特点 1.3 怎样才算多目标问题的最优解
1.3.2.3 Pareto最优前沿(Pareto optimal front)
数学定义： 对于一个多目标问题的Pareto 最优解矢 量X,则Y=(f1(X)),…,fk(X))为X的Pareto前沿. 所有的Pareto 最优前沿称为Pareto 最优前 沿集。
1.3.2.3 Pareto最优前沿(Pareto optimal front)
在许多复杂应用问题中搜索最优解还存在一定的 困难。
2.2 多目标进化算法的通用算法过程
输入：基于多目标函数自变量矢量编码的种群 输出： 多目标优化解集 Step1: 初时化种群 Step2: 适应值评价 Step3: 进化算子操作，生成新的种群 a) 选择算子(Selection) b) 组合算子(Recombination) c) 交叉算子(Mutation) Step4: 如果满足终止条件，结束算法迭代，否则转到Step2.
3.2.2 粒子更新策略
采用动态设置全局极值的方法，在每次迭代时， 采用如下公式动态生成全局极值。
p Random( p , t )
i ,c t i,g t
i i i i i ,c i v wv c R ( p x ) c R ( pt x ) t 1 t 1 1 t t 2 2 t
主题二
2 多目标进化算法(Multi-Objective Evolutionary algorithm)
2.1 进化算法求解多目标优化问题的优势 2.2 多目标进化算法的通用算法过程 2.3 多目标进化算法关键研究领域
2.1 进化算法求解多目标优化问题的优缺点
每轮迭代可以找到多个Pareto近似最优解 迄今为止还没有找到其他方法比EAs更能有效地 解决MOP问题。
y ( y1 , y2 ,..., yk ) Y
1.2 多目标问题的特点
具有多个目标函数。 各个函数之间在最优化方向上存在冲突。 往往需要人的参与。 目标函数集要么是求极大，要么是求极 小，两者只能取其一。
1.3 怎样才算多目标问题的最优解
1.3.1 由人来判断（非Pareto机制） 基本原则：通过加入决策者判断，缩小多 目标问题有效解集的范围。
3.1 粒子群优化算法介绍
Step1: 初时化粒子群的速度和位置 Step2: 适应值评价 Step3: 更形粒子群的速度和位置，从而生 成下一代粒子群 Step4: 如果没有达到终止条件转到Step2。
3.1 粒子群优化算法介绍
◆ PSO种群中任一粒i的移动速度
v
n1 id
v c r (p x ) c r (p x )
1.3.2 不由人来判断(Pareto optimality) 基本原则：多目标问题优化解的自身特性 来搜索多目标问题有效解集的范围。
1.3.1 由人来判断（非Pareto机制）
加权: 由决策者决定每个目标函数不同的 权重因子，将所有的目标函数整合为一个 目标函数。 目标规划：由决策者确定每个目标函数所 能达到的目标值，然后将这些值作为附加 的约束整合进问题中，从而优化目标转换 为最大或最小化目标值和目标函数值之间 的绝对偏差。
1.1 什么是多目标问题
数学定义：
minimize y f ( x ) ( f1 ( x ), f 2 ( x ),..., f k ( x)) subject to e( x ) (e1 ( x ), e2 ( x ),..., em ( x )) 0
Where
x ( x1, x2 ,..., xn ) X
% factory_goal.m A=[ -1 -1 0 0; 0 0 -1 -1; 3 0 2 0; 0 3 0 2]; b=[-30 -30 120 48]; lb=zeros(1,4); x0=[20,10,30,0]; y0=[10000, 40]; x_opt=[18 12 33 0]; [x fval]=fgoalattain(@fun_optim, x0, y0, [1 2e-4], A, b, [], [], lb, [])

f
c
1
3.2 一种多目标粒子群优化算法实例
3.2.2 粒子更新策略 全局极值对粒子群优化算法的收敛性能具有 非常重要的影响, 往往使粒子快速收敛到搜索 空间得某一领域。然而，这种快速收敛机制也 会产生一些负面影响：1）算法最终得到的非 劣解前沿分布性差；2）如果全局极值是一个 局部最优解会产生早熟现象。
◆ 如何更新精英档案 ◆ 从档案中选取哪些精英参与种群进化
主题三
3 一种新颖的多目标算法实例
3.1 粒子群优化算法介绍 3.2 一种多目标粒子群优化算法 3.3 试验结果评价
3.1 粒子群优化算法介绍
粒子群算法(Particle Swarm Optimization,PSO) 是由Kennedy和Eberhart(1995)提出的,他们最 初的灵感来源于对鸟群飞行的观察。 粒子群算法容易实现，并且没有许多 参数需要设置，收敛速度开，相对于遗 传算法等其进化算法更简单有效。
1.3.2.1 Pareto支配(Pareto Dominance)
数学定义： 不失为一般性，仅考虑最小化。设 u=(u1,….uk)和v=(v1,…,vk)为两个自变量矢 量，那么u Pareto 支配v当且仅当ui <=vi ,i=1,…,k ，并且至少有一项ui < vi.
1.3.2.1 Pareto支配(Pareto Dominance)
1.1 什么是多目标问题
简单的概述： 在两个及两个以上的函数集T中，每个函 数的自变量矢量X1必须与其它函数的自变 量矢量X2有交集，优化这个函数集T,使得T 中所有的函数集尽可能的极大或极小，即 为多目标问题的优化。
工厂生产车辆优化问题Байду номын сангаас
% fun_optim.m function [y]= fun_optim(x) y=zeros(1,2); y(1)= -(100*x(1)+90*x(2)+80*x(3)+70*x(4)); y(2)=3*x(2)+2*x(4); 工厂生产两种型号汽车，其中 y(1)代表利润，y(2)代表加班时 间，状态变量x1,x2是A型车在正 常和加班两种情况下的产量， x3,x4是B型车在正常和加班两种 情况下的产量。
1.3.2 不由人来判断(Pareto optimality)
多目标问题最优解具有Pareto-optimal 特 性 什么是Pareto-optimal？ 1.3.2.1 Pareto支配(Pareto Dominance) 1.3.2.2 Pareto最优解(Pareto optimal solutions) 1.3.2.3 Pareto最优前沿(Pareto optimal front)
f2
X
A B Y C
解点A, B, C是非支配点 A Pareto支配X C Pareto 支配Y
f1
1.3.2.2 Pareto最优解(Pareto optimal solutions)