Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Efficient multicriterial optimization based on intensive reuse of search information

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

Abstract

This paper proposes an efficient method for solving complex multicriterial optimization problems, for which the optimality criteria may be multiextremal and the calculations of the criteria values may be time-consuming. The approach involves reducing multicriterial problems to global optimization ones through minimax convolution of partial criteria, reducing dimensionality by using Peano curves and implementing efficient information-statistical methods for global optimization. To efficiently find the set of Pareto-optimal solutions, it is proposed to reuse all the search information obtained in the course of optimization. The results of computational experiments indicate that the proposed approach greatly reduces the computational complexity of solving multicriterial optimization 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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

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. More precisely, minimizing \(F(\lambda ,y)\) can result in obtaining a weakly-efficient solution (a set of weakly-efficient points includes the Pareto domain). This can be corrected by adding an additional correction value in (5)—see, for example, [21, 31].

References

  1. Barkalov, K., Gergel, V.: Parallel global optimization on GPU. J. Glob. Optim. 1–18 (2015). https://doi.org/10.1007/s10898-016-0411-y

  2. Barkalov, K., Gergel, V., Lebedev, I.: Use of xeon phi coprocessor for solving global optimization problems. In: LNCS, vol. 9251, pp. 307–318. Springer, Heidelberg (2015)

  3. Barkalov, K., Gergel, V., Lebedev, I.: Solving global optimization problems on GPU cluster. In: Simos T.E. (ed.) ICNAAM 2015, AIP Conference Proceedings, vol. 1738, No. 400006 (2016)

  4. Bleuler, S., Laumanns, M., Thiele, L., Zitzler, E.: PISA-A platform and programming language independent interface for search algorithms. In: Evolutionary Multi-Criterion Optimization, LNCS, vol. 2632, pp. 494–508 (2003)

  5. Branke, J., Deb, K., Miettinen, K., Slowinski, R. (eds.): Multi-Objective Optimization-Interactive and Evolutionary Approaches. Springer, Berlin (2008)

    Google Scholar 

  6. Collette, Y., Siarry, P.: Multiobjective Optimization: Principles and Case Studies (Decision Engineering). Springer, Berlin (2011)

    MATH  Google Scholar 

  7. Chinchuluun, A., Pardalos, P.M.: A survey of recent developments in multiobjective optimization. Ann. Oper. Res. 154(1), 29–50 (2007). https://doi.org/10.1007/s10479-007-0186-0

    Article  MathSciNet  MATH  Google Scholar 

  8. Chiandussi, G., Codegone, M., Ferrero, S., Varesio, F.E.: Comparison of multi-objective optimization methodologies for engineering applications. Comput. Math. Appl. 63(5), 912–942 (2012)

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

  10. Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Berlin (2005)

    MATH  Google Scholar 

  11. Eichfelder, G.: Scalarizations for adaptively solving multi-objective optimization problems. Comput. Optim. Appl. 44, 249–273 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. Evtushenko, YuG, Posypkin, M.A.: Method of non-uniform coverages to solve the multicriteria optimization problems with guaranteed accuracy. Autom. Remote Control 75(6), 1025–1040 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  13. Figueira, J., Greco, S., Ehrgott, M. (eds.): Multiple Criteria Decision Analysis: State of the Art Surveys. Springer, New York (2005)

    MATH  Google Scholar 

  14. Floudas, C.A., Pardalos, M.P.: Recent Advances in Global Optimization. Princeton University Press, Princeton (2016)

    Google Scholar 

  15. Gablonsky, J.M., Kelley, C.T.: A locally-biased form of the DIRECT algorithm. J. Glob. Optim. 21(1), 27–37 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gaviano, M., Lera, D., Kvasov, D.E., Sergeyev, Y.D.: Software for generation of classes of test functions with known local and global minima for global optimization. ACM Trans. Math. Softw. 29, 469–480 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  17. Gergel, V.: A unified approach to use of coprocessors of various types for solving global optimization problems. In: 2nd International Conference on Mathematics and Computers in Sciences and in Industry, pp. 13–18 (2015). https://doi.org/10.1109/MCSI.2015.18

  18. Gergel, V., Grishagin, V., Gergel, A.: Adaptive nested optimization scheme for multidimensional global search. J. Glob. Optim. 66(1), 35–51 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  19. Gergel, V., Lebedev, I.: Heterogeneous parallel computations for solving global optimization problems. Procedia Comput. Sci. 66, 53–62 (2015). https://doi.org/10.1007/s10898-016-0411-y

    Article  Google Scholar 

  20. Gergel, V., Sidorov, S.: A two-level parallel global search algorithm for solution of computationally intensive multiextremal optimization problems. In: LNCS, vol. 9251, pp. 505–515. Springer, Berlin (2015)

  21. Germeyer, YuB: Introduction in Theory of Operation Research. Nauka, Moscow (1971). (In Russian)

    Google Scholar 

  22. Grishagin, V.A.: Operating characteristics of some global search algorithms. Probl. Stoch. Search 7, 198–206 (1978). (In Russian)

    MATH  Google Scholar 

  23. Grishagin, V.A., Sergeyev, Y.D., Strongin, R.G.: Parallel characteristic algorithms for solving problems of global optimization. J. Glob. Optim. 10, 185–206 (1997)

    Article  MATH  Google Scholar 

  24. Hill, J.D.: A search technique for multimodal surfaces. IEEE Trans. Syst. Cybern. 5(1), 2–8 (1969)

    Article  Google Scholar 

  25. Hillermeier, C., Jahn, J.: Multiobjective optimization: survey of methods and industrial applications. Surv. Math. Ind. 11, 1–42 (2005)

    MATH  Google Scholar 

  26. Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Berlin (1990)

    Book  MATH  Google Scholar 

  27. Kvasov, D.E., Pizzuti, C., Sergeyev, Y.D.: Local tuning and partition strategies for diagonal GO methods. Numer. Math. 94(1), 93–106 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  28. Köksalan, M., Wallenius, J., Zionts, S.: Multiple Criteria Decision Making: From Early History to the 21st Century. World Scientific, Singapore (2011)

    Book  Google Scholar 

  29. Locatelli, M., Schoen, F.: Global Optimization: Theory, Algorithms, and Applications. SIAM, Philadelphia (2013)

    Book  MATH  Google Scholar 

  30. Mardani, A., Jusoh, A., Nor, K., Khalifah, Z., Zakwan, N., Valipour, A.: Multiple criteria decision-making techniques and their applications–a review of the literature from 2000 to 2014. Econ. Res.-Ekon. Istraž. 28(1), 516–571 (2015). https://doi.org/10.1080/1331677X.2015.1075139

    Google Scholar 

  31. Marler, R.T., Arora, J.S.: Survey of multi-objective optimization methods for engineering. Struct. Multidiscip. Optim. 26, 369–395 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  32. Miettinen, K.: Nonlinear Multiobjective Optimization. Springer, Boston (1999)

    MATH  Google Scholar 

  33. Pintér, J.D.: Global Optimization in Action (Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications). Kluwer Academic Publishers, Dortrecht (1996)

    Book  MATH  Google Scholar 

  34. Pardalos, P.M., Žilinskas, A., Žilinskas, J.: Non-Convex Multi-Objective Optimization. Springer, New York (2017)

    Book  MATH  Google Scholar 

  35. Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, Berlin (2014)

    Book  MATH  Google Scholar 

  36. Sergeyev, Y.D., Famularo, D., Pugliese, P.: Index branch-and-bound algorithm for Lipschitz univariate global optimization with multiextremal constraints. J. Glob. Optim. 21(3), 317–341 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  37. Sergeyev, Y.D., Grishagin, V.A.: Sequential and parallel algorithms for global optimization. Optim. Methods Softw. 3, 111–124 (1994)

    Article  MATH  Google Scholar 

  38. Sergeyev, Y.D., Grishagin, V.A.: Parallel asynchronous global search and the nested optimization scheme. J. Comput. Anal. Appl. 3(2), 123–145 (2001)

    MathSciNet  MATH  Google Scholar 

  39. Sergeyev, Y.D., Kvasov, D.E.: Global search based on efficient diagonal partitions and a set of Lipschitz constants. SIAM J. Optim. 16(3), 910–937 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  40. Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer, New York (2013)

    Book  MATH  Google Scholar 

  41. Siwale, I.: Practical multi-objective programming. Technical Report RD-14-2013. Apex Research Limited (2014)

  42. Strongin, R.G.: Numerical Methods in Multiextremal Problems: Information-Statistical Algorithms. Nauka, Moscow (1978). (In Russian)

    MATH  Google Scholar 

  43. Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints. Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000, 2nd ed. 2013, 3rd ed. 2014)

  44. Strongin, R.G., Gergel, V.P., Markin, D.L.: Multicriterion multiextreme optimization with nonlinear constraints. In: Lecture Notes in Economics and Mathematical Systems, vol. 351, pp. 120–127 (1988)

  45. Tan, K.C., Khor, E.F., Lee, T.H.: Multi-Objective Evolutionary Algorithms and Applications. Springer, London (2005)

    MATH  Google Scholar 

  46. Törn, A., Žilinskas, A.: Global optimization. In: LNCS, vol. 350. Springer, Berlin (1989)

  47. Yang, X.-S.: Nature-Inspired Metaheuristic Algorithms. Luniver Press, Frome (2008)

    Google Scholar 

  48. Zavadskas, E.K., Turskis, Z., Kildienė, S.: State of art surveys of overviews on MCDM/MADM methods. Technol. Econ. Dev. Econ. 20, 165–179 (2014)

    Article  Google Scholar 

  49. Zhigljavsky, A.A.: Theory of Global Random Search. Kluwer Academic Publishers, Dordrecht (1991)

    Book  Google Scholar 

  50. Žilinskas, A., Žilinskas, J.: Adaptation of a one-step worst-case optimal univariate algorithm of bi-objective Lipschitz optimization to multidimensional problems. Commun. Nonlinear Sci. Numer. Simul. 21, 89–98 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  51. Zitzler, E., Knowles, J., Thiele, L.: Quality assessment of Pareto set approximations. In: LNCS in Multiobjective Optimization-Interactive and Evolutionary Approaches. LNCS, vol. 5252, pp. 373–404 (2008)

  52. Zhigljavsky, A., Žilinskas, A.: Stochastic Global Optimization. Springer, Berlin (2008)

    MATH  Google Scholar 

Download references

Acknowledgements

This work has been supported by the Russian Science Foundation, Project No. 16-11-10150 “Novel efficient methods and software tools for time-consuming decision making problems using superior-performance supercomputers”.

Author information

Authors and Affiliations

  1. Institute of Information Technology, Mathematics and Mechanics, Lobachevsky State University of Nizhni Novgorod, Nizhni Novgorod, Russia

    Victor Gergel & Evgeny Kozinov

Authors
  1. Victor Gergel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Evgeny Kozinov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Victor Gergel.

Additional information

This study was supported by the Russian Science Foundation, Project No. 16-11-10150.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gergel, V., Kozinov, E. Efficient multicriterial optimization based on intensive reuse of search information. J Glob Optim 71, 73–90 (2018). https://doi.org/10.1007/s10898-018-0624-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-018-0624-3

Keywords

Search

Navigation