Advertisement

Genetic Algorithms and the Design of Experiments

  • Colin R. Reeves
  • Christine C. Wright
Chapter
Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 111)

Abstract

The genetic algorithm (GA) has most often been viewed from a biological perspective. The metaphors of natural selection, cross-breeding and mutation have been helpful in providing a framework in which to explain how and why they work. However, most practical applications of GAs are in the context of optimization, where alternative approaches may prove more effective. In attempting to understand how GAs function as optimizers, several alternative viewpoints have been suggested. In this paper we discuss one of these in some detail—one in which GAs are regarded as a form of sequential experimental design.

The first section of this paper is expository, where we review some of the basic concepts of experimental design as introduced in earlier papers [1, 2] and show how they relate to GAs. We then show how these ideas can be used to investigate the question of how epistasis can be measured, and demonstrate the fact that not all epistasis in necessarily harmful. Using ED concepts we are also able to show that in general it is not possible to determine a priori that a given problem instance is likely to be hard or easy to optimize by means of a GA Finally, we show how the concept of an orthogonal ED can be used to define a lower limit in terms of the necessary amount of computation required to solve an optimization problem.

In the second part, we describe some empirical work in which GAs are compared with ED-based methods. In a typical designed experiment, a fraction of the Universe of all possible solutions is chosen in a way that is thought to enable the identification of important factors (genes in traditional GA terminology) and their associated levels (alleles) in a candidate optimal solution. Generally, this is only the first stage; further tests must be made in order to confirm or reject these tentative conclusions. Sometimes, further experiments are also carried out to refine the values of some of the less important factors.

However, one of the problems with the use of ED for optimization is the sheer amount of human effort needed in order to apply such techniques in this context. For this reason, ED has usually been restricted to fairly small problems (by GA standards). Recently, some suggestions have been made for increasing the range of problems to which ED ideas can be applied by automating some of the decisions customarily made by the experimenter. A GA is also a means for conducting experiments, testing hypotheses (at least implicitly), and identifying candidate optimal solutions. It thus seems appropriate to compare the performance of a GA with ED-based approaches.

We examine an engineering design problem in which one version of the ED-based approach outperformed a GA, and also describe some experiments on artificial test problems of bounded epistasis in which a GA appears much better able to cope with higher-order interactions than ED-based methods.

In conclusion, we discuss the similarities and differences between GAs and ED revealed in the course of this research. One difference in focus is that ED has traditionally been concerned, not merely in finding the best solution, but also in explaining this result in terms of a model. Statisticians have previously seen this as a rather intractable problem for a GA, but recent developments in computer algebra may provide a means for resolving this issue.

Keywords

Genetic Algorithm Elite Solution Engineering Design Problem Orthogonal Subset Orthogonal Fraction 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [1]
    C. R. Reeves and C. C. Wright, (1995), An experimental design perspective on genetic algorithms, In D. Whitley and M. Vose (Eds.), (1995) Foundations of Genetic Algorithms 3, Morgan Kaufmann, San Mateo, CA, 7–22.Google Scholar
  2. [2]
    C. R. Reeves and C. C. Wright, (1995), Epistasis in genetic algorithms: an experimental design perspective, In L. J. Eshelman (Ed.), (1995), Proceedings of the 6th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 217–224.Google Scholar
  3. [3]
    J. H. Holland, (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.Google Scholar
  4. [4]
    D. E. Goldberg, (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, Mass.Google Scholar
  5. [5]
    K. A. de Jong, (1975), An analysis of the behavior of a class of genetic adaptive systems, Doctoral dissertation, University of Michigan.Google Scholar
  6. 6.
    K. A. de Jong, (1993), Genetic algorithms are NOT function optimizers, In L. D. Whitley (Ed.), (1993), Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Mateo, CA, 5–17.Google Scholar
  7. [7]
    M. Behe,(1996),Darwin’s Black Box: The Biochemical Challenge to Evolution, Free Press, New York, NY.Google Scholar
  8. [8]
    M. Denton, (1984), Evolution: A Theory in Crisis. Burnett Books, London.Google Scholar
  9. [9]
    M. Denton, (1996), Biology: The Anthropic Perspective, Libraire Artheme Fayard, Paris.Google Scholar
  10. [10]
    H. Mtihlenbein, (1991), Evolution in time and space-the parallel genetic algorithm, In G. J. E. Rawlins (Ed.), (1991), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 316–337.Google Scholar
  11. [11]
    N. J. Radcliffe, (1991), Forma analysis and random respectful recombination,In R. K. Belew and L.B. Booker (Eds.), (1991), Proceedings of 4thInternational Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 222–229.Google Scholar
  12. [12]
    W. G. Macready and D. H. Wolpert, (1996), On 2-armed Gaussian Bandits and Optimization, Technical Report SFI-TR-9б-03–009, Santa Fe Institute, Santa Fe, New Mexico.Google Scholar
  13. [13]
    D. E. Goldberg, (1989), Genetic algorithms and Walsh functions: part II,deception and its analysis, Complex Systems, 3, 153–171.MathSciNetzbMATHGoogle Scholar
  14. [14]
    D. Whitley, (1991), Fundamental principles of deception in genetic search, In G. J. E. Rawlins (Ed.), (1991), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 221–241.Google Scholar
  15. [15]
    J. J. Grefenstette, (1993), Deception considered harmful, In L. D. Whitley (Ed.), (1993), Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Mateo, CA, 75–91.Google Scholar
  16. [16]
    M. Mitchell, J. H. Holland and S. Forrest, (1994), When will a genetic algorithm outperform hill climbing?, In J. D. Cowan, G. Tesauro and J. Alspector (Eds.), (1994), Advances in Neural Information Processing Systems 6, Morgan Kaufmann, San Mateo, CA.Google Scholar
  17. [17]
    D. Whitley, (1993), An executable model of a simple genetic algorithm, In L. D. Whitley (Ed.), (1993), Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Mateo, CA, 45–62.Google Scholar
  18. [18]
    M. D. Vose, (1993), Modeling simple genetic algorithms, In L.D. Whitley (Ed.), (1993), Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Mateo, CA, 63–73.Google Scholar
  19. [19]
    M. D. Vose, (1994), A closer look at mutation in genetic algorithms, Annals of Maths and Al, 10, 423–434.MathSciNetzbMATHGoogle Scholar
  20. [20]
    M. D. Vose and A. H. Wright, (1995), Stability of vertex fixed points and applications, In D. Whitley and M. Vose (Eds.), (1995), Foundations of Genetic Algorithms 3, Morgan Kaufmann, San Mateo, CA, 103–113.Google Scholar
  21. [21]
    K. A. de Jong, W. M. Spears and D. F. Gordon, (1995), Using Markov chains to analyze GAFOs, In D. Whitley and M. Vose (Eds.), (1995), Foundations of Genetic Algorithms 3, Morgan Kaufmann, San Mateo, CA, 115–137.Google Scholar
  22. [22]
    Y. Davidor, (1990), Epistasis variance: suitability of a representation to genetic algorithms, Complex Systems, 4, 369–383.Google Scholar
  23. [23]
    Y. Davidor, (1991), Epistasis variance: a viewpoint on GA-hardness, In G. J. E. Rawlins (Ed.), (1991), Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 23–35.Google Scholar
  24. [24]
    D. E. Goldberg, (1989), Genetic algorithms and Walsh functions: part I,a gentle introduction, Complex Systems, 3, 129–152.MathSciNetzbMATHGoogle Scholar
  25. [25]
    A. D. Bethke, (1981), Genetic algorithms as function optimizers, Doctoral dissertation, University of Michigan.Google Scholar
  26. [26]
    A. J. Mason, (1991), Partition coefficients, static deception and deceptive problems for non-binary alphabets, In R. K. Belew and L. B. Booker (Eds.), (1991), Proceedings of 4th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 210–214.Google Scholar
  27. [27]
    D. C. Montgomery, (1991), Design and Analysis of Experiments, Wiley, New York.zbMATHGoogle Scholar
  28. [28]
    S. Ghosh, (1990), (Ed.), Statistical Design and Analysis of Industrial Experiments, Marcel Dekker, New York.zbMATHGoogle Scholar
  29. [29]
    M. D. Morris and T. J. Mitchell, (1995), Exploratory designs for computational experiments, J. Statistical Planning and Inference, 43, 381–402.zbMATHCrossRefGoogle Scholar
  30. [30]
    R. A. Bates, R. J. Buck, E. Riccomagno and H. P. Wynn, (1996), Experimental design and observation for large systems, J. R. Statist. Soc. B, 58, 77–94.MathSciNetzbMATHGoogle Scholar
  31. [31]
    C. F. J. Wu, S. S. Mao and F. S. Ma, (1990), SEL: A search method based on orthogonal arrays, In S. Ghosh (1990), (Ed.), Statistical Design and Analysis of Industrial Experiments, Marcel Dekker Inc., New York, 279–310.Google Scholar
  32. [32]
    C. R. Reeves and C. C. Wright, (1997), Genetic algorithms versus experimental methods: a case study, In Th. Bäck (Ed.), (1997), Proceedings of 7th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 214–220.Google Scholar
  33. [33]
    S. E. Carlson, R. Shonkwiler and M. Ingrim, (1993), A comparative evaluation of search methods applied to catalog selection, In S. Forrest (Ed.),(1993), Proceedings of 5th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 630.Google Scholar
  34. [34]
    C. R. Reeves, (1993), Using genetic algorithms with small populations,In S. Forrest (Ed.), (1993), Proc. of 5th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 92–99.Google Scholar
  35. [35]
    T. Haslam, (1996), An Investigation of the Effectiveness of the SEL Search Technique to Locate Optima over Different Response Surfaces, BSc Dissertation, School of Mathematical and Information Sciences, Coventry University.Google Scholar
  36. [36]
    G. Pistone and H. P. Wynn, (1996), Generalised confounding with Gröbner bases, Biometrika, 83, 653–666.MathSciNetzbMATHCrossRefGoogle Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • Colin R. Reeves
    • 1
  • Christine C. Wright
    • 1
  1. 1.School of Mathematical and Information SciencesCoventry UniversityUK

Personalised recommendations