Les méthodes évolutionnaires classiques

Optimisation et informatique évolutionnaire

L’optimisation est un aspect fondamental de l’ingénierie et de la résolution de problèmes. L’objectif de l’optimisation est de chercher les valeurs d’un ensemble de paramètres pour maximiser ou minimiser les fonctions objectives soumises à certaines contraintes. Un choix des valeurs, pour l’ensemble de paramètres, qui satisfont toutes les contraintes, est appelé une solution faisable. Les solutions faisables avec des valeurs de la fonction objective qui sont meilleures que les valeurs de toutes les autres solutions possibles, sont appelées les solutions optimales [OMR 04]. Un problème d’optimisation peut être formulé sous la forme d’un problème de minimisation ou d’un problème de maximisation. Parfois, nous essayons de minimiser une fonction et, parfois, nous essayons de maximiser une fonction.

Il existe certains types particuliers de problèmes d’optimisation:

• Les problèmes généraux sans contraintes: où une fonction non linéaire est définie sur un ensemble de valeurs réelles sans contraintes.
• Les problèmes généraux avec contraintes: où une fonction non linéaire est définie sur un ensemble limité de valeurs réelles. Généralement, les problèmes d’optimisation sont des problèmes d’optimisation avec contraintes [SIM 13a].
• Les problèmes d’optimisation multi-objectifs : dans lesquels un problème nécessite la résolution de plusieurs problèmes simultanément. Souvent, les solutions aux divers problèmes interfèrent entre elles, la meilleure solution est alors une sorte de compromis [KEN 06]. L’optimisation multi-objectif (Multiobjective Optimization : MO) cherche à optimiser les composantes de valeurs de vecteur d’une fonction de coût. Contrairement à l’optimisation avec objectif unique, la solution à ce problème n’est pas un seul point, mais une famille de points connus comme l’ensemble Pareto-optimal. Chaque point de cette surface est optimal dans le sens qu’aucune amélioration ne peut être obtenue en un composant de vecteur de coût. L’ensemble des solutions est appelé l’ensemble de Pareto [FON 93].
• Les problèmes d’optimisation multimodale: ce sont ceux dans lesquels l’espace de recherche contient plusieurs optimums locaux et il est possible qu’il contienne plus d’un optimum global. Ces problèmes sont intéressants, non seulement en raison du défi qu’ils représentent, en évitant les optimums locaux ou la localisation de plus d’un optimum global en même temps, mais parce qu’il existe beaucoup de problèmes du monde réel présentant ces caractéristiques [BAR 11].
• Les problèmes combinatoires: il existe de nombreux problèmes d’optimisation pour lesquels les variables indépendantes sont limitées à un ensemble de valeurs discrètes. Ces problèmes sont appelés problèmes d’optimisation combinatoire [SIM 13a].

La littérature relative à l’optimisation est très abondante et revêt plusieurs formes différentes. Das et al [DAS 09] divisent les méthodes d’optimisation en plusieurs classes et placent celles-ci dans un arbre (Figure 1.1) selon que les méthodes soient exactes ou approximatives, déterministes ou probabilistes, traitent des solutions complètes ou construisent des solutions lors de la recherche, et enfin si elles entretiennent une solution candidate unique ou une population des solutions. Elles donnent les solutions exactes, sauf pour les techniques de recherche locale, telles que la méthode de Newton et les méthodes de gradient, qui offrent, comme les heuristiques modernes, des solutions approximatives. Les méthodes d’analyse directe peuvent être arrêtées à tout moment et renvoient une solution, car elles traitent des solutions complètes, alors que ‘Branch and Bound’, la programmation dynamique (dynamic programming), et ‘Divide and Conquer’ construisent toutes des solutions lors de la recherche, et ne peuvent donc pas être arrêtées pour retourner une solution complète avant que toute la recherche ne soit effectuée.

Les méthodes évolutionnaires classiques 

Les méthodes évolutionnaires représentent une classe de métaheuristiques ayant comme principe de faire évoluer une population de base (constituée de solutions au problème à résoudre) par des opérateurs de variations (croisement et mutation). Cette population est soumise à une sélection pour le croisement puis une sélection pour la survie. L’objectif est de faire converger les solutions (appelées « individus ») vers un optimum en respectant certains critères. Dans les années 70, les premiers travaux sur l’évolution artificielle ont concerné les algorithmes génétiques (AG), les stratégies d’évolution (SE) et la programmation évolutive (PE). Ces trois types d’algorithmes ont utilisé des principes globalement communs car ils se sont tous inspirés des mêmes principes du néo-darwinisme : utilisation d’une population d’individus, évaluation des individus par une fonction, sélection des meilleurs et génération d’une nouvelle population avec des opérateurs de croisement et de mutation. Ensuite, dans les années 90 est apparue la programmation génétique (PG) qui introduit, notamment, des représentations arborescentes [AZZ 04].

Les algorithmes génétiques

Les algorithmes génétiques (Genetic Algorithms) sont des stratégies d’adaptation et des techniques d’optimisation globale [BRO 11]. Ce sont les premiers, les plus connus, et les plus utilisés parmi les méthodes évolutionnaires [SIM 13a]. Les algorithmes génétiques (AGs) ont été développés à l’origine dans les années 60 à l’Université du Michigan par John Holland et son équipe [HOL 75], qui ont mené leur recherche sur des systèmes adaptatifs et robustes. Plus tard, les algorithmes génétiques ont été affinés par De Yong, Goldberg, Michalewicz, et bien d’autres [SER 06]. Ils sont été utilisés au début avec des représentations binaires, où les opérateurs de croisement et de mutation jouent un rôle majeur. Les algorithmes génétiques ont trois applications majeures nommées la recherche intelligente, l’optimisation et l’apprentissage automatique. Un AG a généralement quatre composants : une population d’individus, où chaque individu de la population représente une solution candidate au problème d’optimisation, une fonction de fitness qui est une fonction d’évaluation par laquelle nous pouvons dire si un individu est une bonne solution ou non, une fonction de sélection qui décide comment choisir les bons individus de la population actuelle pour la création de la génération suivante; et des opérateurs génétiques tels que le croisement et la mutation, qui explorent de nouvelles régions de l’espace de recherche tout en gardant une partie de l’information actuelle.

La programmation évolutionnaire 

La programmation évolutionnaire (Evolutionary Programming ) est une autre technique évolutive développée par Fogel et son équipe dans les années 60 [FOG 66]. L’objectif de l’algorithme de programmation évolutionnaire est de maximiser l’adéquation d’une collection de solutions candidates dans le cadre d’une fonction objective à partir du domaine. Cet objectif est poursuivi par l’utilisation d’un modèle adaptatif avec substituts pour le processus d’évolution, en particulier héréditaire (reproduction avec des variations) sous compétition. La représentation utilisée pour les solutions candidates est évaluable directement par un coût ou une fonction objective à partir du domaine [BRO 11]. .

Les stratégies d’évolution 

Les stratégies d’évolution (Evolution Strategies) ont été développées indépendamment par Rechenberg et Schwefel [REC 73] en Allemagne comme une méthode pour résoudre des problèmes d’optimisation pratiques [SER 06]. L’objectif des algorithmes des stratégies d’évolution est de maximiser l’aptitude d’une collection de solutions candidates dans le cadre d’une fonction objective à partir d’un domaine. L’objectif est classiquement atteint grâce à l’adoption de la variation dynamique ; un substitut pour la descendance avec modification ; lorsque le montant de la variation a été adapté de manière dynamique avec des heuristiques basées sur la performance. Les approches contemporaines co-adaptent des paramètres qui contrôlent la quantité et la partialité de variation avec les solutions candidates [BRO 11].

Table des matières

INTRODUCTION GÉNÉRALE
CHAPITRE 1 : Méthodes évolutionnaires pour L’optimisation
1.1. Introduction
1.2. Optimisation et informatique évolutionnaire
1.3. Les méthodes évolutionnaires classiques
1.3.1. Les algorithmes génétiques
1.3.2. La programmation évolutionnaire
1.3.3. Les stratégies d’évolution
1.3.4. La programmation génétique
1.4. L’intelligence en essaims ou Swarm Intelligence
1.4.1. Les colonies de fourmis
1.4.1.1. Le système de fourmis original
1.4.1.2. Les variantes de l’algorithme AS
1.4.2. Les essaims particulaires
1.4.3. Les algorithmes inspirés des abeilles (Bee inspired algorithms)
1.4.3.1. Les colonies d’abeilles artificielles (ABC)
1.4.3.2. L’Algorithme d’abeilles (BA)
1.4.3.3. L’algorithme d’optimisation par les colonies d’abeilles (BCO)
1.4.4. L’algorithme des essaims de poissons artificiels (AFSA)
1.4.5. L’algorithme des chauves-souris (Bat algorithm)
1.4.6. L’algorithme des essaims de lucioles (Firfly algorithm)
1.4.7. L’algorithme d’optimisation de l’exploration bactérienne (BFO)
1.5. Autres méthodes évolutionnaires pour l’optimisation
1.5.1. L’optimisation basée sur la Biogéographie
1.5.2. L’algorithme de recherche gravitationnelle
1.5.3. L’optimisation basée sur l’enseignement-apprentissage
1.6. Conclusion
CHAPITRE 2 : Concepts et méthodes de la sélection d’attributs
2.1. Introduction
2.2. Définition de la sélection d’attributs
2.3. Prosessus de sélection d’attributs
2.3.1. La procédure de génération
2.3.1.1. Génération complète
2.3.1.2. Génération heuristique ou séquentielle
2.3.1.3. Génération aléatoire
2.3.2. La fonction d’évaluation
2.3.2.1. Les mesures indépendantes
2.3.2.2. Les mesures dépendantes
2.3.3. Le critère d’arrêt
2.3.4. La procédure de validation
2.4. Catégorisation des méthodes de sélection d’attributs
2.4.1. Catégorisation basée sur les critères d’évaluation
2.4.2. Catégorisation basée sur la stratégie de recherche
2.5. Méthodes classiques de la sélection d’attributs
2.5.1. Méthodes complètes
2.5.1.1 FOCUS
2.5.1.2 Branch and Bound (BB)
2.5.1.3 Automatic Branch &Bound (ABB)
2.5.2. Méthodes heuristiques
2.5.2.1 Sequential Forward Selection (SFS)
2.5.2.2 Sequential Backward Selection (SBS)
2.5.2.3. Relief
2.5.3. Méthodes Aléatoires
2.5.3.1 Las Vegas Filter et Las Vegas Wrapper
2.5.3.2 Les algorithmes génétiques pour la sélection d’attributs
2.6. Méthodes de sélection d’attributs basées sur l’intelligence en essaims
2.6.1. Sélection d’attributs par les colonies de fourmis
2.6.1.1 Représentation du problème de sélection de caractéristiques avec l’ACO
2.6.1.2. Le processus global de la sélection d’attributs avec ACO
2.6.2. Sélection d’attributs par les essaims particulaires
2.6.2.1. Représentation de la position
2.6.2.2. Représentation de la vitesse
2.6.2.3. Les stratégies de mise à jour de la position et la vitesse
2.7. Applications de la sélection d’attributs
2.7.1. La fouille de données
2.7.2. La catégorisation de textes
2.7.3. La reconnaissance de l’écriture
2.7.4. La reconnaissance d’images
2.7.5. La bioinformatique
2.8. Conclusion
CHAPITRE 3 : Approches classiques et bio-inspirées pour la sélection d’attributs
3.1. Introduction
3.2. Sélection d’attributs basée sur des méthodes bio-inspées non hybrides
3.2.1. Sélection d’attributs avec les algorithmes génétiques
3.2.2. Sélection de d’attributs basée sur les ACO
3.2.3. Sélection de d’attributs avec les PSO
3.2.4. Sélection d’attributs avec les algorithmes inspirés des abeilles
3.2.5. Synthèse de travaux sur la sélection d’attributs avec des méthodes bio-inspirées
3.3. Approches classique proposée pour la sélection d’attributs
3.4. Approche proposée pour la sélection d’attributs basée sur ACO
3.5. Approche proposée pour la sélection d’attributs basée sur PSO
3.6. Évaluation des approches proposées
3.6.1. Choix expérimentaux
3.6.1.1. Paramètres d’ACO et PSO
3.6.1.2. Évaluation des performances de classification
3.6.2. Expérimentations dans le domaine du filtrage de spams
3.6.2.1. Description de la base de données
3.6.2.2. Résultats expérimentaux
3.6.3. Expérimentations des approches basées ACO et PSO avec différentes bases de données
3.6.3.1. Description des bases de données
3.6.3.2. Résultats expérimentaux
3.7. Conclusion
CHAPITRE 4 : Approches bio-inspirées hybrides pour la sélection d’attributs
4.1. Introduction
4.2. Synthèse d’approches hybride basées ACO ou PSO
4.3. Approches bio-inspirées hybrides pour la sélection d’attributs
4.4. Les approches hybrides ACO-PSO proposées pour la sélection d’attributs
4.4.1. L’approche proposée ACO-PSO1
4.4.2. L’approche proposée ACO-PSO2
4.4.3. L’approche proposée ACO-PSO3
4.5. Évaluation des approches hybrides proposées
4.5.1. Bases de données et outils utilisés
4.5.2 Résultats expérimentaux
4.6. Conclusion
CONCLUSION

Lire le rapport complet