Introduction to Evolutionary Computation (22753) and Evolutionary Computation (02411) – Autumn term 2012

New: Facebook discussion group. Join here.

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:

• Introduce the main concepts, techniques and applications in the field of evolutionary computation.
• Give students some experience on when evolutionary techniques are useful, how to use them in practice and how to implement them with different programming languages.
• Apply knowledge learned in this module to solve a non-trivial problem (applies only to 22753).

Assessment

• Introduction to Evolutionary Computation (22753):
• Normal (sessional): 1.5 hr examination (80%) and course work (20%). Two assignments will be handed out, each worth 10%.
1. Assessment 1: [10%]
2. Assessment 2 data [10%]
• Resit (supplementary; where allowed): 1.5 hr examination (80%). The course work mark will be carried forward.
• Evolutionary Computation (02411):
• Normal (sessional): 1.5 hr examination (100%)
• Resit (supplementary; where allowed): As the normal assessment.
• BONUS CREDITS
• Competition on large scale global optimisation of continuous valued functions. Use benchmark functions given on the CEC’12 competition site or/and
  the CEC’08 competition site.
  You are encouraged to form teams and work together. Each team should attempt at least 3 test functions, preferably more.
  We will set aside one hour before the end of the term when each team can present their work. The presentation should include the methods that you used,
  the results obtained in the format set out by the competition instructions, and comparison to previous best results on the same functions.
  Based on the teams’ results and their presentation quality, the members of the best teams can get up to 5% bonus marks, and foremost valuable
  experience with the evolutionary techniques.

Lecture slides

- Overview of EC. Function optimisation examples

- Selection and Recombination Reading

- Fast Evolutionary Programming

- Tutorial exercises

More readings on function optimisation: here, here and here

- Constraint handling

- Tutorial questions

- Niching and Speciation: Fitness sharing & reading

- Crowding

- Intro to co-evolutionary learning

- Tutorial / Case study: The Prisoner’s Dilemma Game

- Multi-objective optimization (pages 1--21)

- Genetic programming

- Combinatorial optimisation & reading1 & reading2

the example is from the Hanbook by T. Baeck, D. B. Fogel, and Z. Michalewicz.

- Case Study on genetic programming

- Tutorial - comments and questions TSP exercise

- Evolving rule-based systems and neural networks; reading1 reading2

- Estimation of Distribution Algorithms (EDA)

- Intro to runtime analysis if evolutionary algorithms – guest lecture by Dr. Christine Zarges

- Further intro to the theory of EC

- Revision lecture

Additional related material (not covered in lectures)

- Sampling and MCMC methods; reading1; reading2; condensation page

-------------------------------------------------------------------------

Recommended Readings (optional)

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

• 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)

• 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)

• 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)

• 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)

• 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)

• 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/

• 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.

• 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)

• 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.

• 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

• 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

• 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.)

• 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.