Skip to main content
Erschienen in: Memetic Computing 1/2016

01.03.2016 | Regular Research Paper

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

verfasst von: Yutong Zhang, Jing Liu, Mingxing Zhou, Zhongzhou Jiang

Erschienen in: Memetic Computing | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
This is the case of maximization problem. For the minimization problem, minus sub-gradient direction will be used.
 
Literatur
1.
Zurück zum Zitat 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 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.
Zurück zum Zitat Miettinen K (1999) Nonlinear Multiobjective Optimization. Kluwer, Norwell, MAMATH Miettinen K (1999) Nonlinear Multiobjective Optimization. Kluwer, Norwell, MAMATH
3.
Zurück zum Zitat Zhang Q, Li H (2007) MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6):712–731CrossRef Zhang Q, Li H (2007) MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6):712–731CrossRef
4.
Zurück zum Zitat Knowles J, Corne D, Deb K (2008) Multiobjective Problem Solving from Nature. Springer-Verlag, Berlin, GermanyCrossRefMATH Knowles J, Corne D, Deb K (2008) Multiobjective Problem Solving from Nature. Springer-Verlag, Berlin, GermanyCrossRefMATH
5.
Zurück zum Zitat Coello CAC, Lamont GB, Veldhuizen DAV (2007) Evolutionary Algorithms for Solving Multiobjective Problems. Springer-Verlag, Berlin, Germany Coello CAC, Lamont GB, Veldhuizen DAV (2007) Evolutionary Algorithms for Solving Multiobjective Problems. Springer-Verlag, Berlin, Germany
6.
Zurück zum Zitat Krasnogor N, Hart W, Smith J (2004) Recent Advances in Memetic Algorithms and Related Search Technologies. Springer-Verlag, Berlin, Germany Krasnogor N, Hart W, Smith J (2004) Recent Advances in Memetic Algorithms and Related Search Technologies. Springer-Verlag, Berlin, Germany
7.
Zurück zum Zitat Chen XS, Ong XS, Lim MH, Tan KC (2011) A multi-facet survey on memetic computation. IEEE Trans. Evol. Comput. 15(5):591–667CrossRef 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.
Zurück zum Zitat Merz P, Freisleben B (2000) Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. Evol. Comput. 4(4):337–352CrossRef 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.
Zurück zum Zitat Knowles JD, Corne D (2000) M-PAES: A memetic algorithm for multiobjective optimization. In: Proc. IEEE Congr. Evol. Comput, California, USA, pp 325–332 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Bosman PAN (2012) On gradients and hybrid evolutionary algorithms for real-valued multiobjective optimization. IEEE Trans. Evol. Comput. 16(1):51–69CrossRef Bosman PAN (2012) On gradients and hybrid evolutionary algorithms for real-valued multiobjective optimization. IEEE Trans. Evol. Comput. 16(1):51–69CrossRef
12.
Zurück zum Zitat 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 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.
Zurück zum Zitat Fliege J, Svaiter BF (2000) Steepest descent methods for multicriteria optimization. Math. Methods Oper. Res. 51(3):479–494CrossRefMathSciNetMATH Fliege J, Svaiter BF (2000) Steepest descent methods for multicriteria optimization. Math. Methods Oper. Res. 51(3):479–494CrossRefMathSciNetMATH
14.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Sindhya K, Miettinen K, Deb K (2013) A hybrid framework for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput. 17(4):495–511CrossRef Sindhya K, Miettinen K, Deb K (2013) A hybrid framework for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput. 17(4):495–511CrossRef
17.
Zurück zum Zitat 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 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.
Zurück zum Zitat Tang L, Wang X (2013) A hybrid multiobjective evolutionary algorithm for multiobjective optimization problems. IEEE Trans. Evol. Comput. 17(1):20–46CrossRef Tang L, Wang X (2013) A hybrid multiobjective evolutionary algorithm for multiobjective optimization problems. IEEE Trans. Evol. Comput. 17(1):20–46CrossRef
19.
Zurück zum Zitat Jadon SS, Bansal JC, Tiwari R, Sharma H (2015) Accelerating artificial bee colony algorithm with adaptive local search. Memetic Comput. 7(3):215–230CrossRef 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Asafuddoula M, Ray T, Sarker R (2015) A decomposition-based evolutionary algorithm for many objective optimization. IEEE Trans. Evol. Comput. 19(3):445–460CrossRef 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Goh SK, Abbass HA, Tan KC, Al-Mamun A (2015) Decompositional independent component analysis using multi-objective optimization. Soft Computing, pp 1–16 Goh SK, Abbass HA, Tan KC, Al-Mamun A (2015) Decompositional independent component analysis using multi-objective optimization. Soft Computing, pp 1–16
28.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Goh CK, Tan KC (2007) An investigation on noisy environments in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 11(3):354–381CrossRef Goh CK, Tan KC (2007) An investigation on noisy environments in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 11(3):354–381CrossRef
31.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Deb K (2001) Multi-objective optimization using evolutionary algorithms. John Wiley & Sons, New YorkMATH Deb K (2001) Multi-objective optimization using evolutionary algorithms. John Wiley & Sons, New YorkMATH
35.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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–657CrossRefMathSciNet 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–657CrossRefMathSciNet
Metadaten
Titel
A multi-objective memetic algorithm based on decomposition for big optimization problems
verfasst von
Yutong Zhang
Jing Liu
Mingxing Zhou
Zhongzhou Jiang
Publikationsdatum
01.03.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
Memetic Computing / Ausgabe 1/2016
Print ISSN: 1865-9284
Elektronische ISSN: 1865-9292
DOI
https://doi.org/10.1007/s12293-015-0175-9

Weitere Artikel der Ausgabe 1/2016

Memetic Computing 1/2016 Zur Ausgabe

Editorial

Editorial