Genetic Algorithms and Genetic Programming

Here are links to the course home page and the formal TQA description.

Description

This module teaches you about genetic algorithms (GAs), genetic programming (GP) and other such evolutionary computing (EC) ideas based on the idea of solving problems through simulated evolution. These techniques are useful for searching very large spaces. For example, they can be used to search huge parameter spaces in engineering design and spaces of possible schedules in scheduling. However, they can also be used to search for rules and rule sets, for data mining, for good feed-forward or recurrent neural nets and so on. The idea of evolving, rather than designing, algorithms and controllers is especially appealing in AI. The module will also introduce other biologically inspired algorithms, particularly Ant Colony Optimisation methods.

Syllabus

• Basics of biological evolution: Darwin, DNA, etc.
• Basics of GAs: selection, recombination and mutation. Choices of algorithm: (mu,lambda), (mu+lambda), steady-state, CHC, etc. Linkage and epistasis. The standard test functions. Fitness and objective functions: scaling, windowing etc.
• Representational issues: binary, integer and real-valued encodings; permutation-based encodings.
• Operator issues: different types of crossover and mutation, of selection and replacement. Inversion and other operators.
• Constraint satisfaction: penalty-function and other methods; repair and write-back; feasibility issues.
• Experimental issues: design and analysis of sets of experiments by t-tests, F-tests, bootstrap tests etc.
• Some theory: the schema theorem and its flaws; selection takeover times; optimal mutation rates; other approaches to providing a theoretical basis for studying GA issues.
• Rival methods: hill-climbing, simulated annealing, population-based incremental learning, tabu search, etc. Hybrid/memetic algorithms.
• Multiple-solutions methods: crowding, niching; island and cellular models.
• Multi-objective methods: Pareto optimisation; dominance selection; VEGA; COMOGA.
• Genetic programming: functions and terminals, S-expressions; parsimony; fitness issues; ADFs.
• Evolving rules and rule-sets. SAMUEL and related methods. Classifier systems: the Pittsburgh and Michigan approaches. Credit allocation: bucket-brigade and profit-sharing. Hierarchic classifier systems.
• Genetic planning: evolving plans, evolving heuristics, evolving planners, optimising plans.
• Ant Colony Optimization: Basic method for the TSP, local search, application to bin packing.
• Applications: engineering optimisation; scheduling and timetabling; data-mining; neural net design; etc.
• Some further ideas: co-evolution; evolvable hardware; multi-level GAs; polyploid GAs.

Assessed Coursework

There will be one assessed practical project.

References:

*** M. Mitchell: An Introduction to Genetic Algorithms. MIT Press, 1996.

* W. Banzhaf, P. Nordin, R. E. Keller, F. D. Francone: Genetic Programming: An Introduction. Morgan Kaufmann, 1988.

* E. Bonabeau, M. Dorigo, G. Theraulez: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, 1999.