Skip to main content

Advertisement

SpringerLink
Log in

A mutation operator based on a Pareto ranking for multi-objective evolutionary algorithms

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

Evolutionary Algorithms, EA’s, try to imitate, in some way, the principles of natural evolution and genetics. They evolve a population of potential solutions to the problem using operators such as mutation, crossover and selection. In general, the mutation operator is responsible for the diversity of the population and helps to avoid the problem of premature convergence to local optima (a premature stagnation of the search caused by the lack of population diversity).

In this paper we present a new mutation operator in the context of Multi-Objective Evolutionary Algorithms, MOEA’s, which makes use of the definition of Pareto optimality and manages the maximal amplitude or maximal step size of the mutation according to the Pareto layer of the individual and also of the iteration number. The behaviour of our mutation operator reveals that the use of variation operators which take into consideration the quality of the solutions, in terms of Pareto dominance or Pareto layers, can help to improve them. The Pareto based mutation operator proposed is compared with four well established and extensively used mutation operators: random mutation, non-uniform mutation, polynomial mutation and Gaussian mutation. The accomplished experiments reveal that our mutation operator performs, in most of the test problems considered, better than the others.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abbass, H.A., Sarker, R.: The Pareto differential evolution algorithm. Int. J. Artif. Intell. Tools 11(4), 531–552 (2002)

    Article  Google Scholar 

  • Alberto, I., Mateo, P.M.: A crossover operator that uses Pareto optimality in its definition. TOP doi:10.1007/s11750-009-0082-7 (2009)

  • Alberto, I., Mateo, P.M.: Re-implementing NSGA-II and SPEA2 using operators based on Pareto ranking. In: Proceedings of the Pyrenees International Workshop and Summer School on Statistics, Probability and Operations Research, (SPO09), Prensas Universitarias de Zaragoza, Zaragoza (2011)

    Google Scholar 

  • Beyer, H.G., Schwefel, H.P.: Evolution strategies. A comprehensive introduction. Nat. Comput. 1, 3–52 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Casella, G., Berger, R.L.: Statistical inference, 2nd edn. In: Duxbury Advanced Series, Pacific Grove, California (2002)

    Google Scholar 

  • CEC (2007) Special session and competition on performance assessment of multi-objective optimization algorithms. http://www3.ntu.edu.sg/home/epnsugan/ (2007). Accessed August 2008

  • Chen, M.R., Lu, Y.Z.: A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization. Eur. J. Oper. Res. 188, 637–651 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Coello, C.A.: EMOO repository (Online). http://delta.cs.cinvestav.mx/~ccoello/EMOO/ (2009). Accessed October 2009

  • Coello, C.A., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary Algorithms for Solving Multi-Objective Problems, 2nd edn. Springer, Berlin (2007)

    MATH  Google Scholar 

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

    MATH  Google Scholar 

  • 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 (2002a)

    Article  Google Scholar 

  • Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable multi-objective optimization test problems. In: Proceedings of the Congress on Evolutionary Computation CEC’2002, vol. 1, pp. 825–830. IEEE Press, Piscataway (2002b)

    Google Scholar 

  • Deb, K., Goyal, M.: A Combined genetic adaptive search (GeneAS) for engineering design. Comput. Sci. Inf. 26(4), 30–45 (1996)

    Google Scholar 

  • Deep, K., Thakur, M.: A new mutation operator for real coded genetic algorithms. Appl. Math. Comput. 193, 211–230 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Dong, H., He, J., Huang, H., Hou, W.: Evolutionary programming using mixed mutation strategy. Inf. Sci. 177, 312–327 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing, 2nd edn. printing. Springer, Berlin (2007)

    Google Scholar 

  • Fonseca, C.M., Paquete, L., Lopez-Ibanez, M.: An improved dimension-sweep algorithm for the hypervolume indicator. In: Congress on Evolutionary Computation CEC’2006, pp. 1157–1163. IEEE Press, Vancouver (2006a)

    Google Scholar 

  • Fonseca, C.M., Paquete, L., Lopez-Ibanez, M.: Computation of the hypervolume indicator, codes. http://sbe.napier.ac.uk/~manuel/hypervolume (2006b). Accessed August 2008

  • Fonseca, C.M., Fleming, P.J.: Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. In: Forrest, S. (ed.) Genetic Algorithms: Proceedings of the Fifth International Conference, pp. 416–423. Morgan Kaufmann, San Mateo (1993)

    Google Scholar 

  • Fu, J., Liu, Q., Zhou, X., Xiang, K., Zeng, Z.: An adaptive variable strategy Pareto differential evolution algorithm for multi-objective optimization. In: Proceedings of the Congress on Evolutionary Computation (CEC08), pp. 648–652. IEEE Press, Vancouver (2008)

    Google Scholar 

  • Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison–Wesley, Reading (1989)

    MATH  Google Scholar 

  • Gomes, A., Antunes, C.H., Martins, A.G.: Design of an adaptive mutation operator in an electrical load management case study. Comput. Oper. Res. 35, 2925–2936 (2008)

    Article  MATH  Google Scholar 

  • Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)

    Google Scholar 

  • Huang, V.L., Qin, A.K., Deb, K., Zitzler, E., Suganthan, P.N., Liang, J.J., Preuss, M., Huband, S.: Problem Definitions for Performance Assessment on Multiobjective Optimization Algorithms. Nanyang Technological University, Singapore (2007a). Tech. Rep. CEC-TR2007

    Google Scholar 

  • Huang, V.L., Qin, A.K., Suganthan, P.N., Tasgetire, M.F.: Multi-objective optimization based on self adaptive differential evolution algorithm. In: Proceedings of the Congress on Evolutionary Computation (CEC07), pp. 3601–3608. (2007b)

    Chapter  Google Scholar 

  • Knowles, J., Corne, D.: Approximating the nondominated front using the Pareto archived evolution strategy. Evol. Comput. 8(2), 149–172 (2000)

    Article  Google Scholar 

  • Larrañaga, P., Lozano, J.A.: Estimation of Distribution Algorithms: a New Tool for Evolutionary Computation. Kluwer, Norwell (2002)

    MATH  Google Scholar 

  • Mezura-Montes, E., Reyes-Sierra, M., Coello, C.A.: Multi-objective optimization using differential evolution: a survey of the state-of-the-art. In: Chakraborty, U.K. (ed.) Advances in Differential Evolution, pp. 173–196. Springer, Berlin (2008)

    Chapter  Google Scholar 

  • Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs, 3rd edn. Springer, Berlin (1996)

    MATH  Google Scholar 

  • Oliveto, P.S., Lehre, P.K., Neumann, F.: Theoretical analysis of rank-based mutation – combining exploration and exploitation. In: Proceedings of the Congress on Evolutionary Computation (CEC09), pp. 1455–1462 (2009)

    Chapter  Google Scholar 

  • Pant, M., Ali, M., Abraham, A.: Mixed mutation strategy embedded differential evolution. In: Proceedings of the Congress on Evolutionary Computation (CEC09), pp. 1240–1246 (2009)

    Chapter  Google Scholar 

  • Schaffer, J.D.: Multiple objective optimization with vector evaluated genetic algorithms. PhD. thesis, Vanderbilt University, Nashville, Tennessee (1984)

  • Schaffer, J.D.: Multiple objective optimization with vector evaluated genetic algorithms. In: Grefenstette, J.J. (ed.) Genetic Algorithms and their Applications, Proceedings of the First International Conference on Genetic, pp. 93–100. Lawrence Erlbaum, Hillsdale (1985)

    Google Scholar 

  • Schwefel, H.P.: Numerical Optimization of Computer Models. Wiley, New York (1981)

    MATH  Google Scholar 

  • Schwefel, H.P.: Evolution and Optimal Seeking. Wiley, New York (1995)

    Google Scholar 

  • Storn, R., Price, K.: Differential evolution – a simple and efficient adaptive scheme for global optimization over continuous spaces, pp. 1–12. International Computer Science, Berkeley (1995). Tech. Rep. TR-95-12

    Google Scholar 

  • Teo, J., Hijazi, H.A., Omar, Z.A., Nohamad, R., Hamid, Y.: Harnessing Mutational diversity at multiple levels for improving optimization accuracy in G3-PCX. In: Proceedings of the Congress on Evolutionary Computation (CEC07), pp. 4502–4507 (2007)

    Chapter  Google Scholar 

  • Van Veldhuizen, D.A., Lamont, G.B.: On measuring multiobjective evolutionary algorithm performance. In: 2000 Congress on Evolutionary Computation, vol. 1, pp. 204–211. IEEE Service Centre, Piscataway (2000)

    Google Scholar 

  • Xing, L.N., Chen, Y.W., Yang, K.W.: A novel mutation operator base on the immunity operation. Eur. J. Oper. Res. 197, 830–833 (2009)

    Article  MATH  Google Scholar 

  • Xue, F., Sanderson, A.C., Graves, R.: Multi-objective differential evolution – algorithm, convergence analysis, and applications. In: Proceedings of the Congress on Evolutionary Computation (CEC05), pp. 743–750 (2005)

    Google Scholar 

  • Yang, S.M., Shao, D.G., Luo, Y.J.: A novel evolution strategy for multiobjective optimization problem. App. Math. Comput. 170, 850–873 (2005)

    MathSciNet  MATH  Google Scholar 

  • Yuen, S.Y., Chow, C.K.: Continuous non-revisiting genetic algorithm. In: Proceedings of the Congress on Evolutionary Computation (CEC09), pp. 1896–1903 (2009a)

    Chapter  Google Scholar 

  • Yuen, S.Y., Chow, C.K.: A genetic algorithm that adaptively mutates and never revisits. IEEE Trans. Evol. Comput. 13(2), 454–472 (2009b)

    Article  Google Scholar 

  • Zhang, J., Chung, H.S.H., Lo, W.L.: Clustering-based adaptive crossover and mutation probabilities for genetic algorithms. IEEE Trans. Evol. Comput. 11(3), 326–335 (2007)

    Article  Google Scholar 

  • Zhao, X.C., Gao, X.S., Hu, Z.C.: Evolutionary programming based on non-uniform mutation. Appl. Math. Comput. 192(1), 1–11 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Zitzler, E.: Evolutionary algorithms for multiobjective optimization: methods and applications. PhD. Thesis, Dissertation ETH No. 13398, Swiss Federal Institute of Technology (ETH), Zürich, Switzerland (1999)

  • Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: Empirical results. Evol. Comput. 8(2), 173–195 (2000)

    Article  Google Scholar 

  • Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Tech. Rep. 103, pp. 1–21. Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institue of Technology (ETH), Zurich, Switzerland (2001)

  • Zitzler, E., Thiele, L.: Multiobjective evolutionary algorithms: A comparative case study and the Strength Pareto Approach. IEEE Trans. Evol. Comput. 3(4), 257–271 (1999)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Statistical Methods, Universidad de Zaragoza, Faculty of Sciences, C/Pedro Cerbuna 12, 50009, Zaragoza, Spain

    P. M. Mateo

  2. Department of Statistical Methods, Universidad de Zaragoza, Technical School of Industrial Engineers, C/María de Luna 3, 50018, Zaragoza, Spain

    I. Alberto

Authors
  1. P. M. Mateo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. I. Alberto
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to P. M. Mateo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mateo, P.M., Alberto, I. A mutation operator based on a Pareto ranking for multi-objective evolutionary algorithms. J Heuristics 18, 53–89 (2012). https://doi.org/10.1007/s10732-011-9156-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-011-9156-4

Keywords

Search

Navigation