This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
Assume the initial population was 17, 21, 4 and 28. Using the same GA methods we used above (PC = 1.0, PM = 0.0), what chance is there of finding the global optimum.
If we look at the values in binary we get
|
We know (although for any realistic problem we would not) that the global optimum
is x = 10 which, in binary is 01010.
You can see that we need a 1 in positions 2 and 4 (counting from the right - although in this case it does not matter). In the initial population there is no individual with a 1 in position 2. This means that no matter how many times we apply single point crossover we will never be able to find the optimum. In addition, only the last individual has a 1 in position 4. This means that unless this individual is selected in the first round of breeding , then this bit will be lost. As the individual has an evaluation of 212 (compared to 17 = 2973, 21 = 1801 and 4 = 2804), it has the least chance of being selected.
1. Coley, D. A. 1999. An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific Publishing
2. Davis, L., 1991. Handbook of Genetic Algorithms. Van Nostrand Reinhold
3. Fraser, A.S. 1957. Simulation of genetic systems by automatic digital computers. II. Effects of linkage on rates under selection. Australian J. of Biol Sci, vol 10, pp 492-499
4. Fraser, A.S. 1960. Simulation of genetic systems by automatic digital computers. IV. Epistatis. Australian J. of Biol Sci, vol 13, pp 329-346
5. Bremermann, H.J. 1958. The Evolution of Intelligence. The Nervous System as a Model of its Environment. Technical Report No. 1, Contract No. 477(17), Dept. of Mathematics, Univ. of Washington, Seattle.
6. Goldberg, D. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning.
7. Gray, F. 1953. Pulse Code Communication, U. S. Patent 2 632 058, March 17, 1953.
8. Holland, John H. 1992. Adaptation in natural and artificial systems.
9. Hollstien, R.B. 1971. Artificial Genetic Adaptation in Computer Control Systems, PhD thesis, University of Michigan
10. Horowitz, P. and Hill, Winfield. 1989. The Art of Electronics. Second Edition, Cambridge University Press
11. Kozen, D. 1992. The Design and Analysis of Algorithms. Springer-Verlag, New York, NY
12. Levy, S. 1993. Artificial Life : The Quest for a New Creation. Penguin Books, pp 153-187
13. Michalewicz, Z. 1996. Genetic algorithms + Data Structures = Evolution Programs. 3rd ed. ISBN 3-540-60676-9
14. Michalewicz, Z and Fogel, D.B. 2000. How To Solve It. Springer-Verlag. ISBN 3-540-66061-5
15. Mitchell, M. 1996. An Introduction to Genetic Algorithms. MIT
16. Press, W.H. Press, et al. 1992. Numerical Recipes in C. Second Edition, Cambridge University Press
17. Reeves, C.R. 1995. Modern Heuristic Techniques for Combinatorial Problems. McGraw Hill
18. Reingold, E.M., et al.. 1977. Combinatorial Algorithms. Prentice Hall, Englewood Cliffs, NJ
19. Russell, S., Norvig, P. 1995. Artificial Intelligence A Modern Approach. Prentice-Hall. ISBN 0-13-103805-2
Previous Page Index Page Next Page
Last Updated : 26/01/2002