多目标问题及多目标进化算法.pptVIP

多目标问题及多目标进化算法研究基于粒子群的一种多目标优化算法 演讲主题 报告人 蒋庆2004级博士研究生 多目标优化问题多目标进化算法多目标粒子群优化算法实例 演讲主题 1多目标问题 Multi ObjectiveProblem 1 1什么是多目标问题1 2多目标问题的特点1 3怎样才算多目标问题的最优解 主题一 简单的概述 在两个及两个以上的函数集T中 每个函数的自变量矢量X1必须与其它函数的自变量矢量X2有交集 优化这个函数集T 使得T中所有的函数集尽可能的极大或极小 即为多目标问题的优化 1 1什么是多目标问题 工厂生产车辆优化问题 fun optim 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 100 00 1 1 3020 0302 b 30 3012048 lb zeros 1 4 x0 20 10 30 0 y0 10000 40 x opt 1812330 xfval fgoalattain fun optim x0 y0 12e 4 A b lb 工厂生产两种型号汽车 其中y 1 代表利润 y 2 代表加班时间 状态变量x1 x2是A型车在正常和加班两种情况下的产量 x3 x4是B型车在正常和加班两种情况下的产量 数学定义 1 1什么是多目标问题 Where 具有多个目标函数 各个函数之间在最优化方向上存在冲突 往往需要人的参与 目标函数集要么是求极大 要么是求极小 两者只能取其一 1 2多目标问题的特点 1 3 1由人来判断 非Pareto机制 基本原则 通过加入决策者判断 缩小多目标问题有效解集的范围 1 3 2不由人来判断 Paretooptimality 基本原则 多目标问题优化解的自身特性来搜索多目标问题有效解集的范围 1 3怎样才算多目标问题的最优解 加权 由决策者决定每个目标函数不同的权重因子 将所有的目标函数整合为一个目标函数 目标规划 由决策者确定每个目标函数所能达到的目标值 然后将这些值作为附加的约束整合进问题中 从而优化目标转换为最大或最小化目标值和目标函数值之间的绝对偏差 1 3 1由人来判断 非Pareto机制 多目标问题最优解具有Pareto optimal特性什么是Pareto optimal 1 3 2 1Pareto支配 ParetoDominance 1 3 2 2Pareto最优解 Paretooptimalsolutions 1 3 2 3Pareto最优前沿 Paretooptimalfront 1 3 2不由人来判断 Paretooptimality 数学定义 不失为一般性 仅考虑最小化 设u u1 uk 和v v1 vk 为两个自变量矢量 那么uPareto支配v当且仅当ui vi i 1 k 并且至少有一项ui vi 1 3 2 1Pareto支配 ParetoDominance 1 3 2 1Pareto支配 ParetoDominance A B C X Y f1 f2 解点A B C是非支配点APareto支配XCPareto支配Y 数学定义 多目标问题的一个矢量解x是Pareto最优解当且仅当不存在另一个矢量解y 使得f y Pareto支配f x 所有的ParetoOptimal解称为ParetoOptimal解集 1 3 2 2Pareto最优解 Paretooptimalsolutions 数学定义 对于一个多目标问题的Pareto最优解矢量X 则Y f1 X fk X 为X的Pareto前沿 所有的Pareto最优前沿称为Pareto最优前沿集 1 3 2 3Pareto最优前沿 Paretooptimalfront 1 3 2 3Pareto最优前沿 Paretooptimalfront 多目标进化算法 Multi ObjectiveEvolutionaryalgorithm 2 1进化算法求解多目标优化问题的优势2 2多目标进化算法的通用算法过程2 3多目标进化算法关键研究领域 主题二 每轮迭代可以找到多个Pareto近似最优解迄今为止还没有找到其他方法比EAs更能有效地解决MOP问题 在许多复杂应用问题中搜索最优解还存在一定的困难 2 1进化算法求解多目标优化问题的优缺点 输入 基于多目标函数自变量矢量编码的种群输出 多目标优化解集Step1 初时化种群Step2 适应值评价Step3 进化算子操作 生成新的种群a 选择算子 Selection b 组合算子 Recombination c 交叉算子 Mutation Step4 如果满足终止条件 结束算法迭代 否则转到Step2 2 2多目标进化算法的通用算法过程 如何使算法产生的优化解集逼近Pareto最优解集如何使算法产生的优化解集均匀分布 2 3多目标进化算法研究关键领域 2 3 1适应度选择和分配 基于聚合的策略组合多个目标成为一个单目标函数 基于准则的策略在选择阶段变换所选的优化目标 基于Pareto优胜关系的策略 2 3多目标进化算法研究关键领域 2 3 2精英档案 ElitismArchive DeJong 1975 提出了一种策略 将第t次迭代的最好的个体保存下来并加入到t 1次迭代的进化过程中 这些被保存的最好个体称为精英 通过试验 DeJong发现精英档案的引入能极大的提高算法的性能 如何更新精英档案 从档案中选取哪些精英参与种群进化 2 3多目标进化算法研究关键领域 3一种新颖的多目标算法实例3 1粒子群优化算法介绍3 2一种多目标粒子群优化算法3 3试验结果评价 主题三 粒子群算法 ParticleSwarmOptimization PSO 是由Kennedy和Eberhart 1995 提出的 他们最初的灵感来源于对鸟群飞行的观察 粒子群算法容易实现 并且没有许多参数需要设置 收敛速度开 相对于遗传算法等其进化算法更简单有效 3 1粒子群优化算法介绍 Step1 初时化粒子群的速度和位置Step2 适应值评价Step3 更形粒子群的速度和位置 从而生成下一代粒子群Step4 如果没有达到终止条件转到Step2 3 1粒子群优化算法介绍 PSO种群中任一粒i的移动速度 PSO种群中任一粒子i的位置 3 1粒子群优化算法介绍 算法使用一个存储非劣解的精英档案 该档案有两个作用 首先 它存储和更新粒子群每轮迭代搜索到的所有非劣解集 在迭代结束后 档案中的成员即为算法整个生命期搜索到的非劣解集 其次 档案通过对当前非劣解前沿的近似估计 从而辅助算法从档案中选择粒子速度更新的全局极值 后者提供了选择压力 通常促使粒子向多目标问题的全局非劣解前沿方向搜索 如果没有这个过程 算法就不能分辨好的和坏的解点 导致粒子在目标搜索空间中漫无目的的飞行 3 2一种多目标粒子群优化算法实例 3 2 1自适应角度分区方法提出了一种自适应角度分区算法 该方法通过计算档案中成员在目标空间中的范围 调整角度分区以覆盖档案中的所有成员 通过角度分区对目标空间中不同区域的拥挤程度进行动态跟踪 以维护外部档案的空间分布性 3 2一种多目标粒子群优化算法实例 3 2 2粒子更新策略全局极值对粒子群优化算法的收敛性能具有非常重要的影响 往往使粒子快速收敛到搜索空间得某一领域 然而 这种快速收敛机制也会产生一些负面影响 1 算法最终得到的非劣解前沿分布性差 2 如果全局极值是一个局部最优解会产生早熟现象 3 2一种多目标粒子群优化算法实例 采用动态设置全局极值的方法 在每次迭代时 采用如下公式动态生成全局极值 3 2 2粒子更新策略 3 3 1性能指标 相对覆盖指标 TwoSetCoverage 间隔指标 spacing 图形法 3 3试验结果评价 相对覆盖指标是对两个集合进行相对覆盖的比较 假设X X 是两个表现性决策向量 CS为有序对 X X 按下式计算后映射到区间 0 1 如果X 上的所有解点支配或者等于X 中的所有点 则根据定义可知CS 1 评价 该指标不需要参考集 可以作为比较两个集合与PFknown的相识度 convergence 和收敛性的指标 TwoSetCoverage 间隔指标 spacing 评价 衡量解集的分布性 使用画图软件将生成的解集的坐标以图形的方式显示出来 图形法 1 TheGeneticAlgorithmsArchivehttp www aic nrl mil galist 2 GeneticAdaptiveSystemsLAB GASLAB GASLABishostedbytheComputerScienceDepartmentoftheUniversityofNevada Reno http www cs unr edu sushil papers conference conf htmlhttp gaslab cs unr edu 3 http www mat sbg ac at uhl GA html4 http www cs gmu edu research gag email kdejong gmu edupublications downloadingwebsite http www cs gmu edu research gas pubs html5 IllinoisGeneticAlgorithmsLaboratoryProf DavidE Goldberg Directorhttp gal4 ge uiuc edu illigal home html6 MichiganStateUnivers