More Web Proxy on the site http://driver.im/

article

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

Authors:

M. LozanoAuthors Info & Claims

Applied Intelligence, Volume 13, Issue 3

Pages 187 - 204

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

Published: 29 November 2000 Publication History

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.

References

[1]

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

Digital Library

[2]

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

Digital Library

[3]

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

Digital Library

[4]

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

Digital Library

[5]

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

Digital Library

[6]

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.

Digital Library

[7]

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

[8]

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

Digital Library

[9]

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

Digital Library

[10]

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.

[11]

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.

[12]

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.

[13]

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.

[14]

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.

Digital Library

[15]

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]

16. T. Bäck, M. Schütz, 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.

Digital Library

[17]

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

Digital Library

[18]

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

Digital Library

[19]

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

[20]

20. T. Bäck and M. Schütz, "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.

Digital Library

[21]

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

Digital Library

[22]

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.

[23]

23. J. Périaux, 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ériaux, M. Galán, and P. Cuesta, John Wiley & Sons: New York, pp. 371-396, 1995.

[24]

24. M. Sefrioui and J. Périaux, "Fast convergence thanks to diversity," in Proc. of the Fifth Annual Conference on Evolutionary Programming, 1996, pp. 313-321.

[25]

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

[26]

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.

[27]

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.

Digital Library

[28]

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 Kaufmann Publishers: San Francisco, 1995, pp. 144-150.

Digital Library

[29]

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.

Digital Library

[30]

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: San Mateo, pp. 265-283, 1991.

[31]

31. J.J. Grefenstette, "Genetic algorithms for changing environments," in Parallel Problem Solving from Nature, vol. 2, edited by R. Männer and B. Manderick, Elsevier Science Publishers: Amsterdam, pp. 137-144, 1992.

[32]

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

Digital Library

[33]

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

Digital Library

[34]

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: San Mateo, 1991, pp. 77- 84.

[35]

35. T. Bäck 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ériaux, M. Galán, and P. Cuesta, John Wiley & Sons: New York, pp. 111-126, 1995.

[36]

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.

Digital Library

[37]

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.

Digital Library

[38]

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

Digital Library

[39]

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

[40]

40. T. Bäck, "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.

[41]

41. A. Törn and ¿. Antanas, Global Optimization, Lecture Notes in Computer Science, vol. 350, Springer: Berlin, 1989.

[42]

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.

[43]

43. D. Schlierkamp-Voosen and H. Mühlenbein, "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.

Digital Library

[44]

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

Digital Library

[45]

45. H. Mühlenbein, 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.

[46]

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.

[47]

47. H. Mühlenbein and D. Schlierkamp-Voosen, "Predictive models for the breeder genetic algorithm I. continuous parameter optimization," Evolutionary Computation, vol. 1, pp. 25-49, 1993.

Digital Library

[48]

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.

[49]

49. H.M. Voigt, H. Mühlenbein, and D. Cvetkovi¿, "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.

Digital Library

[50]

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

[51]

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.

Digital Library

Cited By

Das APratihar D(2019)A directional crossover (DX) operator for real parameter optimization using genetic algorithmApplied Intelligence10.1007/s10489-018-1364-249:5(1841-1865)Online publication date: 17-May-2019
https://dl.acm.org/doi/10.1007/s10489-018-1364-2
Hedar AAli A(2018)Tabu search with multi-level neighborhood structures for high dimensional problemsApplied Intelligence10.1007/s10489-011-0321-037:2(189-206)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1007/s10489-011-0321-0
Gouvêa MAraújo ALanzi P(2011)Adaptive evolutionary algorithm based on population dynamics for dynamic environmentsProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001701(909-916)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001701
Show More Cited By

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

Recommendations

A step size based self-adaptive mutation operator for evolutionary programming
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

The mutation operator is the only genetic operator in Evolutionary Programming (EP). In the past researchers have nominated Gaussian, Cauchy, and Lévy distributions as mutation operators. According to the No Free Lunch theorem [9], no single mutation ...
Hybridizing adaptive and non-adaptive mutation for cooperative exploration of complex multimodal search space
ACST'07: Proceedings of the third conference on IASTED International Conference: Advances in Computer Science and Technology

One of the most efficient Real-Coded Genetic Algorithms (RCGAs) for function optimization currently is the G3-PCX (Parent-Centric Crossover) algorithm. However, its performance for solving complex multimodal problems with highly deceptive fitness ...
Handling uncertainty with a real-coded EA
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Presence of uncertainty in the search environment of Evolutionary algorithms (EA) interferes with the evaluation and the selection process of EA and adversely affects the performance of the algorithm. Presence of noise also means fitness function can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Intelligence

Applied Intelligence Volume 13, Issue 3

November-December 2000

111 pages

ISSN:0924-669X

Issue’s Table of Contents

Copyright © Copyright © 2000 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 29 November 2000

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Das APratihar D(2019)A directional crossover (DX) operator for real parameter optimization using genetic algorithmApplied Intelligence10.1007/s10489-018-1364-249:5(1841-1865)Online publication date: 17-May-2019
https://dl.acm.org/doi/10.1007/s10489-018-1364-2
Hedar AAli A(2018)Tabu search with multi-level neighborhood structures for high dimensional problemsApplied Intelligence10.1007/s10489-011-0321-037:2(189-206)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1007/s10489-011-0321-0
Gouvêa MAraújo ALanzi P(2011)Adaptive evolutionary algorithm based on population dynamics for dynamic environmentsProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001701(909-916)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001701
Lozano MHerrera FKrasnogor NMolina D(2004)Real-coded memetic algorithms with crossover hill-climbingEvolutionary Computation10.1162/106365604177498312:3(273-302)Online publication date: 1-Sep-2004
https://dl.acm.org/doi/10.1162/1063656041774983
Martinez JPistonesi SFlesia A(undefined)Inference Strategies for Texture ParametersProgress in Pattern Recognition, Image Analysis, Computer Vision, and Applications10.1007/978-3-319-25751-8_55(460-467)
https://dl.acm.org/doi/10.1007/978-3-319-25751-8_55

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents