A multi-objective memetic algorithm based on decomposition for big optimization problems

详细信息    查看全文

• 作者：Yutong Zhang ; Jing Liu ; Mingxing Zhou ; Zhongzhou Jiang
• 关键词：Big optimization problems ; Decomposition ; Evolutionary multi ; objective optimization ; Gradient methods ; Memetic algorithms
• 刊名：Memetic Computing
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：8
• 期：1
• 页码：45-61
• 全文大小：3,662 KB
• 参考文献：1.Goh SK, Abbass HA, Tan KC, Mamun AA (2015) Evolutionary big optimization (BigOpt) of signals. In: Proc. IEEE Congr. Evol. Comput. Sendai, Japan, pp 3332–3339
  2.Miettinen K (1999) Nonlinear Multiobjective Optimization. Kluwer, Norwell, MAMATH
  3.Zhang Q, Li H (2007) MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6):712–731CrossRef
  4.Knowles J, Corne D, Deb K (2008) Multiobjective Problem Solving from Nature. Springer-Verlag, Berlin, GermanyCrossRef MATH
  5.Coello CAC, Lamont GB, Veldhuizen DAV (2007) Evolutionary Algorithms for Solving Multiobjective Problems. Springer-Verlag, Berlin, Germany
  6.Krasnogor N, Hart W, Smith J (2004) Recent Advances in Memetic Algorithms and Related Search Technologies. Springer-Verlag, Berlin, Germany
  7.Chen XS, Ong XS, Lim MH, Tan KC (2011) A multi-facet survey on memetic computation. IEEE Trans. Evol. Comput. 15(5):591–667CrossRef
  8.Merz P, Freisleben B (2000) Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. Evol. Comput. 4(4):337–352CrossRef
  9.Knowles JD, Corne D (2000) M-PAES: A memetic algorithm for multiobjective optimization. In: Proc. IEEE Congr. Evol. Comput, California, USA, pp 325–332
  10.Islam MK, Chetty M (2013) Clustered memetic algorithm with local heuristics for ab initio protein structure prediction. IEEE Trans. Evol. Comput. 17(4):558–576CrossRef
  11.Bosman PAN (2012) On gradients and hybrid evolutionary algorithms for real-valued multiobjective optimization. IEEE Trans. Evol. Comput. 16(1):51–69CrossRef
  12.Li H, Zhang Q (2009) Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans. Evol. Comput. 15(2):284–302CrossRef
  13.Fliege J, Svaiter BF (2000) Steepest descent methods for multicriteria optimization. Math. Methods Oper. Res. 51(3):479–494CrossRef MathSciNet MATH
  14.Emmerich M, Deutz A, Beume N (2007) Gradient-based/evolutionary relay hybrid for computing Pareto front approximations maximizing the S-metric. In: Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 4771, pp 140–156
  15.Hernández VAS, Schütze O, Emmerich M (2014) Hypervolume Maximization via Set Based Newton’s Method. In: EVOLVE-A Bridge between Probability. Set Oriented Numerics, and Evolutionary Computation V, vol. 288, pp 15–28
  16.Sindhya K, Miettinen K, Deb K (2013) A hybrid framework for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput. 17(4):495–511CrossRef
  17.Goh CK, Ong YS, Tan KC (2008) An investigation on evolutionary gradient search for multiobjective optimization. In: Proc. IEEE Congr. Evol. Comput. Hong Kong, China, pp 3741–3746
  18.Tang L, Wang X (2013) A hybrid multiobjective evolutionary algorithm for multiobjective optimization problems. IEEE Trans. Evol. Comput. 17(1):20–46CrossRef
  19.Jadon SS, Bansal JC, Tiwari R, Sharma H (2015) Accelerating artificial bee colony algorithm with adaptive local search. Memetic Comput. 7(3):215–230CrossRef
  20.Feng L, Ong Y, Lim MH, Tsang IW (2015) Memetic search with interdomain learning: a realization between CVRP and CARP. IEEE Trans. Evol. Comput. 19(5):644–658CrossRef
  21.Feng L, Ong Y, Tan AH, Tsang IW (2015) Memes as building blocks: a case study on evolutionary optimization + transfer learning for routing problems. Memetic Comput. 7(3):159–180CrossRef
  22.Asafuddoula M, Ray T, Sarker R (2015) A decomposition-based evolutionary algorithm for many objective optimization. IEEE Trans. Evol. Comput. 19(3):445–460CrossRef
  23.Li K, Fialho A, Kwong S, Zhang Q (2014) Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 18(1):114–130CrossRef
  24.Liu H, Gu F, Zhang Q (2014) Decomposition of a multiobjective optimization problem into a number of simple multiobjectivesubproblems. IEEE Trans. Evol. Comput. 18(3):450–455CrossRef
  25.Zhong W, Liu J, Xue M, Jiao L (2004) A multiagent genetic algorithm for global numerical optimization. IEEE Trans. on Syst., Man, and Cybern., Part B 34(2):1128–1141CrossRef
  26.Zhang Y, Zhou M, Jiang Z, Liu J (2015) A multi-agent genetic algorithm for big optimization problems. In: Proc. IEEE Congr. Evol. Comput, Sendai, Japan, pp 703–707
  27.Goh SK, Abbass HA, Tan KC, Al-Mamun A (2015) Decompositional independent component analysis using multi-objective optimization. Soft Computing, pp 1–16
  28.Abbass HA (2014) Calibrating independent component analysis with laplacian reference for real-time EEG artifact removal. In: Neural Information Processing. Springer, vol. 8836, pp 68–75
  29.Goh SK, Abbass HA, Tan KC, Al Mamun A (2014) Artifact removal from EEG using a multi-objective independent component analysis model. In: Neural Information Processing. Springer, vol. 8834, pp 570–577
  30.Goh CK, Tan KC (2007) An investigation on noisy environments in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 11(3):354–381CrossRef
  31.Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms – a comparative case study. In: Proc. 5th Int. Conf. Parallel Problem Solving from Nature. Springer-Verlag, Berlin, Germany, pp 292-301
  32.Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2):182–197CrossRef
  33.Deb K, Jain H (2014) An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints. IEEE Trans. Evol. Comput. 18(4):577–601CrossRef
  34.Deb K (2001) Multi-objective optimization using evolutionary algorithms. John Wiley & Sons, New YorkMATH
  35.Xiong J, Liu J, Chen Y, Abbass HA (2014) A knowledge-based evolutionary multiobjective approach for stochastic extended resource investment project scheduling problems. IEEE Trans. Evol. Comput. 18(5):742–763CrossRef
  36.Das I, Dennis JE (1998) Normal-boundary intersection: A new method for generating Pareto optimal points in multicriteria optimization problems. SIAM J. Optim. 8(3):613–657CrossRef MathSciNet
  
• 作者单位：Yutong Zhang (1)
  Jing Liu (1)
  Mingxing Zhou (1)
  Zhongzhou Jiang (1)
  
  1. Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, Xidian University, Xi’an, 710071, China
  
• 刊物类别：Engineering
• 刊物主题：Applied Mathematics and Computational Methods of Engineering
  Artificial Intelligence and Robotics
  Automation and Robotics
  Complexity
  Bioinformatics
  Applications of Mathematics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1865-9292

文摘

When solving multi-objective optimization problems (MOPs) with big data, traditional multi-objective evolutionary algorithms (MOEAs) meet challenges because they demand high computational costs that cannot satisfy the demands of online data processing involving optimization. The gradient heuristic optimization methods show great potential in solving large scale numerical optimization problems with acceptable computational costs. However, some intrinsic limitations make them unsuitable for searching for the Pareto fronts. It is believed that the combination of these two types of methods can deal with big MOPs with less computational cost. The main contribution of this paper is that a multi-objective memetic algorithm based on decomposition for big optimization problems (MOMA/D-BigOpt) is proposed and a gradient-based local search operator is embedded in MOMA/D-BigOpt. In the experiments, MOMA/D-BigOpt is tested on the multi-objective big optimization problems with thousands of variables. We also combine the local search operator with other widely used MOEAs to verify its effectiveness. The experimental results show that the proposed algorithm outperforms MOEAs without the gradient heuristic local search operator.