《关联变量分组的分解多目标进化算法研究》由会员分享，可在线阅读，更多相关《关联变量分组的分解多目标进化算法研究（17页珍藏版）》请在金锄头文库上搜索。
1、关联变量分组的分解多目标进化算法研究 邱飞岳 胡烜 王丽萍 浙江工业大学信息工程学院 浙江工业大学现代教育技术研究所 浙江工业大学信息智能与决策优化研究所 摘 要： 含有大规模决策变量的优化问题是当前多目标进化算法领域中的研究热点和难点之一。在解决大规模变量问题时, 目前的进化算法并没有寻找决策变量之间的关联信息, 而都只是将所有变量视为一个整体来进行优化。但随着优化问题中决策变量的增多, “变量维度”成为瓶颈, 从而影响算法的性能。针对上述问题, 提出关联变量分组策略, 通过识别决策变量间内在的关联信息把关联变量分配到同组中, 将复杂高维变量的优化问题分解为简单低维的子问题来求解。该策略通过
2、增加关联变量分配到同组中的概率来使算法尽可能地保留变量之间的关联性, 减少分组后子问题间的依赖性, 从而提高子问题最优解的质量并最终获得最佳的 Pareto 最优解集。将该算法在标准测试函数上进行变量扩展后再进行仿真对比实验, 采用性能指标对算法的收敛性和多样性进行对比分析。实验结果表明, 该算法在解决大规模变量的多目标优化问题中, 随着决策变量维度的增加, 比经典的多目标进化算法 NSGA-II、MOEA/D 以及 RVEA 具有更佳的收敛和更好的分布性能, 所求得的 Pareto 解集质量更高。关键词： 大规模优化; 关联变量; 变量识别; 分组分解; 作者简介：邱飞岳 (1965-) ,
3、 男, 博士, 教授, 博士生导师, 主要研究方向为智能控制、优化理论与方法、学习科学与媒体技术;作者简介：胡烜 (1992-) , 男, 硕士生, 主要研究方向为多目标进化算法;作者简介：王丽萍 (1964-) , 女, 博士, 教授, 博士生导师, 主要研究方向为信息处理、决策优化、商务智能。收稿日期：2016-12-25基金：国家自然科学基金项目 (61472366, 61379077) Research on Multi-objective Evolutionary Algorithm Based on Decomposition Using Interacting Variables
4、 GroupingQIU Fei-yue HU Xuan WANG Li-ping College of Information Engineering, Zhejiang University of Technology; Institute of Information Intelligence and Decision Optimization, Zhejiang University of Technology; Abstract： Optimization problem with large-scale decision variable is one of the hot and
5、 difficult points in the multi-objective evolutionary algorithm research field.When solving the problem of large-scale variable, the current evolutionary algorithm does not find the related information between decision variables and treats all the decision variables as a whole to optimize.But the va
6、riable dimensionality will become the bottleneck as the decision variables in the optimization problem increase, which will affect the performance of the algorithm.To settle these problems, this paper proposed a interacting variable grouping strategy to identify the internal relation among the decis
7、ion variables and allocate the inte-racting variables to the same group.Thus, it can decompose a difficult high-dimensional problem into a set of simpler and lowdimensional subproblems that are easier to solve.In order to make the algorithm as far as possible to retain the relationship between varia
8、bles and keep the interdependencies among different subproblems minimal, this strategy increases the probability of assigning the interacting variables to the same group so as to improve the quality of the optimal solution of the subproblems and ultimately gets the best Pareto optimal solution set.C
9、omparative simulation experiment was conducted after the variable extension on standard test function.The convergence and diversity of the algorithm were compared and analyzed using a variety of performance indicators.Experiment results show that this algorithm can produce higher quality Pareto opti
10、mal solution set and is of better convergence and distribution than the classical multi-objective evolutionary algorithms like NSGA-II, MOEA/D and RVEA as the dimension of decision variables increases in multi-objective optimization problem with large-scale variable.Keyword： Large-scale optimization
11、; Interacting variables; Variable identification; Grouping decomposition; Received： 2016-12-251 引言科学和工程中的优化问题往往非常复杂, 不能通过直接的方式来求解最优解。由于多目标优化问题 (Multi-objective Optimization Problems, MOPs) 具有较大的复杂和困难性, 因此将复杂问题简单化的研究势在必行, 而决策变量的数目大小就极大地影响着优化问题的复杂性1。许多实际问题中的多目标优化问题往往含有成百上千个变量, 一般的优化算法已经难以满足实际应用问题的需要。例
12、如, 在物流网络设计中为使供应链的物流成本和库存成本最小化, 制造商需要将许多回收点和处理点设置在一定的区域范围内, 由此将会产生相当数量的决策变量。而当前多目标进化算法 (Multi-objective Evolutionary Algorithms, MOEAs) 主要是将所有的决策变量当作一个整体来进行优化, 随着所求问题变量维度的增加, 算法的性能将会急剧下降2, 这就是人们所说的“维度灾难”。为解决该问题, 现有的学者受到协同进化 (Cooperative Coevolution) 3和联动学习方法 (Linkage Learning Methods) 4的启发, 提出决策变量分解的
13、策略。该策略在解决大规模变量问题时通过将一个带有高维决策变量的 MOPs 分解为几个简单低维并且容易解决的子问题, 并通过各自独立优化每个子问题来求解。该方法已经被证实可以有效提高进化算法在求解大规模变量优化问题中的效率, 因此被广大学者所关注。但是上述这种“分而治之”的策略存在的主要困难在于如何选择一种较好的分解方法来使不同的子问题间的关联性最小并且算法的优化性能对于所选分解策略具有一定的潜在敏感性。对于大规模变量问题, 如果一个算法可以检测函数的结构特征并据此进行变量分解, 将大大降低问题的困难程度。Potter5于1994 年提出变量固定分组的思想, 其主要内容是在种群进化之前, 根据既
14、定方式将变量固定地分解为若干个组, 然后将每组变量通过合作协同优化来求解全局最优解, 但是在处理含有关联变量的问题时, 该算法的性能会显著下降。Yang6于 2008 年提出 MLCC 算法并将其应用于大规模连续型全局函数的优化中, 该算法使用随机分组策略, 在事先未给定任何先验信息的条件下, 通过随机的方式来对决策变量进行分组, 从而增加将关联变量放到同组中的概率并降低人为因素对变量间关联信息的破坏;同时引入自适应机制来利用种群大小弱化关联变量对分组的影响。Omidvar7于 2010 年提出的高频率随机分组的策略以及Li8于 2012 年提出结合动态改变分组大小的随机分组策略均在一定程度上
15、更好地保证了决策变量分组的随机性, 并有效地降低了各分组间的依赖程度。但是, 现有的随机分组策略一般都采用一次性分组, 即决策变量随机分组后, 在优化过程中每组的变量将不再改变。研究表明这种方式在随机分组的初始阶段虽能较好地缓解关联变量对算法性能的影响, 但是随着关联变量的增加, 使用随机分组将关联变量分到同组中的可能性将大大降低, 这就要求对决策变量进行更为频繁的随机分组, 从而增加算法的复杂度与计算代价, 并导致算法的稳定性下降。为此, Omidvar9又提出 delta 分组策略, 该策略通过优化每一维变量的改变值来确定其分组方式。当优化问题中含有关联变量时, 该分组策略能在一定程度上缓
16、解关联变量对解集的影响。最近, Li10提出基于差分分组的变量交互式学习方法, 该方法可以使算法自动判断决策变量间的关联性, 能较好地挖掘变量间的关联信息并据此进行分组。虽然差分分组较好地解决了关联变量的分组问题, 但从差分分组的机制可以看出, 该策略要求在运行优化算法前必须对决策变量逐个进行筛选, 找出关联变量并对其进行分组, 这无疑会致使算法的复杂度随变量个数的增加而急剧上升。以上算法大多用来解决大规模变量的单目标优化问题, 且并没有应用到 MOPs 中, 而 Coello11首次将随机分组策略应用于大变量的多目标问题, 但是由于缺乏考虑关联变量的存在因素, 导致很难使关联变量分配到同组中, 因此该算法无法深入挖掘变量间存在的信息, 从而使其性能受到影响。现有的决策变量分解方法大多集中在单目标优化问题上, 且缺乏发现变量间相关性的有效办法。而解决大规模变量问题的关键在于寻找决策变量之间的关联性。Salomon12研究了不同变量之间的关联性可以显著影响算法在连续域上的优化性能。尽管变量分解在求解大规模
