This course introduces several computational methods that are based on principles of evolutionary biology. Common to these models is an element of natural selection ("survival of the fittest") that gives more fit individuals a higher probability of reproductive success. Depending upon the context, "individuals" can be anything from if-then rules to entire rule sets to problem solutions to simulated organisms. Evolutionary Computation (EC) provides a general methodology for stochastic parallel search that can be applied to a host of problem domains, such as task-scheduling, controller design, pattern recognition, robotics, immunology, economics and machine learning. In addition, EC techniques are commonly used in artificial life (alife), an exciting new interdisciplinary area with strong connections to biology, chemistry, mathematics, computer science and engineering.
We will focus on two popular EC methodologies: genetic algorithms (GA) and genetic programming (GP). The biological and mathematical theories behind GA and GP will be discussed, along with their implementations in Lisp. Students will gain considerable programming experience with GA's and GP's through both homeworks and a final project. Familiarity with Lisp is recommended.
An Introduction to Genetic Algorithms, by Melanie Mitchell (1996). This is available at Tapir for 250 NOK.
Additional research articles will be distributed during the course of the semester.
Anything in the lectures is fair game on the exam, as are pointers to topics in the reading material that the instructor views as relevant. In general, all important concepts (i.e. those that will appear on the exam) will be covered thoroughly in the lectures and/or homeworks. Students expecting to pass the class without coming to the lectures are either very intelligent or very foolish.
20 January : Homework #1 (Boolean satisfiability using GA) given out.
3 February: Homework # 1 due. Homework # 2 (Task scheduling using GA) given out.
17 February: Homework #2 due. Homework #3 (Cellular Automata using GA & GP) given out.
3 March: Homework #3 due. Homework #4 (Controller using GP) given out.
17 March: Homework #4 due.
27 - 29 April: Final project reports and demonstrations due
Final Exam date: May 19th, 1998
Three factors will used to determine a student's final grade:
Full credit, 100%, will be given to any homework assignment that works reasonably well and is delivered on time (before 12:15 on the due date). Late assignments incur a penalty of 25% per day. Group work on the actual coding of homeworks is permitted, but each student must deliver a copy of the code, some runs, and, most importantly, THEIR OWN description of what happened. Copying of these descriptions is not permitted and will result in no credit being given to all parties concerned (copier(s) and copiee).
The final projects will be done in groups of 1 to 3 students. These will be graded more strictly than the homeworks, with special focus on (a) the problem description, (b) the chromosomal representation, (c) the choice of EC parameters, (d) the simulation results, (e) a detailed analysis of the results, (f) a discussion of related work. Project reports will be delivered, and each group will have a demonstration/discussion session with the instructor, along with a shorter presentation to the class as a whole.
Possible project topics include applications of EC to more substantial engineering problems than those covered in the homeworks, such as advanced scheduling or controller design, pattern recognition, machine learning, etc. Other projects may use EC to model natural evolutionary phenomena such as speciation, food web formation, the Baldwin effect (an interaction between evolution and learning), etc. A third alternative is to use existing artificial-life software to investigate a particular evolutionary theory
The exam will cover all topics and methods presented in the lectures and/or covered by the homeworks. Material that is presented in class but not expected to be covered on the exam will be noted DURING THE LECTURE and probably nowhere else.
** A calculator (preferably one with statistical primitives like mean and standard-deviation) will be permitted for the final exam, but books and articles will NOT be permitted.