Skip to main content
SpringerLink
Log in

Two-Loop Real-Coded Genetic Algorithms with Adaptive Control of Mutation Step Sizes

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Genetic algorithms are adaptive methods based on natural evolution that may be used for search and optimization problems. They process a population of search space solutions with three operations: selection, crossover, and mutation. Under their initial formulation, the search space solutions are coded using the binary alphabet, however other coding types have been taken into account for the representation issue, such as real coding. The real-coding approach seems particularly natural when tackling optimization problems of parameters with variables in continuous domains.

A problem in the use of genetic algorithms is premature convergence, a premature stagnation of the search caused by the lack of population diversity. The mutation operator is the one responsible for the generation of diversity and therefore may be considered to be an important element in solving this problem. For the case of working under real coding, a solution involves the control, throughout the run, of the strength in which real genes are mutated, i.e., the step size.

This paper presents TRAMSS, a Two-loop Real-coded genetic algorithm with Adaptive control of Mutation Step Sizes. It adjusts the step size of a mutation operator applied during the inner loop, for producing efficient local tuning. It also controls the step size of a mutation operator used by a restart operator performed in the outer loop, for reinitializing the population in order to ensure that different promising search zones are focused by the inner loop throughout the run. Experimental results show that the proposal consistently outperforms other mechanisms presented for controlling mutation step sizes, offering two main advantages simultaneously, better reliability and accuracy.

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

  1. D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley: New York, 1989.

    Google Scholar 

  2. J.H. Holland, Adaptation in Natural and Artificial Systems, The MIT Press: London, 1992.

    Google Scholar 

  3. T. B¨ack, Evolutionary Algorithms in Theory and Practice, Oxford University Press: Oxford, 1996.

    Google Scholar 

  4. T. B¨ack, D. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation, Oxford University Press: Oxford, 1997.

    Google Scholar 

  5. Z. Michalewicz, Genetic Algorithms C Data Structures D Evolution Programs, Springer-Verlag: New York, 1992.

    Google Scholar 

  6. F. Herrera, M. Lozano, and J.L. Verdegay, “Tackling real-coded genetic algorithms: Operators and tools for the behavioural analysis,” Artificial Intelligence Reviews, vol. 12, no. 4, pp. 265–319, 1998.

    Google Scholar 

  7. P.D. Surry and N.J. Radcliffe, “Real representations,” in Foundations of Genetic Algorithms IV, Morgan Kaufmann: San Mateo, pp. 343–363, 1996.

    Google Scholar 

  8. H.-P. Schwefel, Evolution and Optimum Seeking. Sixth-Generation Computer Technology Series, Wiley: New York, 1995.

    Google Scholar 

  9. D.B. Fogel, Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, IEEE Press: Piscataway, 1995.

    Google Scholar 

  10. T.-H. Li, C.B. Lucasius, and G. Kateman, “Optimization of calibration data with the dynamic genetic algorithm,” Analytica Chimica Acta, vol. 2768, pp. 123–134, 1992.

    Google Scholar 

  11. L.J. Eshelman and J.D. Schaffer, “Preventing premature convergence in genetic algorithms by preventing incest,” in Proc.of the Fourth Int. Conf. on Genetic Algorithms, edited by R. Belew and L.B. Booker, Morgan Kaufmann: San Mateo, 1991,pp. 115–122.

    Google Scholar 

  12. W.M. Spears, “Crossover or mutation?” in Foundations of Genetic Algorithms 2, edited by L.D. Whitley, Morgan,Kaufmann Publishers: San Mateo, pp. 221–238, 1993.

    Google Scholar 

  13. P.J. Angeline, “Adaptive and self-adaptive evolutionary computations,” in Computational Intelligence: A Dynamic Systems Perspective, edited by M. Palaniswami, Y. Attikiouzel, R. Markc, D. Fogel, and T. Fukuda, IEEE Press: Piscataway, NJ, pp. 152–163, 1995.

    Google Scholar 

  14. F. Herrera and M. Lozano, “Adaptation of genetic algorithm parameters based on fuzzy logic controllers,” in Genetic Algorithms and Soft Computing, edited by F. Herrera and J.L. Verdegay, Physica-Verlag: Wurzburg, pp. 95–125, 1996.

    Google Scholar 

  15. R. Hinterding, Z. Michalewicz, and A.E. Eiben, “Adaptation in evolutionary computation: A survey,” in Proc. of the 4th IEEE Conf. on Evolutionary Computation, IEEE Service Center, 1997,pp. 65–69.

  16. T. B¨ack, M. Sch¨utz, and S. Khuri, “Evolution strategies: An alternative evolution computation method,” in Artificial Evolution, edited by J.M. Alliot, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers, Springer: Berlin, pp. 3–20, 1996.

  17. S.W. Mahfoud, “Niching methods for genetic algorithms,” Illinois Genetic Algorithms Laboratory, University of Illinois, Illigal Report No. 95001, 1995.

  18. H.-P. Schwefel, Numerical Optimization of Computer Models, Wiley: Chichester, 1981.

    Google Scholar 

  19. T. B¨ack, “The interaction of mutation rate, selection, and self-adaptation within genetic algorithm,” in Parallel Problem Solving from Nature, vol. 2, edited by R. M¨anner and B. Manderick, Elsevier Science Publishers: Amsterdam, pp. 85–94, 1992.

    Google Scholar 

  20. T. B¨ack and M. Sch¨utz, “Intelligent mutation rate control in canonical genetic algorithms,” in Foundation of Intelligent Systems 9th Int. Symposium, edited by Z.W. Ras and M. Michalewicz, Springer: Berlin, 1996, pp. 158–167.

    Google Scholar 

  21. A.L. Tuson and P. Ross, “Adapting operator settings in genetic algorithms,” Evolutionary Computation, vol. 6, no. 2, pp. 161–184, 1998.

    Google Scholar 

  22. F. Herrera, M. Lozano, and J.L. Verdegay, “Dynamic and heuristic fuzzy connectives-based crossover operators for controlling the diversity and convengence of real coded genetic algorithms,” Int. Journal of Intelligent, vol. 11, pp. 1013–1041, 1996.

    Google Scholar 

  23. J. P´eriaux, M. Sefrioui, B. Stoufflet, B. Mantel, and E. Laporte, “Robust genetic algorithms for optimization problems in aerodynamic design,” in Genetic Algorithms in Engineering and Computer Science, edited by G. Winter, J. P´eriaux, M. Gal´an, and P. Cuesta, John Wiley & Sons: New York, pp. 371–396, 1995.

    Google Scholar 

  24. M. Sefrioui and J. P´eriaux, “Fast convergence thanks to diversity,” in Proc. of the Fifth Annual Conference on Evolutionary Programming, 1996, pp. 313–321.

  25. M. De La Maza and D. Yuret, “Dynamic hillclimbing,” AI Expert, vol. 9, no. 3, 1994.

  26. R. Hinterding, “Gaussian mutation and self-adaptation for numeric genetic algorithms,” in Proc. of IEEE International Conference on Evolutionary Computation, IEEE Press: New York, 1995, pp. 384–389.

    Google Scholar 

  27. R. Hinterding, Z. Michalewicz, and T.C. Peachey, “Self-adaptive genetic algorithm for numeric functions,” in 4th International Conference on Parallel Problem Solving from Nature, edited by H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, Springer-Verlag: Berlin, Germany, 1996, pp. 420–429.

    Google Scholar 

  28. J. Maresky, Y. Davidor, D. Gitler, G. Aharoni, and A. Barak, “Selectively destructive re-start,” in Proc. of the Sixth Int.Conf. on Genetic Algorithms, edited by L. Eshelman, Morgan aufmann Publishers: San Francisco, 1995, pp. 144–150

    Google Scholar 

  29. D.E. Goldberg, “Sizing populations for serial and parallel genetic algorithms,” in Proc. of the Third Int. Conf. on Genetic Algorithms, edited by J.D. Schaffer, Morgan Kaufmann Publishers: San Mateo, 1989, pp. 70–79.

    Google Scholar 

  30. L.J. Eshelman, “The CHC adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination,” in Foundations of Genetic Algorithms 1, edited by G.J.E Rawlin, Morgan Kaufmann Publishers: San Mateo, pp. 265–283, 1991.

    Google Scholar 

  31. J.J. Grefenstette, “Genetic algorithms for changing environments,” in Parallel Problem Solving from Nature, vol. 2, edited by R. M¨anner and B. Manderick, Elsevier Science Publishers: Amsterdam, pp. 137–144, 1992.

    Google Scholar 

  32. C.G. Shaefer, “The ARGOT strategy: Adaptive representation genetic optimizer technique,” in Proc. Second Int. Conf. on Genetic Algorithms, Erlbaum Associates: Hillsdale, MA, 1987.

    Google Scholar 

  33. N.N Schraudolph and R.K. Belew, “Dynamic parameter encoding for genetic algorithms,” Machine Learning, vol. 9, pp. 9–21, 1992.

    Google Scholar 

  34. D. Whitley, K. Mathias, and P. Fitzhorn, “Delta coding: An iterative search strategy for genetic algorithms,” in Proc. of the Fourth Int. Conf. on Genetic Algorithms, edited by R. Belew and L.B. Booker, Morgan Kaufmann Publishers: San Mateo, 1991, pp. 77–84.

    Google Scholar 

  35. T. B¨ack and H.-P. Schwefel, “Evolution strategies I: Variants and their computational implementation,” in Genetic Algorithms in Engineering and Computer Science, edited by G. Winter, J. P´eriaux, M. Gal´an, and P. Cuesta, John Wiley & Sons: New York, pp. 111–126, 1995.

    Google Scholar 

  36. J.E. Baker, “Adaptive selection methods for genetic algorithms,” in Proc. First Int. Conf. on Genetic Algorithms, L. Erlbaum Associates: Hillsdale, MA 1985, pp. 101–111.

    Google Scholar 

  37. J.E. Baker, “Reducing bias and inefficiency in the selection algorithm,” in Proc. Second Int. Conf. on Genetic Algorithms, L. Erlbaum Associates: Hillsdale, MA, 1987, pp. 14–21.

    Google Scholar 

  38. K.A. De Jong, “An analysis of the behavior of a class of genetic adaptive systems,” Doctoral Dissertation, University of Michigan, 1975.

  39. A.O. Griewangk, “Generalized descent of global optimization,” Journal of Optimization Theory and Applications, vol. 34, pp. 11–39, 1981.

    Google Scholar 

  40. T. B¨ack, “Self-Adaptation in genetic algorithms,” in Proc. of the First European Conference on Artificial Life, edited by F.J. Varela and P. Bourgine, The MIT Press: Cambridge, MA, 1992, pp. 263–271.

    Google Scholar 

  41. A. T¨orn and Ž. Antanas, Global Optimization, Lecture Notes in Computer Science, vol. 350, Springer: Berlin, 1989.

    Google Scholar 

  42. D. Whitley, R. Beveridge, C. Graves, and K. Mathias, “Test driving three 1995 genetic algorithms: New test functions and geometric matching,” Journal of Heuristics, vol. 1, pp. 77–104, 1995.

    Google Scholar 

  43. D. Schlierkamp-Voosen and H. M¨uhlenbein, “Strategy adaptation by competing subpopulations,” in Parallel Problem Solving from Nature, vol. III, edited by Y. Davidor, H.-P. Schwefel, and R. Maenner, Springer-Verlag: Berlin, Germany, pp. 199–208, 1994.

    Google Scholar 

  44. D. Whitley, D. Rana, J. Dzubera, and E. Mathias, “Evaluating evolutionary algorithms,” Artificial Intelligence, vol. 85, pp. 245–276, 1996.

    Google Scholar 

  45. H. M¨uhlenbein, M. Schomisch, and J. Born, “The parallel genetic algorithm as function optimizer,” in Fourth Int. Conf. on Genetic Algorithms, edited by R. Belew and L.B. Booker,Morgan Kaufmann: San Mateo, 1991, pp. 271–278.

    Google Scholar 

  46. A. Wright, “Genetic algorithms for real parameter optimization,” in Foundations of Genetic Algorithms, vol. 1, edited by G.J.E. Rawlin, Morgan Kaufmann: San Mateo, pp. 205–218, 1991.

    Google Scholar 

  47. H. M¨uhlenbein and D. Schlierkamp-Voosen, “Predictive models for the breeder genetic algorithm I. continuous parameter optimization,” Evolutionary Computation, vol. 1, pp. 25–49, 1993.

    Google Scholar 

  48. L.J. Eshelman and J.D. Schaffer, “Real-coded genetic algorithms and interval-schemata,” in Foundation of Genetic Algorithms vol. 2, edited by L.D. Whitley, Morgan Kaufmann Publishers: San Mateo, pp. 187–202, 1993.

    Google Scholar 

  49. H.M. Voigt, H. M¨uhlenbein, and D. Cvetkovi´c, “Fuzzy recombination for the breeder genetic algorithm,” in Proc. of the Sixth Int. Conf. on Genetic Algorithms, edited by L. Eshelman, Morgan Kaufmann Publishers: San Francisco, 1995, pp. 104–111.

    Google Scholar 

  50. W.M. Spears, “Adapting crossover in evolutionary algorithms,” in Proc. of the Evolutionary Programming Conference 1995, 1995, pp. 367–384.

  51. F. Herrera and M. Lozano, “Heuristic crossover for real-coded genetic algorithms based on fuzzy connectives,” in 4th International Conference on Parallel Problem Solving from Nature, Lecture Notes on Computer Science, vol. 1141, edited by H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, Springer: Berlin, Germany, 1996, pp. 336–345.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and A.I., University of Granada, 18071, Granada, Spain

    F. Herrera

  2. Department of Computer Science and A.I., University of Granada, 18071, Granada, Spain

    M. Lozano

Authors
  1. F. Herrera
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. Lozano
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Herrera, F., Lozano, M. Two-Loop Real-Coded Genetic Algorithms with Adaptive Control of Mutation Step Sizes. Applied Intelligence 13, 187–204 (2000). https://doi.org/10.1023/A:1026531008287

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1026531008287

Search

Navigation