Aalto University
CS-E4002 Special Course in Computer Science:
Genetic Algorithms

Credit: 3 units

Summer 2017: August 7 to August 18

Lectures: Mondays to Fridays at 900 - 1200

Location: T3

Helpful links

Genetic Algorithms Tutorials. A series of tutorials of different levels.
Genetic Algorithms in Plain English. An Introduction to Genetic Algorithms for beginners.
The GENITOR Research Group in Genetic Algorithms and Evolutionary Computation. A collection of tutorials and application articles on Evolutionary Algorithms.
Genetic Algorithms and Applications. Applications include decision making, finances, and robotics.
Introduction to Genetic Algorithms. An extensive introduction with interesting examples.
A Hypermidia Glossary of Genetic Terms. An extensive, searchable database of 670 terms in genetics.
A Genetic Programming Tutorial. An introduction to Genetic Programming.

Information about the Instructor

Name: Sami Khuri, visiting professor from San Jose State University
Office: B133
Phone: Please use email
Email: sami.khuri@sjsu.edu

Course Description

The course will introduce one of the evolutionary computation techniques: the genetic algorithm. The methodology of genetic algorithms will be described and the course will demonstrate various applications of these algorithms. More precisely, it will show how these probabilistic search algorithms, modeled after organic evolution, can be used to obtain good solutions when applied to NP-complete combinatorial optimization problems, such as the maximum-cut, the minimum tardy task, the set covering, the terminal assignment, scheduling problems and graph coloring problems. The course will then explore the application of genetic algorithms to the problems of Craniofacial Superimposition in Forensic Identification and feature selection in Rough Sets.
The course will also discuss the schemata theorem, its virtues and shortcomings. Walsh functions will also be introduced. They form a convenient basis for the expansion of fitness functions. These orthogonal, rectangular functions, have been used to compute the average fitness values of schemata. We will investigate the use of Haar functions for the same purpose, and compare them to Walsh functions.

Lecture Material and Schedule

Recommended Textbooks (Not required)

Genetic Algorithms in Search, Optimization, and Machine Learning by David E. Goldberg. Addison-Wesley Publishing Company, 1989.
Genetic Algorithms + Data Structures = Evolution Programs by Zbigniew Michalewicz Springer-Verlag, 1992.

A copy of my notes can be found here.
A copy of more applications of genetic algorithms can be found here here (6 slides per page) and here (2 slides per page) .

A selection of articles of interest to the course: (not finalized)

Genetic Algorithms
- Genetic Algorithms. Introduction to Simple Genetic Algorithm and Data Mining
- Fabian Theis. Lecture notes on Genetic Algorithms and Optimization.
- GECCO 2016. Conference Program of GECCO 2016.
- GECCO 2017. Accepted Papers of GECCO 2017.
- Gentic Programming. Introduction to Genetic Programming by John Koza.
Walsh and Haar Functions and Bases, and Deceptive Functions
- Haar 1994. Introductory paper on Haar Functions in GA.
- Walsh and Haar 1994. Comparison of Walsh and Haar Functions in GA.
- Kosters et al,. Fourier Analysis of Genetic Algorithms.
- Evelyne Lutton Genetic Algorithms and Fractals.
- David Goldberg Deception and its Analysis.
- Malcom Heywood Deception in Genetic Search.
More Applications of Genetic Algorithms
- Forensic Science: Sergio Damas et al,. Forensic Identification by Computer-Aided Craniofacial Superimposition.
- Fragment Assembly Problem: Kikuchi et al., 2006. Heuristically Tuned GA to Solve Genome Fragment Assembly Problem.
- Multiple Sequence Alignment: Naznin et al., 2011. Vertical decomposition with Genetic Algorithm for Multiple Sequence Alignment.
- Rough Sets: Jakob Wroblewski. Finding Minimal Reducts using Genetic Algorithm.
- Protein Structure Prediction: Benitez et al., 2010. Protein Structure Prediction with the 3D-HP Side-Chain Model using a Master-Slave Parallel Genetic Algorithm.
- Evolving Colors: Chubbyemu. Youtube example of using Genetic Algorithm to evolve and produce a certain color. (May 31, 2017)

Course Requirements

Problem Set: One homework assignment. No late homework will be accepted.
The homework is due in the beginning of the lecture, on Wednesday, August 16, 2017.
The two tables for problem 2 of the homework can be found here .
The document "koza_basic.ga" that contains more information on the hamburger restaurant problem (pages 14 to 46) for problem 2 of the homework can be found here .

Term Project

There will be a group project. Each group consists of two students. The group chooses a topic and writes a term-project. The term-project is due on Friday, September 15, 2017. Please email your work (in pdf) to sami.khuri@sjsu.edu with "Aalto Project" as subject.

Grading Policy

The final grade will be computed as shown below:

Assignment: 40%
Class Participation: 10%
Project: 50%

Aalto University CS-E4002 Special Course in Computer Science: Genetic Algorithms