Abstract
In this paper, a highly parallel approach for solving multicriteria optimization problems is proposed. The considered approach is based on the reduction of the multicriterial problems to the global optimization ones using the minimax convolution of the partial criteria, the dimensionality reduction with the use of the Peano space-filling curves, and the application of the efficient parallel information-statistical global optimization methods. The required computations can be time-consuming since functions representing individual criteria can be multiextremal and computationally expensive. The proposed approach comprises two different schemes for efficient parallel computations on high performance systems with shared and distributed memory and with a large number of computational units. The computational efficiency is achieved by storing all the computed criteria values and their intensive reuse for finding new solutions. The results of numerical experiments have demonstrated that this approach allows to reduce the computational costs of solving multicriteria optimization problems by a factor between 10 and 100.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
More precisely, the minimization of \(F(\lambda ,y)\) can lead to the obtaining of the weakly-efficient variants (the set of the weakly-efficient decisions includes the Pareto domain).
- 2.
The lower indices denote the increasing order of the coordinate values of the points \(x_i\), \(1 \le i \le k\).
- 3.
MGA is the sequential implementation of the parallel MPMGA method.
- 4.
Due to the initial assumption that the computational complexity of multicriteria optimization problems is determined by the complexity of calculations of the criteria values, the speedup is defined as the reduction of the number of executed iterations.
References
Miettinen, K.: Nonlinear Multiobjective Optimization. Springer, New York (1999). https://doi.org/10.1007/978-1-4615-5563-6
Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Heidelberg (2010). https://doi.org/10.1007/3-540-27659-9
Collette, Y., Siarry, P.: Multiobjective Optimization: Principles and Case Studies (Decision Engineering). Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-662-08883-8
Marler, R.T., Arora, J.S.: Survey of multi-objective optimization methods for engineering. Struct. Multidisciplinary Optim. 26, 369–395 (2004)
Figueira, J., Greco, S., Ehrgott, M. (eds.): Multiple Criteria Decision Analysis: State of the Art Surveys. Springer, New York (2005). https://doi.org/10.1007/b100605
Eichfelder, G.: Scalarizations for adaptively solving multi-objective optimization problems. Comput. Optim. Appl. 44, 249–273 (2009)
Strongin, R., Sergeyev, Ya.: Global Optimization with Non-Convex Constraints. Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000). (2nd ed. 2013, 3rd ed. 2014)
Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-8042-6
Floudas, C.A., Pardalos, M.P.: Recent Advances in Global Optimization. Princeton University Press, Princeton (2016)
Locatelli, M., Schoen, F.: Global optimization: theory, algorithms, and applications. In: SIAM (2013)
Sergeyev, Y.D., Grishagin, V.A.: Parallel asynchronous global search and the nested optimization scheme. J. Comput. Anal. Appl. 3(2), 123–145 (2001)
Marler, R.T., Arora, J.S.: Multi-Objective Optimization: Concepts and Methods for Engineering. VDM Verlag, Saarbrücken (2009)
Hillermeier, C., Jahn, J.: Multiobjective optimization: survey of methods and industrial applications. Surv. Math. Ind. 11, 1–42 (2005)
Gergel, V., Sidorov, S.: A two-level parallel global search algorithm for solution of computationally intensive multiextremal optimization problems. In: Malyshkin, V. (ed.) PaCT 2015. LNCS, vol. 9251, pp. 505–515. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21909-7_49
Barkalov, K., Gergel, V., Lebedev, I.: Solving global optimization problems on GPU cluster. In: AIP Conference Proceedings, vol. 1738, p. 400006 (2016) https://doi.org/10.1063/1.4952194
Gergel, V., Kozinov, E.: Efficient multicriteria optimization based on intensive reuse of search information. J. Glob. Optim. 71(1), 73–90 (2018)
Evtushenko, Y.G., Posypkin, M.A.: A deterministic algorithm for global multi-objective optimization. Optim. Meth. Softw. 29(5), 1005–1019 (2014)
Ž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)
Pardalos, P.M., Žilinskas, A., Žilinskas, J.: Non-Convex Multi-Objective Optimization. Springer, Heidelberg (2017)
Gergel, V., Kozinov, E.: Accelerating parallel multicriterial optimization methods based on intensive using of search information. Procedia Comput. Sci. 108, 1463–1472 (2017)
Bleuler, S., Laumanns, M., Thiele, L., Zitzler, E.: PISA—a platform and programming language independent interface for search algorithms. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Thiele, L., Deb, K. (eds.) EMO 2003. LNCS, vol. 2632, pp. 494–508. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36970-8_35
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)
Gaviano, M., Kvasov, D.E., Lera, D., Sergeyev, Ya.D.: Software for generation of classes of test functions with known local and global minima for global optimization. ACM Trans. Math. Softw. 29(4), 469–480 (2003)
Borisenko, A., Gorlatch, S.: Parallelizing metaheuristics for optimal design of multiproduct batch plants on GPU. In: Malyshkin, V. (ed.) PaCT 2017. LNCS, vol. 10421, pp. 405–417. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62932-2_39
Gergel, V.P., Strongin, R.G.: Parallel computing for globally optimal decision making. In: Malyshkin, V.E. (ed.) PaCT 2003. LNCS, vol. 2763, pp. 76–88. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45145-7_7
Sakharov, M.K., Karpenko, A.P.: Adaptive load balancing in the modified mind evolutionary computation algorithm. Supercomput. Front. Innov. 5(4), 5–14 (2018)
Acknowledgements
This work has been supported by 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
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Gergel, V., Kozinov, E. (2019). A Highly Parallel Approach for Solving Computationally Expensive Multicriteria Optimization Problems. In: Voevodin, V., Sobolev, S. (eds) Supercomputing. RuSCDays 2019. Communications in Computer and Information Science, vol 1129. Springer, Cham. https://doi.org/10.1007/978-3-030-36592-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-36592-9_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-36591-2
Online ISBN: 978-3-030-36592-9
eBook Packages: Computer ScienceComputer Science (R0)