Skip to main content
SpringerLink
Log in

The algebra of genetic algorithms

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

A rigorous formulation of the generalisation of schema analysis known as forma analysis is presented. This is shown to provide a direct mechanism for harnessing knowledge about a search space, codified through the imposition of equivalence relations over that space, to generate a genetic representation and operators. It is shown that a single characterisation of a space leads to a unique genetic representation, and the kinds of representations that are possible are classified and discussed. A relatively new operator, calledrandom assorting recombination (RAR w ), is defined rigorously and is shown to be, in an important sense, a universal recombination operator.

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. J. Antonisse, A new interpretation of schema notation that overturns the binary coding constraint,Proc. 3rd Int. Conf. on Genetic Algorithms (Morgan Kaufmann, San Mateo, 1989).

    Google Scholar 

  2. A.D. Bethke, Genetic algorithms and function optimizers, Ph.D. Thesis, University of Michigan (1970).

  3. C. Bridges and D.E. Goldberg, An analysis of reproduction and crossover in a binary-coded genetic algorithm,Proc. 2nd Int. Conf. on Genetic Algorithms (Lawrence Erlbaum Assoc., Hillsdale, New Jersey, 1987).

    Google Scholar 

  4. D.J. Cavicchio, Adaptive search using simulated evolution. Ph.D. Thesis, University of Michigan (1970).

  5. L.J. Eshelman, R.A. Caruana and J.D. Schaffer, Biases in the crossover landscape,Proc. 3rd Int. Conf. on Genetic Algorithms (Morgan Kaufmann, San Mateo, 1989).

    Google Scholar 

  6. D.R. Franz, Non-linearities on genetic adaptive search, Ph.D. Thesis, University of Michigan (1972).

  7. D.E. Goldberg and R. Lingle Jr., Alleles, loci and the traveling salesman problem,Proc. Int. Conf. on Genetic Algorithms (Lawrence Erlbaum Assoc., Hillsdale, 1985).

    Google Scholar 

  8. S. Good, Applying a genetic algorithm to a high frequency detector location problem, Technical Report (final year), Department of Computer Science, University of Edinburgh (1993).

  9. J.H. Holland, Adaptation in natural and artificial systems (University of Michigan Press, Ann Arbor, 1975).

    Google Scholar 

  10. G.P. Jones, Parallel genetic algorithms for large travelling salesrep problems, Master's Thesis, University of Edinburgh (1992).

  11. A. Nix and M.D. Vose, Modeling genetic algorithms with Markov chains, Ann. Math. and AI 5 (1991) 79–88.

    Google Scholar 

  12. N.J. Radcliffe and F.A.W. George, A study in set recombination, in:Genetic Algorithms: Proc. 5th Int. Conf. (GA-93), ed. S. Forrest (Morgan Kaufmann, San Mateo, 1993).

    Google Scholar 

  13. N.J. Radcliffe, Genetic neural networks on MIMD computers, Ph.D. Thesis, University of Edinburgh (1990).

  14. N.J. Radcliffe, Equivalence class analysis of genetic algorithms, Complex Syst. 5(2) (1991) 183–205.

    Google Scholar 

  15. N.J. Radcliffe, Forma analysis and random respectful recombination,Proc. 4th Int. Conf. on Genetic Algorithms (Morgan Kaufmann, San Mateo, 1991) pp. 222–229.

    Google Scholar 

  16. N.J. Radcliffe, Genetic set recombination, in:Foundations of Genetic Algorithms 2, ed. D. Whitley (Morgan Kaufmann, San Mateo, 1992).

    Google Scholar 

  17. N.J. Radcliffe, Genetic set recombination and its application to neural network topology optimisation, Neural Comput. Appl. 1(1) (1992).

  18. N.J. Radcliffe, Non-linear genetic representations, in:Parallel Problem Solving from Nature 2, eds. R. Männer and B. Manderick (North-Holland, Amsterdam, 1992) pp. 259–268.

    Google Scholar 

  19. J. Shapcott, Genetic algorithms for investment portfolio selection, Technical Report EPCC-SS92-24, Edinburgh Parallel Computing Centre, University of Edinburgh (1992).

  20. W.M. Spears and K.A. De Jong, On the virtues of parameterised uniform crossover,Proc. 4th Int. Conf. on Genetic Algorithms (Morgan Kaufmann, San Mateo, 1991) pp. 230–236.

    Google Scholar 

  21. G. Syswerda, Uniform crossover in genetic algorithms,Proc. 3rd Int. Conf. on Genetic Algorithms (Morgan Kaufmann, San Mateo, 1989).

    Google Scholar 

  22. M.D. Vose and G.E. Liepins, Punctuated equilibria in genetic search, Complex Syst. 5 (1991) 31–44.

    Google Scholar 

  23. M.D. Vose and G.E. Liepins, Schema disruption,Proc. 4th Int. Conf. on Genetic Algorithms (Morgan Kaufmann, San Mateo, 1991) pp. 237–243.

    Google Scholar 

  24. M.D. Vose, Generalizing the notion of schema in genetic algorithms, Artificial Intelligence (1991).

  25. D. Whitley, An executable model of a simple genetic algorithm, in:Foundations of Genetic Algorithms 2, ed. D. Whitley (Morgan Kaufmann, San Mateo, 1992).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Edinburgh Parallel Computing Centre, University of Edinburgh, King's Buildings, EH9 3JZ, Edinburgh, Scotland

    Nicholas J. Radcliffe

Authors
  1. Nicholas J. Radcliffe
    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

Radcliffe, N.J. The algebra of genetic algorithms. Ann Math Artif Intell 10, 339–384 (1994). https://doi.org/10.1007/BF01531276

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01531276

Keywords

Search

Navigation