一种带差分局部搜索的改进型NSGA2算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (10): 235-238.

一种带差分局部搜索的改进型NSGA2算法

谢承旺,李凯,廖国勇

华东交通大学软件学院南昌330013;华东交通大学软件学院南昌330013;华东交通大学基础科学学院南昌330013

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(61165004),江西省自然科学基金(20114BAB201025),江西省教育厅科技项目(GJJ12307)资助

Improved NSGA2Algorithm with Differential Evolution Local Search

XIE Cheng-wang,LI Kai and LIAO Guo-yong

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： NSGA2算法以其Pareto支配的选择模式并辅以解个体密度估计算子选择胜出解的策略而成为了现代多目标进化算法的典范,但是该算法通过计算解个体的聚集距离来保持群体的分布性的机制存在一定的缺陷。鉴于此,提出了一种带差分局部搜索的改进型NSGA2算法。新算法利用差分进化中变异算子的定向引导作用,抽取其中的差分向量,并与NSGA2算法结合以改善解群的分布性。仿真实验表明:新算法较NSGA2算法在解群分布的均匀性和广度上有明显的改善。此外,新算法在时间复杂性方面与经典的NSGA2算法相当。

关键词: 差分进化,局部搜索,NSGA2,分布性

Abstract: NSGA2algorithm with its selection mode of Pareto dominate method and the strategy of using individual density estimation operator of solution to select winning solution becomes the model of modern multi-objective evolutionary algorithm,but the algorithm by computing the solution of individual crowding distance to keep the population distribution mechanisms has certain defects．In view of this,this paper proposed a kind of improved algorithm which takes differential local search with NSGA2algorithm.The new algorithm uses the differential evolution mutation operator in directional guiding ideology,takes the difference vector,and combines the NSGA2algorithm to improve the solution population distribution．Simulation results show that the new algorithm compared with the NSGA2algorithm in the solution of cluster distribution uniformity and depth is improved obviously．In addition,the new algorithm in the time complexity is same as the classic NSGA2algorithm.

Key words: Differential evolution,Local search,NSGA2,Diversity

谢承旺,李凯,廖国勇. 一种带差分局部搜索的改进型NSGA2算法[J]. 计算机科学, 2013, 40(10): 235-238. https://doi.org/

XIE Cheng-wang,LI Kai and LIAO Guo-yong. Improved NSGA2Algorithm with Differential Evolution Local Search[J]. Computer Science, 2013, 40(10): 235-238. https://doi.org/

参考文献

[1] Schaffer J D.Multiple objective optimization,with vector evaluated genetic algorithms[C]∥Proceedings of International Conference on Genetic Algorithms and Their Applications．Pittsburgh,PA,1985:93-100
[2] Zitzler E,Thiele L.Multi-objective evolutionary algorithms:Acomparative case study and the strength pareto approach[J].IEEE Transactions on Evolutionary Computation,1999,3(4):257-271
[3] Zitzler E,Laumanns M,Thiele L.SPEA2:Improving the streng-th Pareto evolutionary algorithm[R]．TIK2Report 103.2001
[4] Srinivas N,Deb K.Multi-objective optimization using non-dominated sorting in genetic algorithms[J].Evolutionary Computation,1994,2(3):221-248
[5] Deb K,Agrawal S,Pratab A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGAII[R]．KanGAL Report 200001．Indian Institute of Technology,Kanpur,India,2000
[6] Corne D W,Knowles J D,Oates M J.The Pareto envelope-based selection algorithm for multiobjective optimization[C]∥Schoenauer M,Deb K,Rudolph G,et al.Proceedings of the Parallel Problem Solving from Nature VI Conference.New York:Springer,2000:839-848
[7] Deb K,Mohan M,Mishra S.A fast multi-objective evolutionary algorithm for finding well-spread Pareto-optimal solutions[R].KanGAL Report No 2003002．2003
[8] Storn R,Price K.Differential Evolution-A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J].Journal of Global Optimization,1997,11(4):341-359
[9] Noman N,Iba H.Accelerating differential evolution using anadaptive local search[J]．IEEE Trans,Evolut．Comput.,2008,12:107-125
[10] 刘波,王凌,金以慧.差分进化算法研究发展[J].控制与决策,2007,34(3):1-5
[11] 郑金华.多目标进化算法及应用[M].北京:科学出版社,2007:23-24
[12] Schott J R.Fault tolerant design using single and multicriteria genetic algorithm optimization[D].Department of Aeronautics and Astronautics,Massachusetts Institute of Technology,Cambridge,Massachusetts,1995

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed