基于聚类和高斯变异的多目标粒子群算法.pdf
《基于聚类和高斯变异的多目标粒子群算法.pdf》由会员分享,可在线阅读,更多相关《基于聚类和高斯变异的多目标粒子群算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、为了解决工程中遇到的多目标优化问题,提出一种改进的多目标粒子群算法。首先,加人动态非线性余弦变化惯性参数,提升了算法的寻优能力;然后,提出一种改进的Pareto支配关系更新粒子的个体最优解,并根据拥挤距离对外部存档进行维护,提高了解集分布的均匀性;最后,将K-means聚类算法和高斯变异算法融合到多目标粒子群算法的迭代过程中,避免算法陷人局部最优解。在5个测试函数上进行仿真实验,结果表明,在保持解的均匀性和多样性的同时,改进算法使得Pareto解集具有更好的收敛性。关键词:多目标优化;粒子群算法;K-means聚类;高斯变异中图分类号:TN823文献标志码:A文章编号:10 0 1-9146(
2、2 0 2 3)0 3-0 0 0 1-0 80引言粒子群算法(ParticleSwarmOptimization,PSO)是一种群聚智能优化算法,源于对鸟类捕食行为的研究1。鸟类捕食时,找到食物最简单有效的策略就是搜寻距离食物最近的区域,基于该思想衍生的多目标粒子群算法广泛应用于工程实践。例如,Sannigrahi等2 将多目标粒子群算法应用于配电系统规划;邢小红等3 运用多目标优化算法解决水库洪水调度问题;张玉平等4 将多目标粒子群算法应用于斜拉桥索拉力优化分析。PSO具有结构简单、收敛速度快等特点5,但由于多目标问题本身的复杂性,运用该算法解决多目标问题时,很难确定多目标优化问题中的局部
3、最优个体和全局最优个体,搜索精度不高,容易陷人局部最优解6 。为此,本文提出一种改进的多目标粒子群算法,将K-means聚类算法7 和高斯变异算法融合到多目标粒子群算法的迭代过程中,避免算法陷人局部最优解的同时还提高了算法的局部搜索能力和精度。1基础理论1.1多目标优化问题在科学研究和工程实践中遇到的问题大多是多目标优化问题,不仅涉及多个目标函数的优化,各优化目标之间也存在复杂的约束关系8 。在优化部分目标的同时,往往出现其他目标遭受损失的情况,很难得到同时使每个目标达到最优的结果。所以,多目标问题并不存在一个可以满足全部目标的全局最优解,只能对所有目标进行权衡,得到相对较优的解,这些解组成了
4、多目标优化问题的解集。一个包含m个目标函数,n个决策变量,p个不等式约束和q个等式约束的多目标优化问题,表示如下:minimize F(x)=(fi(x),f2(x),.,fm(x)g;(x)0i=1,2,3,pS.t.(h,(x)=0j=1,2,3,q收稿日期:2 0 2 2-0 6-2 7基金项目:浙江省高校基本科研业务费专项资金项目(GK219909299001-024)作者简介:程兵(1997 一),男,研究方向:天线设计智能优化算法。E-mail:h y c j 0 7 10 h d u.e d u.c n。通信作者:项铁铭,副教授,研究方向:天线设计与智能优化算法。E-mail:。
5、(1)2式中,x=(,,,z )ER,是一个n维决策变量,F(x)=(fi(x),f2(x),fm(x)为m维目标向量,g;(x)为第i个不等式约束,h,(x)为第i个等式约束,p和q值分别为2 种约束条件的个数。多目标优化问题最终得到一个解的集合,即Pareto前沿 。多目标优化算法的目的就是寻找这一解集。1.2标准粒子群算法PSO中的每个粒子都代表问题的一个潜在解,粒子的适应度值用来衡量位置的好坏,粒子的速度决定了该粒子的运动方向和距离,并且速度随着个体最优值(pbest)和全局粒子的历史最优值(gbest)进行动态调整,从而实现优化。粒子群算法的迭代公式如下:v;(t+1)=ww;(t)
6、+ciri(xpbest,-x;(t)+c2r2(gbet,-x;(t)式中,v(t)和x;(t)分别表示第i个粒子在t时刻的速度和位置,为惯性权重,用于平衡局部搜索和全局搜索,C1和c2分别表示个体最优和历史最优的学习因子,决定粒子在进化过程中向个体最优和群体最优学习的权重大小,ri和r为加速因子,是介于0,1 之间的随机数。2基于聚类和高斯变异的多目标粒子群算法针对PSO算法的局部搜索能力不足、收敛精度不高、算法易陷人局部最优解等缺陷,本文分别从惯性参数动态变化方式、个体最优和全局最优的选取、解的多样性维护、种群的变异等方面进行改进,提出一种融合多种改进策略的多目标粒子群算法。2.1权重非
7、线性变化策略在PSO中,惯性权重w通常随着当前迭代次数T动态变化。一些改进的粒子算法采用惯性权重线性下降策略来加强算法的寻优能力,权重变化公式如下:Tmax式中Wmax和Wmin分别为惯性参数的最大值和最小值,Tmax为最大迭代次数。但是,线性下降策略的搜索精度不高,在优化过程中,最好是一开始就着重于全局搜索,后期逐渐收敛后再着重于局部搜索,这样不仅可以提升算法的收敛速度,而且还可以提高算法的搜索精度。为此,本文提出一种惯性权重余弦递减策略,权重变化公式如下:元T(Wmax一Wmin)cos(Tmax2由式(4)和式(5)得到惯性权重随迭代次数T的变化趋势如图1所示。杭州电子科技大学学报(自然
8、科学版)x;(t+1)=x,(t)+v;(t+1)Wmx-WminXTw=Wmax一余弦.线性2023年(2)(3)(4)Wmin(5)Tmax/2图12 种权重变化策略下,惯性权重随选代次数T的变化曲线Tmax第3期从图1可以看出,和线性下降策略相比,余弦递减策略下的惯性权重在算法搜索过程的前期和后期的下降速率更为缓慢,说明该策略下,算法在前期具有较强的全局搜索能力,在后期具有较高的局部搜索精度。2.2个体最优值的选取在个体最优值选取过程中,以往的做法是将个体的当前位置与其历史最优位置进行比较,选出一个非支配解作为个体最优值。但是,在算法后期,要优化的目标数较多时,个体的当前位置与其历史最优
9、位置往往不存在支配关系,无法直接比较,如果随机选择其中一个解作为个体最优值,反而会降低算法的性能。为此,本文在Pareto支配原则的基础上,提出更为精细的比较方法。依据Pareto支配原则进行比较,如果两者存在相互支配关系,则将其中的非支配解直接作为个体最优值,如果互相不支配,则进一步比较两者所在每一个目标函数上适应度值的大小,分别统计两者适应度值较小的次数,选择较小次数多的解作为个体最优值,避免在2 个解互不支配情况下盲目选取个体最优值。2.3全局最优值的选取多目标粒子群算法需要解决的一个重要问题是全局最优值的选取。本文采用拥挤距离排序的方法来确定每个粒子的全局最优解。首先,按照拥挤距离的定
10、义,计算外部存档中每个粒子的拥挤距离,并从大到小排序;然后,将前2 0%的粒子单独取出,按轮盘赌法为每个粒子选取全局最优值,处在稀疏区域的粒子拥挤距离大,被选中成为粒子全局最优解的概率就大,不仅有利于算法的快速收敛,还可以保证解集分布的均匀性。2.4基于聚类算法的高斯变异策略标准多目标粒子群算法很容易陷人局部最优解,导致算法早熟,收敛精度差。为了提高算法的性能,本文将K-means聚类算法和高斯变异算法融合到标准粒子群算法中。从非支配解集中随机选取k个解作为初始聚类中心(Ci,C 2,C),再计算每个粒子到每个聚类中心的距离,(6)t=1式中,x;表示第i个粒子,表示第i个粒子的第t维的值,C
11、,表示第i个聚类中心,C表示第个聚类中心的第t维的值。依次比较每个粒子到每个聚类中心的距离,将粒子划分到距离其最近的聚类中心所在的类中,得到k个类簇(Si,S2,,S)。每次分类完成之后,重新计算聚类中心,将本类中所有粒子在各个维度上的均值作为下次分类的聚类中心,以此循环计算,直至满足算法要求。聚类中心更新计算公式如下:(7)式中,Ci表示第1个类中心,S|表示第1个类簇中包含解的个数,x,表示第1个类簇中的第i个粒子。最终将解集分为k类,并且满足误差平方和达到最小。误差平方和(Sumof SquaresforError,SSE)的定义如下:(8)式中,dist(xi,C)表示类S,中的第i个
12、解到该类中心C,的距离。所有非支配解均经过K-means聚类后,再计算得到每个类中所有粒子的每一维度上的方差,以该方差为依据,为该类中的每个粒子进行变异,具体变异公式如下:(9)P Q(T)72Q(T)=1 e式中,表示第i个粒子在第维度上的值,c表示i变异之后的值,Gaussian(O,)表示一个服从均值程兵,等:基于聚类和高斯变异的多目标粒子群算法dist(x;,C,)=C,=Ese=22dist(x.,C.)*i+Gaussian(O,o)P Q(T)=3(-C.)2(10)4为0,方差为的高斯分布的随机数,方差为该粒子所在的类中所有粒子的方差,对粒子的每一维进行概率为Q(T)的变异操作
13、,T为算法的当前迭代次数,Tmax为最大迭代次数,P为一个服从O,1区间均匀分布的随机数。与传统变异策略相比较,结合聚类算法的高斯变异后,每个类中的个体都有极高的相似性,避免了种群变异的盲目性和随机性,使得变异的结果更为理想并且范围可控,相当于在原先解的基础上对每一维度进行微量扰动,有利于算法在原先解的邻域空间内找到更为优质的解,有效提高了算法的局部搜索能力和精度。3仿真实验与分析在Windows 10 Intel(R)Co r e(T M)i 7-7 50 0 U M A T LA B2 0 2 0 a 的环境下,选用ZDT2-ZDT4101和DTLZ1-DTLZ211测试函数,分别对标准多
14、目标粒子群算法MOPSO、基于精英策略的快速非支配排序遗传算法(NSGA-II)12 、基于2 个局部最佳的多目标粒子群算法(2 LBMOPSO)131、使用拥挤距离机制和突变操作保持非支配解多样性的多目标粒子群算法(MOPSO-CD)141、基于精英学习策略的粒子群算法(MOPSO-ELS)15和本文改进的多目标粒子群算法进行仿真实验。6 种算法均采用相同设置,种群和外部存档规模N=100,送代次数T=1000,惯性权重Wmax和min分别取2.0 和0.4。分别统计每种算法在30 次独立运行下求得的反转世代距离(Inverted GenerationalDistance,IG D)16 、
15、超体积(H y p e r v o l u me,H V)17 、多样性(Diversity,DIV)18、空间性(Spacing,SP)19 的均值(Mean)和标准差(Std),本文选取(1,1)和(1,1,1)两点分别作为二目标和三目标测试函数HV指标计算的参考点,其中“表示数据超出有效范围,实验结果如表1所示。性能算法类别指标NSGA-IIMOPSO2LBMOPSOIGDMOPSO-CDMOPSO-ELS本文算法NSGA-IIMOPSO2LBMOPSOHVMOPSO-CDMOPSO-ELS本文算法NSGA-IIMOPSO2LBMOPSODIVMOPSO-CDMOPSO-ELS本文算法N
16、SGA-IIMOPSO2LBMOPSOSPMOPSO-CDMOPSO-ELS本文算法杭州电子科技大学学报(自然科学版)表1不同算法的性能指标ZDT2ZDT3MeanStd5.60e-34.89e-44.90e-12.40e-15.10e-32.27e-44.19e-11.61e-27.80e-39.21e-43.90e-32.39e-53.27e-11.36e-21.14e-11.22e-13.28e-19.60e-34.19e-26.90e-33.28e-11.42e-23.34e-11,39e-24.63e-13.26e-29.30e-11.41e-14.14e-12.47e-29.25e
17、-11.09e-22.97e-15.55e-26.98e-28.60e-36.70e-39.81e-42.10e-34.30e-37.30e-36.27e-41.55e-24.78e-46.02e-38.97e-44.20e-34.68e-52023年ZDT4DTLZ1MeanStd5.90e-3 4.85e-41.45e-17.44e-26.00e-33.70e-43.20e-16.25e-25.40 e-33.41e-44.30e-3 2.19e-57.79e-11.53e-27.60e-1 5.95e-28.00e-11.04e-25.46e-19.79e-27.99e-11.08e-2
18、8.04e-19.40e-36.99e-12.35e-28.23e-14.08e-26.93e-12.06e-28.09e-17.03e-26.78e-12.26e-21.73e-11.11e-28.40e-38.28e-46.10e-3 1.50e-37.90e-3 7.49e-47.30e-36.30e-38.20e-31.90e-34.02e-31.79e-4DTLZ2MeanStd1.26e-0 8.16e-11.34e-01.66e-11.71e-07.27e-11.87e-01.65e-14.60e-33.82e-43.60e-35.96e-57.38e-2 1.67e-15.02
19、e-41.00e-36.57e-11.70e-26.65e-11.01e-27.74e-19.28e-28.96e-13.08e-27.89e-19.58e-28.66e-11.49e-23.22e-13.06e-27.39e-21.39e-29.70e-3 1.70e-31.54e-23.10e-31.44e-21.70e-25.90e-34.40e-36.20e-3 6.07e-44.10e-34.44e-5Mean14.22e-04.57e-04.54e-01.93e-06.76e-01.92e-04.16e-01.58e-03.07e-21.80e-32.53e-22.30e-3一9.
20、66e-16.70e-39.69e-13.50e-37.82e-16.23e-28.14e-11.25e-17.88e-13.66e-28.96e-11.06e-18.34e-12.36e-27.72e-12.12 e-21.26e-04.82e-12.56e-0 1.12e-02.35e-04.77e-110.57e-06.06e-02.17e-22.40e-31.97e-22.30e-3StdMean7.72e-23.00e-33.11e-13.32e-29.23e-24.90e-38.68e-16.10e-36.56e-21.50e-36.50e-23.10e-33.69e-11.60e
21、-22.23e-12.21e-23.07e-11.82e-23.02e-11.63e-23.57e-11.71e-23.80e-11.12e-27.06e-13.91e-26.50e-13.35e-26.22e-1 2.34e-27.07e-12.90e-26.29e-13.67e-26.14e-11.84e-25.75e-25.10e-34.44e-25.30e-36.12 e-28.30e-36.62e-21.62e-25.74e-25.10e-35.03e-21.90e-3Std第3期从表1可以看出,本文算法的IGD,HV和DIV的均值比其他5种算法小,同时SP指标的均值也取得3个较好的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 变异 多目标 粒子 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。