引用本文

余伟伟, 谢承旺, 闭应洲, 夏学文, 李雄, 任柯燕, 赵怀瑞, 王少锋. 一种基于自适应模糊支配的高维多目标粒子群算法. 自动化学报, 2018, 44(12): 2278-2289. doi: 10.16383/j.aas.2018.c170573

YU Wei-Wei, XIE Cheng-Wang, BI Ying-Zhou, XIA Xue-Wen, LI Xiong, REN Ke-Yan, ZHAO Huai-Rui, WANG Shao-Feng. Many-objective Particle Swarm Optimization Based on Adaptive Fuzzy Dominance. ACTA AUTOMATICA SINICA, 2018, 44(12): 2278-2289. doi: 10.16383/j.aas.2018.c170573

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170573

关键词

自适应模糊支配，精英个体扰动，粒子群算法，高维多目标优化问题，高维多目标粒子群优化算法 

摘要

高维多目标优化问题由于具有巨大的目标空间使得一些经典的多目标优化算法面临挑战.提出一种基于自适应模糊支配的高维多目标粒子群算法MAPSOAF，该算法定义了一种自适应的模糊支配关系，通过对模糊支配的阈值自适应变化若干步长，在加强个体间支配能力的同时实现对种群选择压力的精细化控制，以改善算法的收敛性；其次，通过从外部档案集中选取扰动粒子，并在粒子速度更新公式中新增一扰动项以克服粒子群早熟收敛并改善个体分布的均匀性；另外，算法利用简化的Harmonic归一化距离评估个体的密度，在改善种群分布性的同时降低算法的计算代价.该算法与另外五种高性能的多目标进化算法在标准测试函数集DTLZ{1，2，4，5}上进行对比实验，结果表明该算法在收敛性和多样性方面总体上具有较显著的性能优势.

文章导读

科学研究与工程实践中不断涌现出要求同时优化4个或4个以上目标的问题, 研究者一般将这类优化问题称为高维多目标优化问题(Many-objective optimization problem, MAOP), 与优化目标数为2至3个的多目标优化问题(Multi-objective optimization problem, MOP)相比, MAOP问题的目标空间更大, 搜索的难度也更大.其原因在于:随着目标空间维度的增加, 种群中非被占优个体的数量将呈指数级增长, 运用Pareto支配关系择优个体的方法面临失效的窘地, 算法的搜索能力被极大地削弱; 另外, 由于Pareto支配关系在高维空间中效果变差, 使得分布性保持机制成为算法选择个体的主导因素, 但是由个体密度信息主导的选择机制不一定能有效地驱动近似Pareto前沿向真实Pareto前沿逼近, 甚至可能对优化过程有负面影响[1-3].为解决高维多目标优化问题带来的挑战, 各国学者从不同的视角提出了解决方法.陈振兴等[4]融合张角拥挤控制策略解决MAOP问题.巩敦卫等[5]基于目标分解的策略提出高维多目标并行优化方法. Drechsler等[6]提出了目标优胜关系的宽松Pareto支配关系: Favor关系, 但该关系易受到目标函数量纲差别的影响. Di Pierro等[7]提出K-占优机制, 但其只考虑了一个目标向量相对于另一个目标向量的改善目标数. Sato等[8]提出对解个体的支配区域进行缩放以改变解个体在目标空间中的位置, 从而达到改变解个体支配关系的目的.需要指出, 这种方法需要用户为每一个目标函数指定修正参数. Hernandez-diaz等[9]通过引入评判目标间优劣关系的阈值提出了ε-占优机制, 但该策略依赖阈值的选取方法. Kang等[10]在总结新型占优机制优劣的基础上提出了E-占优, 但E-占优方法在求解MAOP问题中的性能如何, 文献中并未讨论. Zou等[11]提出了一种L-最优性, 该占优方法不仅考虑了目标值得到改善的目标个数而且在所有目标具有同等重要性的情况下, 改善的目标函数也考虑其中, 但该方法随着目标个数的持续增加, 仍面临着选择压力退化的问题. Farina等[12]将模糊理论引入到多目标优化算法中, 但该策略亦存在产生循环支配之缺陷.毕晓君等[13]将模糊理论引入高维多目标进化算法模型, 并结合模糊理论α-截集提出了新的环境选择策略.

粒子群优化(Particle swarm optimization, PSO)是Kennedy等[14]受到飞鸟集群活动的启发而提出的一种群体智能优化算法, 其具有易于实现和收敛速度快等优势.近年来, PSO算法在多目标优化领域的研究取得了很大的进展, 涌现出了不少的多目标粒子群算法(Multi-objective particle swarm optimization algorithm, MOPSO), 但将其用于高维多目标优化问题求解的理论和方法还很少.

本文在已有多目标粒子群算法和宽松支配关系等研究的基础上, 提出一种基于自适应模糊支配的高维多目标粒子群优化(Many-objective particle swarm optimization based on adaptive fuzzy dominance, MAPSOAF)算法, 以求解复杂的MAOP问题.算法的创新点主要包括: 1)以步长幅度自适应地调整模糊隶属度支配的阈值来改进模糊支配关系, 在加强个体间支配能力的同时实现对种群选择压力的精细化调控, 以改善算法的收敛性; 2)增加扰动粒子改造基本PSO算法的速度更新公式, 在克服种群早熟收敛的同时改善个体分布的均匀性; 3)利用简化的Harmonic归一化距离评估个体的密度, 在改善种群分布性的同时降低算法的计算代价.上述三种策略有机结合, 形成了MAPSOAF算法的主要特点, 这些策略在算法的不同阶段实施, 以协同地提高MAPSOAF算法的总体性能.

论文的第1节简要介绍高维多目标优化问题相关概念.第2节描述构成MAPSOAF算法的若干重要组件和算法的流程, 它是本文的重点章节.第3节是论文的仿真实验与结果分析.最后是本文的结论部分.

图 1  多目标粒子群算法中粒子的速度更新示意图

图 2  增加扰动项之后算法中粒子的速度更新示意图

高维多目标优化问题巨大的目标空间使得一些经典的多目标优化算法面临困境, 迫切需要发展新型高维多目标优化算法应对挑战.论文提出一种基于自适应模糊支配的高维多目标粒子群算法MAPSOAF, 该算法以步长为幅度, 自适应地调整模糊隶属度支配阈值, 实现对种群选择压力的精细化控制; 其次算法在粒子速度更新公式中新增一扰动项, 实现在克服种群早熟收敛的同时改善群体的分布性; 最后, 算法采用简化的Harmonic归一化距离评估个体的密度, 实现改善群体分布性的同时降低算法的计算代价. MAPSOAF算法与其他5种代表性的MOEA算法在12个基准高维多目标测试函数上进行IGD性能实验, 结果表明本文的算法具有较显著的收敛性和多样性的性能优势.

未来将利用MAPSOAF算法求解实践中如雷达优化问题、水资源优化问题、翼行设计问题和护士排班等典型高维多目标优化问题, 以进一步测试和改善算法的性能; 另外, 考虑将一些新近提出的进化范例引入到高维多目标优化算法的框架中, 以不断提高解决复杂MAOP问题的能力.

作者简介

余伟伟   

北京工业大学信息学部软件学院硕士研究生.2012年获得华东交通大学软件学院学士学位.主要研究方向为智能计算与多目标优化E-mail:ecjtu_yuweiwei@163.com

闭应洲   

广西师范学院计算机与信息工程学院教授.2008年获得武汉大学计算机软件与理论专业博士学位.主要研究方向为智能计算与自然语言处理.E-mail:byzhou@163.com

夏学文  

华东交通大学软件学院副教授.2009年获得武汉大学计算机软件与理论专业博士学位.主要研究方向为计算智能及其应用.E-mail:xwxia@whu.edu.cn

李雄  

华东交通大学软件学院讲师.2015年获得湖南大学计算机科学与技术专业博士学位.主要研究方向为数据挖掘, 机器学习, 生物信息处理.E-mail:lx_hncs@163.com

任柯燕   

北京工业大学信息学部讲师.2011年获得北京邮电大学电气工程专业博士学位.主要研究方向为大规模场景目标检测, 跟踪与识别.E-mail:keyanren@bjut.edu.cn

赵怀瑞   

华东交通大学机电与车辆工程学院讲师.2012年获得北京交通大学车辆工程专业博士学位.主要研究方向为空气动力学, 多学科设计优化和结构疲劳.E-mail:shiren@ecjtu.jx.cn

王少锋   

华东交通大学土建学院讲师.2014年获得同济大学道路与铁道工程专业博士学位.主要研究方向为轮轨关系, 轨道损伤机理及维护.E-mail:hexieshehui@foxmail.com

谢承旺   

广西师范学院计算机与信息工程学院副教授.2010年获得武汉大学计算机软件与理论专业博士学位.主要研究方向为智能计算, 多目标和高维多目标优化.本文通信作者.E-mail:chengwangxie@163.com