All programmes > Genetic Algorithms and Evolutionary Computing

Genetic Algorithms and Evolutionary Computing (B-KUL-H02D1A)

4 ECTSEnglish70 First termCannot be taken as part of an examination contract
Vannieuwenhoven Nick
POC Artificial Intelligence

Aims

The student understands, recognizes, can explain why, and can give examples of settings in which evolutionary algorithms are or are not a viable solution approach. They can pinpoint, explain, and analyze the strengths and weaknesses of evolutionary algorithms both in general and in specific problem instances.

The student can list, describe, explain, analyze, and implement in the Python programming language the common basic components of evolutionary algorithms (objective function, representation, selection operators, variation operators, and elimination operators). Additionally, they can propose, develop, and implement new problem-specific, adapted components as required in a specific application. The student can list, describe, explain, analyze, and implement in the Python programming language advanced components of evolutionary algorithms that represent some of its characteristic strengths such as diversity promotion mechanisms, multi-objective optimization, and local search operators. The student furthermore can describe, analyze, and reason about the interaction between the various common and advanced components of evolutionary algorithms. In particular, they can analyze and explain the role of the various hyperparameters that can influence the strength and nature of these interactions.

The student can design and implement in Python a full evolutionary algorithm pipeline well adapted to a specific problem. Moreover, the student can put their opinions, arguments, and reasoning about the aptness of an evolutionary algorithm design (i.e. the employed components and their interactions) into both convincing writing and oral communication.

The student can implement in the Python programming language a complete evolutionary algorithm pipeline, including objective function, representation, selection operators, variation operators, elimination operators, local search operators, diversity promotion mechanisms, and multi-objective optimization techniques from scratch. They can recognize, interpret, analyze, and resolve common problems arising in evolutionary algorithms, such as loss of diversity, misalignment of the selective pressure, misalignment of exploration versus exploitation, and computational bottlenecks.

Previous knowledge

Basic undergraduate courses in informatics (programming, algorithms, data structures) and mathematics (statistics, calculus). The following specific items are assumed to be known:

Informatics

  • Good programming skills in Python (or Julia)
  • Elementary data structures (arrays, lists, matrices)
  • Graphs (definition, basic graph algorithms like shortest path computation)
  • Elementary theoretical computer science (computational problems, P vs. NP) is a bonus

Calculus

  • Multivariate functions
  • Minimization and maximization
  • Partial and full derivatives
  • Gradients of multivariate functions

Statistics

  • Normal distribution
  • Random variables
  • Probability density function, cumulative density function
  • Mean, variance, standard deviation

Is included in these courses of study

Activities

1.8 ects. Genetic Algorithms and Evolutionary Computing: Lecture (B-KUL-H02D1a)

1.8 ECTSEnglishFormat: Lecture20 First term
Vannieuwenhoven Nick
POC Artificial Intelligence

Content

High-level contents and materials

  • Lecture 1: Introduction
  • Lecture 2: Problems, representation, and variation
  • Lecture 3: Population management
  • Online module 1: Local search operators 
  • Online module 2: Multiobjective optimization and diversity promotion
  • Online case study modules: Hands-on programming exercises

Detailed contents

Basics of evolutionary algorithms

  • Exploration versus exploitation
  • Computational and optimization problems
  • Objective function
  • Representation
  • Constraints
  • Variation operators
  • Selection and elimination operators
  • Hyperparameter self-adaptivity

Local search operators

  • Steepest descent
  • Monte Carlo sampling
  • k-opt

Multi-objective optimization and diversity promotion

  • Crowding
  • Island model
  • Fitness sharing
  • Scalarization (fixed tradeoff)
  • Pareto front

Course material

Study cost: 51-75 euros (The information about the study costs as stated here gives an indication and only represents the costs for purchasing new materials. There might be some electronic or second-hand copies available as well. You can use LIMO to check whether the textbook is available in the library. Any potential printing costs and optional course material are not included in this price.)

Slides, online videos, textbook (e-book).

0.6 ects. Genetic Algorithms and Evolutionary Computing: Exercises (B-KUL-H00H1a)

0.6 ECTSEnglishFormat: Practical10 First term
Vannieuwenhoven Nick
POC Artificial Intelligence

Content

The exercises consists of four guided sessions during which (most of) the group phase of the project is executed. For the group phase you will be assigned to balanced groups of 3-5 students. Attendance to the exercise sessions is mandatory, and non-participation results in a final mark of NA.

In the four exercise sessions, a basic evolutionary algorithm will be designed. The content of the sessions are:

  • Design of an elementary evolutionary algorithm
  • Computer implementation of an evolutionary algorithm in Python
  • Experimentation with the algorithm and reporting
  • Reading reports and providing peer feedback to other groups

1.6 ects. Genetic Algorithms and Evolutionary Computing: Project (B-KUL-H08M3a)

1.6 ECTSEnglishFormat: Assignment40 First term
Vannieuwenhoven Nick
POC Artificial Intelligence

Content

The students undertake a two-phase project. The first phase is a group work in which the students analyze a model problem and design, implement, and test an evolutionary algorithm in the Python programming language. This phase is concluded by a peer feedback assignment in which the students analyse one or more designs from other teams and provide feedback on them. The second phase is performed individually by each student, in which they analyze the results from their group phase, and based on the acquired insights, design, implement, and test improved variation and local search operators, selection mechanisms, diversity promotion schemes, among others. The students report the results of their analysis (results, computational performance, strengths and weaknesses, among others) via two reports, one for each phase. 

The reports will be discussed on the oral exam and, along with additional general questions, constitute the majority of the grade for this course. See the evaluation section for more details.

Evaluation

Evaluation: Genetic Algorithms and Evolutionary Computing (B-KUL-H22D1a)

Type : Partial or continuous assessment with (final) exam during the examination period
Description of evaluation : Oral, Participation during contact hours, Take-Home
Type of questions : Open questions
Learning material : None

Explanation


The evaluation is oral without written preparation. The exam consists of a short discussion of the project and open theoretical questions about the course with the project as potential case study.

The score of the exam is the sum of the score of the group phase of the project, the individual phase of the project, and the exam.

If the student fails to participate in one of the components of the project (exercises, peer feedback, individual programming, individual report), the outcome of the exam is NA.

Information about retaking exams

The retake exam consists of an updated project assignment for the take-home exam and an oral exam without written preparation. The setup of the exam and scoring is the same as in the first examination period, except that the group phase must be completed individually if its previous outcome was NA. The updated assignment will be uploaded after the closing of the second examination period to Toledo. The deadline of the project will be at least one week before the opening of the third examination period.

The score of the exam is determined according to the same modalities as in the first exam attempt.