- ARCHIVE for reference only

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

Undergraduate Course: Natural Computing (INFR09038)

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 bio-inspired algorithms for optimisation and search problem. The algorithms are based on simulated evolution (including Genetic algorithms and Genetic programming), particle swarm optimisation, ant colony optimisation as well as systems made of membranes or biochemical reactions among molecules. 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. In a similar way it is tempting to use the intrinsic dynamics of real systems consisting e.g. of quadrillions of molecules to perform computations for us. The course includes technical discussions about the applicability and a number of practical applications of the algorithms.

In this module, students will learn about

- The practicalities of natural computing methods: How to design algorithms for particular classes of problems.

- Some of the underlying theory: How such algorithms work and what is provable about them.

- Issues of experimental design: How to decide whether an metaheuristic algorithm works well.

- Current commercial applications.

- Current research directions.
Entry Requirements (not applicable to Visiting Students)
Pre-requisites It is RECOMMENDED that students have passed ( Mathematics for Informatics 4a (MATH08044) AND Mathematics for Informatics 4b (MATH08045)) OR Informatics Research Proposal (INFR11071)
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 certain amount of mathematics in a some places, mainly basic probability and statistics.
Additional Costs None
Information for Visiting Students
Displayed in Visiting Students Prospectus?No
Course Delivery Information
Delivery period: 2011/12 Semester 1, Available to all students (SV1) WebCT enabled:  No Quota:  None
Location Activity Description Weeks Monday Tuesday Wednesday Thursday Friday
CentralLecture1-11 15:00 - 15:50
CentralLecture1-11 15:00 - 15:50
First Class Week 1, Tuesday, 15:00 - 15:50, Zone: Central. Bristo Sq 7 LT1
Exam Information
Exam Diet Paper Name Hours:Minutes
Main Exam Diet S2 (April/May)2:00
Resit Exam Diet (August)2:00
Delivery period: 2011/12 Semester 1, Part-year visiting students only (VV1) WebCT enabled:  No Quota:  None
Location Activity Description Weeks Monday Tuesday Wednesday Thursday Friday
CentralLecture1-11 15:00 - 15:50
CentralLecture1-11 15:00 - 15:50
First Class Week 1, Tuesday, 15:00 - 15:50, Zone: Central. Bristo Sq 7 LT1
Exam Information
Exam Diet Paper Name Hours:Minutes
Main Exam Diet S1 (December)2:00
Summary of Intended Learning Outcomes
- Understanding of natural computation techniques and their broad applicability to a range of hard problems in search, optimisation and machine learning.

- To know when a natural computing technique is applicable, which one to choose and how to evaluate the results.

- To know how to apply a natural computing technique to a real problem and how to choose the parameters for optimal performance.

- Matching techniques with problems, evaluating results, tuning parameters, creating algorithms using inspiration from natural systems.
Assessment Information
Written Examination 70 %;
Assessed Assignments 30 %


The coursework is comprised of two homework assignments. The first assignment will be a computational study of an application of a bio-inspired algorithm (it will be worth 10%), the second assignment is worth 20% of the course mark and will be a comparison of two or more algorithms on a different problem. A six-page report and a MatLab program are to be prepared for each assignment.
Special Arrangements
Additional Information
Academic description Not entered
Syllabus The lectures will cover the following subjects:

- Computational aspects of animal behaviour and of biological, chemical or physical systems.

- The basics of biological evolution: genes, selection, DNA, genetic drift, adaptation etc.

- The basics of GAs: selection, recombination and mutation. Fitness and objective functions

- Variants of GAs: different types of crossover and mutation, of selection and replacement. Inversion and other operators, crowding, niching, island and cellular models

- Some theory: the schema theorem and its flaws; selection takeover times; statistical mechanics approaches as a theoretical basis for studying GA issues

- Hybrid algorithms, memetic algorithms

- Pareto optimisation

- Genetic programming: Evolving programs, controlling complexity of the solutions, applications

- Ant Colony Optimisation: Basic method for the travelling salesperson problem, local search, application to bin packing, tuning, convergence issues and complexity.

- Swarm intelligence, particle swarms, differential evolution.

- DNA computing, molecular computing, membrane computing.

- Applications such as engineering optimisation; scheduling and timetabling; data-mining; neural net design.

- Comparisons among metaheuristic algorithms. Experimental issues: design and analysis of sets of experiments.
Transferable skills Not entered
Reading list - Melanie Mitchell: An Introduction to Genetic Algorithms. MIT Press, 1996.

- J. R. Koza: Genetic Programming: On the programming of computers by means of natural selection, MIT Press, 1992.

- 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

- G. Rozenberg, T. Bäck, J. N. Kok: Handbook of Natural Computing. Springer 2010 (to appear) [for reference only, don't think of buying it]
Study Abroad Not entered
Study Pattern Lectures: 20
Tutorials: 8
Non-timetabled assessed assignments: 24
Private Study/Other: 48
Total: 100
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