Introduction to Evolutionary Computation (22753) and Evolutionary Computation (02411) 2009-2010

Outline

Evolutionary computation is the study of computational systems that use ideas and get inspiration from natural evolution. Its techniques can be applied to optimisation, learning and design. Example topics covered in this module include natural and artificial evolution, evolutionary, chromosome representations, search operators, co-evolution, constraint handling techniques, niching and speciation, genetic programming, classifier systems and theoretical foundations.

Aims

The aims of this module are to:

Assessment

Relevant Links

Project Proposals

Lecture and Tutorial Schedule

th same
# Date Topic Lecture notes Lecturer and Demonstrator
01 Friday 02/10/2009 Brief Overview of Evolutionary Computation PDF Xin Yao
02 Monday 05/10/2009 Genetic Representation, search operators, selection schemes and selection pressure PDF Xin Yao
03 Friday 09/10/2009 Operators on Real-valued Representations PDF Philipp Rohlfshagen
04 Monday 12/10/2009 Tutorial 1 PDF Victor Landassuri-Moreno
05 Friday 16/10/2009 Constraint handling and fitness landscapes PDF Thorsten Schnier
06 Monday 19/10/2009 Niching and fitness sharing PDF Thorsten Schnier
07 Friday 23/10/2009 Tutorial 2 PDF Victor Landassuri-Moreno
08 Monday 26/10/2009 Multi-objective Evolutionary Optimisation 1/2 PDF1 PDF2 Per Kristian Lehre
09 Friday 30/10/2009 Multi-objective Evolutionary Optimisation 2/2 PDF1 PDF2 Per Kristian Lehre
10 Monday 02/11/2009 Tutorial 3 PDF, EA.c Victor Landassuri-Moreno
11 Friday 06/11/2009 Genetic Programming 1/2 PDF Thorsten Schnier
12 Monday 09/11/2009 Genetic Programming 2/2 - A Case Study PDF Thorsten Schnier
13 Friday 13/11/2009 Tutorial 4 PDF, sampleCode Victor Landassuri-Moreno
14 Monday 16/11/2009 Co-evolution and speciation PDF Xin Yao
15 Friday 20/11/2009 Multi-population methods and dynamic optimisation PDF,Code Philipp Rohlfshagen
16 Monday 23/11/2009 Tutorial 5 PDF, CodeEA_real Victor Landassuri-Moreno
17 Friday 27/11/2009 Evolving learning-machines 1/2 PDF Xin Yao
18 Monday 30/11/2009 Evolving learning-machines 2/2 PDF Xin Yao
19 Friday 04/12/2009 Tutorial 6 PDF, ExtraTutorial Victor Landassuri-Moreno
20 Monday 07/12/2009 Introductory theoretical Analysis of Evolutionary Algorithms 1/2 PDF Per Kristian Lehre
21 Friday 11/12/2009 Introductory theoretical Analysis of Evolutionary Algorithms 2/2 PDF Per Kristian Lehre
22 Revision Lecture 1 PDF Xin Yao

Exercises

# Given Due date Topic Files
01 Friday 09/10/2009 Monday 12/10/2009 Intro EC PDF
02 Monday 12/10/2009 Monday 19/10/2009 Random and other parameters PDF
03 Monday 19/10/2009 Monday 26/10/2009 EA implementation PDF
04 Monday 26/10/2009 Monday 2/11/2009 General questions PDF
05 Monday 2/11/2009 Monday 9/11/2009 General questions PDF
06 Monday 9/11/2009 Monday 16/11/2009 General questions PDF
07 Monday 16/11/2009 Monday 23/11/2009 General questions PDF
08 Monday 23/11/2009 Monday 30/11/2009 General questions PDF
09 Monday 30/11/2009 Monday 7/12/2009 General questions PDF

Coursework (applies only to 22753)

# Given Due date Topic Files
1 09/10/2010 30/10/2010 Real-Valued Optimisation PDF
2 09/11/2009 11/12/2009 Genetic Programming PDF data file

The coursework is to be submitted online using the school's BOSS system so we can run your code. You may find information regarding the submission system here. You can use an application client (i.e., running on your machine) or the web client (here). In case you encounter any problems, please email support or Philipp Rohlfshagen. Please remember: Submit your source code (as a zip) and report (as a pdf).

Lecture-specific Reading

Some of the following resources are IP restricted. For off-campus access, please follow the instructions provided by IT Services.

# References
02
  • Relevant sections of T. Baeck, D. B. Fogel, and Z. Michalewicz (eds.) Handbook on Evolutionary Computation, IOS Press, 1997. (In the School library.)
  • T. Baeck (1994). Selective pressure in evolutionary algorithms: A characterization of selection mechanisms. In Proceedings of the 1st IEEE Conf. on Evolutionary Computation, pages 57-62. IEEE Press. (PDF IEEE Xplore)
  • Goldberg, D. E. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms, pages 69-93. Morgan Kaufmann. (PDF)
03
  • H.-M. Voigt and J. Lange Local evolutionary search enhancement by random memorizing Proc. of the 1998 IEEE Int. Conf. on Evolutionary Computation. IEEE Press, Piscataway, NJ, USA, pp.547-552, 1998.
  • K.-H. Liang, X. Yao and C. S. Newton Combining landscape approximation and local search in global optimization Proc. of the 1999 Congress on Evolutionary Computation. Vol. 2, IEEE Press, Piscataway, NJ, USA, pp.1514-1520, July 1999. (PDF)
  • X. Yao, Y. Liu and G. Lin Evolutionary programming made faster IEEE Transactions on Evolutionary Computation. 3(2):82-102, July 1999. (PDF)
  • Rowe, J.E. and Hidovic, D. (2004) An Evolution Strategy using a continuous version of the Gray-code neighbourhood distribution Proceedings of GECCO 2004, Part 1 (Lecture Notes in Computer Science, vol. 3102), K. Deb et al. (eds). Springer-Verlag, pages 725-736. (PDF)
06
  • T. Baeck, D. B. Fogel, and Z. Michalewicz (eds.) Handbook on Evolutionary Computation, IOS Press, 1997. Sections C6.1 and C6.2 (in the School library)
  • P. Darwen and X. Yao, A dilemma for fitness sharing with a scaling function, Proc. of 1995 IEEE Conference on Evolutionary Computation (ICEC'95), Dec. 1995, Perth, Australia, IEEE Press, pp.166-171. (PDF IEEE Xplore)
08
  • K. Deb, Multi-Objective Optimization using Evolutionary Algorithms, Wiley, 2001. Chapters 1 and 2 (except Section 2.5). Sections 3.1, 3.2, 5.1, 5.4, 6.2, 6.4, 6.6, 7.1, 7.2 and 7.5. (In the school library)
09
  • Beume, N., Naujoks, B., and Emmerich, M. (2007). SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3):1653-1669. (PDF ScienceDirect)
11
  • Basic Reading: Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, and Frank D. Francone Genetic Programming: An Introduction Morgan Kaufmann Publishers, Chapter 5
  • Advanced Reading: Other chapters in Banzhaf et. al
  • Advanced Reading: John R. Koza: Genetic Programming: On the Programming of Computers by Means of Natural Selection (don't be put off by the volume of the book, you can skim over a lot of the material quickly, just pick interesting applications.)
  • Online: http://www.geneticprogramming.com/
12
  • Basic Reading: J. Li, X. Yao, C. Frayn, H. G. Khosroshahi, S. Raychaudhury, An Evolutionary Approach to Modeling Radial Brightness Distributions in Elliptical Galaxies Proc. of the 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII), Lecture Notes in Computer Science, Vol. 3242, pp.591-601, Springer, September 2004. http://www.cs.bham.ac.uk/~xin/papers/Li_ppsn314.pdf
  • Advanced Reading: Humies: http://www.genetic-programming.org/hc2005/main.html, any of the papers and presentations, in particular 2007 and 2008 winners and placed.
14
  • Pollack, J, Blair, A. and Land, M. (1996). Coevolution of A Backgammon Player. Proceedings Artificial Life V, C. Langton, (Ed), MIT Press. (PDF)
  • Juille, H. and Pollack, J. B. (1996). Dynamics of Co-evolutionary Learning. Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior, Cape Cod, MA, September 9 - 13, 1996, MIT Press, pp. 526-534. (PDF)
  • Juille H. and Pollack, J. B. (1996). Co-evolving Intertwined Spirals. Proceedings of the Fifth Annual Conference on Evolutionary Programming, San Diego, CA, February 29 - March 2, 1996, MIT Press, pp. 461-468. (PDF)
  • A. Arcuri and X. Yao, Coevolving programs and unit tests from their specification Proc. of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE'2007), Atlanta, Georgia, USA, pp.397-400, ACM Press, New York, NY, USA, November 2007. (PDF ACM DL)
  • P. Darwen and X. Yao, Speciation as automatic categorical modularization, IEEE Transactions on Evolutionary Computation, 1(2):101-108, 1997. (PDF IEEE Xplore)
  • T. Baeck, D. B. Fogel, and Z. Michalewicz (eds.), Handbook of Evolutionary Computation, IOP Publ. Co. & Oxford University Press, 1997. Section C6.1 and Section C6.2. (In the school library)
15
  • Jin, Y. and Branke, J. Evolutionary Optimization in Uncertain Environment - A Survey IEEE Transactions on Evolutionary Computation, 2005, 9, 303-3170
  • Rohlfshagen, P. and Yao, X. Dynamic Combinatorial Optimisation Problems: An Analysis of the Subset Sum Problem To appear in: Soft Computing (Special issue on Evolutionary Optimization and Learning) 2009
  • Richter, H. Detecting change in dynamic fitness landscapes Proc. IEEE Congress on Evolutionary Computation, IEEE CEC 2009, (Ed. A. Tyrrell), IEEE Press, Piscataway, NJ, 1613-1620.
  • Bosman, P.A.N. Learning, Anticipation and Time-Deception in Evolutionary Online Dynamic Optimization Evolutionary Algorithms for Dynamic Optimization Problems EvoDOP Workshop at the Genetic and Evolutionary Computation Conference - GECCO-2005, pages 39-47, ACM Press, New York, New York, 2005.
17
  • J. Bobbin and X. Yao, Evolving rules for nonlinear control, New Frontier in Computational Intelligence and its Applications, Masoud Mohammadian (ed.), IOS Press, Amsterdam, 2000, pp.197-202. (ISBN 90 5199 476 1) PDF
  • J. Bobbin and X. Yao, Automatic Discovery of Relational Information in Comprehensible Control Rules by Evolutionary Algorithms, Proceedings of the Third Australia-Japan Joint Workshop on Intelligent and Evolutionary Systems, Canberra, Australia, 23-25 November 1999, pp.117-123. PDF
18
  • X. Yao and Md. M. Islam, Evolving artificial neural network ensembles, IEEE Computational Intelligence Magazine, 3(1):31-42, February 2008. PDF IEEE Xplore
  • X. Yao, Evolving artificial neural networks, Proceedings of the IEEE, 87(9):1423-1447, September 1999. PDF IEEE Xplore
  • X. Yao and Y. Liu, A new evolutionary system for evolving artificial neural networks, IEEE Transactions on Neural Networks, 8(3):694-713, May 1997. PDF IEEE Xplore
20
  • Droste, S., Jansen, T., and Wegener, I. (2006) Upper and lower bounds for randomized search heuristics in black-box optimization., Theory of Computing Systems, 39(4):525-544. PDF SpringerLink (Only Section 1 and Section 2.)
  • Droste, S., Jansen, T., and Wegener, I. (2002) Optimization with randomized search heuristics - the (A)NFL theorem, realistic scenarios, and difficult functions., Theoretical Computer Science, 287(1):131-144. PDF ScienceDirect (All proofs, except the proof of Theorem 1, are for cursory reading.)
21
  • Rudolph, G. (1998). Finite markov chain results in evolutionary computation: A tour d'horizon. Fundamenta Informaticae, 35(1):67-89. PDF (Only Section 1 and Section 2.)
  • Oliveto, P. S., He, J., and Yao, X. (2007). Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4(1):100-106. PDF

Recommended Books

Title Author(s) Publisher, Date Comments
Handbook on Evolutionary Computation T. Baeck, D. B. Fogel, and Z. Michalewicz (eds.) IOS Press, 1997 Very good and comprehensive reference to evolutionary computation. Should read relevant sections after each lecture.
Genetic Algorithms + Data Structures = Evolution Programs (3rd edition) Z Michalewicz Springer-Verlag, 1996 Recommended reference book for this module. It is more up-to-date than Goldberg's book.
Multi-Objective Optimization Using Evolutionary Algorithms Deb Kalyanmoy Wiley, 2001
Introduction to Stochastic Search and Optimization James C. Spall Wiley, 2003
Markov Chain Monte Carlo in Practice W.R. Gilks, S. Richardson & D.J. Spiegelhalter Chapman & Hall, 1996 Comprehensive coverage of MCMC methodology for realistic statistical modeling
Genetic Algorithms in Search, Optimisation & Machine Learning D E Goldberg Addison-Wesley, 1989 Good reference book on genetic algorithms and classifier systems, but no other topics. Somewhat out of date.
Genetic Programming: An Introduction W Banzhaf, P Nordin, R E Keller & Frank D Francone Morgan Kaufmann, 1999 A comprehensive up-to-date textbook on genetic programming.
Evolutionary Computation: Theory and Applications X Yao (ed) World Scientific, 1999 Good for reference.
Various articles in journals and conference proceedings Good for reference.