LES ALGORITHMES EVOLUTIONNAIRES

♣ Contenu du memoire

TABLE DES FIGURES
LE RESUME
INTRODUCTION GENERALE
CHAPITRE I: L’OPTIMISATION MULTIOBJECTIFS
I. INTRODUCTION
II. DEFINITIONS
II.1 Un problème
II.2 Types des problèmes
III. UN PROBLEME COMBINATOIRE
IV. UN PROBLEME D’OPTIMISATION
IV.1 Définition
IV.1.1 Fonction objective
IV.1.2 Variables de décision
IV.1.3 Minimum global
IV.1.4 Minimum local fort
IV.1.5 Minimum local faible
IV.2 Les variables d’un problème multiobjectifs
IV.2.1 Les variables indépendantes
IV.2.2 Les variables dépendantes
IV.2.3 Les variables d’état
IV.2.4 Les variables opérationnelles
IV.2.5 Les variables de l’environnement
IV.3 La classification des problèmes multiobjectifs
V. LA DOMINANCE
V.1 La dominance au sens de Pareto
V.2 La surface de compromis
V.2.1 Représentation de la surface de compromis
VI. EXEMPLES DE PROBLEMES COMBINATOIRES
VI.1 Le voyageur de commerce
VI.1.1 L’historique
VI.1.2 La complexité
VI.1.3 Intérêt
VI.2 Le sac à dos (knapsack Problem)
VI.2.1 Le problème de sac à dos multiobjectifs multidimensionnel
VI.3 Problème SAT (Problème de satisfaction)
VI.4 Problème de coloration de graphe (graph coloring)
VI.5 Problème de N-Queen
VII. LES METHODES D’OPTIMISATION MULTIOBJECTIFS
VII.1 Schéma de méthodes
VII.2 Les méthodes scalaires
VII.3.1 La méthode de pondération de fonctions objectives
VII.3.2 La méthode de Keeney-Raiffa
VII.3.3 La méthode de la distance à un objectif de référence
VII.3.4 La méthode de compromis
VII.3 Les méthodes interactives
VII.3.1 La méthode de compromis par substitution
VII.3.2 La méthode de Jahn
VII.3.3 La méthode de geoffrion
VII.3.4 La méthode simplex
VII.4 Les méthodes floues
VII.4.1 La méthode de Sakawa
VII.5 Les méthodes exploitant une métaheuristique
VII.5.1 Qu’est-ce qu’une métaheuristique ?
VII.5.2 Généralités
VII.5.3 Le recuit simulé
VII.5.4 La Recherche Tabou
VII.5.5 La méthode GRASP
VII.5.6 La méthode de Colonie de Fourmis
VII.5.7 Monté Carlo
VII.5.8 Particle Swarm Optimization « PSO »
VII.5.9 Les algorithmes évolutionnaires
VII.5.10 Les méthodes hybrides
VIII. CONCLUSION
CHAPITRE II: LES ALGORITHMES EVOLUTIONNAIRES
I INTRODUCTION
II HISTORIQUE ET DEFINITIONS
II.1 Historique
II.2 Définition
II.2.1 La diversité génétique
II.2.2 Le dilemme exploration – exploitation
II.2.3 Principes généraux
III TYPES D’ALGORITHMES EVOLUTIONNAIRES
III.1 Les algorithmes génétiques
III.1.1 De la génétique à l’algorithmique
III.1.2 Définition :
III.1.3 Les éléments des algorithmes génétiques
III.1.4 Les opérateurs d’un algorithme génétique
III.1.5 L’optimisation multiobjectifs et les algorithmes génétiques
III.1.6 Les méthodes non agrégatives
III.1.7 Les méthodes agrégatives
III.2 La programmation évolutionnaire
III.2.1 Le processus
III.3 Les stratégies d’évolution
IV L’OPTIMISATION MULTIOBJECTIFS EVOLUTIONNAIRE
IV.1 Maintenir la diversité !
IV.1.1 Le sharing
IV.1.2 La réinitialisation
IV.1.3 Le crowding
IV.2 L’élitisme
V CONCLUSION
CHAPITRE III: LA PROGRAMMATION GENETIQUE
I. INTRODUCTION
II. HISTORIQUE
III. DEFINITION
IV. CONCEPTS DE BASE DE GP
V. AUTRES PARAMETRES DE GP
VI. LA PROGRAMMATION GENETIQUE ET LE PHENOMENE DE BLOATING
VII. LA PROGRAMMATION GENETIQUE ET LES PROBLEMES COMPLEXES :
VIII. MULTIOBJECTIVE GENETIC PROGRAMMING :
IX. EXEMPLE DE PROBLEME POUR LA PROGRAMMATION GENETIQUE :
X. CONCLUSION
CHAPITRE IV: OPTIMISATION MULTIOBJECTIFS PAR PROGRAMMATION GENETIQUE
I. INTRODUCTION
II. LA RESOLUTION D’UN PROBLEME D’OPTIMISATION PAR GP
III.1 Le choix de paramètres :
II.1.1 Les fonctions
II.1.2 Les terminaux
II.1.3 La fonction de fitness (définition de problème)
II.1.4 Le réglage des opérateurs (reproduction, croisement, mutation)
II.1.5 L’initialisation de la population :
II.1.6 Les limites de la taille et la profondeur des arbres :
II.1.7 Le meilleur individu
II.1.8 Le calcul de la complexité et la diversité
II.1.9 Quels sont les individus qui survivent ?
II.1.10 La représentation graphique des résultats
III.2 Exemple « TSP »
II.2.1 Remarques sur les résultats
III. L’OPTIMISATION DE L’ARBRE COMME UN 2 EME OBJECTIF
III.1 Formulation de problème
III.2 Les méthodes de résolution de problème du Bloating
III.2.1 Constant Parsimony Pressure
III.2.2 La méthode de deux étapes
III.2.3 Adaptive Parsimony Pressure
III.3 La définition du bloating comme une 2 ème fonction objectif
III.4 Les frontières de Pareto bi-objectifs
III.5 L’approche SPEA2
IV. APPLICATION DE L’APPROCHE MOGP+SPEA2
IV.1 Les ressources utilisées
IV.2 Le problème de TSP Bi-objectifs
IV.3 Le problème de « N-Parity »
V. CONCLUSION
CONCLUSION GENERALE
BIBLIOGRAPHIE