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

多目标问题及多目标进化算法研究基于粒子群的一种多目标优化算法演讲主题报告人：蒋庆2004级博士研究生1.多目标优化问题2.多目标进化算法3.多目标粒子群优化算法实例演讲主题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什么是多目标问题minimize()((),(),...,())12()((),(),...,())012yfxfxfxfxksubjecttoexexexexm12(,,...,)nxxxxX12y(,,...,)kyyyY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，并且至少有一项uivi.1.3.2.1Pareto支配(ParetoDominance)1.3.2.1Pareto支配(ParetoDominance)ABCXYf1f2解点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)2多目标进化算法(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多目标进化算法的通用算法过程1如何使算法产生的优化解集逼近Pareto最优解集2如何使算法产生的优化解集均匀分布。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的位置)()(22111nidngdnnidnidnnidnidxprcxprcvv3.1粒子群优化算法介绍11nidnidnidvxx算法使用一个存储非劣解的精英档案，该档案有两个作用。首先，它存储和更新粒子群每轮迭代搜索到的所有非劣解集，在迭代结束后，档案中的成员即为算法整个生命期搜索到的非劣解集。其次，档案通过对当前非劣解前沿的近似估计，从而辅助算法从档案中选择粒子速度更新的全局极值。后者提供了选择压力，通常促使粒子向多目标问题的全局非劣解前沿方向搜索。如果没有这个过程，算法就不能分辨好的和坏的解点，导致粒子在目标搜索空间中漫无目的的飞行。3.2一种多目标粒子群优化算法实例3.2.1自适应角度分区方法提出了一种自适应角度分区算法，该方法通过计算档案中成员在目标空间中的范围，调整角度分区以覆盖档案中的所有成员。通过角度分区对目标空间中不同区域的拥挤程度进行动态跟踪，以维护外部档案的空间分布性。3.2一种多目标粒子群优化算法实例iparticles1f2fcab3.2.2粒子更新策略全局极值对粒子群优化算法的收敛性能具有非常重要的影响,往往使粒子快速收敛到搜索空间得某一领域。然而，这种快速收敛机制也会产生一些负面影响：1）算法最终得到的非劣解前沿分布性差；2）如果全局极值是一个局部最优解会产生早熟现象。3.2一种多目标粒子群优化算法实例采用动态设置全局极值的方法，在每次迭代时，采用如下公式动态生成全局极值。3.2.2粒子更新策略,,(,)icigttpRandompt,()()11122ictiiiiivwvcRpxcRxtttttp3.3.1性能指标◆相对覆盖指标(TwoSetCoverage)◆间隔指标(spacing)◆图形法3.3试验结果评价相对覆盖指标是对两个集合进行相对覆盖的比较。假设X’、X’’是两个表现性决策向量，CS为有序对(X’,X’’)按下式计算后映射到区间[0,1]:如果X’上的所有解点支配或者等于X’’中的所有点，则根据定义可知CS=1.评价：该指标不需要参考集，可以作为比较两个集合与PFknown的相识度（convergence）和收敛性的指标。TwoSetCoverage''''''''''''''|{;:}|(,):||aXaXaaTSCXXXTSCMopso:SpeaMopso:SoeaSpea:MopsoSoea:MopsoBest1.01.00.01140.0Worst0.89390.00.00.0Mean0.97101.00.00360.0Std0.03870.00.00560.0Median0.98571.00.00.0间隔指标(spacing)niiddns12)(11评价：衡量解集的分布性。SMOPSOSPEASOEABest0.12000.11480.1675Worst0.12720.15990.1675Mean0.12280.13360.1675Std0.00260.01030.0Median0.12130.13400.1675使用画图软件将生成的解集的坐标以图形的方式显示出来图形法•1.TheGeneticAlgorithmsArchive••2.GeneticAdaptiveSystemsLAB(GASLAB)•GASLABishostedbytheComputerScienceDepartmentoftheUniversityofNevada-Reno.•~sushil/papers/conference/conf.html••3.~uhl/GA.html•4.•email:[e-mail]•publications:(downloadingwebsite)•://gal4.ge.uiuc.edu./illigal.home.html•6.MichiganStateUniversity•GeneticAlgorithmsResearchandApplicationsGroup(GARAGE)•BillPunch([e-mail],517-353-3541)•ErikGoodman([e-mail],517-355-6453)••7.•8=5882•9