基于聚类的新型多目标分布估计算法及其应用
|
摘要
为改善常见的多目标分布估计算法在求解多目标优化问题的过程中存在的不足,即:对问题的规则特性考虑不够,对种群中异常解的处理不当,种群多样性容易丢失,过多的计算开销用于构建最优概率模型,提出一种基于聚类的新型多目标分布估计算法(clustering-based multi-objective estimation of distribution algorithm,CEDA)。CEDA在每一代运用凝聚层次聚类算法发掘种群个体的邻近结构,基于此结构,为每个个体构建一个多元高斯模型逼近种群结构并抽样产生新个体。为了降低建模计算开销,邻近个体共享相同的协方差矩阵建立高斯模型。基于标准测试题的对比实验表明CEDA能够解决复杂的多目标优化问题。基于齿轮减速器优化设计的实际应用表明CEDA同样具有良好的实用性和优越性。
In order to improve the deficiencies,that is,insufficiently considering the regularity property,inappropriately handling abnormal solutions,easily losing population diversity,and the excessive computational cost of constructing the optimal probabilistic model,which exist in the process of using common multi-objective estimation of distribution algorithms to solve multi-objective optimization problems,this paper proposes a clustering-based multi-objective estimation of distribution algorithm(CEDA).At each generation,CEDA adopts an agglomerative hierarchical clustering algorithm to find the neighborhood structure of population,and based on the structure,CEDA builds a multivariate Gaussian model for each solution to approximate population structure and to sample new solutions.In order to reduce the computational cost of modelling,neighboring solutions share the same covariance matrix to construct Gaussian models.The comparison experiments based on benchmark instances indicate that CEDA is able to solve complicated multi-objective optimization problems.Practical application based on optimization design of the gear reducer shows CEDA also has favorable practicability and superiority.
In order to improve the deficiencies,that is,insufficiently considering the regularity property,inappropriately handling abnormal solutions,easily losing population diversity,and the excessive computational cost of constructing the optimal probabilistic model,which exist in the process of using common multi-objective estimation of distribution algorithms to solve multi-objective optimization problems,this paper proposes a clustering-based multi-objective estimation of distribution algorithm(CEDA).At each generation,CEDA adopts an agglomerative hierarchical clustering algorithm to find the neighborhood structure of population,and based on the structure,CEDA builds a multivariate Gaussian model for each solution to approximate population structure and to sample new solutions.In order to reduce the computational cost of modelling,neighboring solutions share the same covariance matrix to construct Gaussian models.The comparison experiments based on benchmark instances indicate that CEDA is able to solve complicated multi-objective optimization problems.Practical application based on optimization design of the gear reducer shows CEDA also has favorable practicability and superiority.
引文
[1]ZHOU A,QU B Y,LI H,et al.Multiobjective evolutionary algorithms:a survey of the state of the art[J].Swarm&Evolutionary Computation,2011,1(1):32-49.
[2]DEB K,BEYER H G.Self-adaptive genetic algorithms with simulated binary crossover[J].Evolutionary Computation,2001,9(2):197-221.
[3]SCHAER J D.Multiple objective optimization with vector evaluated genetic algorithms[C]∥Proc.of the International Conference on Genetic Algorithms and Their Applications,1985:93-100.
[4]MARTíL,GRIMME C,KERSCHKE P,et al.Averaged Hausdorff approximations of pareto fronts based on multiobjective estimation of distribution algorithms[C]∥Proc.of the Companion Publication of the Annual Conference on Genetic and Evolutionary Computation,2015:1427-1428.
[5]PELIKAN M,SASTRY K,GOLDBERG D E.Multiobjective estimation of distribution algorithms[C]∥Proc.of the Scalable Optimization Via Probabilistic Modeling,2006:223-248.
[6]LARRA珦NAGA P,LOZANO J A.Estimation of distribution algorithms:A new tool for evolutionary computation[M].Springer Science&Business Media,2002.
[7]ZHANG Q,ZHOU A,JIN Y.RM-MEDA:a regularity modelbased multiobjective estimation of distribution algorithm[J].IEEE Trans.on Evolutionary Computation,2008,12(1):41-63.
[8]BOSMAN P A,THIERENS D.Multi-objective optimization with diversity preserving mixture-based iterated density estimation evolutionary algorithms[J].International Journal of Approximate Reasoning,2002,31(3):259-289.
[9]PELIKAN M,SASTRY K,GOLDBERG D E.Multiobjective hBOA,clustering,and scalability[C]∥Proc.of the 7th Annual Conference on Genetic and Evolutionary Computation,2005:663-670.
[10]SASTRY K,GOLDBERG D E,PELIKAN M.Limits of scalability of multiobjective estimation of distribution algorithms[C]∥Proc.of the IEEE Congress on Evolutionary Computation,2005:2217-2224.
[11]SHIM V A,TAN K C,CHEONG C Y.A hybrid estimation of distribution algorithm with decomposition for solving the multiobjective multiple traveling salesman problem[J].IEEE Trans.on Systems,Man,and Cybernetics,Part C(Applications and Reviews),2012,42(5):682-691.
[12]CHENG R,JIN Y,NARUKAWA K,et al.A multiobjective evolutionary algorithm using Gaussian process-based inverse modeling[J].IEEE Trans.on Evolutionary Computation,2015,19(6):838-856.
[13]ZHOU A,ZHANG Q,JIN Y.Approximating the set of Paretooptimal solutions in both the decision and objective spaces by an estimation of distribution algorithm[J].IEEE Trans.on Evolutionary Computation,2009,13(5):1167-1189.
[14]WANG Y,XIANG J,CAI Z.A regularity model-based multiobjective estimation of distribution algorithm with reducing redundant cluster operator[J].Applied Soft Computing,2012,12(11):3526-3538.
[15]LI Y,XU X,LI P,et al.Improved RM-MEDA with local learning[J].Soft Computing,2014,18(7):1383-1397.
[16]LI K,KWONG S.A general framework for evolutionary multiobjective optimization via manifold learning[J].Neurocomputing,2014,146(1):65-74.
[17]XU R,WUNSCH D.Clustering[M].New Jersey:Wiley,2008.
[18]BEUME N,NAUJOKS B,EMMERICH M.SMS-EMOA:multiobjective selection based on dominated hypervolume[J].European Journal of Operational Research,2007,181(3):1653-1669.
[19]ZITZLER E,THIELE L,LAUMANNS M,et al.Performance assessment of multiobjective optimizers:an analysis and review[J].IEEE Trans.on Evolutionary Computation,2003,7(2):117-132.
[20]ZHANG H,ZHOU A,SONG S,et al.A self-organizing multiobjective evolutionary algorithm[J],IEEE Trans.on Evolutionary Computation,2016,20(5):792-806.
[21]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J].IEEE Trans.on Evolutionary Computation,2002,6(2):182-197.
[22]JIN Y,SENDHOFF B.Connectedness,regularity and the success of local search in evolutionary multi-objective optimization[C]∥Proc.of the IEEE Congress on Evolutionary Computation,2003:1910-1917.
[23]ZHOU A,ZHANG Q,JIN Y,et al.A model-based evolutionary algorithm for bi-objective optimization[C]∥Proc.of the IEEE Congress on Evolutionary Computation,2005:2568-2575.
[24]ZITZLER E,THIELE L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Trans.on Evolutionary Computation,1999,3(4):257-271.
[25]LIU H L,GU F,CHEUNG Y.T-MOEA/D:MOEA/D with objective transform in multi-objective problems[C]∥Proc.of the International Conference on Information Science and Management Engineering,2010:282-285.
[26]FARHANG-MEHR A,AZARM S.Entropy-based multi-objective genetic algorithm for design optimization[J].Structural&Multidisciplinary Optimization,2002,24(5):351-361.
[27]AZARM S,TITS A,FAN M.Tradeoff driven optimizationbased design of mechanical systems[C]∥Proc.of the Symposium on Multidisciplinary Analysis and Optimization,1989:551-558.
[2]DEB K,BEYER H G.Self-adaptive genetic algorithms with simulated binary crossover[J].Evolutionary Computation,2001,9(2):197-221.
[3]SCHAER J D.Multiple objective optimization with vector evaluated genetic algorithms[C]∥Proc.of the International Conference on Genetic Algorithms and Their Applications,1985:93-100.
[4]MARTíL,GRIMME C,KERSCHKE P,et al.Averaged Hausdorff approximations of pareto fronts based on multiobjective estimation of distribution algorithms[C]∥Proc.of the Companion Publication of the Annual Conference on Genetic and Evolutionary Computation,2015:1427-1428.
[5]PELIKAN M,SASTRY K,GOLDBERG D E.Multiobjective estimation of distribution algorithms[C]∥Proc.of the Scalable Optimization Via Probabilistic Modeling,2006:223-248.
[6]LARRA珦NAGA P,LOZANO J A.Estimation of distribution algorithms:A new tool for evolutionary computation[M].Springer Science&Business Media,2002.
[7]ZHANG Q,ZHOU A,JIN Y.RM-MEDA:a regularity modelbased multiobjective estimation of distribution algorithm[J].IEEE Trans.on Evolutionary Computation,2008,12(1):41-63.
[8]BOSMAN P A,THIERENS D.Multi-objective optimization with diversity preserving mixture-based iterated density estimation evolutionary algorithms[J].International Journal of Approximate Reasoning,2002,31(3):259-289.
[9]PELIKAN M,SASTRY K,GOLDBERG D E.Multiobjective hBOA,clustering,and scalability[C]∥Proc.of the 7th Annual Conference on Genetic and Evolutionary Computation,2005:663-670.
[10]SASTRY K,GOLDBERG D E,PELIKAN M.Limits of scalability of multiobjective estimation of distribution algorithms[C]∥Proc.of the IEEE Congress on Evolutionary Computation,2005:2217-2224.
[11]SHIM V A,TAN K C,CHEONG C Y.A hybrid estimation of distribution algorithm with decomposition for solving the multiobjective multiple traveling salesman problem[J].IEEE Trans.on Systems,Man,and Cybernetics,Part C(Applications and Reviews),2012,42(5):682-691.
[12]CHENG R,JIN Y,NARUKAWA K,et al.A multiobjective evolutionary algorithm using Gaussian process-based inverse modeling[J].IEEE Trans.on Evolutionary Computation,2015,19(6):838-856.
[13]ZHOU A,ZHANG Q,JIN Y.Approximating the set of Paretooptimal solutions in both the decision and objective spaces by an estimation of distribution algorithm[J].IEEE Trans.on Evolutionary Computation,2009,13(5):1167-1189.
[14]WANG Y,XIANG J,CAI Z.A regularity model-based multiobjective estimation of distribution algorithm with reducing redundant cluster operator[J].Applied Soft Computing,2012,12(11):3526-3538.
[15]LI Y,XU X,LI P,et al.Improved RM-MEDA with local learning[J].Soft Computing,2014,18(7):1383-1397.
[16]LI K,KWONG S.A general framework for evolutionary multiobjective optimization via manifold learning[J].Neurocomputing,2014,146(1):65-74.
[17]XU R,WUNSCH D.Clustering[M].New Jersey:Wiley,2008.
[18]BEUME N,NAUJOKS B,EMMERICH M.SMS-EMOA:multiobjective selection based on dominated hypervolume[J].European Journal of Operational Research,2007,181(3):1653-1669.
[19]ZITZLER E,THIELE L,LAUMANNS M,et al.Performance assessment of multiobjective optimizers:an analysis and review[J].IEEE Trans.on Evolutionary Computation,2003,7(2):117-132.
[20]ZHANG H,ZHOU A,SONG S,et al.A self-organizing multiobjective evolutionary algorithm[J],IEEE Trans.on Evolutionary Computation,2016,20(5):792-806.
[21]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J].IEEE Trans.on Evolutionary Computation,2002,6(2):182-197.
[22]JIN Y,SENDHOFF B.Connectedness,regularity and the success of local search in evolutionary multi-objective optimization[C]∥Proc.of the IEEE Congress on Evolutionary Computation,2003:1910-1917.
[23]ZHOU A,ZHANG Q,JIN Y,et al.A model-based evolutionary algorithm for bi-objective optimization[C]∥Proc.of the IEEE Congress on Evolutionary Computation,2005:2568-2575.
[24]ZITZLER E,THIELE L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach[J].IEEE Trans.on Evolutionary Computation,1999,3(4):257-271.
[25]LIU H L,GU F,CHEUNG Y.T-MOEA/D:MOEA/D with objective transform in multi-objective problems[C]∥Proc.of the International Conference on Information Science and Management Engineering,2010:282-285.
[26]FARHANG-MEHR A,AZARM S.Entropy-based multi-objective genetic algorithm for design optimization[J].Structural&Multidisciplinary Optimization,2002,24(5):351-361.
[27]AZARM S,TITS A,FAN M.Tradeoff driven optimizationbased design of mechanical systems[C]∥Proc.of the Symposium on Multidisciplinary Analysis and Optimization,1989:551-558.