Saad Dahlab University (Blida 1)
Computer Science Department
Master 1 of Intelligent System Engineering
Metaheuristics and Evolutionary Algorithms
TD/TP N°2: Population based Metaheuristics: Genetic Algorithms
Exercise N 1:
Consider the simple genetic algorithm applied to a population of 8 integer numbers.
Suppose that at time t in the evolution the population has the following composition:
• x=1: 2 copies
• x=2: 3 copies
• x=3: 3 copies
Assuming that the fitness function is f (x) = x2, calculate the probability of selecting individuals.
x = 1, x = 2 and x = 3 using roulette selection
Exercise N 2:
Consider a population of simple individuals, with a single chromosome of length n =1000. Each entry
in the chromosome can take four values (A, C, G, T). Let's assume that the population size is equal to
M.
1) How many possible chromosomes are there ?
2) Assuming that the length of the chromosomes and the size of the population remain constant,
what is the upper bound of the number of different chromosomes assessed (evaluated) in G
generations?
3) If the population size is constant and is equal to 1012, what will be the total number of
chromosomes that will be evaluated over 109 generations, assuming that all the chromosomes
evaluated are different?
Exercise N 3:
We want to manufacture metal cylinders with a capacity of at least 300 litters and a minimum quantity
of metal. The quantity of metal necessary for the manufacture of a cylinder is equal to its surface and is
given by the formula. Its volume is given by the formula where h is the height of the cylinder and d is
the diameter of its section such that d and h are real numbers and 0 < 𝑑 ≤ 16 𝑒𝑡 0 < ℎ ≤ 16.
The purpose of this exercise is to determine the optimal values of the dimensions d and h which satisfy
these constraints and minimize the amount of metal.
1) Write the mathematical formulation of this problem as an optimization problem.
2) Explain the search space for this problem.
3) In order to solve this problem using a genetic algorithm, we code a solution by a couple of
reals (d, h).
4) Write the initialization algorithm for a population of m individuals and then compute its
complexity.
5) Write the crossover algorithm, which consists in permuting the heights of two successive
solutions of the population, and then compute its complexity.
FZ. Zahra
Exercise N 4:
A magic square of order n is a square matrix nxn containing the first n2 first integers from 1 to n2, such
that their sums on each row column and on each main diagonal are equal. The value S(n) of these sums
is then called the magic constant. It has been proven that for any integer n > 2, there is a magic square
of order n and that S(n)=(n+n3)/2
Example: for n=3; S(n)=15 (See the following figure)
Consider the problem: "Find a magic square of order n". Knowing that this problem is, in general, NP-
hard, we propose to solve it using a genetic algorithm.
1) Propose a coding for a solution to this problem (one individual from the population).
2) What is the size of the search space?
3) Write a procedure that generates an initial population of size K.
4) Write down the mathematical formulae that an optimal solution must satisfy.
5) Derive a fitness function to evaluate the solutions.
6) Propose a crossover operator and a mutation operator.
Exercise N 5:
Solve the traveling Salesman Problem using Genetic Algorithms:
1. Formulate the problem (Fitness Function, Solution representation, Reproduction operators, ...)
2. Implement the solution using python
Exercise N 6:
Solve the Knapsack Problem using Genetic Algorithms:
1. Formulate the problem (Fitness Function, Solution representation, Reproduction operators, …)
2. Implement the solution using python
FZ. Zahra
