[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

A preference-based evolutionary algorithm for multiobjective optimization: the weighting achievement scalarizing function genetic algorithm

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

When solving multiobjective optimization problems, preference-based evolutionary multiobjective optimization (EMO) algorithms introduce preference information into an evolutionary algorithm in order to focus the search for objective vectors towards the region of interest of the Pareto optimal front. In this paper, we suggest a preference-based EMO algorithm called weighting achievement scalarizing function genetic algorithm (WASF-GA), which considers the preferences of the decision maker (DM) expressed by means of a reference point. The main purpose of WASF-GA is to approximate the region of interest of the Pareto optimal front determined by the reference point, which contains the Pareto optimal objective vectors that obey the preferences expressed by the DM in the best possible way. The proposed approach is based on the use of an achievement scalarizing function (ASF) and on the classification of the individuals into several fronts. At each generation of WASF-GA, this classification is done according to the values that each solution takes on the ASF for the reference point and using different weight vectors. These vectors of weights are selected so that the vectors formed by their inverse components constitute a well-distributed representation of the weight vectors space. The efficiency and usefulness of WASF-GA is shown in several test problems in comparison to other preference-based EMO algorithms. Regarding a metric based on the hypervolume, we can say that WASF-GA has outperformed the other algorithms considered in most of the problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. We mean by ‘cognitive effort’ or ‘cognitive burden’ the DM’s effort required to understand the information provided by an algorithm, interpret its meaning and learn from it.

  2. To maintain the diversity of the population, repeating solutions in the same front is not allowed in case one solution reaches the lowest ASF value for several weight vectors at the same time. That is, once a solution is selected as the one with the lowest value of \(s(\mathbf {q}, \mathbf {f}(\mathbf {x}), \mu ^j)\) for one \(j = 1, \ldots , N_\mu \), it is removed and cannot be chosen for another index \(r > j\).

References

  1. Ben Said, L., Bechikh, S., Ghedira, K.: The r-dominance: a new dominance relation for interactive evolutionary multicriteria decision making. IEEE Trans. Evol. Comput. 14(5), 801–818 (2010)

  2. Branke, J.: Consideration of partial user preferences in evolutionary multiobjective optimization. In: Branke, J., Deb, K., Miettinen, K., Slowinski, R. (eds.) Multiobjective Optimization, Interactive and Evolutionary Approaches, Volume 5252 of Lecture Notes in Computer Science, pp. 157–178. Springer, Berlin (2008)

  3. Branke, J., Deb, K.: Integrating user preferences into evolutionary multi-objective optimization. In: Jin, Y. (ed.) Knowledge Incorporation in Evolutionary Computation, pp. 461–477. Springer, Berlin (2004)

    Google Scholar 

  4. Branke, J., Kaussler, T., Schemeck, H.: Guidance in evolutionary multi-objective optimization. Adv. Eng. Softw. 32, 499–507 (2001)

    Article  MATH  Google Scholar 

  5. Chankong, V., Haimes, Y.Y.: Multiobjective Decision Making Theory and Methodology. Elsevier Science Publishing, New York (1983)

    MATH  Google Scholar 

  6. Coello, C.A.C., Lamont, G.B., Veldhuizen, D.A.V.: Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd edn. Springer, New York (2007)

    MATH  Google Scholar 

  7. Coello, C.A.C.: Handling preferences in evolutionary multiobjective optimization: a survey. In: IEEE Congress on Evolutionary Computation, pp. 30–37 (2000)

  8. Corne, D.W., Knowles, J.D.: Techniques for highly multiobjective optimisation: some nondominated points are better than others. In: Annual Conference on Genetic and Evolutionary Computation. GECCO ’07, pp. 773–780. ACM Press, New York (2007)

  9. Deb, K.: Multi-objective Optimization using Evolutionary Algorithms. Wiley, Chichester (2001)

    MATH  Google Scholar 

  10. Deb, K.: Salient issues of multi-objective evolutionary algorithms. In: Deb, K. (ed.) Multi-Objective Optimization using Evolutionary Algorithms, vol. 8, pp. 315–445. Wiley, Chichester (2001)

    Google Scholar 

  11. Deb, K., Kumar, A.: Interactive evolutionary multi-objective optimization and decision-making using reference direction method. In: 9th Annual Conference on Genetic and Evolutionary Computation (GECCO-2007), pp. 781–788 (2007)

  12. Deb, K., Kumar, A.: Light beam search based multi-objective optimization using evolutionary algorithms. In: IEEE Congress on Evolutionary Computation (CEC-2007), pp. 2125–2132 (2007)

  13. Deb, K., Miettinen, K.: Nadir point estimation using evolutionary approaches: better accuracy and computational speed through focused search. In: Ehrgott, M., Naujoks, B., Stewart, T.J., Wallenius, J. (eds.) Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems, pp. 339–354. Springer, Berlin (2010)

    Chapter  Google Scholar 

  14. Deb, K., Miettinen, K., Chaudhuri, S.: Towards an estimation of nadir objective vector using a hybrid of evolutionary and local search approaches. IEEE Trans. Evol. Comput. 14(6), 821–841 (2010)

    Article  Google Scholar 

  15. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)

    Article  Google Scholar 

  16. Deb, K., Saxena, D.: Searching for pareto-optimal solutions through dimensionality reduction for certained large-dimensional multi-objective optimization problems. In: World Congress on Comutational Intelligence, pp. 3352–3360 (2006)

  17. Deb, K., Sinha, A., Korhonen, P.J., Wallenius, J.: An interactive evolutionary multiobjective optimization method based on progressively approximated value functions. IEEE Trans. Evol. Comput. 14(5), 723–739 (2010)

    Article  Google Scholar 

  18. Deb, K., Sundar, J., Ubay, B., Chaudhuri, S.: Reference point based multi-objective optimization using evolutionary algorithm. Int. J. Comput. Intell. Res. 2(6), 273–286 (2006)

    MathSciNet  Google Scholar 

  19. Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable multi-objective optimization test problems. In: Congress on Evolutionary Computation (CEC-2002), pp. 825–830 (2002)

  20. Durillo, J.J., Nebro, A.J.: jMetal: a java framework for multi-objective optimization. Adv. Eng. Softw. 42, 760–771 (2011)

    Article  Google Scholar 

  21. Ehrgott, M., Tenfelde-Podehl, D.: Computation of ideal and nadir values and implications for their use in MCDM methods. Eur. J. Oper. Res. 151, 119–139 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  22. Figueira, J.R., Liefooghe, A., Talbi, E.G., Wierzbicki, A.P.: A parallel multiple reference point approach for multi-objective optimization. Eur. J. Oper. Res. 205, 390–400 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  23. Fonseca, C.M., Fleming, P.J.: Genetic algorithms for multiobjective optimization: formulation, discussion and generalization. In: 5th International Conference on Genetic Algorithms, pp. 416–423 (1993)

  24. Fonseca, C.M., Paquete, L., and Lopez-Ibanez, M.: An improved dimension-sweep algorithm for the hypervolume indicator. In: IEEE Congress on Evolutionary Computation (CEC-2006), pp. 1157–1163 (2006)

  25. Gong, M., Liu, F., Zhang, W., Jiao, L., and Zhang, Q.: Interactive MOEA/D for multi-objective decision making. In: 13th Annual Conference on Genetic and Evolutionary Computation, GECCO ’11, pp. 721–728 (2011)

  26. Huband, S., Hingston, P., Barone, L., While, L.: A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. Evol. Comput. 10(5), 477–506 (2006)

    Article  Google Scholar 

  27. Hwang, C.L., Masud, A.S.M.: Multiple Objective Decision Making-Methods and Applications: A State-of-the-Art Survey. Springer, Berlin (1979)

    Book  MATH  Google Scholar 

  28. Jaszkiewicz, A., Branke, J.: Interactive multiobjective evolutionary algorithms. In: Branke, J., Deb, K., Miettinen, K., Slowinski, R. (eds.) Multiobjective Optimization, Interactive and Evolutionary Approaches, Volume 5252 of Lecture Notes in Computer Science, pp. 179–193. Springer, Berlin (2008)

  29. Jaszkiewicz, A., Slowiński, R.: The ’light beam search’ approach—an overview of methodology and applications. Eur. J. Oper. Res. 113(2), 300–314 (1999)

    Article  MATH  Google Scholar 

  30. Knowles, J.D., Corne, D.W.: Approximating the nondominated front using the pareto archived evolution strategy. Evol. Comput. 8(2), 149–172 (2000)

    Article  Google Scholar 

  31. Korhonen, P., Laakso, J.: A visual interactive method for solving the multiple criteria problem. Eur. J. Oper. Res. 24(2), 277–287 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  32. Li, H., Zhang, Q.: Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans. Evol. Comput. 13(2), 284–302 (2009)

    Article  Google Scholar 

  33. Luque, M., Miettinen, K., Eskelinen, P., Ruiz, F.: Incorporating preference information in interactive reference point methods for multiobjective optimization. Omega 37(2), 450–462 (2009)

    Article  Google Scholar 

  34. Luque, M., Ruiz, F., Miettinen, K.: Global formulation for interactive multiobjective optimization. OR Spectr. 33(1), 27–48 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  35. MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: 5-th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297. University of California Pressley, Berkeley (1967)

  36. Miettinen, K.: Nonlinear Multiobjective Optimization. Kluwer, Boston (1999)

    MATH  Google Scholar 

  37. Miettinen, K., Mäkelä, M.M.: Comparative evaluation of some interactive reference point-based methods for multi-objective optimisation. J. Oper. Res. Soc. 50(9), 949–959 (1999)

    Article  MATH  Google Scholar 

  38. Miettinen, K., Mäkelä, M.M.: On scalarizing functions in multiobjective optimization. OR Spectr. 24(2), 193–213 (2002)

    Article  MATH  Google Scholar 

  39. Miettinen, K., Mäkelä, M.M., Kaario, K.: Experiments with classification-based scalarizing functions in interactive multiobjective optimization. Eur. J. Oper. Res. 175(2), 931–947 (2006)

    Article  MATH  Google Scholar 

  40. Molina, J., Santana, L.V., Hernandez-Diaz, A.G., Coello, C.A., Caballero, R.: g-Dominance: reference point based dominance for multiobjective metaheuristics. Eur. J. Oper. Res. 197, 685–692 (2009)

    Article  MATH  Google Scholar 

  41. Rachmawati, L., Srinivasan, D.: Preference incorporation in multiobjective evolutionary algorithms. In: IEEE Congress on Evolutionary Computation, pp. 3385–3391 (2006)

  42. Ruiz, F., Luque, M., Cabello, J.M.: A classification of the weighting schemes in reference point procedures for multiobjective programming. J. Oper. Res. Soc. 60(4), 544–553 (2009)

    Article  MATH  Google Scholar 

  43. Sawaragi, Y., Nakayama, H., Tanino, T.: Theory of Multiobjective Optimization. Academic Press, Orlando (1985)

    MATH  Google Scholar 

  44. Sindhya, K., Miettinen, K., Deb, K.: A hybrid framework for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput. 17(4), 495–511 (2013)

    Article  Google Scholar 

  45. Sindhya, K., Ruiz, A.B., and Miettinen, K.: A preference based interactive evolutionary algorithm for multi-objective optimization: PIE. In: Takahashi, R., Deb, K., Wanner, E., Greco, S. (eds.) Evolutionary Multi-Criterion Optimization, Volume 6576 of Lecture Notes in Computer Science, pp. 212–225 (2011)

  46. Sinha, A., Korhonen, P.J., Wallenius, J., Deb, K.: An interactive evolutionary multi-objective optimization method based on polyhedral cones. In: Blum, C., Battiti, R. (eds.) Learning and Intelligence Optimization, Volume 6073 Lecture Notes in Computer Science, pp. 318–332. Springer, Berlin (2010)

  47. Thiele, L., Miettinen, K., Korhonen, P., Molina, J.: A preference-based evolutionary algorithm for multi-objective optimization. Evol. Comput. 17(3), 411–436 (2009)

    Article  Google Scholar 

  48. Wierzbicki, A.P.: The use of reference objectives in multiobjective optimization. In: Fandel, G., Gal, T. (eds.) Multiple Criteria Decision Making. Theory and Applications, pp. 468–486. Springer, Berlin (1980)

  49. Wilcoxon, F.: Individual comparisons by ranking methods. Biom. Bull. 1(6), 80–83 (1945)

    Article  Google Scholar 

  50. Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007)

    Article  Google Scholar 

  51. Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: empirical results. Evol. Comput. 8(2), 173–195 (2000)

    Article  Google Scholar 

  52. Zitzler, E., Kuenzli, S.: Indicator-based selection in multiobjective search. In: Yao, X., Burke, E., Lozano, J.A., Smith, J., Merelo-Guervos, J.J., Bullinaria, J.A., Rowe, J., Tino, P., Kaban, A., Schwefel, H.P. (eds.) 8th International Conference on Parallel Problem Solving from Nature—PPSN VIII, pp. 832–842. Springer, Berlin (2004)

    Chapter  Google Scholar 

  53. Zitzler, E., Laumanns, M., Thiele L.: SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou, K.C. et al., (eds.) Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), pp. 95–100. International Center for Numerical Methods in Engineering (CIMNE) (2002)

  54. Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms–a comparative case study. In: Eiben, A., Bäck, T., Schoenauer, M., Schwefel, H.P. (eds.) Parallel Problem Solving from Nature, Volume 1498 of Lecture Notes in Computer Science, pp. 292–301. Springer, Berlin (1998)

  55. Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117–132 (2003)

    Article  Google Scholar 

  56. Zou, X., Chen, Y., Liu, M., Kang, L.: A new evolutionary algorithm for solving many-objective optimization problems. IEEE Trans. Syst. Man Cybern. Part B 38(5), 1402–1412 (2008)

Download references

Acknowledgments

This research was partly supported by the Spanish Ministry of Innovation and Science (MTM2010-14992) and by the Andalusia Regional Ministry of Innovation, Science and Enterprises (PAI group SEJ-532).

Author information

Authors and Affiliations

  1. Department of Applied Economics (Mathematics), Universidad de Málaga, Calle Ejido 6, 29071 , Málaga, Spain

    Ana Belén Ruiz, Rubén Saborido & Mariano Luque

Authors
  1. Ana Belén Ruiz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rubén Saborido
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mariano Luque
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mariano Luque.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ruiz, A.B., Saborido, R. & Luque, M. A preference-based evolutionary algorithm for multiobjective optimization: the weighting achievement scalarizing function genetic algorithm. J Glob Optim 62, 101–129 (2015). https://doi.org/10.1007/s10898-014-0214-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-014-0214-y

Keywords

Search

Navigation