- ARCHIVE for reference only

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Undergraduate Course: Genetic Algorithms and Genetic Programming (INFR09017)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Course typeStandard AvailabilityAvailable to all students
Credit level (Normal year taken)SCQF Level 9 (Year 3 Undergraduate) Credits10
Home subject areaInformatics Other subject areaNone
Course website Taught in Gaelic?No
Course descriptionThis 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.

In this module, you will learn about:

- The practicalities of GAs, GP and EC: how to design an appropriate evolutionary algorithm.
- Some of the underlying theory: how such algorithms work, and what is provable about them.
- Issues of experimental design: how to decide whether it works well.
- Current commercial applications.
- Current research directions.
Entry Requirements (not applicable to Visiting Students)
Pre-requisites Co-requisites
Prohibited Combinations Other requirements Successful completion of Year 2 of an Informatics Single or Combined Degree, or equivalent by permission of the School. The course will involve a modest amount of mathematics in a few places, mainly basic probability and a little statistics.
Additional Costs None
Information for Visiting Students
Displayed in Visiting Students Prospectus?Yes
Course Delivery Information
Delivery period: 2011/12 Semester 1, Available to all students (SV1) WebCT enabled:  No Quota:  0
Location Activity Description Weeks Monday Tuesday Wednesday Thursday Friday
CentralLecture1-11 15:00 - 15:50
CentralLecture1-11 15:00 - 15:50
First Class First class information not currently available
No Exam Information
Summary of Intended Learning Outcomes
1 - Understanding of evolutionary computation techniques and their broad applicability to a range of hard problems in search, optimisation and machine learning.
2 - To know when an evolutionary technique is applicable, which one to choose and how to evaluate the results.
3 - To know how to apply an evolutionary technique to a real problem and how to choose the parameters for optimal performance.
4 - Matching techniques with problems, evaluating results, tuning parameters, creating algorithms using inspiration from natural systems.
Assessment Information
Written Examination 75
Assessed Assignments 25
Oral Presentations 0

One practical exercise which usually involves programming in a language of your choice.

If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year.
Visiting Student Variant Assessment
Written Examination 75
Assessed Assignments 25
Oral Presentations 0

One practical exercise which usually involves programming in a language of your choice.
Special Arrangements
Additional Information
Academic description Not entered
Syllabus The lectures will cover the following subjects:

* The basics of biological evolution: Darwin, DNA, etc.
* The basics of GAs: selection, recombination and mutation. Choices of algorithm. The standard test functions. Fitness and objective functions.
* 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.
* Experimental issues: design and analysis of sets of experiments.
* The schema theorem and its flaws; selection takeover times; other approaches to providing a theoretical basis for studying GA issues.
* Rival methods: hill-climbing, simulated annealing, tabu search, etc. Hybrid/memetic algorithms.
* Multiple-solutions methods: crowding, niching; island and cellular models.
* Genetic programming: functions and terminals; parsimony; fitness issues.
* (If time) Evolving rules and rule-sets. Classifier systems. 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 such as engineering optimisation; scheduling and timetabling; data-mining; neural net design; etc.
* Some further ideas such as co-evolution; evolvable hardware; multi-level GAs.

Relevant QAA Computing Curriculum Sections: Artificial Intelligence, Developing Technologies, Intelligent Information Systems Technologies
Transferable skills Not entered
Reading list * [set book] Melanie Mitchell: An Introduction to Genetic Algorithms. MIT Press, 1996.
* Wolfgang Banzhaf, Peter Nordin, Robert E. Keller and Frank D. Francone: Genetic Programming: An Introduction. Morgan Kaufmann, 1988.
* Eric Bonabeau, Marco Dorigo and Guy Theraulez: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, 1999.
* L. N. de Castro: Fundamentals of Natural Computing: Basic Concepts, Algorithms, and Applications. Chapman & Hall/CRC, 2006
Study Abroad Not entered
Study Pattern Not entered
KeywordsNot entered
Course organiserDr Nigel Goddard
Tel: (0131 6)51 3091
Course secretaryMiss Tamise Totterdell
Tel: 0131 650 9970
Help & Information
Search DPTs and Courses
Degree Programmes
Browse DPTs
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Important Information
© Copyright 2011 The University of Edinburgh - 16 January 2012 6:16 am