Skip to main content
SpringerLink
Log in

The impact of representation on the efficacy of Artificial intelligence: The case of genetic algorithms

  • Published:
AI & SOCIETY Aims and scope Submit manuscript

Abstract

This paper is about representations for Artificial Intelligence systems. All of the results described in it involve engineering the representation to make AI systems more effective. The main AI techniques studied here are varieties of search: path-finding in graphs, and probablilistic searching via simulated annealing and genetic algorithms. The main results are empirical findings about the granularity of representation in implementations of genetic algorithms. We conclude by proposing a new algorithm, called “Long-Term Evolution,” which is a genetic algorithm running on an evolving problem description. We see this as modelling the evolution of a species from simpler (more coarsely described— fewer genes) types of organisms to more complex ones. The results, which are reported here of our experiments with the algorithm make it seem a promising optimisation technique.

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

  • Amarel, S. (1968). On Representations of Problems of Reasoning About Actions. In Michie (ed.)Machine Intelligence, 3, Edinburgh University Press. 131–171

  • Banerji, R.B. (1980). Artificial Intelligence: A Theoretical Approach, North-Holland Elsevier Science Publishing.

  • Davis L. and Steenstrup, M. (1987). Genetic Algorithms and Simulated Annealing: An Overview. In Davis (ed.)Genetic Algorithms and Simulated Annealing, Pitman, 1–11.

  • de Jong, K. A. (1975). An Analysis of the Behavior of a Class of Genetic Adaptation Systems, PhD Thesis, University of Michigan.

  • Donald B., Xavier, P., Canny, J., and Reif, J. (1993). Kinodynamic Motion Planning.Journal of the ACM. 40(5), 1048–1066.

    Article  MATH  MathSciNet  Google Scholar 

  • Fikes, R. and Nilsson, N.J. (1971). STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.Artificial Intelligence. 2, 189–208.

    Article  MATH  Google Scholar 

  • Hart, P.E., Nilsson N.J., and Raphael B. (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Paths.IEEE Transactions on Systems Science and Cybernetics. 4(2), 100–107.

    Article  Google Scholar 

  • Holland, J.H. (1975). Adaptation in Natural and Artificial Systems, The University of Michigan Press.

  • Holte, R. C., Mkadmi, T., Zimmer R.M., and MacDonald, A.J. (1996). Speeding Up Problem-Solving by Abstraction: A Graph-Oriented Approach.Artificial Intelligence., 85, 321–361.

    Article  Google Scholar 

  • Holte, R.C., Drummond C., Perez, M.B., Zimmer, R.M., and MacDonald, A.J. (1994). Searching with Abstractions: A Unifying Framework and New High-Performance Algorithm.Proc. of the 10th Canadian Conference on Artificial Intelligence (Artificial Intelligence ’94), Morgan Kaufman Publishers. 263–270.

  • Kavraki, L. and Latombe J.-C. (1994). Randomized Preprocessing of Configuration Space for Fast Path Planning.Proceedings of the IEEE International Conference on Robotics and Automation.

  • Kirkpatrick, S., Gelatt, C.D. and Vecchi, M. P. (1983). Optimisation by Simulated Annealing.Science 220. 671–680

    Article  MathSciNet  Google Scholar 

  • Knoblock, C.A. (1990). A Theory of Abstraction for Hierarchical Planning. In Benjamin (ed.)Change of Representation and Inductive Bias, Kluwer. 81–104.

  • Knoblock, C.A. (1994). Automatically Generating Abstractions for Planning.Artificial Intelligence. 68(2), 243–302.

    Article  MATH  Google Scholar 

  • Korf, R.E. (1980). Towards a Model of Representation Changes.Artificial Intelligence. 14(1), 41–78.

    Article  MathSciNet  Google Scholar 

  • Korf, R.E. (1985). Macro-operators: a weak method for learning,Artificial Intelligence, 26, 35–77.

    Article  MATH  MathSciNet  Google Scholar 

  • Metropolis, N, Rosenbluth A., Rosenbluth M, Teller A, Teller E. (1953) “Equation of State Calculations by Fast Computing Machines”,Journal of Chemical Physics 275. Springer-Verlag, 354–372.

  • Minton S. (1990), Quantitative Results Concerning the Utility of Explanation-based Learning.Artificial Intelligence. 42(2–3), 363–392.

    Article  Google Scholar 

  • Prieditis, A., and Janakiraman, B. (1993). Generating Effective Admissible Heuristics by Abstraction and Reconstitution.Proc. AAAI ’93. 743–748.

  • Schraudolph, N.N. and Belew, R.K. (1992). Dynamic Parameter Encoding for Genetic Algorithms.Machine Learning, 9.

  • Yang, Q. and Tenenberg J.D. (1990), Abtweak: Abstracting a nonlinear, least commitment planner.Proc. AAAI ’90, 204–209.

    Google Scholar 

  • Zimmer, R. M., MacDonald A.J., and Holte R. C. (1991). Reasoning about Representations.Florida Artificial Intelligence Research Symposium. 201–205.

  • Zimmer, R. (1990). Category Theory and Representation Engineerin. In Benjamin (ed.)Change of Representation and Inductive Bias, Kluwer.

Download references

Author information

Authors and Affiliations

  1. Department of Information Systems and Computing, Brunel University, UB8 3PH, Uxbridge, England

    Robert Zimmer & Alan MacDonald

  2. Computer Science Department, University of Ottawa, Ottawa, Ontario, Canada

    Robert Holte

Authors
  1. Robert Zimmer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Robert Holte
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alan MacDonald
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Robert Zimmer.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zimmer, R., Holte, R. & MacDonald, A. The impact of representation on the efficacy of Artificial intelligence: The case of genetic algorithms. AI & Soc 11, 76–87 (1997). https://doi.org/10.1007/BF02812440

Download citation

  • Issue Date:

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

Keywords

Search

Navigation