Skip to main content
Top

2013 | OriginalPaper | Chapter

A Study on the Specification of a Scalarizing Function in MOEA/D for Many-Objective Knapsack Problems

Authors : Hisao Ishibuchi, Naoya Akedo, Yusuke Nojima

Published in: Learning and Intelligent Optimization

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In recent studies on evolutionary multiobjective optimization, MOEA/D has been frequently used due to its simplicity, high computational efficiency, and high search ability. A multiobjective problem in MOEA/D is decomposed into a number of single-objective problems, which are defined by a single scalarizing function with evenly specified weight vectors. The number of the single-objective problems is the same as the number of weight vectors. The population size is also the same as the number of weight vectors. Multiobjective search for a variety of Pareto optimal solutions is realized by single-objective optimization of a scalarizing function in various directions. In this paper, we examine the dependency of the performance of MOEA/D on the specification of a scalarizing function. MOEA/D is applied to knapsack problems with 2-10 objectives. As a scalarizing function, we examine the weighted sum, the weighted Tchebycheff, and the PBI (penalty-based boundary intersection) function with a wide range of penalty parameter values. Experimental results show that the weighted Tchebycheff and the PBI function with an appropriate penalty parameter value outperformed the weighted sum and the PBI function with no penalty parameter in computational experiments on two-objective problems. However, better results were obtained from the weighted sum and the PBI function with no penalty parameter for many-objective problems with 6-10 objectives. We discuss the reason for these observations using the contour line of each scalarizing function. We also suggest potential usefulness of the PBI function with a negative penalty parameter value for many-objective problems.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

Literature
1.
go back to reference Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11, 712–731 (2007)CrossRef Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11, 712–731 (2007)CrossRef
2.
go back to reference Chang, P.C., Chen, S.H., Zhang, Q., Lin, J.L.: MOEA/D for flowshop scheduling problems. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 1433–1438 (2008) Chang, P.C., Chen, S.H., Zhang, Q., Lin, J.L.: MOEA/D for flowshop scheduling problems. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 1433–1438 (2008)
3.
go back to reference Zhang, Q., Liu, W., Li, H.: The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 203–208 (2009) Zhang, Q., Liu, W., Li, H.: The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 203–208 (2009)
4.
go back to reference Li, H., Zhang, Q.: Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans. Evol. Comput. 13, 284–302 (2009)CrossRef Li, H., Zhang, Q.: Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans. Evol. Comput. 13, 284–302 (2009)CrossRef
5.
go back to reference Ishibuchi, H., Sakane, Y., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, pp. 1820–1825 (2009) Ishibuchi, H., Sakane, Y., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations. In: Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, pp. 1820–1825 (2009)
6.
go back to reference Zhang, Q., Liu, W., Tsang, E., Virginas, B.: Expensive multiobjective optimization by MOEA/D with Gaussian process model. IEEE Trans. Evol. Comput. 14, 456–474 (2010)CrossRef Zhang, Q., Liu, W., Tsang, E., Virginas, B.: Expensive multiobjective optimization by MOEA/D with Gaussian process model. IEEE Trans. Evol. Comput. 14, 456–474 (2010)CrossRef
7.
go back to reference Tan, Y.Y., Jiao, Y.C., Li, H., Wang, X.K.: A modification to MOEA/D-DE for multiobjective optimization problems with complicated pareto sets. Inf. Sci. 213, 14–38 (2012)MathSciNetCrossRefMATH Tan, Y.Y., Jiao, Y.C., Li, H., Wang, X.K.: A modification to MOEA/D-DE for multiobjective optimization problems with complicated pareto sets. Inf. Sci. 213, 14–38 (2012)MathSciNetCrossRefMATH
8.
go back to reference Zhao, S.Z., Suganthan, P.N., Zhang, Q.: Decomposition-based multiobjective evolutionary algorithm with an ensemble of neighborhood sizes. IEEE Trans. Evol. Comput. 16, 442–446 (2012)CrossRef Zhao, S.Z., Suganthan, P.N., Zhang, Q.: Decomposition-based multiobjective evolutionary algorithm with an ensemble of neighborhood sizes. IEEE Trans. Evol. Comput. 16, 442–446 (2012)CrossRef
9.
go back to reference Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182–197 (2002)CrossRef Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182–197 (2002)CrossRef
10.
go back to reference Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report 103, Department of Electrical Engineering, ETH, Zurich (2001) Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. TIK-Report 103, Department of Electrical Engineering, ETH, Zurich (2001)
11.
go back to reference Ishibuchi, H., Hitotsuyanagi, Y., Ohyanagi, H., Nojima, Y.: Effects of the existence of highly correlated objectives on the behavior of MOEA/D. In: Takahashi, R.H.C., Deb, K., Wanner, E.F., Greco, S. (eds.) EMO 2011. LNCS, vol. 6576, pp. 166–181. Springer, Heidelberg (2011) Ishibuchi, H., Hitotsuyanagi, Y., Ohyanagi, H., Nojima, Y.: Effects of the existence of highly correlated objectives on the behavior of MOEA/D. In: Takahashi, R.H.C., Deb, K., Wanner, E.F., Greco, S. (eds.) EMO 2011. LNCS, vol. 6576, pp. 166–181. Springer, Heidelberg (2011)
12.
go back to reference Ishibuchi, H., Sakane, Y., Tsukamoto, N., Nojima, Y.: Simultaneous use of different scalarizing functions in MOEA/D. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 519–526 (2010) Ishibuchi, H., Sakane, Y., Tsukamoto, N., Nojima, Y.: Simultaneous use of different scalarizing functions in MOEA/D. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 519–526 (2010)
13.
go back to reference Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evol. Comput. 3, 257–271 (1999)CrossRef Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. Evol. Comput. 3, 257–271 (1999)CrossRef
14.
go back to reference Ishibuchi, H., Hitotsuyanagi, Y., Ohyanagi, H., Nojima, Y.: Effects of the existence of highly correlated objectives on the behavior of MOEA/D. In: Takahashi, R.H.C., Deb, K., Wanner, E.F., Greco, S. (eds.) EMO 2011. LNCS, vol. 6576, pp. 166–181. Springer, Heidelberg (2011) Ishibuchi, H., Hitotsuyanagi, Y., Ohyanagi, H., Nojima, Y.: Effects of the existence of highly correlated objectives on the behavior of MOEA/D. In: Takahashi, R.H.C., Deb, K., Wanner, E.F., Greco, S. (eds.) EMO 2011. LNCS, vol. 6576, pp. 166–181. Springer, Heidelberg (2011)
15.
go back to reference Miettinen, K.: Nonlinear Multiobjective Optimization. Kluwer, Dordrecht (1999)MATH Miettinen, K.: Nonlinear Multiobjective Optimization. Kluwer, Dordrecht (1999)MATH
16.
go back to reference Hughes, E. J.: Evolutionary many-objective optimisation: many once or one many? In: Procedings of IEEE Congress on Evolutionary Computation, pp. 222–227 (2005) Hughes, E. J.: Evolutionary many-objective optimisation: many once or one many? In: Procedings of IEEE Congress on Evolutionary Computation, pp. 222–227 (2005)
17.
go back to reference Purshouse, R.C., Fleming, P.J.: On the evolutionary optimization of many conflicting objectives. IEEE Trans. Evol. Comput. 11, 770–784 (2007)CrossRef Purshouse, R.C., Fleming, P.J.: On the evolutionary optimization of many conflicting objectives. IEEE Trans. Evol. Comput. 11, 770–784 (2007)CrossRef
18.
go back to reference Sato, H., Aguirre, H.E., Tanaka, K.: Local dominance and local recombination in MOEAs on 0/1 multiobjective knapsack problems. Eur. J. Oper. Res. 181, 1708–1723 (2007)CrossRefMATH Sato, H., Aguirre, H.E., Tanaka, K.: Local dominance and local recombination in MOEAs on 0/1 multiobjective knapsack problems. Eur. J. Oper. Res. 181, 1708–1723 (2007)CrossRefMATH
19.
go back to reference Ishibuchi, H., Tsukamoto, N., Hitotsuyanagi, Y., Nojima, Y.: Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 649–656 (2008) Ishibuchi, H., Tsukamoto, N., Hitotsuyanagi, Y., Nojima, Y.: Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems. In: Proceedings of Genetic and Evolutionary Computation Conference, pp. 649–656 (2008)
20.
go back to reference Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: a short review. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 2424–2431 (2008) Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: a short review. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 2424–2431 (2008)
21.
go back to reference Kowatari, N., Oyama, A., Aguirre, H., Tanaka, K.: Analysis on population size and neighborhood recombination on many-objective optimization. In: Coello, C.A.C., Cutello, V., Deb, K., Forrest, S., Nicosia, G., Pavone, M. (eds.) PPSN 2012, Part II.LNCS, vol. 7492, pp. 22–31. Springer, Heidelberg (2012) Kowatari, N., Oyama, A., Aguirre, H., Tanaka, K.: Analysis on population size and neighborhood recombination on many-objective optimization. In: Coello, C.A.C., Cutello, V., Deb, K., Forrest, S., Nicosia, G., Pavone, M. (eds.) PPSN 2012, Part II.LNCS, vol. 7492, pp. 22–31. Springer, Heidelberg (2012)
22.
go back to reference Ishibuchi, H., Nojima, Y., Doi, T.: Comparison between single-objective and multi-objective genetic algorithms: performance comparison and performance measures. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 3959–3966 (2006) Ishibuchi, H., Nojima, Y., Doi, T.: Comparison between single-objective and multi-objective genetic algorithms: performance comparison and performance measures. In: Proceedings of IEEE Congress on Evolutionary Computation, pp. 3959–3966 (2006)
23.
go back to reference Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Diversity improvement by non-geometric binary crossover in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 14, 985–998 (2010)CrossRef Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Diversity improvement by non-geometric binary crossover in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 14, 985–998 (2010)CrossRef
Metadata
Title
A Study on the Specification of a Scalarizing Function in MOEA/D for Many-Objective Knapsack Problems
Authors
Hisao Ishibuchi
Naoya Akedo
Yusuke Nojima
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-44973-4_24

Premium Partner