[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Using Disruptive Selection to Maintain Diversity in Genetic Algorithms

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. With their great robustness, genetic algorithms have proven to be a promising technique for many optimization, design, control, and machine learning applications. A novel selection method, disruptive selection, has been proposed. This method adopts a nonmonotonic fitness function that is quite different from conventional monotonic fitness functions. Unlike conventional selection methods, this method favors both superior and inferior individuals. Since genetic algorithms allocate exponentially increasing numbers of trials to the observed better parts of the search space, it is difficult to maintain diversity in genetic algorithms. We show that Disruptive Genetic Algorithms (DGAs) effectively alleviate this problem by first demonstrating that DGAs can be used to solve a nonstationary search problem, where the goal is to track time-varying optima. Conventional Genetic Algorithms (CGAs) using proportional selection fare poorly on nonstationary search problems because of their lack of population diversity after convergence. Experimental results show that DGAs immediately track the optimum after the change of environment. We then describe a spike function that causes CGAs to miss the optimum. Experimental results show that DGAs outperform CGAs in resolving a spike function.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. D.H. Ackley, A Connectionist Machine for Genetic Hillclimbing, Kluwer Academic Publishers: Boston, MA, 1987.

    Google Scholar 

  2. J.E. Baker, “Adaptive selection methods for genetic algorithms,” in Proceedings of the First International Conference on Genetic Algorithms and Their Applications, edited by J.J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, July 1985, pp. 101–111.

    Google Scholar 

  3. J.E. Baker, “An analysis of the effects of selection in genetic algorithms,” Ph.D. thesis, Vanderbilt University, Nashville, 1989.

    Google Scholar 

  4. R.J. Berry, Genetics, English University Press: London, 1965.

    Google Scholar 

  5. B. Bhanu, S. Lee, and J. Ming, “Self-optimizing image segmentation system using a genetic algorithm,” in Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, edited by R.K. Belew and L.B. Booker, Morgan Kaufmann: San Mateo, CA, July 1991, pp. 362–369.

    Google Scholar 

  6. L.B. Booker, “Intelligent behavior as an adaptation to the task environment,” Ph.D. thesis, Univ. of Michigan, 1982.

  7. L.B. Booker, “Triggered rule discovery in classifier systems,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 265–274.

    Google Scholar 

  8. G.A. Cleveland and S.F. Smith, “Using genetic algorithms to schedule flow shop releases,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 160–169.

    Google Scholar 

  9. J.P. Cohoon, S.U. Hegde, W.N. Martin, and D.S. Richards, “Punctuated equilibria: A parallel genetic algorithm,” in Proceedings of the Second International Conference on Genetic Algorithms and Their Applications, edited by J.J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, July 1987, pp. 148–154.

    Google Scholar 

  10. R.J. Collins and D.R. Jefferson, “Selection in massively parallel genetic algorithms,” in Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, edited by R.K. Belew and L.B. Booker, Morgan Kaufmann: San Mateo, CA, July 1991, pp. 249–256.

    Google Scholar 

  11. Y. Davidor, “A naturally occurring niche and species phenomenon: The model and first results,” in Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, edited by R.K. Belew, Morgan Kaufmann: San Mateo, CA, July 1991, pp. 257–263.

    Google Scholar 

  12. K. Deb, “Genetic algorithms in multimodal function optimization,” Technical Report, TCGA Report No. 89002, University of Alabama, 1989.

  13. K. Deb and D.E. Goldberg, “An investigation of niche and species formation in genetic function optimization,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 42–50.

    Google Scholar 

  14. M. Dorigo and U. Schnepf, “Genetic-based machine learning and behavior-based robotics: A new synthesis,” IEEE Transactions on System, Man, and Cybernetics, vol. SMC-23,no. 1, pp. 141–154, 1993.

    Google Scholar 

  15. L.J. Eshelman, R.A. Caruana, and J.D. Schaffer, “Biases in the crossover landscape,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 10–19.

    Google Scholar 

  16. L.J. Eshelman and J.D. Schaffer, “Preventing premature convergence in genetic algorithms by preventing incest,” in Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, edited by R.K. Belew and L.B. Booker, Morgan Kaumann: San Mateo, CA, July 1991, pp. 115–122.

    Google Scholar 

  17. D.E. Goldberg, “Genetic algorithms and rules learning in dynamic system control,” in Proceedings of the First International Conference on Genetic Algorithms and Their Applications, edited by J.J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, July, 1985, pp. 8–15.

    Google Scholar 

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

    Google Scholar 

  19. D.E. Goldberg, “Sizing populations for serial and parallel genetic algorithms,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J. David Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 70–79.

    Google Scholar 

  20. D.E. Goldberg and R. Lingle, Jr., “Alleles, loci, and the traveling salesman problem,” in Proceedings of the First International Conference on Genetic Algorithms and Their Applications, edited by J.J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, July 1985, pp. 154–159.

    Google Scholar 

  21. D.E. Goldberg and J. Richardson, “Genetic algorithms with sharing for multimodal function optimization,” in Proceedings of the Second International Conference on Genetic Algorithms, edited by J.J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, July 1987, pp. 41–49.

    Google Scholar 

  22. M. Gorges-Schleuter, “Asparagos an asynchronous parallel genetic optimization strategy,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 422–427.

    Google Scholar 

  23. J.J. Grefenstette, “Optimization of control parameters for genetic algorithms,” IEEE Transactions on System, Man, and Cybernetics, vol. SMC-16,no. 1, pp. 122–128, 1986.

    Google Scholar 

  24. J.J. Grefenstette, “Credit assignment in rule discovery systems based on genetic algorithms,” Machine Learning, vol. 3,no. 2/3, pp. 225–245, 1988.

    Google Scholar 

  25. J.J. Grefenstette and J.E. Baker, “How genetic algorithms work: A critical look at implicit parallelism,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 20–27.

    Google Scholar 

  26. J.J. Grefenstette, R. Gopal, B.J. Rosmaita, and D.V. Gucht, “Genetic algorithms for the traveling salesman problem,” in Proceedings of the First International Conference on Genetic Algorithms and Their Applications, edited by J.J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, July 1985, pp. 160–168.

    Google Scholar 

  27. P.B. Grosso, “Computer simulation of genetic adaptation: Parallel subcomponent interaction in a multilocus model,” Ph.D. thesis, Univ. of Michigan, 1985.

  28. S.A. Harp, T. Samad, and A. Guha, “Towards the genetic synthesis of neural networks,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 360–369.

    Google Scholar 

  29. J.H. Holland, Adaptation in Natural and Artificial System, The University of Michigan Press: Ann Arbor, MI, 1975.

    Google Scholar 

  30. J.H. Holland, “Searching nonlinear functions for high values,” Applied Mathematics and Computation, vol. 32, pp. 255–274, 1989.

    Google Scholar 

  31. K.A. De Jong, “An analysis of the behavior of a class of genetic adaptive systems,” Ph.D. thesis, Univ. of Michigan, 1975.

  32. K.A. De Jong, “Learning with genetic algorithms: An overview,” Machine Learning, vol. 3,no. 2/3, pp. 121–138, 1988.

    Google Scholar 

  33. C.L. Karr, “Design of an adaptive fuzzy logic controller using a genetic algorithm,” Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, Morgan Kaufmann: San Mateo, CA, July 1991, pp. 450–457.

    Google Scholar 

  34. K. Kristinsson and G.A. Dumont, “System identification and control using genetic algorithms,” IEEE Transactions on System, Man, and Cybernetics, vol. SMC-22,no. 5, pp. 1033–1046, 1992.

    Google Scholar 

  35. T. Kuo and S.Y. Hwang, “A genetic algorithm with disruptive selection,” IEEE Transactions on System, Man, and Cybernetics, vol. SMC-26,no. 2, pp. 299–307, 1996.

    Google Scholar 

  36. T. Kuo and S.Y. Hwang, “A genetic algorithm with disruptive selection,” in Proceedings of the Fifth International Conference on Genetic Algorithms, edited by S. Forrest, Morgan Kaufmann: San Mateo, CA, July 1993, pp. 65–69.

    Google Scholar 

  37. T. Kuo and S.Y. Hwang, “A study on diversity and convergence in distruptive genetic algorithms,” in Proceedings of 1994 International Computer Symposium, National Chiao Tung University, Hsinchu, Taiwan, Republic of China, Dec. 1994, pp. 145–150.

    Google Scholar 

  38. U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley: Reading, MA, 1989.

    Google Scholar 

  39. H. Mühlenbein, “Parallel genetic algorithms, population genetics and combinatorial optimization,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J. David Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 416–421.

    Google Scholar 

  40. G.F. Miller, P.M. Todd, and S.U. Hegde, “Designing neural networks using genetic algorithms,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 379–384.

    Google Scholar 

  41. E. Pettit and K.M. Swigger, “An analysis of genetic-based pattern tracking and cognitive-based component tracking models of adaptation,” in Proceedings of the National Conference on Artificial Intelligence, pp. 327–332, 1983.

  42. C.B. Petty, M.R. Leuze, and J.J. Grefenstette, “A parallel genetic algorithm,” in Proceedings of the Second International Conference on Genetic Algorithms and Their Applications, edited by J.J. Grefenstette, Lawrence Erlbaum Associates: Hillsdale, NJ, July 1987, pp. 155–161.

    Google Scholar 

  43. R.E. Smith, S. Forrest, and A.S. Perelson, “Searching for diverse, cooperative population with genetic algorithms,” Evolutionary Computation, vol. 1,no. 2, pp. 127–149, 1993.

    Google Scholar 

  44. R.E. Smith and D.E. Goldberg, “Diploidy and dominance in artificial genetic search,” Complex Systems, vol. 6,no. 3, pp. 251–285, 1992.

    Google Scholar 

  45. P. Spiessens and B. Manderick, “A massively parallel genetic algorithm: Implementation and first results,” in Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, edited by R.K. Belew and L.B. Booker, Morgan Kaufmann: San Mateo, CA, July 1991, pp. 279–286.

    Google Scholar 

  46. M.M. Syslo, N. Deo, and J.S. Kowalik, Discrete Optimization Algorithms with Pascal Programs, Prentice-Hall: Englewood Cliffs, NJ, 1983.

    Google Scholar 

  47. G. Syswerda, “Uniform crossover in genetic algorithms,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 2–9.

    Google Scholar 

  48. G. Syswerda and J. Palmucci, “The application of genetic algorithms to resource scheduling,” in Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, edited by R.K. Belew and L.B. Booker, Morgan Kaufmann: San Mateo, CA, July 1991, pp. 502–508.

    Google Scholar 

  49. R. Tanese, “Distributed genetic algorithms,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 434–440.

    Google Scholar 

  50. R. Tanese, “Distributed genetic algorithms for function optimization,” Ph.D. thesis, Univ. of Michigan, 1989.

  51. D. Whitley, “The genitor algorithm and selection pressure: Why rank-based allocation of reproductive trials is best,” in Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, edited by J.D. Schaffer, Morgan Kaufmann: San Mateo, CA, June 1989, pp. 116–123.

    Google Scholar 

  52. D. Whitley and J. Kauth, “Genitor: A different algorithm,” in Proc. of Rocky Mountain Conference on Artificial Intelligence, 1988, pp. 118–130.

  53. D. Whitley and T. Starkweather, “Genitor II: A distributed genetic algorithm,” Journal of Experimental and Theoretical Artificial Intelligence, vol. 2,no. 3, pp. 189–214, 1990.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of International Trade, Takming Junior College of Commerce, Institute of Computer Science and Information Engineering, National Chiao Tung University, Taiwan

    Ting Kuo & Shu-Yuen Hwang

Authors
  1. Ting Kuo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shu-Yuen Hwang
    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

Kuo, T., Hwang, SY. Using Disruptive Selection to Maintain Diversity in Genetic Algorithms. Applied Intelligence 7, 257–267 (1997). https://doi.org/10.1023/A:1008276600101

Download citation

  • Issue Date:

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

Search

Navigation