Devoir N°2 : Intelligence Artificielle

January 30, 2022

Réalisé par:
Oussama D ERAOUI

1 Question 1 (5pts)
Décrire en 30 lignes maximum le principe des algorithmes génétiques ? vous pour insert 4 images
au maximum (voir en bas comment l’image est inserée)
Votre description ici.
Le code de ce devoir s’appuie sur la mise en œuvre que nous avons vue lors de travaux pratiques
sur les algorithmes génétiques
Les algorithmes génétiques (ou GA) s’inspirent de l’évolution naturelle et sont particulièrement
utiles dans les problèmes d’optimisation et de recherche avec de grands espaces d’états. Avant
d’expliquer le principe de l’algorithme, on va d’abord introduire la terminologie qu’on va utilisé
dans tout le notebook.

• Les chromosomes sont des

chaînes d’ADN.
• L’élément de base des chromo-
somes est un gène.
• La position d’un gène sur le chro-
mosome est son locus.
• L’ensemble des gènes d’un indi-
vidu est son génotype.
• l’ensemble du patrimoine géné-
tique d’une espèce est le génome.
• Les différentes versions d’un
même gène sont appelées allèles

Le fonctionnement de tout AG peut être d’écrit par le principe illustrè par la figure ci-dessous:

1
• Un principe de codage des individus de la population : la qualité du codage des données
conditionnent le succès de l’algorithme.
• Un mécanisme de génération de la population initiale: Ce mécanisme doit être capable de
reproduire une population d’individus qui servira de base pour les générations futures. Le
choix de la population initiale est important car il influe sur la rapidité de trouver un opti-
mum.
• Définnir une fonction d’évaluation appelée généralement “Fitness”. Cette dernière a pour
objectif d’évaluer une solution et la comparer aux autres ;
• Choisissez les solutions par un mécanisme de sélection pour un éventuel couplage.
• Générer de nouvelles solutions à l’aide du croisement et de mutation. Si le taux de la muta-
tion est grand, la recherche devient purement aléatoire. S’il est faible la population est moins
diversifiée et en plus il y a risque de stagnation.
On peut arrêter le processus au bout d’un nombre arbitraire de générations ou lorsqu’une
solution possède une note suffisamment satisfaisante.

2
[1]: from math import cos, sin
from random import choices, choice, randint, randrange, shuffle, sample
from random import random as rnd
from typing import List, Optional, Callable, Tuple, Set
from copy import deepcopy
from statistics import mean, stdev
import statistics as st

from contextlib import contextmanager

import time
from functools import partial

import plotly.graph_objects as go
from [Link] import make_subplots
from [Link] import iplot
import [Link] as px

Genome = List[int]
Chromosome = List[int]
Population = List[Chromosome]
PopulateFunc = Callable[[], Population]
FitnessFunc = Callable[[Chromosome], int]
SelectionFunc = Callable[[Population, FitnessFunc], Tuple[Chromosome,␣
,→Chromosome]]

CrossoverFunc = Callable[[Chromosome, Chromosome], Tuple[Chromosome, Chromosome]]

MutationFunc = Callable[[Chromosome], Chromosome]
PrinterFunc = Callable[[Population, int, FitnessFunc], None]

def generate_chromosome(genome: Genome, length=None) -> Chromosome:

while True:
shuffle(genome)
if length is None:
return genome[:]
chromosome = []
while len(chromosome) <= length:
shuffle(genome)
chromosome += list(genome[:])
chromosome = chromosome[0:length]
#if admissible(chromosome):
return chromosome

# return choices(list(genome), k=len(genome) if length is None else length )

3
def generate_population(size: int, genome: Genome, length) -> Population:
population = []
while len(population) < size:
chrom = generate_chromosome(genome, length)
if chrom not in population:
[Link](chrom)
return population

def single_point_crossover(a: Chromosome, b: Chromosome) -> Tuple[Chromosome,␣

,→Chromosome]:

if len(a) != len(b):
raise ValueError("Chromosomes a and b must be of same length")
length = len(a)
if length < 2:
return a, b
p = randint(1, length - 1)
return a[0:p] + b[p:], b[0:p] + a[p:]

def mutation(chromosome: Chromosome, genome: Genome,

num: int = 1, probability: float = 0.5) -> Chromosome:
m_chromosome = deepcopy(chromosome)
for _ in range(num):
index = randrange(len(m_chromosome))
if rnd() < probability:
to_mut = m_chromosome[index]
[Link](to_mut)
m_chromosome[index] = choice(genome)
[Link](to_mut)
return m_chromosome

def population_fitness(population: Population, fitness_func: FitnessFunc) -> int:

return sum([fitness_func(chromosome) for chromosome in population])

def selection_pair(population: Population, fitness_func: FitnessFunc) ->␣

,→Population:

return choices(
population=population,
weights=[fitness_func(gene) for gene in population],
k=2
)

4
def sort_population(population: Population, fitness_func: FitnessFunc, maximize:␣
,→bool) -> Population:

return sorted(population, key=lambda Chromosome: fitness_func(Chromosome),␣

,→reverse=maximize)

def chromosome_to_string(chromosome: Chromosome) -> str:

return "".join(map(str, chromosome))

def print_statistics(population: Population, generation_id: int,

fitness_func: FitnessFunc, maximize: bool = False):
#print("GENERATION %02d" % generation_id)
#print("=================")
#print("Population: [%s]" % ", ".join([chromosome_to_string(gene) for gene␣
,→in population]))

fits = [fitness_func(gene) for gene in population]

#print(" Min %s" % min(fits))
#print(" Max %s" % max(fits))
#print(" Avg %s" % mean(fits))
#print(" Std %s" % stdev(fits))

fit = max(fits) if maximize else min(fits)

return fit, mean(fits)

def run_evolution(populate_func: PopulateFunc,

fitness_func: FitnessFunc, fitness_limit: int, maximize: bool␣
,→= False,

selection_func: SelectionFunc = selection_pair,

crossover_func: CrossoverFunc = single_point_crossover,
mutation_func: MutationFunc = mutation, generation_limit: int␣
,→= 100,

printer: Optional[PrinterFunc] = None) -> Tuple[Population,␣

,→int]:

population = populate_func()

population = sort_population(population, fitness_func, maximize)

i = 0
for i in range(generation_limit):
if printer is not None:
printer(population, i, fitness_func)
if maximize:
if fitness_func(population[0]) >= fitness_limit: break

5
 elif fitness_func(population[0]) <= fitness_limit:
break

next_generation = population[0:2]

for j in range(int(len(population) / 2) - 1):

parents = selection_func(population, fitness_func)
offspring_a, offspring_b = crossover_func(parents[0], parents[1])
offspring_a = mutation_func(offspring_a)
offspring_b = mutation_func(offspring_b)
next_generation += [offspring_a, offspring_b]

population = next_generation
population = sort_population(population, fitness_func, maximize)

if printer is not None:

print_statistics(population, i, fitness_func=fitness_func)
return population, i

@contextmanager
def timer():
start = [Link]()
yield
end = [Link]()
global elapsed_time
elapsed_time =(end - start)
print(f"Elapsed Time: {(end - start)}s")

2 Question 2 (3pts)
Dans ce problème, une fonction présentant plusieurs maxima locaux (ce qui rend inapplicables
les algorithmes les plus simples de recherche de maximum) est définie sur un certain intervalle et
le but est de déterminer à l’aide des algorithmes génétiques l’abscisse du maximum global (sur
l’intervalle) de la fonction. On va donc utiliser une population dans laquelle chaque individu
correspond à une abscisse située dans l’intervalle.
La fonction g( x ) = x2 cos(1/(10x ))sin( x/10)/10 à optimiser est présentée dans la figure suivante:

6
2.0.1 Remarque :
l’étude d’une fonction à une variable n’a pour but uniquement la démonstration pédagogique et il-
lustratif, puisque vous constaterez que le nombre total d’abscisses testées avant d’atteindre le max-
imum global (égal au nombre de générations multiplié par la taille de la population) est générale-
ment tel qu’on aurait un aussi bon résultat en répartissant simplement ce nombre d’abscisses
uniformément sur l’intervalle puis en cherchant Max(f(Xi)). L’intérêt des algorithmes génétiques
pour la recherche de maximum de fonction n’est en pratique réel que dans le cas d’une fonction à
beaucoup de variables, car alors toute exploration systématique de l’espace des n-uplets possibles
devient prohibitive, tandis qu’un algorithme génétique peut rester efficace. Malheureusement, la
visualisation de la recherche du maximum d’une fonction à n variables est problématique pour
n=2, et devient carrément impossible (ou en tout cas incompréhensible) pour n>=3. . .

2.0.2 Codage du Chromosome

Une des premières questions qui se posent est celle du codage : à quelle séquence de gènes faire
correspondre une abscisse de l’intervalle ? On peut faire le choix de prendre chaque gène égal à
un bit (donc le génome original est 01), et de faire correspondre à chaque chromosome (du type
10011100. . . ) l’abscisse x = xMin + N ∗ ( xMax − xMin)/Nmax où N est l’entier dont la représen-
tation binaire est donnée par le chromosome, et Nmax est le plus grand entier représentable avec
le nombre de bits correspondant à taille du chromosome. Il ne reste donc plus qu’à choisir le
nombre de bits constituant le génome de chaque individu. Nous nous intéressons à optimiser la
fonction g(x) dans l’intervalle I = [−255, 255].

7
 2.0.3 2.1) Que représentent xMin, et xMax.

[2]: xMin, xMax = -255, 255 # "Your Code Here"

2.0.4 2.2) Taille du chromosome

Si la taille du chromosome est n bits, donner Nmax en fonction de n (noté bien que pour 8 bits
=> Nmax=256), puis déduire le nombre minimal de bits (n_min) constituant le chromosome de
chaque individu pour pouvoir representer 8 individus entre chaque deux entiers de l’interval I
(Le nombre total d’individus representable est donc (xMax - xMin)*8).

[3]: #return the maximum integer to represent by n bits ()

def n_max(n) :
return 2**n - 1 #

#return the minimum nombre of bits to represent N

def n_bits(N):
return N.bit_length() - 1

n_min = n_bits((xMax - xMin)*8)

print("n_min=", n_min)
Nmax = n_max(n_min)

print('Nmax=', Nmax)

n_min= 11
Nmax= 2047

3 Question 3 (3pts)
MAXIMIZING g( x ) = x2 /10cos(1/(10x ))sin( x/10) USING GENETIC ALGORITHM

3.1) Ecrire la fonction genome_gx que retourne un genome composé de deux gènes 0 et 1
[4]: def genome_gx() -> Genome:
return [0,1]

3.2) En utilisant l’opérateur de décalage de bits +| ecrire la fonction qui convertie un chromo-
some (liste binaire) en entier.
[5]: def chromosome_to_integer(chromosome: Chromosome):
# using bit shift + | operator converting binary list to integer
n = 0
for i, b in enumerate(reversed(chromosome)):
n |= b << i
return n

8
 Genome=genome_gx()
chromosome=generate_chromosome(Genome, length=11)

print(chromosome_to_integer(chromosome))

1229

3.3) En utilisant la fonction précedente ecrire une fonction qui transforme un chromosome en
un individus x (abscisse) $x = xMin + N*(xMax - xMin)/Nmax $, ou N est l’entier représenté par
le chromosome.
[6]: def chromosome_to_x(chromosome: Chromosome):
return xMin + chromosome_to_integer(chromosome)*(xMax-xMin)/Nmax
print(chromosome_to_x(chromosome))

51.19931607230092

3.4) En utilisant la fonction précedente ecrire la fonction gx qui retourne l’évaluation d’un chro-
mosome par la fonction g( x ) = x2 cos(1/(10x ))sin( x/10)/10
[7]: from decimal import Decimal
def gx(chromosome: Chromosome):
x= chromosome_to_x(chromosome)
if x==0:
return 0
gx= x**2*cos(1/(10*x))*sin(x/10)/10
return gx
print(gx(chromosome))

-240.66688438720067

3.5) En utilisant le moteur de recherche de google (ecrire dans le champs de recherche

l’expression x*x cos(1/(10x))sin(x/10)/10 ) verifier que la valeur minimale de g dans l’intervale I
est −5555 et mettre le boolean à True si oui.
[8]: verified = True

3.6) Ecrire la fonction fitenss_gx qui retourne (gx(chromosone) + 5555)/100

[9]: def fitness_gx(chromosome: Chromosome):
# use the functions above
return (gx(chromosome) + 5555)/100
print(fitness_gx(chromosome))

48.62097767248808

3.7) Expliquer pourquoi nous avons ajouté 5555 à gx et pour quel raison nous avons divisé
par 100 On a ajouté 5555 pour éliminer toutes les valeurs négatives, et on a divisé par 100 pour
obtenir un pourcentage.

3.8) Quelle est la valeur max du fitness_gx (FITNESS_LIMIT ) si le max de g(x) dans I est 5555

9
[10]: FITNESS_LIMIT = 111 #

3.9) C’est le temps de tester l’agorithme genetique sur g(x)

[11]: POPULATION_SIZE = 4
MUTATION_RATE = 0.1
GENERATION_LIMIT = 100

[12]: def run_genetic():

with timer():
population, generations = run_evolution(
populate_func=partial(generate_population, size=POPULATION_SIZE,␣
,→genome=genome_gx(), length=n_bits(Nmax)),

fitness_func=fitness_gx, mutation_func=partial(mutation,␣
,→genome=genome_gx(), probability=MUTATION_RATE),

fitness_limit=FITNESS_LIMIT, crossover_func=single_point_crossover,
printer=print_statistics, maximize=True,
generation_limit=GENERATION_LIMIT)

fit_sol, avg_fit = print_statistics(population, generations,␣

,→fitness_func=fitness_gx, maximize=True)

print(f"Elapsed Time: {elapsed_time}s")

return chromosome_to_x(population[0]), fit_sol, avg_fit, generations,␣
,→elapsed_time

x, fitness, avg_fit, gen,t = run_genetic() #,t

print("x qui maximise g {:.2f}".format(x))
print("g( {:.2f} )= {:.2f}".format(x, (x * x * cos(1 / (10. * x)) * sin(x / 10.)␣
,→/ 10.)))

print("fitness de x : {:.2f}".format(fitness))
print("nombre de generations:", gen)
print("la moyen des fitness de la generation ", gen, " est {:.2f}".
,→format(avg_fit))

print("Le temps d'execution est {:.3f}".format(t))

Elapsed Time: 0.01995229721069336s

Elapsed Time: 0.01995229721069336s
x qui maximise g -234.57
g( -234.57 )= 5472.05
fitness de x : 110.27
nombre de generations: 99
la moyen des fitness de la generation 99 est 110.27
Le temps d'execution est 0.020

10
 4 Question 4 (3pts)
L’impact du nombre d’individus de la population sur la convergence: si celui-ci est trop petit,
il faut beaucoup plus de générations pour atteindre le maximum, car il n’y a pas assez de var-
iété dans la population initiale, et seules les mutations finissent par permettre à l’algorithme de
converger.
En suivant le schema suivant (Même principe utilié en devoir pour collecter et plotter des résul-
tats) :
Initialisez un Tableau des resultats (Results)
Pour POPULATION_SIZE allons de 2 jusqu’à 20 faire
pour i alons de 1 jusqu'à 100 faire
executez la fonction run_genetic()
les resultats sont collecter dans une liste

calculez les moyennes sur les 100 executions uiliser le module statistic vois plus haut
et sauvgardez les dans le Tableau Results
Tracer les courbes des resultats (fitness, avg_fitness, generations, temps) en fonction de POPULA-
TION_SIZE
Note: fitness et avg_fitness pouvent être tracées sur la même figure.
Commentez les courbes.

[16]: import pandas as pd

Results = []
Results_final = []
Index=[]
for y in range(2,21):
POPULATION_SIZE=y
for i in range(1,5):
[Link](run_genetic())
for j in Results:
[Link](j)
df = [Link](Index, columns=[ "x" , "fitness" , "avg_fitness",␣
,→"Generation" , "time"])

Results_final.append([[Link](df["fitness"]) , [Link](df["avg_fitness"]) ,␣
,→[Link](df["Generation"]), [Link](df["time"])])

df_mean = [Link](Results_final,columns= ["mean fitness", "mean␣

,→avg_fitness",

"mean generation" , "mean time"],␣

,→index=range(2,21))

print("End")

11
Elapsed Time: 0.00299072265625s
Elapsed Time: 0.00299072265625s
Elapsed Time: 0.0059854984283447266s
Elapsed Time: 0.0059854984283447266s
Elapsed Time: 0.003989458084106445s
Elapsed Time: 0.003989458084106445s
Elapsed Time: 0.00698089599609375s
Elapsed Time: 0.00698089599609375s
Elapsed Time: 0.005986690521240234s
Elapsed Time: 0.005986690521240234s
Elapsed Time: 0.005978584289550781s
Elapsed Time: 0.005978584289550781s
Elapsed Time: 0.006981611251831055s
Elapsed Time: 0.006981611251831055s
Elapsed Time: 0.005984067916870117s
Elapsed Time: 0.005984067916870117s
Elapsed Time: 0.010970115661621094s
Elapsed Time: 0.010970115661621094s
Elapsed Time: 0.012965202331542969s
Elapsed Time: 0.012965202331542969s
Elapsed Time: 0.015955209732055664s
Elapsed Time: 0.015955209732055664s
Elapsed Time: 0.01396322250366211s
Elapsed Time: 0.01396322250366211s
Elapsed Time: 0.0039882659912109375s
Elapsed Time: 0.0039882659912109375s
Elapsed Time: 0.008976459503173828s
Elapsed Time: 0.008976459503173828s
Elapsed Time: 0.007978200912475586s
Elapsed Time: 0.007978200912475586s
Elapsed Time: 0.00498652458190918s
Elapsed Time: 0.00498652458190918s
Elapsed Time: 0.022939205169677734s
Elapsed Time: 0.022939205169677734s
Elapsed Time: 0.0019943714141845703s
Elapsed Time: 0.0019943714141845703s
Elapsed Time: 0.020943164825439453s
Elapsed Time: 0.020943164825439453s
Elapsed Time: 0.013962745666503906s
Elapsed Time: 0.013962745666503906s
Elapsed Time: 0.015956878662109375s
Elapsed Time: 0.015956878662109375s
Elapsed Time: 0.020943880081176758s
Elapsed Time: 0.020943880081176758s
Elapsed Time: 0.012965917587280273s
Elapsed Time: 0.012965917587280273s
Elapsed Time: 0.018951892852783203s
Elapsed Time: 0.018951892852783203s

12
Elapsed Time: 0.0029909610748291016s
Elapsed Time: 0.0029909610748291016s
Elapsed Time: 0.02892279624938965s
Elapsed Time: 0.02892279624938965s
Elapsed Time: 0.025928974151611328s
Elapsed Time: 0.025928974151611328s
Elapsed Time: 0.0059854984283447266s
Elapsed Time: 0.0059854984283447266s
Elapsed Time: 0.001994609832763672s
Elapsed Time: 0.001994609832763672s
Elapsed Time: 0.01994490623474121s
Elapsed Time: 0.01994490623474121s
Elapsed Time: 0.020941495895385742s
Elapsed Time: 0.020941495895385742s
Elapsed Time: 0.0s
Elapsed Time: 0.0s
Elapsed Time: 0.03091716766357422s
Elapsed Time: 0.03091716766357422s
Elapsed Time: 0.026927471160888672s
Elapsed Time: 0.026927471160888672s
Elapsed Time: 0.0029921531677246094s
Elapsed Time: 0.0029921531677246094s
Elapsed Time: 0.028922557830810547s
Elapsed Time: 0.028922557830810547s
Elapsed Time: 0.02692699432373047s
Elapsed Time: 0.02692699432373047s
Elapsed Time: 0.0009982585906982422s
Elapsed Time: 0.0009982585906982422s
Elapsed Time: 0.0009970664978027344s
Elapsed Time: 0.0009970664978027344s
Elapsed Time: 0.04488015174865723s
Elapsed Time: 0.04488015174865723s
Elapsed Time: 0.007977485656738281s
Elapsed Time: 0.007977485656738281s
Elapsed Time: 0.001996755599975586s
Elapsed Time: 0.001996755599975586s
Elapsed Time: 0.012964248657226562s
Elapsed Time: 0.012964248657226562s
Elapsed Time: 0.04089069366455078s
Elapsed Time: 0.04089069366455078s
Elapsed Time: 0.003988742828369141s
Elapsed Time: 0.003988742828369141s
Elapsed Time: 0.001995086669921875s
Elapsed Time: 0.001995086669921875s
Elapsed Time: 0.003988742828369141s
Elapsed Time: 0.003988742828369141s
Elapsed Time: 0.04787111282348633s
Elapsed Time: 0.04787111282348633s

13
Elapsed Time: 0.0019943714141845703s
Elapsed Time: 0.0019943714141845703s
Elapsed Time: 0.005984067916870117s
Elapsed Time: 0.005984067916870117s
Elapsed Time: 0.0009961128234863281s
Elapsed Time: 0.0009961128234863281s
Elapsed Time: 0.058841705322265625s
Elapsed Time: 0.058841705322265625s
Elapsed Time: 0.05984044075012207s
Elapsed Time: 0.05984044075012207s
Elapsed Time: 0.05784416198730469s
Elapsed Time: 0.05784416198730469s
Elapsed Time: 0.012964725494384766s
Elapsed Time: 0.012964725494384766s
Elapsed Time: 0.003989696502685547s
Elapsed Time: 0.003989696502685547s
Elapsed Time: 0.008976459503173828s
Elapsed Time: 0.008976459503173828s
Elapsed Time: 0.005983114242553711s
Elapsed Time: 0.005983114242553711s
Elapsed Time: 0.014960765838623047s
Elapsed Time: 0.014960765838623047s
Elapsed Time: 0.01096963882446289s
Elapsed Time: 0.01096963882446289s
Elapsed Time: 0.007979154586791992s
Elapsed Time: 0.007979154586791992s
Elapsed Time: 0.06283140182495117s
Elapsed Time: 0.06283140182495117s
Elapsed Time: 0.007978439331054688s
Elapsed Time: 0.007978439331054688s
Elapsed Time: 0.08078384399414062s
Elapsed Time: 0.08078384399414062s
Elapsed Time: 0.052858591079711914s
Elapsed Time: 0.052858591079711914s
Elapsed Time: 0.000997781753540039s
Elapsed Time: 0.000997781753540039s
Elapsed Time: 0.000997304916381836s
Elapsed Time: 0.000997304916381836s
Elapsed Time: 0.005984067916870117s
Elapsed Time: 0.005984067916870117s
Elapsed Time: 0.09175372123718262s
Elapsed Time: 0.09175372123718262s
Elapsed Time: 0.09574484825134277s
Elapsed Time: 0.09574484825134277s
Elapsed Time: 0.013961553573608398s
Elapsed Time: 0.013961553573608398s
Elapsed Time: 0.00498652458190918s
Elapsed Time: 0.00498652458190918s

14
 Elapsed Time: 0.005983591079711914s
Elapsed Time: 0.005983591079711914s
Elapsed Time: 0.11369657516479492s
Elapsed Time: 0.11369657516479492s
Elapsed Time: 0.01994776725769043s
Elapsed Time: 0.01994776725769043s
Elapsed Time: 0.011967897415161133s
Elapsed Time: 0.011967897415161133s
End

[17]: df_mean.[Link]="Pop Size"

print("mean dataframe :")
print(df_mean)

mean dataframe :
mean fitness mean avg_fitness mean generation mean time
Pop Size
2 54.895750 52.855793 99.000000 0.004987
3 60.307310 57.157070 99.000000 0.005402
4 66.041996 63.096317 99.000000 0.006815
5 70.121757 66.715074 96.925000 0.007205
6 73.338866 69.612281 94.666667 0.007879
7 75.984487 71.890326 93.369048 0.008643
8 78.406342 74.101301 91.357143 0.009314
9 80.706288 75.981102 89.034722 0.009745
10 82.761761 77.876413 87.316667 0.010294
11 84.618929 79.483569 85.527273 0.010803
12 86.278316 80.922623 83.583333 0.011227
13 87.760365 82.147363 81.519231 0.011568
14 89.085903 83.133907 79.420330 0.011875
15 90.278762 84.028894 77.635714 0.012310
16 91.357598 84.721431 75.745833 0.012622
17 92.331259 85.349051 74.125000 0.013064
18 93.218252 85.795277 72.462418 0.013425
19 94.021910 86.234487 71.035088 0.013935
20 94.756118 86.658298 69.690789 0.014472

[18]: trace1 = [Link](

x=df_mean.index,
y=df_mean['mean fitness'],
name='Moyenne Fitness',
marker=dict(
color='rgb(34,163,192)'
)
)
trace2 = [Link](
x=df_mean.index,
y=df_mean['mean avg_fitness'],

15
 name='Moyenne avg_fitness',
yaxis='y2'

fig = make_subplots(specs=[[{"secondary_y": True}]])

fig.add_trace(trace1)
fig.add_trace(trace2,secondary_y=True)
fig['layout'].update(height = 600, width = 800, title = 'Fig1: Fitness et la␣
,→moyenne de fitness en fonction de la taille de population',xaxis=dict(

tickangle=-90
))
iplot(fig)

[19]: fig = [Link](df_mean, y="mean time", x=df_mean.index, title="Fig2: La moyenne␣

,→du temps en fonction de la taille de population")

[Link]()

16
 4.0.1 Conclusion
Fig1 : On remarque que la moyenne de Fitness est proportionnelle avec la moyenne de avg_fitness.
Lorsque la population augmente la moyenne de la fitness augmente (puisqu’on maximisime la
fonction) sans jamais dépasser la limite 111.
Fig2 : On remarque que le temps d’excecution augmente avec la taille de population. Car
l’algorithme génétique prends beaucoup plus de temps lorsque la population est grande.

5 Question 5 (3pts)
L’influence de la taille du chromosome : si elle est trop faible, l’algorithme est susceptible de se
bloquer dans un maximum local au lieu de converger vers le maximum global.
En suivant le même schema mais en fixant POPULATION_SIZE à la bonne valeur déduite de la
question précedente (le cas écheant utiliser POPULATION_SIZE=6), et en variant Nmax sur [16,
32, 64, 128, 255, 1024, 2047]
Tracer les courbes des resultats (fitness, avg_fitness, generations, temps) en fonction de
n_bits(Nmax)
Note: fitness et avg_fitness pouvent être ploté sur la même figure.
Commentez les courbes.

[20]: #Your code here

POPULATION_SIZE= 6
Results = []
Results_final = []
Index=[]
for Nmax in [16,32,64,128,255,1024,2047]:

17
 for i in range(1,5):
[Link](run_genetic())
for j in Results:
[Link](j)
df = [Link](Index, columns=[ "x" , "fitness" , "avg_fitness",␣
,→"Generation" , "time"])

Results_final.append([[Link](df["fitness"]) , [Link](df["avg_fitness"]) ,
[Link](df["Generation"]), [Link](df["time"])])

df_mean = [Link](Results_final,columns= ["mean fitness", "mean␣

,→avg_fitness",

"mean generation" , "mean␣

,→time"],index=[16,32,64,128,255,1024,2047])

df_mean.[Link] = "Nmax"

print(df_mean)

Elapsed Time: 0.022937536239624023s

Elapsed Time: 0.022937536239624023s
Elapsed Time: 0.020946502685546875s
Elapsed Time: 0.020946502685546875s
Elapsed Time: 0.0169525146484375s
Elapsed Time: 0.0169525146484375s
Elapsed Time: 0.012965679168701172s
Elapsed Time: 0.012965679168701172s
Elapsed Time: 0.01595759391784668s
Elapsed Time: 0.01595759391784668s
Elapsed Time: 0.016953706741333008s
Elapsed Time: 0.016953706741333008s
Elapsed Time: 0.013962268829345703s
Elapsed Time: 0.013962268829345703s
Elapsed Time: 0.01795172691345215s
Elapsed Time: 0.01795172691345215s
Elapsed Time: 0.018948793411254883s
Elapsed Time: 0.018948793411254883s
Elapsed Time: 0.01695561408996582s
Elapsed Time: 0.01695561408996582s
Elapsed Time: 0.016952037811279297s
Elapsed Time: 0.016952037811279297s
Elapsed Time: 0.01994609832763672s
Elapsed Time: 0.01994609832763672s
Elapsed Time: 0.01994633674621582s
Elapsed Time: 0.01994633674621582s
Elapsed Time: 0.013962507247924805s
Elapsed Time: 0.013962507247924805s
Elapsed Time: 0.01795172691345215s

18
 Elapsed Time: 0.01795172691345215s
Elapsed Time: 0.011968374252319336s
Elapsed Time: 0.011968374252319336s
Elapsed Time: 0.007979154586791992s
Elapsed Time: 0.007979154586791992s
Elapsed Time: 0.000997781753540039s
Elapsed Time: 0.000997781753540039s
Elapsed Time: 0.014959573745727539s
Elapsed Time: 0.014959573745727539s
Elapsed Time: 0.001995563507080078s
Elapsed Time: 0.001995563507080078s
Elapsed Time: 0.01894831657409668s
Elapsed Time: 0.01894831657409668s
Elapsed Time: 0.011967897415161133s
Elapsed Time: 0.011967897415161133s
Elapsed Time: 0.0s
Elapsed Time: 0.0s
Elapsed Time: 0.020944833755493164s
Elapsed Time: 0.020944833755493164s
Elapsed Time: 0.023934602737426758s
Elapsed Time: 0.023934602737426758s
Elapsed Time: 0.010970592498779297s
Elapsed Time: 0.010970592498779297s
Elapsed Time: 0.01196742057800293s
Elapsed Time: 0.01196742057800293s
Elapsed Time: 0.0189511775970459s
Elapsed Time: 0.0189511775970459s
mean fitness mean avg_fitness mean generation mean time
Nmax
16 69.830325 69.830325 99.000000 0.018451
32 80.874612 80.392371 99.000000 0.017702
64 86.139625 85.339304 99.000000 0.017661
128 89.824466 88.879246 99.000000 0.017478
255 92.713818 91.201567 95.433333 0.016672
1024 94.214850 92.136291 92.750000 0.016111
2047 95.576271 93.043151 90.830357 0.015824

[21]: p=[]
for i in [16,32,64,128,255,1024,2047]:
[Link](n_bits(i))

trace1 = [Link](
x=p,
y=df_mean['mean fitness'],
name='Moyenne Fitness',
marker=dict(
color='rgb(34,163,192)'

19
 )
)
trace2 = [Link](
x=p,
y=df_mean['mean avg_fitness'],
name='Moyenne avg_fitness',
yaxis='y2'

fig = make_subplots(specs=[[{"secondary_y": True}]])

fig.add_trace(trace1)
fig.add_trace(trace2,secondary_y=True)
fig['layout'].update(height = 600, width = 800, title = 'Fig1: Fitness et la␣
,→moyenne de fitness en fonction de la taille du chromosome',xaxis=dict(

tickangle=-90
))
iplot(fig)

[22]: fig = [Link](df_mean, y="mean time", x=df_mean.index, title="Fig2: La moyenne␣

,→du temps en fonction de la taille du chromosome")

[Link]()

20
 5.0.1 Conclusion
Fig1 : On remarque que la moyenne de Fitness est proportionnelle avec la moyenne de avg_fitness.
Lorsque la taille des chromosomes augmente la moyenne de la fitness augmente (puisqu’on max-
imisime la fonction) sans jamais dépasser la limite 111.
Fig2 : On remarque que le temps d’excecution varie avec la taille du chromosome. Car
l’algorithme génétique prends beaucoup plus de temps lorsque la taille du chromosome est
grande.

6 Question 6 (2pts)
MINIMIZING ( x ) = x2 /10cos(1/(10x ))sin( x/10) USING GENETIC ALGORITHM reécrire
les codes de la question 3 pour lancer un teste de minimization de g(x)

[23]: #Your code here

FITNESS_LIMIT = 0 #Cas de minimisation

def fitness_gx1(chromosome: Chromosome):

# use the functions above
return (gx(chromosome)+5555)/100
print(fitness_gx(chromosome))

48.62097767248808

[24]: def run_genetic():

with timer():
population, generations = run_evolution(
populate_func=partial(generate_population, size=POPULATION_SIZE,␣
,→genome=genome_gx(), length=n_bits(Nmax)),

21
 fitness_func=fitness_gx, mutation_func=partial(mutation,␣
,→ genome=genome_gx(), probability=MUTATION_RATE),
fitness_limit=FITNESS_LIMIT, crossover_func=single_point_crossover,
printer=print_statistics, maximize=False,
generation_limit=GENERATION_LIMIT)

fit_sol, avg_fit = print_statistics(population, generations,␣

,→fitness_func=fitness_gx1, maximize=False)

#print(f"Elapsed Time: {elapsed_time}s")

return chromosome_to_x(population[0]), fit_sol, avg_fit, generations,␣
,→elapsed_time

x, fitness, avg_fit, gen ,t= run_genetic()

print("x qui minimise g {:.2f}".format(x))
print("g( {:.2f} )= {:.2f}".format(x, (x * x * cos(1 / (10. * x)) * sin(x / 10.)␣
,→/ 10.)))

print("fitness de x : {:.2f}".format(fitness))
print("nombre de generations:", gen)
print("la moyen des fitness de la generation ", gen, " est {:.2f}".
,→format(avg_fit))

print("Le temps d'execution est {:.3f}".format(t))

Elapsed Time: 0.016956806182861328s

x qui minimise g -205.42
g( -205.42 )= -4188.55
fitness de x : 13.66
nombre de generations: 99
la moyen des fitness de la generation 99 est 56.46
Le temps d'execution est 0.017

22