关联变量分组的分解多目标进化算法研究

doi:10.11896/j.issn.1002-137X.2017.12.037

摘要/Abstract

摘要： 含有大规模决策变量的优化问题是当前多目标进化算法领域中的研究热点和难点之一。在解决大规模变量问题时,目前的进化算法并没有寻找决策变量之间的关联信息,而都只是将所有变量视为一个整体来进行优化。但随着优化问题中决策变量的增多,“变量维度”成为瓶颈,从而影响算法的性能。针对上述问题,提出关联变量分组策略,通过识别决策变量间内在的关联信息把关联变量分配到同组中,将复杂高维变量的优化问题分解为简单低维的子问题来求解。该策略通过增加关联变量分配到同组中的概率来使算法尽可能地保留变量之间的关联性,减少分组后子问题间的依赖性,从而提高子问题最优解的质量并最终获得最佳的Pareto最优解集。将该算法在标准测试函数上进行变量扩展后再进行仿真对比实验,采用性能指标对算法的收敛性和多样性进行对比分析。实验结果表明,该算法在解决大规模变量的多目标优化问题中,随着决策变量维度的增加,比经典的多目标进化算法NSGA-II、MOEA/D以及RVEA具有更佳的收敛和更好的分布性能,所求得的Pareto解集质量更高。

关键词: 大规模优化,关联变量,变量识别,分组分解

Abstract: Optimization problem with large-scale decision variable is one of the hot and 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 variable 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 decision 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 low-dimensional subproblems that are easier to solve.In order to make the algorithm as far as possible to retain the relationship between variables 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.Comparative 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 optimal 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.

Key words: Large-scale optimization,Interacting variables,Variable identification,Grouping decomposition

邱飞岳,胡烜,王丽萍. 关联变量分组的分解多目标进化算法研究[J]. 计算机科学, 2017, 44(12): 202-210. https://doi.org/10.11896/j.issn.1002-137X.2017.12.037

QIU Fei-yue, HU Xuan and WANG Li-ping. Research on Multi-objective Evolutionary Algorithm Based on Decomposition Using Interacting Variables Grouping[J]. Computer Science, 2017, 44(12): 202-210. https://doi.org/10.11896/j.issn.1002-137X.2017.12.037

参考文献

[1] WEISE T,CHIONG R,TANG K.Evolutionary optimization:Pitfalls and booby traps[J].Journal of Computer Science and Technology,2012,7(5):907-936.
[2] LIU Y,YAO X,ZHAO Q F,et al.Scaling up fast evolutionary programming with cooperative coevolution[C]∥Proceedings of IEEE Congress on Evolutionary Computation.Seoul,2001:1101-1108.
[3] YANG Z Y,TANG K,YAO X.Large scale evolutionary optimization using cooperative coevolution[J].Information Sciences,2008,8(15):2985-2999.
[4] CHEN Y P,YU T L,SASTRY K,et al.A survey of linkage learning techniques in genetic and evolutionary algorithms[R].Urbana IL:University of IUinois at Urbana-champaign,2007.
[5] POTTER M A,DE JONG K A.A cooperative coevolutionary approach to function optimization[C]∥Proceedings of International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg,1994:249-257.
[6] YANG Z Y,TANG K,YAO X.Multilevel cooperative coevolution for large scale optimization[C]∥Proceedings of IEEE Congress on Evolutionary Computation.Hong Kong,2008:1663-1670.
[7] OMIDVAR M N,LI X D,YANG Z Y,et al.Cooperative co-evolution for large scale optimization through more frequent random grouping[C]∥Proceedings of IEEE World Congress on Computation Intelligence.Barcelona,2010:1754-1761.
[8] LI X D,YAO X.Cooperatively coevolving particle swarms for large scale optimization[J].IEEE Transactions on Evolutionary Computation,2012,6(2):210-224.
[9] OMIDVAR M N,LI X D,YAO X.Cooperative co-evolutionwith delta grouping for large scale non-separable function optimization[C]∥Proceedings of IEEE World Congress on Computation Intelligence.Barcelona,2010:1762-1769.
[10] OMIDVAR M N,LI X D,MEI Y,et al.Cooperative co-evolution with differential grouping for large scale optimization[J].IEEE Transactions on Evolutionary Computation,2014,8(3):378-393.
[11] ANTONIO L M,COELLO C A C.Use of cooperative coevolution for solving large scale multiobjective optimization problems[C]∥Proceedings of IEEE Congress on Evolutionary Computation.Cancun,2013:2758-2765.
[12] SALOMON R.Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions:A survey of some theoretical and practical aspects of genetic algorithms[J].BioSystems,1996,9(3):263-278.
[13] LI K,ZHANG Q F,KWONG S,et al.Stable matching-based selection in evolutionary multiobjective optimization[J].IEEE Transactions on Evolutionary Computation,2014,8(6):909-923.
[14] DEB K.Multi-objective optimization using evolutionary algo-rithms[M].John Wiley & Sons,2001.
[15] ZHANG Q F,LI H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,1(6):712-731.
[16] CHEN W X,WEISE T,YANG Z Y,et al.Large-scale global optimization using cooperative coevolution with variable interaction learning[C]∥Proceedings of International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg,2010:300-309.
[17] ZHANG Q F,ZHOU A M,ZHAO S Z,et al.Multiobjective optimization test instances for the CEC 2009 special session and competition[R].Colchester:University of Essex,2008.
[18] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[19] CHENG R,JIN Y C,OLHOFER M,et al.A reference vector guided evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation,2016,20(5):773-791.
[20] VAN VELDHUIZEN D A,LAMONT G B.On measuring multiobjective evolutionary algorithm performance[C]∥Procee-dings of IEEE Congress on Evolutionary Computation.California,2000:204-211.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed