Projet IN 104
Algorithme Génétique
Réalisé par
Mohamed ISSA Année universitaire
Mahdi CHEIKHROUHOU 2019/2020
1
Introduction au problème
Formalisation du problème
Structures de données
PLAN
Démarche de resolution
Autre démarche
2
Introduction au problème
Dans ce problème on se propose de déterminer à partir d’un ensemble
d’entiers relatifs donné en entrée, les sous-ensembles maximaux éventuels
dont la somme de leurs éléments (au signe prés) est nulle.
Exemple:
Soit l’ensemble suivant
Parmi les sous-ensembles maximaux de dont la somme de leurs éléments est
nulle sont :
dont les éléments sont respectivement affectés des signes .
dont les éléments sont respectivement affectés des signes .
3
Formalisation du problème
Afin de résoudre notre problème, on procède à la technique
d’optimisation de l’algorithme génétique.
Celui-ci est appliqué essentiellement aux théories d’évolution biologique.
4
Les étapes de
résolution:
Initialisation
Sélection
Reproduction
Croisement
Mutation
Terminaison
5
Structures de données
Pour modéliser notre problème, on va adopter les notations suivantes:
L’ensemble d’entiers relatifs donné: tableau dynamique d’entiers.
la taille du tableau : entier.
Individu: Struct d’éléments:
• DNA: tableau dynamique d’entiers (chromosome).
• Value: entier (valeur de la fonction fitness).
• nb: entier(taille du sous-ensemble).
• next: pointeur vers l’individu suivant.
:la génération(liste chaînée triée d’individus).
la taille de la génération: entier.
6
Démarche de résolution
L’attribut DNA d’un individu représente un codage ternaire. Chaque élément
de DNA est un entier de {0,1,2} tel que l’attribut vaut qui est le résultat de la
fonction fitness.
Pour résoudre le problème génétique on va chercher un individu dont la valeur
de l’attribut value est la plus adéquate (minimise la fonction fitness) .
7
Démarche de résolution
1. Initialisation
On génère dans cette partie la génération initiale aléatoirement à l’aide de la
fonction getInitialGeneration qui fait appel à la fonction getNewIndividu n fois.
8
Démarche de résolution
1er individu. 2e individu. 3e individu. 4e individu. 2. Sélection
Dans cettepartie on sélectionne les
10% parents à partir de la génération gen
donnéeen argument à la
fonctionaddChildGenenutilisant la
méthode de la roulette pour affecter à
20% 40% chaqueindividu de gen uneprobabilté
de sélection qui reflète son rang.
Cetteprobabilitéestdonnée pour
chaque rang i sous la forme:
30%
9
Démarche de résolution
3. Reproduction
A l’aide de la fonction addChildGen on effectue les
deux étapes:
a) Croisement
Aprés avoir sélectionner les paires des parents on
effectue les croisements à l’aide de la fonction
croisement entre eux pour fournir une nouvelle
génération Childgen.
b) Mutation
Cette étape consiste à altérer l’un des gènes de
certains individus et de les insérer à la génération
Childgen.
A l’issu de ce processus on fusionne les deux
générations et on choisit les n meilleurs individus à
l’aide de la fonction GetBestElements.
10
Démarche de résolution
4. Terminaison
Après avoir effectuer num_iteration itération le processus de sélection et de
reproduction. On obtient une génération finale gen dont la tête présente la solution
optimale de notre problème.
11
Autre démarche
La complexité de l’algorithme qu’on a proposé est de l’ordre de O(num_iteration*n²*l).
Une autre démarche consiste à utiliser une autre structure de donnée qui est le treap
De complexité inférieure de l’ordre de O(num_iteration*n*log(n)*l).
12
Merci pour votre attention !
13
