Soutenance mémoire
Les Algorithmes Génétiques
Principe de base d’un AG standard
Un AG standard nécessite en premier le codage de l’ensemble des paramètres du problème d’optimisation en une chaîne de longueur finie. Le principe d’un AG est simple, il s’agit de simuler l’évolution d’une population d’individus jusqu’à un critère d’arrêt.On commence par générer une population initiale d’individus (solutions) de façon aléatoire. Puis, à chaque génération, des individus sont sélectionnés, cette sélection est effectuée à partir d’une fonction objectif appelée fonction d’adaptation (fitness) Puis, les opérateurs de croisement et de mutation sont appliqués et une nouvelle population est créée. Ce processus est itéré jusqu’à un critère d’arrêt. Le critère le plus couramment utilisé est le nombre maximal de générations que l’on désire effectuer.
L’AG débute par :
la génération d’une population initiale et l’évaluation de la fonction d’adaptation de tous les individus qui composent cette première population. Puis, des individus sont sélectionnés aléatoirement pour la reproduction selon le principe de la survie du plus adapté. Ensuite, des individus « enfants » (ou les descendants) sont générés en appliquant les deux opérateurs génétiques suivants : o le croisement o la mutation. Ces enfants sont placés dans une nouvelle population P(t) et vont se substituer, en tout ou en partie, à la population de la génération précédente. De nouvelles populations d’individus vont ensuite se succéder, d’une génération (t) à la génération (t+1), chaque génération représentant une itération jusqu’à l’atteinte du critère d’arrêt. L’AG présenté ci-dessus est dit générationnel car tous les individus enfants générés sont placés dans une population et vont remplacer entièrement la population des individus parents.
Codage
Chaque paramètre d’une solution est assimilé à un gène, toutes les valeurs qu’il peut prendre sont les allèles de ce gène, on doit trouver une manière de coder chaque allèle différent de façon unique (établir une bijection entre l’allèle « réel » et sa représentation codée).Un chromosome est une suite de gène, on peut par exemple choisir de regrouper les paramètres similaires dans un même chromosome (chromosome à un seul brin) et chaque gène sera repérable par sa position : son locus sur le chromosome en question.Chaque individu est représenté par un ensemble de chromosomes, et une population est un ensemble d’individus.Il y a trois principaux types de codage utilisables, et on peut passer de l’un à l’autre relativement facilement :
le codage binaire : c’est le plus utilisé. Chaque gène dispose du même alphabet binaire {0, 1}, un gène est alors représenté par un entier long (32 bits), les chromosomes qui sont des suites de gènes sont représentés par des tableaux de gènes et les individus de notre espace de recherche sont représentés par des tableaux de chromosomes.
Ce cas peut être généralisé à tout alphabet allélique n-aire permettant un codage plus intuitif, par exemple pour le problème du voyageur de commerce on peut préférer utiliser l’alphabet allélique {?1,?2,?3,…,??} où ci représente la ville de numéro i.
le codage réel : cela peut-être utile notamment dans le cas où l’on recherche le maximum d’une fonction réelle.
le codage de Gray Il existe de nombreuses méthodes pour la sélection, le croisement et la mutation.
Sélection
La sélection a pour objectif d’identifier les individus qui doivent se reproduire. Cet opérateur ne crée pas de nouveaux individus mais identifie les individus sur la base de leur fonction d’adaptation, les individus les mieux adaptés sont sélectionnés alors que les moins bien adaptés sont écartés [3].
La sélection doit favoriser les meilleurs éléments selon le critère à optimiser (minimiser ou maximiser). Ceci permet de donner aux individus dont la valeur est plus grande une probabilité plus élevée de contribuer à la génération suivante.
Il existe plusieurs méthodes de sélection, les plus connues étant la « roue de la fortune » et la « sélection par tournoi » :
o La « roue de la fortune » est la plus ancienne, où chaque individu, de la population de taille maximale ???? , occupe une section de la roue proportionnellement à sa fonction d’adaptation ???????( ?) , la probabilité de sélection d’un individu ( ? ) s’écrit :
Prob (j) = ???????( ?) ∑ ???????( ?) Jmax j=1
À chaque fois qu’un individu doit être sélectionné, un tirage à la loterie s’effectue et propose un candidat, les individus possédant une plus grande fonction d’adaptation ayant plus de chance d’être sélectionnés.
o A chaque fois qu’il faut sélectionner un individu, la « sélection par tournoi » consiste à tirer aléatoirement ( ? ) individus de la population, sans tenir compte de la valeur de leur fonction d’adaptation, et de choisir le meilleur individu parmi les ? individus. Le nombre d’individus sélectionnés a une influence sur la pression de sélection, lorsque ? = 2, la sélection est dite par « tournoi binaire».
Croisement
Le croisement permet de créer de nouvelles chaînes en échangeant de l’information entre deux chaînes. Le croisement s’effectue en deux étapes.
D’abord les nouveaux éléments produits par la reproduction sont appariés ensuite chaque paire de chaînes subit un croisement comme suit :
un entier ? représentant une position sur la chaîne est choisi aléatoirement entre 1 et la longueur de chaîne ( ? ) moins un (? −1).
Deux nouvelles chaînes sont créées en échangeant tous les caractères compris entre les positions ? +1 et ? inclusivement. L’exemple suivant montre deux chaînes (A1 et A2) de longueur ? = 5 appartenant à la population initiale. Les deux nouvelles chaînes (A3 et A4) appartenant à la nouvelle population sont obtenues par croisement à la position? = 4.
Il existe d’autres opérateurs de croisement :
Croisement en deux points : on choisit au hasard deux points de croisement et on échange les parties de chaîne situées entre ces deux points .
Croisement uniforme : dans ce type de croisement, on utilise un masque de croisement (mask), qui consiste en un vecteur généré aléatoirement, de longueur identique aux chaînes parents, et composé de 0 et 1. Lorsque le bit du masque vaut 0, l’enfant hérite le bit du premier parent, sinon il hérite de celui du second parent. Le second enfant est le complémentaire du premier. Ce croisement peut être considéré comme une généralisation du croisement multipoint sans connaissance préalable du point de croisement.
Mutation
La mutation est exécutée seulement sur une seule chaîne. Elle représente la modification aléatoire et occasionnelle de faible probabilité de la valeur d’un caractère de la chaîne, pour un codage binaire cela revient à changer un 1 en 0 et vice versa, Cet opérateur introduit de la diversité dans le processus de recherche des solutions et peut aider l’AG à ne pas stagner dans un optimum local
Paramètres d’un AG
Pour appliquer un AG à un problème réel, on doit posséder les éléments suivants :
1. Initialiser la population initiale P.
2. Evaluer P.
3. Tant Que (Pas Convergence) faire :
P ‘ = Sélection des Parents dans P
P ‘ = Appliquer Opérateur de Croisement sur P ‘
P ‘ = Appliquer Opérateur de Mutation sur P ‘
P = Remplacer les Anciens de P par leurs Descendants de P ‘
Evaluer P
Fin Tant Que Le critère de convergence peut être de nature diverse, par exemple :
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,
Une combinaison de ces deux points.
|
Guide du mémoire de fin d’études avec la catégorie Principe de base d’un AG standard |
|
Étudiant en université, dans une école supérieur ou d’ingénieur, et que vous cherchez des ressources pédagogiques entièrement gratuites, il est jamais trop tard pour commencer à apprendre et consulter une liste des projets proposées cette année, vous trouverez ici des centaines de rapports pfe spécialement conçu pour vous aider à rédiger votre rapport de stage, vous prouvez les télécharger librement en divers formats (DOC, RAR, PDF).. Tout ce que vous devez faire est de télécharger le pfe et ouvrir le fichier PDF ou DOC. Ce rapport complet, pour aider les autres étudiants dans leurs propres travaux, est classé dans la catégorie L’adaptation des algorithmes génétiques où vous pouvez trouver aussi quelques autres mémoires de fin d’études similaires.
|
Table des matières
Introduction
Chapitre 1 : Généralités sur la confection des tableaux de service des enseignants dans un établissement d’enseignement secondaire
Introduction
1. définition
2. Historique
3. Notions de base
4. Les contraintes
Conclusion
Chapitre 2 : Les Algorithmes Génétiques
Introduction
1. Algorithmes génétiques
Principe de base d’un AG standard
1.1. Codage
1.2. Sélection
1.3. Croisement
1.4. Mutation
2. Paramètres d’un AG
Conclusion
Chapitre 3 : formulation du problème de confection des tableaux de service des enseignants dans un lycée privé
Introduction
1. Position du problème
1.1. Définition
1.2. La vérification de la suffisance d’enseignants et des salles
2. Modélisation
2.1. Les données
2.2. Variables
2.3. Les contraintes
2.4. La fonction objective
3. Le Modèle Mathématique
Conclusion
Chapitre 4 : Application au problème d’un lycée privé
Introduction
1. Les données du lycée
2. Vérification de faisabilité du problème
3. L’adaptation des algorithmes génétiques
4. Programmation en langage C
4.1. Génération d’un individu
4.2. fonction d’adaptation
Conclusion
Conclusion générale et Perspectives
Bibliographie et web-graphie
Télécharger le rapport complet
