26
1. Les Algorithmes Génétiques OUESSAI Abdessamed

1. Les Algorithmes Génétiques

Embed Size (px)

DESCRIPTION

1. Les Algorithmes Génétiques. OUESSAI Abdessamed. 1. Algorithmes Génétiques. 1.1 Généralités. Les algorithmes génétiques appartient a la famille des algorithmes évolutionnistes. Utilisent la notion de sélection naturelle sur une population de solutions potentielles. - PowerPoint PPT Presentation

Citation preview

Page 1: 1. Les Algorithmes Génétiques

1. Les Algorithmes GénétiquesOUESSAI Abdessamed

Page 2: 1. Les Algorithmes Génétiques

1. Algorithmes Génétiques

Les algorithmes génétiques appartient a la famille des algorithmes évolutionnistes.

Utilisent la notion de sélection naturelle sur une population de solutions potentielles.

Initialement introduit de manière formelle par John Holland [1975] puis vulgariser par Goldberg [1989].

1.1 Généralités

Page 3: 1. Les Algorithmes Génétiques

On simule l’évolution d’une population d’individus divers (Tirée aléatoirement au début).

On applique les différents opérateurs (croissement, mutations…) et on fait une sélection à chaque génération.

La population tend à s’améliorer, si la sélection s’opère à partir de la fonction d’adaptation.

L’algorithme ne nécessite aucune connaissance du problème.

1. Algorithmes Génétiques 1.1 Généralités

Page 4: 1. Les Algorithmes Génétiques

Evaluation

Sélection

Croisement et Mutation

Terminé ?

Population de Base

Non

Oui => Résultat atteint

Organigramme d’un algorithme génétique.

1. Algorithmes Génétiques 1.2 L’Algorithme

Page 5: 1. Les Algorithmes Génétiques

Pour utiliser les AG, on doit disposer des cinq éléments suivants:

Un principe de codage des éléments de la population

Un mécanisme de génération de la population initiale.

Une fonction à optimiser. Des opérateurs permettant de

diversifier la population. Des paramètres de dimensionnement.

1. Algorithmes Génétiques 1.2 L’Algorithme

Page 6: 1. Les Algorithmes Génétiques

Les chromosomes sont des chaînes d'ADN.

L'élément de base des chromosomes est un gène.

La position d'un gène sur le chromosome est son locus.

L'ensemble des gènes d'un individu 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.

1. Algorithmes Génétiques 1.3 Terminologie

Page 7: 1. Les Algorithmes Génétiques

Population

Individus

Chromosomes

Gènes

Bits

Les 5 niveaux d’organisation dans un AG

1. Algorithmes Génétiques 1.3 Terminologie

Page 8: 1. Les Algorithmes Génétiques

Chaque paramètre d'une solution est assimilé à un gène.

Les valeurs qu’il prend sont les allèles de ce gène.

On peut regrouper les paramètres similaire dans le même chromosome.

Chaque individu est représenté par un ensemble de chromosomes.

Une population est un ensemble d'individus. Il faut trouver une manière de coder chaque

allèle différent de façon unique.

1. Algorithmes Génétiques 1.4 Codage des Solutions (individus)

Page 9: 1. Les Algorithmes Génétiques

Codage Binaire Son principe est de coder la solution selon une

chaîne de bits (0 et 1) Exemple :

o un gène est codée sur 32 bit (entier long), o un chromosome est représenté par un

tableaux de gènes.o un individu est représenté par un tableau de

chromosomes.0 1 1 1 0 1 1 1 0 0

Un gène sur 10 bits

1. Algorithmes Génétiques 1.4 Codage des Solutions (individus)

Page 10: 1. Les Algorithmes Génétiques

Codage réel Chaque chromosome est représenté par une série

de valeurs quelconque, du contexte de problème.

Codage Gray En codage binaire deux éléments voisin (en

distance de Hamming) ne codent pas toujours deux solutions proche.

En codage gray, on évite cet inconvénient . La distance de Hamming entre deux éléments n et

n + 1 (voisins dans l’espace de recherche) est 1.

556 59.12 456 18.33 661

1. Algorithmes Génétiques 1.4 Codage des Solutions (individus)

Page 11: 1. Les Algorithmes Génétiques

La Sélection

Fondé sur la théorie de sélection naturelle. Elle définit quels seront les individus de P qui

vont être dupliqués dans la nouvelle population P‘.

les individus les plus aptes à répondre à certains critères seront sélectionnés.

Si n est le nombre d'individus de P, on doit en sélectionner n/2.

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 12: 1. Les Algorithmes Génétiques

Méthodes de Sélection Méthode de la "loterie biaisée" (roulette

Wheel) chaque individu a une chance d'être sélectionné

proportionnelle à sa performance. La Méthode élitiste

On trie de manière décroissante la population P selon la fitness de ses individus.

On prend les n meilleurs individus. La Sélection par Tournois

On effectue un tirage avec remise de deux individus de P, et on les fait "combattre".

Celui qui a la fitness la plus élevée l'emporte avec une probabilité p comprise entre 0.5 et 1, et on répètent n fois.

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 13: 1. Les Algorithmes Génétiques

Méthodes de Sélection

La Sélection Universelle Stochastique On prend l'image d'un segment découpé en

autant de sous-segments qu'il y a d'individus. Les individus sélectionnés sont désignés par

un ensemble de points équidistants.

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 14: 1. Les Algorithmes Génétiques

Le Croissement (Crossover)

Il consiste à combiner deux individus quelconques (dits parents) pour en ressortir deux autres individus (dits enfants).

On coupent en un ou plusieurs points deux individus (aux mêmes endroits dans les deux individus) et on échangent les parties situées entre ces points.

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 15: 1. Les Algorithmes Génétiques

Types de Croisement

Croisement en un point on choisit au hasard un point de croisement,

pour chaque couple (le croissement s’effectue au niveau binaire).

Exemple:

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 16: 1. Les Algorithmes Génétiques

Types de Croisement

Croisement en deux points On choisit au hasard deux points de croisement. Exemple:

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 17: 1. Les Algorithmes Génétiques

Types de Croisement

Croisement Uniforme On définit un « Masque » de manière aléatoire,

de même longueur que les chromosomes parents.

Pour un locus, si le locus du masque est 0 il hérite du parent 1, si 1 il hérite du parent 2, et de manière symétrique pour le deuxième fils.

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 18: 1. Les Algorithmes Génétiques

Types de Croisement

Croisement Uniforme

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 19: 1. Les Algorithmes Génétiques

La Mutation

La modification aléatoire d’un paramètre du dispositif (l’inversion d’un bit dans un chromosome).

Les mutations empêchent l’évolution de se figer. Probabilité de mutation pm est très faible,

comprise entre 0.01 et 0.001.

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 20: 1. Les Algorithmes Génétiques

Le Remplacement Réintroduit les descendants (P’) obtenus par

application successive des opérateurs génétiques précédents, dans la population de leurs parents (P).

Méthodes de remplacement Le remplacement stationnaire

les enfants remplacent automatiquement les parents sans tenir compte de leurs performances respectives.

Le remplacement élitiste on garde au moins l'individu possédant les

meilleures performances d'une génération à la suivante.

1. Algorithmes Génétiques 1.5 Les Operateurs Génétiques

Page 21: 1. Les Algorithmes Génétiques

La Taille de la population

Si elle est grande La diversité augmente. La convergence vers un optimum local diminue.

Si elle est petite La probabilité de s’attarder. sur des minima

locaux est grande. Selon le cas, elle est entre 25 et 100.

1. Algorithmes Génétiques 1.6 Les Paramètres d’un AG

Page 22: 1. Les Algorithmes Génétiques

Le Taux de Croisement L’opérateur de croisement est appliqué avec une

probabilité Pc.

Plus le taux est élevé plus de nouveau individus sont introduits.

En général, Pc varie entre 0.25 et 0.70.

Le Taux de Mutation L’opérateur de mutation est appliqué avec une

probabilité Pm. Si ce taux 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.

1. Algorithmes Génétiques 1.6 Les Paramètres d’un AG

Page 23: 1. Les Algorithmes Génétiques

Le Fossé des Générations (Generation Gap) C’est l’écart entre les générations, un nombre

compris entre 0 et 1. Le rapport entre le nombre de nouveaux individus

introduit dans P, et le nombre d’individus de P. S’il est égal a 1, l’ensemble de population est

remplacé.

Critère d’Arrêt Un taux minimum qu'on désire atteindre

d'adaptation de la population au problème. Un certain temps de calcul à ne pas dépasser.

1. Algorithmes Génétiques 1.6 Les Paramètres d’un AG

Page 24: 1. Les Algorithmes Génétiques

1. Algorithmes Génétiques 1.7 Exemple (TSP)

Pour un TSP de taille on à : Les individus : des permutations de

On utilise le codage réel Ex : Indiv1

La fonction à optimiser :

permutation.matrice d’incidence.

Après la sélection, on applique les operateurs de croissement et de mutation.

Mutation :

On applique l’algorithme pour un nombre fini

d’itération.

Page 25: 1. Les Algorithmes Génétiques

Nécessite beaucoup de temps de calcul. Ils sont le plus souvent difficiles à mettre

en œuvre . Impossible d'être assuré que la solution

trouvée est la meilleure. Problème de convergence vers un

optimum local, si celui si est le plus majoritaire.

1. Algorithmes Génétiques 1.8 Inconvénients

Page 26: 1. Les Algorithmes Génétiques

1. fr.wikipedia.org2. Algorithmes Génétiques - Souquet Amédée &

Radet François-Gérard / TE de fin d’année 20043. http://magnin.plil.net/ Vincent MAGNIN –

Méthodes de L’AG – Internet – 20104. LES ALGORITHMES GENETIQUES

APPLICATION A LA SEGMENTATION DES IMAGES - LASSOUAOUI Nadia, HAMAMI Latifa, NOUALI Nadia Centre de Recherche sur l’Information Scientifique et Technique / Ecole Nationale Polytechnique, Laboratoire Signal & Communications, Alger - 2004

1. Algorithmes Génétiques 1.9 Bibliographie