《多目标问题及多目标进化算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《多目标问题及多目标进化算法ppt课件.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、多目标问题及多目标进化算法研究基于粒子群的一种多目标优化算法演讲主题 报告人： 蒋庆 2004级博士研究生 1. 多目标优化问题2. 多目标进化算法3. 多目标粒子群优化算法实例演讲主题1 多目标问题(Multi-Objective Problem) 1.1 什么是多目标问题 1.2 多目标问题的特点 1.3 怎样才算多目标问题的最优解主题一u 简单的概述： 在两个及两个以上的函数集T中，每个函数的自变量矢量X1必须与其它函数的自变量矢量X2有交集，优化这个函数集T,使得T中所有的函数集尽可能的极大或极小，即为多目标问题的优化。1.1 什么是多目标问题工厂生产车辆优化问题% fun_optim
2、.mfunction 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);% factory_goal.mA= -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, )工厂生产两种型
3、号汽车，其中y(1)代表利润，y(2)代表加班时间，状态变量x1,x2是A型车在正常和加班两种情况下的产量，x3,x4是B型车在正常和加班两种情况下的产量。u 数学定义： 1.1 什么是多目标问题minimize ( )( ),( ),.,( )12 ( )( ),( ),.,( )012yf xfxfxfxksubject to e xex exexm12 ( ,.,)nxx xxX12y(,.,)ky yyYWhere u 具有多个目标函数。u 各个函数之间在最优化方向上存在冲突。u 往往需要人的参与。u 目标函数集要么是求极大，要么是求极小，两者只能取其一。1.2 多目标问题的特点1.3
4、.1 由人来判断（非Pareto机制） 基本原则：通过加入决策者判断，缩小多目标问题有效解集的范围。1.3.2 不由人来判断(Pareto optimality) 基本原则：多目标问题优化解的自身特性来搜索多目标问题有效解集的范围。1.3 怎样才算多目标问题的最优解u 加权: 由决策者决定每个目标函数不同的权重因子，将所有的目标函数整合为一个目标函数。u 目标规划：由决策者确定每个目标函数所能达到的目标值，然后将这些值作为附加的约束整合进问题中，从而优化目标转换为最大或最小化目标值和目标函数值之间的绝对偏差。1.3.1 由人来判断（非Pareto机制）u 多目标问题最优解具有Pareto-op
5、timal 特性u 什么是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)1.3.2 不由人来判断(Pareto optimality)u 数学定义： 不失为一般性，仅考虑最小化。设u=(u1,.uk)和v=(v1,vk)为两个自变量矢量，那么u Pareto 支配v当且仅当ui =vi ,i=1,k ，并且至少有一项ui vi. 1.3.2.1 Pareto支配(Paret
6、o Dominance) 1.3.2.1 Pareto支配(Pareto Dominance) ABCXYf1f2解点解点A, B, C是非支配点是非支配点A Pareto支配支配X C Pareto 支配支配Yu 数学定义： 多目标问题的一个矢量解x是Pareto 最优解当且仅当不存在另一个矢量解y,使得f(y)Pareto支配 f(x). 所有的Pareto Optimal 解称为Pareto Optimal 解集。 1.3.2.2 Pareto最优解(Pareto optimal solutions) u 数学定义： 对于一个多目标问题的Pareto 最优解矢量X,则Y=(f1(X),f
7、k(X)为X的Pareto前沿.所有的Pareto 最优前沿称为Pareto 最优前沿集。 1.3.2.3 Pareto最优前沿(Pareto optimal front) 1.3.2.3 Pareto最优前沿(Pareto optimal front)2多目标进化算法(Multi-Objective Evolutionary algorithm) 2.1 进化算法求解多目标优化问题的优势 2.2 多目标进化算法的通用算法过程 2.3 多目标进化算法关键研究领域 主题二u 每轮迭代可以找到多个Pareto近似最优解 u迄今为止还没有找到其他方法比EAs更能有效地解决MOP问题。u 在许多复杂应
8、用问题中搜索最优解还存在一定的困难。 2.1 进化算法求解多目标优化问题的优缺点 输入：基于多目标函数自变量矢量编码的种群 输出： 多目标优化解集 Step1: 初时化种群 Step2: 适应值评价 Step3: 进化算子操作，生成新的种群 a) 选择算子(Selection) b) 组合算子(Recombination) c) 交叉算子(Mutation) Step4: 如果满足终止条件，结束算法迭代，否则转到Step2. 2.2 多目标进化算法的通用算法过程1如何使算法产生的优化解集逼近Pareto最优解集2如何使算法产生的优化解集均匀分布。 2.3 多目标进化算法研究关键领域2.3.1
9、适应度选择和分配 基于聚合的策略 组合多个目标成为一个单目标函数 基于准则的策略 在选择阶段变换所选的优化目标 基于Pareto优胜关系的策略 2.3 多目标进化算法研究关键领域2.3.2 精英档案(Elitism Archive) De Jong(1975)提出了一种策略，将第t次迭代的最好的个体保存下来并加入到t+1次迭代的进化过程中，这些被保存的最好个体称为精英。通过试验，De Jong发现精英档案的引入能极大的提高算法的性能。 如何更新精英档案 从档案中选取哪些精英参与种群进化 2.3 多目标进化算法研究关键领域3 一种新颖的多目标算法实例 3.1 粒子群优化算法介绍 3.2 一种多目
10、标粒子群优化算法 3.3 试验结果评价 主题三 粒子群算法(Particle Swarm Optimization,PSO)是由Kennedy和Eberhart(1995)提出的,他们最初的灵感来源于对鸟群飞行的观察。 粒子群算法容易实现，并且没有许多参数需要设置，收敛速度开，相对于遗传算法等其进化算法更简单有效。3.1 粒子群优化算法介绍Step1: 初时化粒子群的速度和位置Step2: 适应值评价Step3: 更形粒子群的速度和位置，从而生成下一代粒子群Step4: 如果没有达到终止条件转到Step2。3.1 粒子群优化算法介绍 PSO种群中任一粒i的移动速度 PSO种群中任一粒子i的位置
11、)()(22111nidngdnnidnidnnidnidxprcxprcvv3.1 粒子群优化算法介绍11nidnidnidvxx 算法使用一个存储非劣解的精英档案，该算法使用一个存储非劣解的精英档案，该档案有两个作用。首先，它存储和更新粒子群档案有两个作用。首先，它存储和更新粒子群每轮迭代搜索到的所有非劣解集，在迭代结束每轮迭代搜索到的所有非劣解集，在迭代结束后，档案中的成员即为算法整个生命期搜索到后，档案中的成员即为算法整个生命期搜索到的非劣解集。其次，档案通过对当前非劣解前的非劣解集。其次，档案通过对当前非劣解前沿的近似估计，从而辅助算法从档案中选择粒沿的近似估计，从而辅助算法从档案中
12、选择粒子速度更新的全局极值。后者提供了选择压力，子速度更新的全局极值。后者提供了选择压力，通常促使粒子向多目标问题的全局非劣解前沿通常促使粒子向多目标问题的全局非劣解前沿方向搜索。如果没有这个过程，算法就不能分方向搜索。如果没有这个过程，算法就不能分辨好的和坏的解点，导致粒子在目标搜索空间辨好的和坏的解点，导致粒子在目标搜索空间中漫无目的的飞行。中漫无目的的飞行。3.2 一种多目标粒子群优化算法实例 3.2.1 自适应角度分区方法自适应角度分区方法 提出了一种自适应角度提出了一种自适应角度分区算法，该方法通过计分区算法，该方法通过计算档案中成员在目标空间算档案中成员在目标空间中的范围，调整角度
13、分区中的范围，调整角度分区以覆盖档案中的所有成员。以覆盖档案中的所有成员。通过角度分区对目标空间通过角度分区对目标空间中不同区域的拥挤程度进中不同区域的拥挤程度进行动态跟踪，以维护外部行动态跟踪，以维护外部档案的空间分布性。档案的空间分布性。 3.2 一种多目标粒子群优化算法实例 3.2.2 粒子更新策略 全局极值对粒子群优化算法的收敛性能具有全局极值对粒子群优化算法的收敛性能具有非常重要的影响非常重要的影响, 往往使粒子快速收敛到搜索往往使粒子快速收敛到搜索空间得某一领域。然而，这种快速收敛机制也空间得某一领域。然而，这种快速收敛机制也会产生一些负面影响：会产生一些负面影响：1）算法最终得到
14、的非）算法最终得到的非劣解前沿分布性差；劣解前沿分布性差；2）如果全局极值是一个）如果全局极值是一个局部最优解会产生早熟现象。局部最优解会产生早熟现象。 3.2 一种多目标粒子群优化算法实例采用动态设置全局极值的方法，在每次迭代时，采用如下公式动态生成全局极值。 3.2.2 粒子更新策略,(, )i ci gttpRandom pt,()()11 12 2i ctiiiiivwvc Rpxc Rxtttttp3.3.1 性能指标 相对覆盖指标(Two Set Coverage) 间隔指标(spacing) 图形法 3.3 试验结果评价 相对覆盖指标是对两个集合进行相对覆盖的比较。假设X、X是两
15、个表现性决策向量，CS为有序对(X,X)按下式计算后映射到区间0,1: 如果X上的所有解点支配或者等于X中的所有点，则根据定义可知CS=1.评价评价：该指标不需要参考集，可以作为比较两个集合与PFknown的相识度（convergence）和收敛性的指标。Two Set Coverage |;:|(,):|aXaXaaTSC XXXTSCMopso: SpeaMopso: SoeaSpea:MopsoSoea:MopsoBest1.01.00.01140.0Worst0.89390.00.00.0Mean0.97101.00.00360.0Std0.03870.00.00560.0Median
16、0.98571.00.00.0 间隔指标(spacing)niiddns12)(11评价： 衡量解集的分布性。SMOPSOSPEA SOEABest0.12000.11480.1675Worst0.12720.15990.1675Mean0.12280.13360.1675Std0.00260.01030.0Median0.12130.13400.1675使用画图软件将生成的解集的坐标以图形的方式显示出来 图形法1.The Genetic Algorithms Archive http:/www.aic.nrl.mil/galist/ 2.Genetic Adaptive Systems LA
17、B (GASLAB) GASLAB is hosted by the Computer Science Department of the University of Nevada-Reno. http:/www.cs.unr.edu/sushil/papers/conference/conf.html http:/gaslab.cs.unr.edu/ 3.http:/www.mat.sbg.ac.at/uhl/GA.html 4.http:/www.cs.gmu.edu/research/gag/ email:kdejonggmu.edu publications: (downloading
18、 website) http:/www.cs.gmu.edu/research/gas/pubs.html 5.Illinois Genetic Algorithms Laboratory Prof. David E. Goldberg, Director http:/gal4.ge.uiuc.edu./illigal.home.html 6.Michigan State University Genetic Algorithms Research and Applications Group (GARAGE) Bill Punch (punchcps.msu.edu,517-353-3541) Erik Goodman (goodmanegr.msu.edu,517-355-6453) http:/garage.cs.msu.edu/ 7.ftp:/ftp.egr.msu.edu/pub/EC/GA/ 8 http:/ www.swarmintelligence.org进化算法网络资源 感谢大家！