Soutenance mémoire
Illustration du modèle organisationnel d’AMF
ALGORITHMES EVOLUTIONNISTES
Le principe des algorithmes évolutionnistes est de faire évoluer une population d’individus (solutions) en appliquant des procédures de croisement, de mutation et de sélection. Chaque nouvelle génération d’individus est obtenue en croisant et mutant les individus de la génération courante, puis en appliquant une sélection sur la population composée des nouveaux et des anciens individus. Au début de la recherche, quand les solutions sont plutôt différentes, le croisement a un rôle d’exploration, car la combinaison des solutions produit des solutions placées aux endroits non encore visités pendant la recherche. Par contre, à la fin de la recherche, les parents sont similaires, ce qui produit des enfants similaires, accordant au croisement un rôle plutôt d’intensification (ou d’exploitation). Pratiquement, en recombinant des individus, l’enfant peut être potentiellement infaisable. Après le croisement, un opérateur de mutation est appliqué au sein de la population des enfants avec une probabilité, nommée taux de mutation. Cet opérateur joue le rôle d’un (élément perturbateur). Il introduit du (bruit). Il permet ainsi de maintenir la diversité de la population des enfants et d’explorer l’espace de recherche en évitant à l’algorithme de converger trop rapidement vers un optimum local. Pour cela dans les algorithmes évolutionnistes, l’intensification et la diversification peuvent être décrites selon plusieurs points de vues. Eiben et
Master MACS Schippers considèrent les opérateurs de mutation et de croisement comme des opérateurs de diversification permettent d’explorer l’espace de recherche. Et l’intensification est effectuée par la sélection des individus. Cette sélection est fondée sur la fonction de fitness des individus (évaluation des solutions) et consiste à favoriser la conservation des meilleurs individus. Certaines études ne partagent pas ce point de vue où l’opérateur de croisement est uniquement associé à l’exploration de l’espace de recherche. L’objectif de cet opérateur est parfois énoncé comme étant la combinaison des meilleures composantes des individus. À ce titre, le croisement peut être considéré comme étant un opérateur d’intensification. Le modèle organisationnel d’algorithme évolutionniste de la figure ci-dessous est représenté suivant le point de vue de Eiben et Schippers dans [8]. Le modèle organisationnel d’algorithme évolutionniste est composé de trois rôles : Selector, Recombinator-Mutator et Coordinator.
La définition des trois rôles est la suivante :
Rôle Recombinator–Mutator : La diversifivation de la recherche est obtenue par le croisement et la mutation. Ainsi, le role Recombinator–Mutator, raffinement du rôle Diversifieur, est chargé à diversifier une population de solutions en appliquant des opérateurs de croisement et de mutation. Rôle Selector : Le rôle Selector est un raffinement du rôle Intensifieur. Il consiste sélectionner les individus d’une population en favorisant la conservation des meilleurs individus.
Rôle Coordinator : Dans les algorithmes évolutionnistes, la mémoire est constituée d’une population d’individus. Ces individus évoluent grâce aux opérateurs de mutation et de croisement et sont mis en compétition dans le cadre de la sélection. Le comportement du rôle Coordinator, raffinement du rôle Guide, consiste à soumettre la population aux croisements et mutations en interagissant avec le rôle Recombinator-Mutator, puis à obtenir la nouvelle génération d’individus par l’intermédiaire du rôle Selector.
Le rôle Stratège peut consister dans les algorithmes évolutionnistes à observer l’évolution des différentes générations de populations et à ajuster les paramètres stratégiques des rôles Recombinator-Mutator, Selector et Coordinator. Parmi les différentes variantes des algorithmes évolutionnistes l’approche de distribution des îles (island EA) [8]. Cette approche de distribution consiste en un ensemble de souspopulations séparées les unes des autres et ne communi-quant que périodiquement au travers de migrations d’individus. Pour modéliser cette variante des algorithmes évolutionnistes, le modèle organisationnel (figure 2.10)est légèrement adapté afin d’ajouter l’interaction correspondant à la migrations d’individus. A la manière de l’approche des îles une instance d’algorithme évolutionniste est distribuée et composée de trois agents. Les agents interagissent lors des migrations d’individus. Chaque agent joue l’ensemble des rôles et dispose donc d’une population d’individus.
Conclusion Dans ce chapitre, nous avons présenté le framework AMF destiné à l’analyse et à la conception de métaheuristiques. Le modèle organisationnel d’AMF, qui est à la base de ce framework, adopte les concepts du méta-modèle RIO et présente ainsi une métaheuristique sous la forme d’une organisation composée de quatre rôles fondamentaux nommés: Intensifieur, Diversifieur, Guide et Stratège, en interaction. Ce modèle peut être considéré comme un schéma qui doit être raffiné en fonction des caractéristiques particulières de la métaheuristique que nous voulons retenir, et suivant le ou les problèmes à traiter.
|
Guide du mémoire de fin d’études avec la catégorie Illustration du modèle organisationnel d’AMF |
|
É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 Raffinement du modèle organisationnel d’AMF où vous pouvez trouver aussi quelques autres mémoires de fin d’études similaires.
|
Table des matières
Introduction générale
Chapitre I Agent et système multi-agent
1. Introduction
2. Notion d’agent
2.1. Définitions
2.2. Agent Réactif
2.3. Agent Cognitif
3. Système multi-agent
3.1. Définitions
3.2. La communication dans les systèmes multi-agents
4. Conclusion
Chapitre II Les systèmes multi-agent et les métaheuristiques
1. Introduction
2. Un framework pour la modélisation et l’implantation de métaheuristiques AMF
2.1. Approche organisationnelle et méta-modèle RIO
2.2. Modèle organisationnelle et métaheuristiques
3. Phases du processus de conception associé au méta-modèle RIO pour la modélisation de métaheuristiques
4. Illustration du modèle organisationnel d’AMF
4.1. Optimisation par colonies de fourmis
4.2. Algorithmes évolutionnistes
5. Conclusion
Chapitre III Conception d’une métaheuristique à base de coalition d’agent (CBM)
1. Introduction
2. Hyper-heuristique
3. Structure générale de CBM
4. Raffinement du modèle organisationnel d’AMF
4.1. Organisation CBM
4.2. Rôles Intensifieur et Diversifieur
4.3. Rôle guide
4.4. Rôle stratège
5. Agentification du modèle organisationnel de CBM
6. Système de décision de CBM
6.1 Stratégie d’alternance entre la diversification et l’intensification
6.2 Processus de décision
7. Mécanismes d’apprentissage
7.1. Apprentissage par renforcement
7.2. Apprentissage par mimétisme
8. Comportement d’un agent dans CBM
9. Conclusion
Chapitre IV Application du CBM à la résolution du problème de tournées de véhicules
1. Introduction
2. Problème de tournées de véhicules
3. Spécialisation de CBM
4.2. Opérateurs d’intensification
4.3. Opérateurs de diversification
4. Résultats expérimentaux
5. Conclusion
Conclusion générale
Bibliographie
Télécharger le rapport complet
