Abstract
Parallelism arises as an attractive option when Multi-Objective Evolutionary Algorithms (MOEAs) demand an intensive use of CPU or memory. The computational complexity of a MOEA depends on the scalability of its input parameters (i.e., the population size, number of decision variables, objectives, etc.) and on the computational cost of evaluating the objectives of the problem. Nonetheless, current research efforts have focused only on the second case. Therefore, in this chapter, we investigate the performance and behavior of S-PAMICRO, a recently proposed parallelization of SMS-EMOA that inhibits exponential execution time as the number of objectives increases. The idea behind S-PAMICRO is to divide the overall population into several semi-independent subpopulations each of which has very few individuals. Each subpopulation evolves a serial SMS-EMOA with an external archive for maintaining diversity. Our experimental results show that S-PAMICRO outperforms the standard island version of some state-of-the-art MOEAs in most instances of the many-objective Deb-Thiele-Laumanns-Zitzler (DTLZ) and Walking-Fish-Group (WFG) test suites.
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
References
Bader, J., Zitzler, E.: HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol. Comput. 19(1), 45–76 (2011)
Beume, N., Naujoks, B., Emmerich, M.: SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3), 1653–1669 (2007)
Brockhoff, D., Wagner, T., Trautmann, H.: On the properties of the \(R2\) indicator. In: 2012 Genetic and Evolutionary Computation Conference (GECCO’2012), pp. 465–472. ACM Press, USA (2012). ISBN: 978-1-4503-1177-9
Coello Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd edn. Springer, New York (2007)
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)
Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable test problems for evolutionary multiobjective optimization. In: Abraham, A., Jain, L., Goldberg, R. (eds.) Evolutionary Multiobjective Optimization, Advanced Information and Knowledge Processing, pp. 105–145. Springer, London (2005)
Fleischer, M.: The measure of Pareto optima applications to multi-objective metaheuristics. In: Fonseca, C., Fleming, P., Zitzler, E., Thiele, L., Deb, K. (eds.) Evolutionary Multi-Criterion Optimization. Lecture Notes in Computer Science, vol. 2632, pp. 519–533. Springer, Heidelberg (2003)
Fritsch, F.N., Carlson, R.E.: Monotone piecewise cubic interpolation. SIAM J. Numer. Anal. 17(2), 238–246 (1980)
Gómez, R.H., Coello, C.A.C., Alba, E.: A parallel version of SMS-EMOA for many-objective optimization problems. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) 14th International Conference on Parallel Problem Solving from Nature – PPSN XIV. Lecture Notes in Computer Science, vol. 9921, pp. 568–577. Springer, UK (2016). ISBN 978-3-319-45822-9
Gómez, R.H., Coello, C.A.C., Alba Torres, E.: A multi-objective evolutionary algorithm based on parallel coordinates. In: Proceedings of the 2016 Genetic and Evolutionary Computation Conference, GECCO 2016, pp. 565–572. ACM, New York (2016)
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)
Inselberg, A.: Parallel Coordinates: Visual Multidimensional Geometry and Its Applications. Springer, New York (2009)
Ishibuchi, H., Masuda, H., Tanigaki, Y., Nojima, Y.: Modified distance calculation in generational distance and inverted generational distance. In: Gaspar-Cunha, A., Antunes, C.H., Coello, C.A.C. (eds.) 8th International Conference on Evolutionary Multi-Criterion Optimization, EMO. Lecture Notes in Computer Science, vol. 9019, pp. 110–125. Springer, Portugal (2015)
Klinkenberg, J.W., Emmerich, M.T., Deutz, A.H., Shir, O.M., Bäck, T.: A reduced-cost SMS-EMOA using Kriging, self-adaptation, and parallelization. In: Ehrgott, M., Naujoks, B., Stewart, T.J., Wallenius, J. (eds.) Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems. Lecture Notes in Economics and Mathematical Systems, vol. 634, pp. 301–311. Springer, Heidelberg (2010)
Lücken, C., Barán, B., Brizuela, C.: A survey on multi-objective evolutionary algorithms for many-objective problems. Comput. Optim. Appl. 58(3), 707–756 (2014)
Rudolph, G.: Evolutionary search for minimal elements in partially ordered finite sets. In: Porto, V., Saravanan, N., Waagen, D., Eiben, A. (eds.) Evolutionary Programming VII, Proceedings of the 7th Annual Conference on Evolutionary Programming, pp. 345–353. Springer, Berlin (1998)
Wessing, S., Rudolph, G., Menges, D.A.: Comparing asynchronous and synchronous parallelization of the SMS-EMOA. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) 14th International Conference on Parallel Problem Solving from Nature – PPSN XIV. Lecture Notes in Computer Science, vol. 9921, pp. 558–567. Springer, UK (2016). ISBN 978-3-319-45822-9
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007)
Zitzler, E.: Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph.D. thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland (1999)
Zitzler, E., Künzli, S.: Indicator-based selection in multiobjective search. In: X.Y., et al. (eds.) Parallel Problem Solving from Nature - PPSN VIII. Lecture Notes in Computer Science, vol. 3242, pp. 832–842. Springer, UK (2004)
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)
Acknowledgements
The authors gratefully acknowledge support from CONACYT project no. 221551, and ABACUS-CINVESTAV, CONACYT grant EDOMEX-2011-C01-165873.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Hernández Gómez, R., Coello Coello, C.A., Alba, E. (2020). A Parallel Island Model for Hypervolume-Based Many-Objective Optimization. In: Bartz-Beielstein, T., Filipič, B., Korošec, P., Talbi, EG. (eds) High-Performance Simulation-Based Optimization. Studies in Computational Intelligence, vol 833. Springer, Cham. https://doi.org/10.1007/978-3-030-18764-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-18764-4_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-18763-7
Online ISBN: 978-3-030-18764-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)