Investigation of Archiving Techniques for Evolutionary Multi-objective Optimizers

Authors

  • Hudson Geovane de Medeiros Universidade Federal do Rio Grande do Norte
  • Elizabeth Ferreira Gouvêa Goldbarg Universidade Federal do Rio Grande do Norte
  • Marco Cesar Goldbarg Universidade Federal do Rio Grande do Norte

DOI:

https://doi.org/10.22456/2175-2745.80478

Keywords:

Archiving techniques, Multi-objective evolutionary algorithms, Recycling techniques.

Abstract

Abstract: The optimization of multi-objective problems from the Pareto dominance viewpoint can lead to huge sets of incomparable solutions. Many heuristic techniques proposed to these problems have to deal with approximation sets that can be limited or not. Usually, a new solution generated by a heuristic is compared with other archived non-dominated solutions generated previously. Many techniques deal with limited size archives, since comparisons within unlimited archives may require significant computational effort. To maintain limited archives, solutions need to be discarded. Several techniques were proposed to deal with the problem of deciding which solutions remain in the archive and which are discarded. Previous investigations showed that those techniques might not prevent deterioration of the archives. In this study, we propose to store discarded solutions in a secondary archive and, periodically, recycle them, bringing them back to the optimization process. Three recycling techniques were investigated for three known methods. The datasets for the experiments consisted of 91 instances of discrete and continuous problems with 2, 3 and 4 objectives. The results showed that the recycling method can benefit the tested optimizers on many problem classes.

Downloads

Download data is not yet available.

References

ZITZLER, E.; LAUMANNS, M.; THIELE, L. SPEA2: Improving the strength pareto evolutionary algorithm. Evol. Methods Des. Optim. Control, v. 1, n. 1, p. 95–100, 2002.

KNOWLES, J.; CORNE, D. The pareto archived evolution strategy: a new baseline algorithm for pareto multiobjective optimisation. In: Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on. Washington, USA: IEEE, 1999. (CEC, ’99).

ZITZLERECKARTANDKU ̈NZLI,S.Indicator-based selection in multiobjective search. In: Parallel Problem Solving from Nature - PPSN VIII. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. (LNCS, v. 3242).

KNOWLES, J.; CORNE, D. Properties of an adaptive archiving algorithm for storing nondominated vectors. Trans. Evol. Comp, v. 7, n. 2, p. 100–116, 2003. USA: ACM, 2009. (FOGA, ’09).

KNOWLES, J. D. Local-Search and Hybrid Evolutionary Algorithms for Pareto Optimization. Tese (Doutorado) — University of Reading, UK, Reading, UK, 2002.

LAUMANNS, M. et al. On the Convergence and Diversity-Preservation Properties of Multi-Objective Evolutionary Algorithms. 2001.

KNOWLES JOSHUAAND CORNE, D. Bounded pareto archiving: Theory and practice. In: GANDIBLEUX, X. et al. (Ed.). Metaheuristics for Multiobjective Optimisation. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. (Lecture Notes in Economics and Mathematical Systems, v. 535).

LOPEZ-IBAN EZ,M.;KNOWLES,J.D.;LAUMANNS, M. On sequential online archiving of objective vectors. In: TAKAHASHI, R. H. C. et al. (Ed.). Evolutionary Multi-criterion Optimization (EMO 2011), Lecture Notes in Computer Science. Berlin, Germany: Springer, 2011. (LNCS, v. 6576).

MEDEIROS, H. G. de; GOLDBARG, E. F. G.; GOLDBARG, M. C. Analyzing limited size archivers of multi-objective optimizers. In: Brazilian Conference on Intelligent Systems. Sa ̃o Paulo, Brazil: IEEE, 2014. (BRACIS, ’14).

DEB, K. et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput., v. 6, n. 2, p. 182–197, 2002.

LAUMANNS, M.; ZENKLUSEN, R. Stochastic convergence of random search methods to fixed size pareto front approximations. Eur. J. Oper. Res., v. 213, n. 2, p. 414–442, 2011.

POZO, A.; BRITTO, A. B. de. Using archiving methods to control convergence and diversity for many-objective problems in particle swarm optimization. In: ABBASS, H.; ESSAM, D.; SARKER, R. (Ed.). WCCI 2012 IEEE World Congress on Computational Intelligence. Brisbane, Australia: IEEE, 2012. (CEC, ’12).

JIN, H.; WONG, M.-L. Adaptive, convergent, and diversified archiving strategy for multiobjective evolutionary algorithms. Expert Syst. Appl., v. 37, n. 12, p. 8462–8470, 2010.

HANNE, T. On the convergence of multiobjective evolutionary algorithms. Eur. J. Oper. Res., v. 117, n. 3, p. 553–564, 1999.

BRINGMANN, K.; FRIEDRICH, T. Don’t be greedy when calculating hypervolume contributions. In: GARIBAY, I. et al. (Ed.). Proceedings of the Tenth ACM SIGEVO Investigation of Archiving Techniques for Evolutionary Multi-objective Optimisers

ZITZLER, E.; THIELE, L. A comparative case study and the strength pareto approach. IEEE Trans. Evol. Comput., v. 3, n. 4, p. 257–271, 1999.

ZITZLER, E. et al. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput., v. 7, n. 2, p. 117–132, 2003.

DURILLO, J. J.; NEBRO, A. J. jmetal: A java framework for multi-objective optimization. Adv. Eng. Softw., v. 42, n. 10, p. 760–771, 2011.

KRUSKAL, W. H.; WALLIS, W. A. Use of ranks in one-criterion variance analysis. J. Amer. Statist. Assoc., v. 47, n. 260, p. 583–621, 1952.

BLEULER, S. et al. PISA — a platform and programming language independent interface for search algorithms. In: FONSECA, C. M. et al. (Ed.). Evolutionary Multi-Criterion Optimization (EMO 2003). Berlin: Springer, 2003. (Lecture Notes in Computer Science, v. 2632).

KOOPMANS, T. C.; BECKMANN, M. Assignment problems and the location of economic activities. Econometrica, v. 25, n. 1, p. 53–76, 1957.

KNOWLES, J.; CORNE, D. Instance generators and test suites for the multiobjective quadratic assignment problem. In: FONSECA, C. et al. (Ed.). Evolutionary Multi-Criterion Optimization, Second International Conference, EMO 2003. Faro, Portugal: Springer, 2003. (LNCS, v. 2632).

HUBAND, S. et al. A scalable multi-objective test problem toolkit. In: COELLO, C. C.; AGUIRRE, A. H.; ZITZLER, E. (Ed.). Evolutionary Multi-Criterion Optimization. 1. ed. Berlin, Germany: Springer Berlin Heidelberg, 2005, (Lecture Notes in Computer Science, v. 3410). p. 280–295.

LI, H.; ZHANG, Q. Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans, Evol. Comput., v. 13, n. 2, p. 284–302, 2009.

DEB, K. et al. Scalable multi-objective optimization test problems. In: Congress on Evolutionary Computation. Hawaii, USA: IEEE Press, 2002. (CEC, ’02).

ZITZLER, E.; DEB, K.; THIELE, L. Comparison of multiobjective evolutionary algorithms: Empirical results.

VIENNET, R.; FONTEIX, C.; MARC, I. Multicriteria optimization using a genetic algorithm for determining a pareto set.

FONSECA, C. M.; FLEMING, P. J. An overview of evolutionary algorithms in multiobjective optimization. Evol. Comput., v. 3, n. 1, p. 1–16, 1995.

KURSAWE, F. A variant of evolution strategies for vector optimization. In: SCHWEFEL, H.-P.; Ma ̈NNER, R. (Ed.). Parallel Problem Solving from Nature. 1st Workshop, PPSN I, volume 496 of Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag, 1991. (PPSN, ’91).

KO PPEN,M.;YOSHIDA,K.Substitutedistance assignments in nsga-ii for handling many-objective optimization problems. In: Proceedings of the 4th International Conference on Evolutionary Multi-criterion Optimization. Berlin, Heidelberg: Springer-Verlag, 2007. (EMO, ’07).

Downloads

Published

2018-11-19

How to Cite

Medeiros, H. G. de, Goldbarg, E. F. G., & Goldbarg, M. C. (2018). Investigation of Archiving Techniques for Evolutionary Multi-objective Optimizers. Revista De Informática Teórica E Aplicada, 25(4), 11–27. https://doi.org/10.22456/2175-2745.80478

Issue

Section

Special Issue - Exact and Heuristic Solutions for Optimization Problems

Most read articles by the same author(s)