UNIVERSITÉ MOHAMED CHERIF MESSAADIASOUK AHRAS
ALGORITHME GÉNÉTIQUE
Faculté Des SciencesDépartement :Math et Informatique
1ére Année Master : Génie Logiciel
Présenter Par: Daoudi Ilhem
Année Universitaire:2015-2016
LE PLAN: Historique.
1.L’algorithmes génétiques.
2.Principe.
3.L’algorithme.
4.Le codage.
5.Sélection.
6.Croisement.
7. Mutation.
8.Exemple.
9.Quelques applications.
1 0 –Références.
HISTORIQUE :
• Les algorithmes génétiques ont été inventés par Jonh Holland dans les
années 60.
• Repris notamment par Golberg dans les années 70, Le principe des
algorithmes génétiques s’inspire directement des lois de la sélection
naturelle, décrites par Darwin.
• cette technique connait aujourd’hui un franc succès. On l’utilise dans la
résolution de problèmes complexes, nécessitant des temps de calcul
élevés.
1.L’ALGORITHMES GÉNÉTIQUES:
• Les algorithmes génétiques sont des algorithmes d’optimisation s’appuyant
sur des techniques dérivées de la génétique et des mécanismes d’évolution de la
nature : croisements, mutations, sélections, etc... Ils appartiennent à la classe des
algorithmes évolutionnaires.
• Les applications des AG sont multiples : traitement d’image (alignement de
photos satellites, reconnaissance de suspects...), optimisation d’emplois du temps,
optimisation de design, apprentissage des réseaux de neurones [Renders, 1995],
etc.
2.PRINCIPE:
3.L’ALGORITHME:Un algorithme génétique générique à la forme suivante :
1) Initialiser la population initiale P.
2) Evaluer P.
3) Tant Que (K < > maxi) faire :
a) P ' = Sélection des Parents dans P
b) P ' = Appliquer Opérateur de Croisement sur P '
c) P ' = Appliquer Opérateur de Mutation sur P '
d) P = Remplacer les Anciens de P par leurs Descendants de P '
e) Evaluer P
FinTantQue
4.LE CODAGE :
• Dans l’informatique nous utilisons un codage binaire (0 et 1), par exemple un gène
est un entier long (32 bits).
• Les formules de codage et de décodage sont :
gi = (xi-ximin / ximax-xmin) gmax.
xi= ximin + (ximax-ximin) gi / gmax
5.SÉLECTION:
• Selon la qualité des individus, chacun se voit attribuer un pourcentage de chances
d’être choisi pour la reproduction, qui correspond à l’importance relative de la qualité
de l’individu par rapport à la qualité totale de la population.
5.SÉLECTION (SUITE):
• Il existe plusieurs méthodes de sélection :
• La méthode de roulette Wheel.
•La méthode élitiste .
•La sélection par tournois.
•La sélection universelle stochastique.
6.CROISEMENT :• e phénomène de croisement est une propriété naturelle de l’ADN, et c’est analogiquement
qu’on fait les opérations de croisement dans les AG.
• a- Croisement en un point : on choisit au hasard un point de croisement.
• b- Croisement en deux points : On choisit au hasard deux points de croisement .
7. MUTATION :
• Nous définissons une mutation comme étant l’inversion d’un bit dans un
chromosome . Cela revient à modifier aléatoirement la valeur d’un paramètre
du dispositif.
8.EXEMPLE:
9.QUELQUES APPLICATIONS :
• Prédiction de systèmes non-linéaires: bio / socio / météo / écono, etc.
• Conception, design et mise en oeuvre des réseaux neuronaux.
• Optimisation des trajectoires des robots.
• Traitement d'images, par exemple la re-synthèse des textures naturelles.
• conception et organisation des circuits électroniques.
10 -RÉFÉRENCES:
• http://wwwgremaq.univtlse1.fr/perso/cbontemps/Cours/AG/CoursOpti2.pdf
• http://slauncha.dyndns.org/index.php?article63/creation-d-un-algorithme-
genetique
• http://www.umc.edu.dz/buc/theses/electronique/TER4682.pdf
• http://produ.chez.com/badro/
• https://skyduino.wordpress.com/2015/07/16/tutorielpython-les-algorithmes-
genetiques-garantis-sans-ogm/
1111111111111111