×

zbMATH — the first resource for mathematics

Distributed localized bi-objective search. (English) Zbl 1339.90295
Summary: We propose a new distributed heuristic for approximating the Pareto set of bi-objective optimization problems. Our approach is at the crossroads of parallel cooperative computation, objective space decomposition, and adaptive search. Given a number of computing nodes, we self-coordinate them locally, in order to cooperatively search different regions of the Pareto front. This offers a trade-off between a fully independent approach, where each node would operate independently of the others, and a fully centralized approach, where a global knowledge of the entire population is required at every step. More specifically, the population of solutions is structured and mapped into computing nodes. As local information, every node uses only the positions of its neighbors in the objective space and evolves its local solution based on what we term a ‘localized fitness function’. This has the effect of making the distributed search evolve, over all nodes, to a high quality approximation set, with minimum communications. We deploy our distributed algorithm using a computer cluster of hundreds of cores and study its properties and performance on \(\rho\)MNK-landscapes. Through extensive large-scale experiments, our approach is shown to be very effective in terms of approximation quality, computational time and scalability.

MSC:
90C29 Multi-objective and goal programming
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aguirre, H. E.; Tanaka, K., Working principles, behavior, and performance of MOEAs on MNK-landscapes, European Journal of Operational Research, 181, 3, 1670-1690, (2007) · Zbl 1123.90063
[2] Aneja, Y. P.; Nair, K. P.K., Bicriteria transportation problem, Management Science, 25, 1, 73-78, (1979) · Zbl 0442.90056
[3] Bader, J.; Zitzler, E., Hype: an algorithm for fast hypervolume-based many-objective optimization, Evolutionary Computation, 19, 1, 45-76, (2011)
[4] Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: multiobjective selection based on dominated hypervolume, European Journal of Operational Research, 181, 3, 1653-1669, (2007) · Zbl 1123.90064
[5] Bleuler, S.; Laumanns, M.; Thiele, L.; Zitzler, E., PISA—A platform and programming language independent interface for search algorithms, (International conference on evolutionary multi-criterion optimization (EMO 2003), Lecture notes in computer science, Vol. 2632, (2003), Springer Faro, Portugal), 494-508 · Zbl 1037.68743
[6] Branke, J., Schmeck, H., Deb, K., & Reddy, M. (2004). Parallelizing multi-objective evolutionary algorithms: Cone separation. In IEEE congress on evolutionary computation (CEC 2004) (pp. 1952-1957). Portland, USA.
[7] Bui, L. T.; Abbass, H. A.; Essam, D., Local models—an approach to distributed multi-objective optimization, Computational Optimization and Applications, 42, 1, 105-139, (2009) · Zbl 1153.90530
[8] Coello Coello, C. A.; Lamont, G. B.; Van Veldhuizen, D. A., Evolutionary algorithms for solving multi-objective problems, (2007), Springer New York, USA · Zbl 1142.90029
[9] Coello Coello, C. A.; Sierra, M. R., A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm, (Mexican international conference on artificial intelligence (MICAI 2004), Lecture notes in computer science, Vol. 2972, (2004), Springer Mexico City), 688-697
[10] Deb, K., Multi-objective optimization using evolutionary algorithms, (2001), John Wiley & Sons Chichester, UK · Zbl 0970.90091
[11] Deb, K.; Agrawal, S.; Pratap, A.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197, (2002)
[12] Deb, K.; Zope, P.; Jain, A., Distributed computing of Pareto-optimal solutions with evolutionary algorithms, (International conference on evolutionary multi-criterion optimization (EMO 2003), Lecture notes in computer science, Vol. 2362, (2003), Springer Faro, Portugal), 534-549 · Zbl 1036.90526
[13] Durillo, J. J., Nebro, A. J., Luna, F., & Alba, E. (2008). A study of master-slave approaches to parallelize NSGA-II. In IEEE international symposium on parallel and distributed processing (IPDPS 2008) (pp. 1-8). Miami, USA.
[14] Durillo, J.; Zhang, Q.; Nebro, A.; Alba, E., Distribution of computational effort in parallel MOEA/D, (International conference on learning and intelligent optimization (LION 5), Lecture notes in computer science, Vol. 6683, (2011), Springer Rome, Italy), 488-502
[15] Ehrgott, M., Multicriteria optimization, (2005), Springer Berlin, Germany · Zbl 1132.90001
[16] Figueira, J. R.; Liefooghe, A.; Talbi, E.-G.; Wierzbicki, A. P., A parallel multiple reference point approach for multi-objective optimization, European Journal of Operational Research, 205, 2, 390-400, (2010) · Zbl 1188.90237
[17] Hiroyasu, T., Yoshii, K., & Miki, M. (2007). Discussion of parallel model of multi-objective genetic algorithms on heterogeneous computational resources. In Genetic and evolutionary computation conference (GECCO 2007) (pp. 904-904). ACM, London, UK.
[18] Humeau, J.; Liefooghe, A.; Talbi, E.-G.; Verel, S., Paradiseo-MO: from fitness landscape analysis to efficient local search algorithms, Journal of Heuristics, 19, 6, 881-915, (2013) · Zbl 1365.90008
[19] Jozefowiez, N.; Semet, F.; Talbi, E.-G., Parallel and hybrid models for multi-objective optimization: application to the vehicle routing problem, (International conference on parallel problem solving from nature (PPSN VII), Lecture notes in computer science, Vol. 24, (2002), Springer, Granada Spain), 271-280
[20] Kauffman, S. A., The origins of order, (1993), Oxford University Press New York, USA
[21] Knowles, J., Thiele, L., & Zitzler, E. (2006). A tutorial on the performance assessment of stochastic multiobjective optimizers. TIK Report 214, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Zurich, Switzerland.
[22] Liefooghe, A.; Jourdan, L.; Talbi, E.-G., A software framework based on a conceptual unified model for evolutionary multiobjective optimization: paradiseo-MOEO, European Journal of Operational Research, 209, 2, 104-112, (2011)
[23] López-Ibáñez, M.; Paquete, L.; Stützle, T., Exploratory analysis of stochastic local search algorithms in biobjective optimization, (Experimental methods for the analysis of optimization algorithms, (2010), Springer), 209-222 · Zbl 1208.90154
[24] Melab, N.; Talbi, E.-G.; Cahon, S., On parallel evolutionary algorithms on the computational grid, (Parallel evolutionary computations, Studies in computational intelligence, Vol. 22, (2006), Springer), 117-132 · Zbl 1103.68977
[25] Mostaghim, S., Parallel multi-objective optimization using self-organized heterogeneous resources, (Parallel and distributed computational intelligence, Studies in computational intelligence, Vol. 269, (2010), Springer), 165-179 · Zbl 1200.68049
[26] Mostaghim, S., Branke, J., & Schmeck, H. (2007). Multi-objective particle swarm optimization on computer grids. In Genetic and evolutionary computation conference (GECCO 2007) (pp. 869-875). ACM, London, UK.
[27] Nebro, A. J.; Durillo, J. J., A study of the parallelization of the multi-objective metaheuristic MOEA/D, (International conference on learning and intelligent optimization (LION 4), Lecture notes in computer science, Vol. 6073, (2010), Springer Venice, Italy), 303-317
[28] Peleg, D., Distributed computing: A locality-sensitive approach, (2000), Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 0959.68042
[29] Qi, Y.; Ma, X.; Liu, F.; Jiao, L.; Sun, J.; Wu, J., MOEA/D with adaptive weight adjustment, Evolutionary Computation, 22, 2, 231-264, (2014)
[30] Streichert, F.; Ulmer, H.; Zell, A., Parallelization of multi-objective evolutionary algorithms using clustering algorithms, (International conference on evolutionary multi-criterion optimization (EMO 2005), Lecture notes in computer science, Vol. 3410, (2005), Springer Guanajuato, Mexico), 92-107 · Zbl 1109.68637
[31] Talbi, E.-G.; Mostaghim, S.; Okabe, T.; Ishibuchi, H.; Rudolph, G.; Coello Coello, C. A., Parallel approaches for multiobjective optimization, (Multiobjective optimization - Interactive and evolutionary approaches, Lecture notes in computer science, Vol. 5252, (2008), Springer), 349-372
[32] Tan, K.; Yang, Y. J.; Goh, C., A distributed cooperative coevolutionary algorithm for multiobjective optimization, IEEE Transactions on Evolutionary Computation, 10, 5, 527-549, (2006)
[33] Tomassini, M., Spatially structured evolutionary algorithms: Artificial evolution in space and time, Natural computing series, (2005), Springer Berlin, Germany · Zbl 1089.68114
[34] Van Veldhuizen, D. A.; Zydallis, J. B.; Lamont, G. B., Considerations in engineering parallel multiobjective evolutionary algorithms, IEEE Transactions on Evolutionary Computation, 7, 2, 144-173, (2003)
[35] Verel, S.; Liefooghe, A.; Jourdan, L.; Dhaenens, C., On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives, European Journal of Operational Research, 227, 2, 331-342, (2013)
[36] Zhang, Q.; Li, H., MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Transactions on Evolutionary Computation, 11, 6, 712-731, (2007)
[37] Zhu, Z. -Y., & Leung, K. -S. (2002). Asynchronous self-adjustable island genetic algorithm for multi-objective optimization problems. In IEEE world on congress on computational intelligence (WCCI 2002) (pp. 837-842). Honolulu, USA.
[38] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 4, 257-271, (1999)
[39] Zitzler, E.; Thiele, L.; Laumanns, M.; Foneseca, C. M.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Transactions on Evolutionary Computation, 7, 2, 117-132, (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.