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

article

Replacement strategies to preserve useful diversity in steady-state genetic algorithms

Authors:

Francisco Herrera,

José Ramón CanoAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 178, Issue 23

Pages 4421 - 4433

https://doi.org/10.1016/j.ins.2008.07.031

Published: 01 December 2008 Publication History

Abstract

In this paper, we propose a replacement strategy for steady-state genetic algorithms that considers two features of the candidate chromosome to be included into the population: a measure of the contribution of diversity to the population and the fitness function. In particular, the proposal tries to replace an individual in the population with worse values for these two features. In this way, the diversity of the population becomes increased and the quality of the solutions gets better, thus preserving high levels of useful diversity. Experimental results show the proposed replacement strategy achieved significant performance for problems with different difficulties, with regards to other replacement strategies presented in the literature.

References

[1]

Bäck, T., Self-adaptation in genetic algorithms. In: Varela, F.J., Bourgine, P. (Eds.), Proceedings of the First European Conference on Artificial Life, The MIT Press, Cambridge, MA. pp. 263-271.

[2]

Branke, J., Cutaia, M. and Dold, H., Reducing genetic drift in steady state evolutionary algorithms. In: Banzhaf, W. (Ed.), Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kaufmann, San Francisco, CA. pp. 68-74.

[3]

Bonham, C.R. and Parmee, I.C., An investigation of exploration and exploitation within cluster oriented genetic algorithms (COGAs). In: Proceedings of the Genetic and Evolutionary Computation Conference 1999, Morgan Kaufmann, San Francisco, California. pp. 1491-1497.

[4]

Cantú-Paz, E., Selection intensity in genetic algorithms with generation gaps. In: Whitley, D., Goldberg, D.E., Cantú-Paz, E., Spector, L., Parmee, I., Beyer, H.-G. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference 2000, Morgan Kaufmann, San Francisco, California. pp. 911-918.

[5]

Cedeño, W., Vemuri, V. and Slezak, T., Multi-niche crowding in genetic algorithms and its application to the assembly of DNA restriction-fragments. Evolutionary Computation. v2 i4. 321-345.

Digital Library

[6]

Cedeño, W. and Vemuri, V., Analysis of speciation and niching in the multi-niche crowding GA. Theoretical Computer Science. v229. 177-197.

Digital Library

[7]

Chellapilla, K., Combining mutation operators in evolutionary programming. IEEE Transactions on Evolutionary Computation. v2 i3. 91-96.

Digital Library

[8]

De Jong, K.A. and Sarma, J., Generation gaps revisited. In: Whitley, L.D. (Ed.), Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Mateo, CA. pp. 19-28.

[9]

E.D. De Jong, R.A. Watson, J.B. Pollack. Reducing bloat and promoting diversity using multi-objective methods, in: L. Spector et al., (Ed.), Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, CA, Morgan Kaufmann, 2001.

[10]

K.A. De Jong, An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph.D. dissertation, University of Michigan, Ann Arbor, 1975.

Digital Library

[11]

Dozier, G., Steady-state evolutionary path planning, adaptive replacement and hyper-diversity. In: Schoenauer, M. (Ed.), Parallel Problem Solving from Nature VI, Springer-Verlag, Berlin. pp. 561-570.

Digital Library

[12]

Eshelman, L.J., The CHC adaptive search algorithm: how to have safe search when engaging in nontraditional genetic recombination. In: Rawlin, G.J.E. (Ed.), Foundations of Genetic Algorithms 1, Morgan Kaufmann, San Mateo, CA. pp. 265-283.

[13]

Eshelman, L.J. and Schaffer, J.D., Preventing premature convergence in genetic algorithms by preventing incest. In: Belew, R., Booker, L.B. (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA. pp. 115-122.

[14]

Eshelman, L.J. and Schaffer, J.D., Real-coded genetic algorithms and interval-schemata. In: Darrell Whitley, L. (Ed.), Foundation of Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo. pp. 187-202.

[15]

Eshelman, L.J., Mathias, K.E. and Schaffer, J.D., Convergence controlled variation. In: Belew, R., Vose, M. (Eds.), Foundations of Genetic Algorithms 4, Morgan Kaufmann, San Mateo, CA. pp. 203-224.

[16]

Ghosh, A., Tsutsui, S. and Tanaka, H., Function optimization in nonstationary environment using steady state genetic algorithms with aging of individuals. In: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, IEEE Press, New York. pp. 666-671.

[17]

Goldberg, D.E., Genetic Algorithms in Search Optimization, and Machine Learning. 1989. Addison-Wesley, Reading, MA.

Digital Library

[18]

Goldberg, D.E. and Deb, K., A comparative analysis of selection schemes used in genetic algorithms. In: Rawlins, G.J.E. (Ed.), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA. pp. 69-93.

[19]

Griewangk, A.O., Generalized descent of global optimization. Journal of Optimization Theory and Applications. v34. 11-39.

[20]

Harik, G., Finding multimodal solutions using restricted tournament selection. In: Eshelman, L.J. (Ed.), Proceedings of the 6th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA. pp. 24-31.

Digital Library

[21]

Herrera, F., Lozano, M. and Verdegay, J.L., Tackling real-coded genetic algorithms: operators and tools for behavioural analysis. Artificial Intelligence Review. v12 i4. 265-319.

Digital Library

[22]

Y. Ichikawa, Y. Ishiiolland, Retainig diversity of genetic algorithms for multivariable optimization and neural network learning, in: Proceedings of IEEE International on Conference on Neural Networks, IEEE Press, San Francisco, California, 1993, pp.1110-1114.

[23]

Lee, C.-Y., Entropy-Boltzmann selection in the genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics. v33 i1. 138-149.

Digital Library

[24]

Li, T.-H., Lucasius, C.B. and Kateman, G., Optimization of calibration data with the dynamic genetic algorithm. Analytica Chimica Acta. v2768. 123-1342.

[25]

Mahfoud, S.W., Crowding and preselection revised. In: Männer, R., Manderick, B. (Eds.), Parallel Problem Solving from Nature 2, Elsevier, Amsterdam. pp. 27-36.

[26]

S.W. Mahfoud, Niching methods for genetic algorithms. IlliGAL report 95001, University of Illinois at Urbana-Champaign, IL, Illinois Genetic Algorithms Laboratory, 1995.

[27]

K. Matsui, New selection method to improve the population diversity in genetic algorithms, in: Systems, Man, and Cybernetics, 1999. IEEE SMC'99 Conference Proceedings, 1999 IEEE International Conference, vol. 1, 12-15 October 1999, pp. 625-630.

[28]

Mengshoel, O.J. and Goldberg, D.E., Probabilistic crowding: deterministic crowding with probabilistic replacement. In: Banzhaf, W. (Ed.), Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, Morgan Kaufmann Publishers, San Francisco, CA. pp. 409-416.

[29]

Mori, N., Yoshida, J., Tamaki, H., Kita, H. and Nichikawa, Y., A thermodynamical selection rule for genetic algorithms. In: Proceedings of the 2nd IEEE Conference on Evolutionary Computation (ICEC'95), IEEE Press, New York. pp. 188-192.

[30]

Mühlenbein, H., Schomisch, M. and Born, J., The parallel genetic algorithm as function optimizer. In: Belew, R., Booker, L.B. (Eds.), Fourth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA. pp. 271-278.

[31]

Mühlenbein, H. and Schlierkamp-Voosen, D., Predictive models for the breeder genetic algorithm I. Continuous parameter optimization. Evolutionary Computation. v1. 25-49.

Digital Library

[32]

Rogers, A. and Prügel-Bennett, A., Modelling the dynamics of a steady state genetic algorithm. In: Banzhaf, W., Reeves, C. (Eds.), Foundations of Genetic Algorithms 5, Morgan Kaufmann, San Francisco, CA. pp. 57-68.

[33]

Sareni, B. and Krähenbühl, L., Fitness sharing and niching methods revisited. IEEE Transactions on Evolutionary Computation. v2 i3. 97-106.

Digital Library

[34]

Sedbrook, T.A., Wright, H. and Wright, R., Application of a genetic classifier for patient triage. In: Belew, R., Booker, L. (Eds.), Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA. pp. 334-338.

[35]

Schlierkamp-Voosen, D. and Mühlenbein, H., Strategy adaptation by competing subpopulations. In: Davidor, Y., Schwefel, H.-P., Männer, R. (Eds.), Parallel Problem Solving from Nature 3, Springer-Verlag, Berlin. pp. 199-208.

Digital Library

[36]

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

Digital Library

[37]

Shimodaira, H., A diversity control oriented genetic algorithm (DCGA): development and experimental results. In: Proceedings of the Genetic and Evolutionary Computation Conference 1999, Morgan Kaufmann, San Francisco, California. pp. 603-611.

[38]

Shimodaira, H., A new genetic algorithm using large mutation rates and population-elitist selection (GALME). In: Proceedings of the International Conference on Tools with Artificial Intelligence, IEEE Computer Society. pp. 25-32.

Digital Library

[39]

Smith, J. and Vavak, F., Replacement strategies in steady state genetic algorithms: static environments. In: Banzhaf, W., Reeves, C. (Eds.), Foundations of Genetic Algorithms, Morgan Kaufmann, San Francisco, CA. pp. 219-233.

[40]

Stadnyk, I., Schema recombination in pattern recognition problems. In: Grefenstette, J.J. (Ed.), Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum, Hillsdale, NJ. pp. 27-35.

Digital Library

[41]

R. Storn, K. Price, Differential evolution - a simple and efficient adaptive scheme for global optimization over continuous spaces, Technical Report TR-95-012, International Computer Science Institute, Berkeley, CA, 1995.

[42]

Syswerda, G., Uniform crossover in genetic algorithms. In: David Schaffer, J. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo. pp. 2-9.

Digital Library

[43]

Thierens, D., Selection schemes, elitist recombination, and selection intensity. In: Bäck, T. (Ed.), Proceedings of the Seventh International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo. pp. 152-159.

[44]

Toffolo, A. and Benini, E., Genetic diversity as an objective in multi-objective evolutionary algorithms. Evolutionary Computation. v11 i2. 151-167.

Digital Library

[45]

Törn, A. and Antanas, ¿., . 1989. Lecture Notes in Computer Science 350, 1989.Springer, Berlin.

[46]

Tsutsui, S. and Fujimoto, Y., Forking genetic algorithm with blocking and shrinking modes. In: Forrest, S. (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA. pp. 206-213.

Digital Library

[47]

Vavak, F. and Fogarty, T.C., Comparison of steady state and generational genetic algorithms for use in nonstationary environments. In: Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, IEEE Press, New York. pp. 192-195.

Digital Library

[48]

Wakunda, J. and Zell, A., Median-selection for parallel steady-state evolution strategies. In: Lecture Notes in Computer Science, vol. 1917. Springer. pp. 405-414.

Digital Library

[49]

Whitley, D., The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best. In: David Schaffer, J. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo. pp. 116-121.

Digital Library

[50]

Whitley, D., Rana, S., Dzubera, J. and Mathias, E., Evaluating evolutionary algorithms. Artificial Intelligence. v85. 245-276.

Digital Library

[51]

Wiese, K. and Goodwin, S.D., Convergence characteristics of keep-best reproduction. Selected Areas in Cryptography. 312-318.

[52]

Wolpert, D.H. and Macready, W.G., No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation. v1 i1. 67-82.

Digital Library

[53]

Yoon, H.-S. and Moon, B.-R., An empirical study on the synergy of multiple crossover operators. IEEE Transactions on Evolutionary Computation. v6 i2. 212-223.

Digital Library

Cited By

Al-Eiadeh MAbdallah M(2024) GeniGraphComputers and Security10.1016/j.cose.2024.103927144:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.cose.2024.103927
Wang JLi CZeng SYang S(2023)History-Guided Hill Exploration for Evolutionary ComputationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325034727:6(1962-1975)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TEVC.2023.3250347
Rueda RCuéllar MRuiz LPegalajar M(2022)A similarity measure for Straight Line Programs and its application to control diversity in Genetic ProgrammingExpert Systems with Applications: An International Journal10.1016/j.eswa.2021.116415194:COnline publication date: 15-May-2022
https://dl.acm.org/doi/10.1016/j.eswa.2021.116415
Show More Cited By

Index Terms

Replacement strategies to preserve useful diversity in steady-state genetic algorithms
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
      2. Modeling methodologies
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation

Recommendations

Standard Steady State Genetic Algorithms Can Hillclimb Faster Than Mutation-Only Evolutionary Algorithms
Explaining to what extent the real power of genetic algorithms (GAs) lies in the ability of crossover to recombine individuals into higher quality solutions is an important problem in evolutionary computation. In this paper we show how the interplay ...
Replacement Strategies in Steady-State Multi-objective Evolutionary Algorithm: A Comparative Case Study
ICNC '08: Proceedings of the 2008 Fourth International Conference on Natural Computation - Volume 01

The paper investigates different replacement strategies for an elite, steady-state multi-objective evolutionary algorithm (MOEA), where the main population and archive population are evolved simultaneously. A new archive population replacement strategy ...
Fitness Uniform Selection to Preserve Genetic Diversity

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 178, Issue 23

December, 2008

167 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2008.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 December 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Al-Eiadeh MAbdallah M(2024) GeniGraphComputers and Security10.1016/j.cose.2024.103927144:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.cose.2024.103927
Wang JLi CZeng SYang S(2023)History-Guided Hill Exploration for Evolutionary ComputationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325034727:6(1962-1975)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TEVC.2023.3250347
Rueda RCuéllar MRuiz LPegalajar M(2022)A similarity measure for Straight Line Programs and its application to control diversity in Genetic ProgrammingExpert Systems with Applications: An International Journal10.1016/j.eswa.2021.116415194:COnline publication date: 15-May-2022
https://dl.acm.org/doi/10.1016/j.eswa.2021.116415
Dang DNguyen NHwang D(2022)Hybrid genetic algorithms for the determination of DNA motifs to satisfy postulate 2-OptimalityApplied Intelligence10.1007/s10489-022-03491-753:8(8644-8653)Online publication date: 20-Apr-2022
https://dl.acm.org/doi/10.1007/s10489-022-03491-7
Zhong XLiu JChen KChen JWang NHe CLu QCheng ZHuang W(2021)A time-optimal wellbore trajectory design for slide drilling systemsStructural and Multidisciplinary Optimization10.1007/s00158-020-02732-y63:2(881-896)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s00158-020-02732-y
Segura CMiranda GSegredo EChacón J(2019)A Novel Memetic Algorithm with Explicit Control of Diversity for the Menu Planning Problem2019 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2019.8790339(2191-2198)Online publication date: 10-Jun-2019
https://dl.acm.org/doi/10.1109/CEC.2019.8790339
Zhang HWang RLiu HLuo HLiu Y(2019)MCDMSRApplied Intelligence10.1007/s10489-019-01414-749:8(2918-2941)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s10489-019-01414-7
Song YWang FChen X(2019)An improved genetic algorithm for numerical function optimizationApplied Intelligence10.1007/s10489-018-1370-449:5(1880-1902)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10489-018-1370-4
Huemmer CHofmann CMaas RKellermann W(2018)Estimating Parameters of Nonlinear Systems Using the Elitist Particle Filter Based on Evolutionary StrategiesIEEE/ACM Transactions on Audio, Speech and Language Processing10.1109/TASLP.2017.278818326:3(595-608)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1109/TASLP.2017.2788183
Zhang HLiu YZhou J(2018)Balanced-evolution genetic algorithm for combinatorial optimization problemsNatural Computing: an international journal10.1007/s11047-018-9670-517:3(611-639)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11047-018-9670-5
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents