Genetic Algorithms

Teaching -> Genetic Algorithms

Duration: Approximately 30 lecture hours

                 

Prerequisites: Writing computer programs using a programming language (preferably Java or C++).

Course contents:

1. Lecture 01 - Brief introduction of optimization, Categories of optimization, Problems with classical optimization methods, Natural optimization methods, Properties of natural optimization methods, Biological optimization, Biological terms, Sexual reproduction

2. Lecture 02 - Darwin’s Theory of Evolution, Hardy-Weinberg Law, Introduction – Genetic Algorithms, Why GA rather than a traditional method?, Some Applications of Genetic Algorithms, Search Spaces, Enumerative Search

3. Lectures 03 & 04 - Genetic Algorithms: Natural Selection on a Computer, Analogy Between a Numerical GA and Biological Genetics, Binary Genetic Algorithms, Crossover Operator, Roulette Wheel Selection, Simulating: Roulette Wheel Selection, How Does the Crossover Operator Work?, What Does Mutation Represent? How Does the Mutation Operator Work?, An Example to explain the Binary Genetic Algorithms, crossover and mutation operators

4. Lecture 05 - Importance of Mutation, Performance Graph, Comparison of Biological and GA Terminology, Robustness, NP-Complete Problems, Heuristic Algorithms, Search Methods - Search for stored data, Search for paths to goals, Search for solutions, Common Steps of Search for Solutions

5. Lectures 06 & 07 - Case Study: Maintenance Scheduling, Why are scheduling problems so difficult?, Specify the problem, define constraints and optimum criteria, Represent the problem domain as a chromosome, Define a fitness function to evaluate the chromosome’s performance, Construct the genetic operators, Run the GA and tune its parameters

6. Lecture 08 - Why Genetic Algorithms Work - Schema, Instances, Order of schema, Schema Theorem, How about effects caused by crossover and mutation, What is the defining length of a schema?, Representation of non-integer unknowns, A question of accuracy, Multi-parameter Problems

7. Lecture 09 - Evolutionary Strategies (ES), How do we implement an ES?, What are differences between GA and ES?, Which method works best?, Genetic Programming (GP), LISP (List Processor), How do we apply GP to a problem?, Initial Population, Crossover operator, Mutation Operator, GP - Summary, GP Vs. GA

8. Lectures 10 & 11 - Evolutionary Neural Networks, Evolutionary Weight Optimization, Fitness Function, Crossover Operator, Mutation Operator, Evolutionary Optimal Topology, Encoding Network Architecture into a Chromosome, Travelling Salesman Problem (TSP), Applications of TSP, Different Techniques to Solve TSP, Encoding a Path, Crossover Operator, Mutation Operator, Fitness Function, Implementing the GA

9. Lecture 12 - Goals of Search Strategies, Encoding - Binary Encoding, Octal and Hexadecimal Encoding, Permutation Encoding (Real Number Coding), Value Encoding, Tree Encoding, Breeding, Selection - Roulette-Wheel Selection, Random Selection, Rank Selection, Tournament Selection, Stochastic Universal Sampling

10. Lectures 13 & 14 - Crossover Operator: Single Point Crossover, Two Point Crossover, Multi-Point Crossover (N-Point crossover), Uniform Crossover, Three Parent Crossover, Crossover with Reduced Surrogate, Shuffle Crossover, Replacement - Generational Updates and Steady State Updates

11. Lecture 15 -Multi-Objective Optimization using Evolutionary Algorithms

Objectives:

• To introduce the main concepts, techniques and applications in the field of Genetic Algorithms.
• To give students some practical experience on when Genetic Algorithms are useful, how to use them in practice and how to implement them on a computer.

Learning outcomes:

• Understand the relations between the Genetic Algorithms, other most important evolutionary algorithms (ES, GP, etc.), and other search and optimization techniques.
• Understand the implementation issues of Genetic Algorithms.
• Determine the appropriate parameter settings to make Genetic Algorithms work well.
• Design new operators, representations and fitness functions for specific practical and scientific applications.
• Apply evolutionary algorithms to multi-objective optimization problems.

Method of Assessments:

• Final Examination - 70%
• Continuous Assessments - 30%

Attendance:           

• Only those who satisfy the requirement of attendance (at least 80%) at lectures are allowed to sit the end of semester examination.

Recommended readings:  

• Genetic Algorithms in Search, Optimisation & Machine Learning, D E Goldberg, Addison-Wesley, 1989.
• An Introduction to Genetic Algorithms, Melanie Mitchell, The MIT Press, 1999.
• Artificial Intelligence - A Guide to Intelligent Systems (Second Edition), Michael Negnevitsky, Addison-Wesley, 2005
• An Introduction to Genetic Algorithms for Scientists and Engineers, David A. Coley, World SCientific
• Introduction to Genetic Algorithms, S.N. Sivanandam and S.N. Deepa, Springer 
• Multi-Objective Optimization using Evolutionary Algorithms, Kalyanmoy Deb, Wiley Student Edition