View
119
Download
1
Category
Preview:
Citation preview
Réalisé par:Réalisé par: * Boudjit Nabil * Boudjit Nabil * Belhadje Amina * Belhadje Amina * Haoues Hakim * Haoues Hakim * Malki Rima* Malki Rima
Proposer par:Mr:A.K.Boukabou
*REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET *REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE*POPULAIRE* *Ministère de l’Enseignement et de la Recherche *Ministère de l’Enseignement et de la Recherche ScientifiqueScientifique * *Université Abdelhak Benhamouda de JIJEL**Université Abdelhak Benhamouda de JIJEL*
Commande par algorithme génétiqueCommande par algorithme génétiqueCommande par algorithme génétiqueCommande par algorithme génétique
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
IntroductionIntroduction Les AG sont des algorithmes :Les AG sont des algorithmes :De recherche d’optimisation globale De recherche d’optimisation globale
aléatoire inspirés de la nature .aléatoire inspirés de la nature .Codant les individus dans un espace Codant les individus dans un espace
de recherche .de recherche .Les AG nécessitent pas une parfaite Les AG nécessitent pas une parfaite
compréhension du problème posé.compréhension du problème posé.
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
Le but des AG est de retrouver Le but des AG est de retrouver
l’extremum d’une fonction l’extremum d’une fonction (évaluation ou fitness) , qui (évaluation ou fitness) , qui transforme les individus depuis un transforme les individus depuis un espace de recherche X vers R.espace de recherche X vers R.
Le ButLe But
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
Historique Historique 1860 >Charles Darwin et l’origine des 1860 >Charles Darwin et l’origine des
espèces.espèces.19 19 èmeème siècle > Mise en évidence de siècle > Mise en évidence de
l'existence. de mutations génétiques.l'existence. de mutations génétiques. 1966 >Programmation évolutionnaire 1966 >Programmation évolutionnaire
(Fogel).(Fogel).1975 >11975 >1erer modèle formel de AG (J.Holland). modèle formel de AG (J.Holland).Années 90 >Création de GAlib. Librairie en Années 90 >Création de GAlib. Librairie en
C++contenant des outils pour les C++contenant des outils pour les problèmes d’optimisation à base d’AG.problèmes d’optimisation à base d’AG.
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
ApplicationApplication Applications des AG :Applications des AG :Recherche d’extremum de fonctions Recherche d’extremum de fonctions
multi variables.multi variables.Prévision des marchés boursier.Prévision des marchés boursier.Simulation de certains modèles Simulation de certains modèles
physiques.physiques.Ordonnancement des systèmes de Ordonnancement des systèmes de
production.production.Programmation des robots Programmation des robots
d’assemblage.d’assemblage. Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
PrincipesPrincipes
Codage >Codage > Population Population ((∑∑d’individus)d’individus)
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
oCodage >Codage > Individu (Individu (∑∑de de chromosomes)chromosomes)
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
oCodageCodage > > ChromosomesChromosomes ( (∑∑de de gènes)gènes)
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
oCodage > Codage > ((GènesGènes = = ∑∑ Bits) Bits)
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
oFonction de fitness Fonction de fitness (évaluation) :(évaluation) :
Fonction qui détermine la Fonction qui détermine la qualité d’un individu notée f .qualité d’un individu notée f .
Pour n individus :Pour n individus :
avec i avec i de 1 à n . de 1 à n .
La probabilité de chaque individu La probabilité de chaque individu
F = ∑ f(xi)
P(xi) = f(xi) / F
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
SélectionSélection Il y’ a plusieurs méthodes de Il y’ a plusieurs méthodes de
sélection ,sélection ,
citons quelques-unes :citons quelques-unes :
Roulette de casino .Roulette de casino . N/2 – élitisme.N/2 – élitisme.
Par tournoi .Par tournoi .
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
oSélection:Sélection:Méthode de la Méthode de la Roulette de casino Roulette de casino
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
CroisementCroisement >>
Croisement binaireCroisement binaire Croisement réelCroisement réel
Croisement Croisement arithmétique arithmétique
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
CroisementCroisement > > ( croisement ( croisement binaire )binaire )
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
Mutation :Mutation :
Nous définissons une mutation Nous définissons une mutation comme étant l’inversion d’un bit comme étant l’inversion d’un bit dans un chromosome . Cela dans un chromosome . Cela revient à modifier aléatoirement la revient à modifier aléatoirement la valeur d’un paramètre du valeur d’un paramètre du dispositifdispositif . .
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
o Les méthodes de mutationLes méthodes de mutation Il y’ a plusieurs méthodes deIl y’ a plusieurs méthodes de
mutation , mutation ,
citons quelques-unes citons quelques-unes Mutation binaireMutation binaire . .
Mutation non uniformeMutation non uniforme . .
Mutation réelle Mutation réelle . .
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
oMutation Mutation >>
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
EXEMPLE EXEMPLE
Utilisation de l’age dans un algorithme génétique: Nous construisons un algorithme génétique binaire qui permet de sélectionner des individus en utilisant l’âge.
Ainsi nous souhaitons modifier une population initiale en prenant en compte le génotype des individus et leur âge, qui n’a pas de lien direct avec le génotype. Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Objectifs et paramètres :Objectifs et paramètres : L’évaluation d’ une population L’évaluation d’ une population
d’individus, et suivant une fonction d’individus, et suivant une fonction unidimensionnelle : f_eval.unidimensionnelle : f_eval.
Nous souhaitons obtenir un Nous souhaitons obtenir un ensemble de chromosomes ou ensemble de chromosomes ou individus qui minimise la fonction individus qui minimise la fonction d’évaluation f_eval. d’évaluation f_eval.
Les Npop chromosomes qui ont Les Npop chromosomes qui ont tous le même nombre de bitstous le même nombre de bits. .
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
ÉvaluationÉvaluation : : L’évaluation L’évaluation f_evalf_eval qui dépend de 2 qui dépend de 2 paramètres indépendants.paramètres indépendants.
Le 1er est évaluation et il dépend uniquement Le 1er est évaluation et il dépend uniquement du génotype de l’individu X=[x1 x2]du génotype de l’individu X=[x1 x2]
évaluation=20+x1×sin((2×pi/3)×x1))+x2×sin(4×pi×2)évaluation=20+x1×sin((2×pi/3)×x1))+x2×sin(4×pi×2)
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Le 2Le 2èmeème Prob_selec dépend Prob_selec dépend uniquement de l’âge. uniquement de l’âge.
Pc ( j ) =age ( j ) / ∑ Pc ( j ) =age ( j ) / ∑ age ( i )age ( i )
F_eval(x) = coeff. * évaluation(x) + F_eval(x) = coeff. * évaluation(x) + (1-coeff) * Pc(x)(1-coeff) * Pc(x)
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Population initiale:Population initiale:
La population initiale est La population initiale est composé de Npop individus du composé de Npop individus du même âge : 1 an. Ils entrent dans même âge : 1 an. Ils entrent dans la boucle (sélection croisement la boucle (sélection croisement mutation ). Les individus sont mutation ). Les individus sont codés en binaire. Leurs bits sont codés en binaire. Leurs bits sont groupés tel que le montre le groupés tel que le montre le vecteur bit .vecteur bit .
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Sélection:Sélection: deux critères :deux critères :
11erer leur évaluation par la fonction leur évaluation par la fonction évaluation. évaluation.
22èmeème leur âge qui se trouve dans leur âge qui se trouve dans un tableau ageun tableau age..
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Croisement :Croisement : Le croisement s’opère en 2 étapes :Le croisement s’opère en 2 étapes : 11erer sélection de couples de sélection de couples de
reproducteurs qui deviendront parents.reproducteurs qui deviendront parents.22èmeème croisement des parents et croisement des parents et
formation de 2 enfants par couple.formation de 2 enfants par couple.
Nous obtenons une population Nous obtenons une population intermédiaire.intermédiaire.
L’âge des parents est augmenté de 1. Et L’âge des parents est augmenté de 1. Et celui des celui des
enfants est de 1 an.enfants est de 1 an.
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Mutation :Mutation :
Nous effectuons une mutation Nous effectuons une mutation
sur les individus. Cette mutation sur les individus. Cette mutation affecte tous les individus de la affecte tous les individus de la même manière. Nous pourrions même manière. Nous pourrions choisir de faire en sorte qu’elle choisir de faire en sorte qu’elle dépendent de l’âge.dépendent de l’âge.
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Test de convergence :Test de convergence :
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Résultat :Résultat :
Figure.1: Création de la population initiale
Figure.1: Création de la population initiale
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Figure.2: Affichage de la population final
Figure.2: Affichage de la population final
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Figure.3: La moyenne des individus Figure.3: La moyenne des individus
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Figure.4: Teste de la convergenceFigure.4: Teste de la convergence
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Conclusion :Conclusion :
Nous avons réalisé un AG Nous avons réalisé un AG faisant intervenir l’âge des faisant intervenir l’âge des individus. L’âge n’intervient que individus. L’âge n’intervient que dans les phases de sélection mais dans les phases de sélection mais on pourrait le faire intervenir on pourrait le faire intervenir dans les phases de mutation et de dans les phases de mutation et de croisement.croisement.
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
Difficile de trouvée un bon codage Difficile de trouvée un bon codage adaptée à la structure du problème.adaptée à la structure du problème.
L’application de la fonction de L’application de la fonction de décodage lords l’évaluation de la décodage lords l’évaluation de la fitness est coûteuse en temps de fitness est coûteuse en temps de calcul. calcul.
Les opérateurs de croisement et Les opérateurs de croisement et mutation ne tiennent aucun mutation ne tiennent aucun compte de la structure du problème.compte de la structure du problème.
Les problèmes de Les problèmes de AG :AG :
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
Conclusion Générale Conclusion Générale Les AG sont excellent pour la Les AG sont excellent pour la
rechercherecherche de solutions approximatives de de solutions approximatives de
certains problèmes difficilement certains problèmes difficilement modélisable.Comme ils ne remplaceront modélisable.Comme ils ne remplaceront jamais le programme déterministe qui jamais le programme déterministe qui permettrai de trouver la solution;ils permettrai de trouver la solution;ils faut un nombre important et un bon faut un nombre important et un bon paramétrage de l’AG pour garantir une paramétrage de l’AG pour garantir une bonne solution. bonne solution.
Université de JIJEL – Module : Tec 464 – FEVRIER 2007Université de JIJEL – Module : Tec 464 – FEVRIER 2007
Les problèmes AGLes problèmes AG
ExempleExemple d’application d’application
SélectionSélectionCroisementCroisementCodageCodage
ConclusionConclusion
PrincipePrincipe
MutationMutation
IntroductionIntroduction
ButButHistoriqueHistorique
ApplicationApplication
Plan de travaillePlan de travaillePlan de travaillePlan de travaille
MERCI MERCI POUR POUR VOTRE VOTRE
ATTENTIOATTENTIONN
Recommended