Soutenance mémoire
Dans leurs activités, les ingénieurs et les décideurs sont confrontés à des problèmes de complexité grandissante, en vue de maximiser les bénéfices, minimiser les pertes…etc. Ces problèmes surgissent dans des domaines très divers, comme la conception et l’implémentation des systèmes d’aide à la décision, les réseaux informatiques, le traitement d’images, en robotique, en électronique. Dans le domaine de diagnostic médical, la résolution des problèmes se base sur le traitement de données extraites à partir des informations acquises sur des patients, et structurées sous forme de vecteurs de caractéristiques. La qualité du système de diagnostic dépend énormément du bon choix du contenu de ces vecteurs. Cependant, dans de nombreux cas, la résolution pratique du problème devient presque impossible à cause de la dimensionnalité importante de ces vecteurs. Par conséquent, il est souvent utile, et parfois nécessaire, de réduire la taille de ces caractéristiques à une taille plus optimale, en utilisant des méthodes de résolution dédiées. Dans plusieurs cas, la résolution des problèmes complexes avec des descripteurs de grande taille pourrait être gérée, en utilisant peu de caractéristiques extraites des données initiales.
Généralités sur les métaheuristiques
Un grand nombre de problèmes d’aide à la décision, comme les problèmes d’apprentissage et de sélection de variables, peuvent être décrits sous forme de problèmes d’optimisation. Ces derniers occupent actuellement une place grandissante dans la communauté scientifique. Ils peuvent être combinatoires (discrets) ou à variables continues, avec un seul ou plusieurs objectifs (optimisation mono ou multiobjectif), statiques ou dynamiques, avec ou sans contraintes. Cette liste n’est pas exhaustive et un problème peut être, par exemple, à la fois continu et dynamique.
Définition d’un problème d’optimisation
L’optimisation se définit comme la sélection du meilleur élément (appelé optimum) parmi un ensemble d’éléments autorisés (appelé espace de recherche), en fonction d’un critère de comparaison. Un problème d’optimisation P peut être décrit comme un triple (S, C, F) ou :
S : est l’espace de recherche défini sur un ensemble de variables de décisions.
C : est l’ensemble de contraintes d’égalités ou inégalités qui doivent être satisfaites pour qu’une solution soit faisable.
F : est la fonction objective (fonction de cout) qui assigne une valeur du coût positive à chaque élément (ou solution) de S.
Plusieurs problèmes d’optimisation dépendent du choix de la meilleure configuration de l’ensemble de variables pour atteindre ses objectifs, ils peuvent se découper en deux catégories : les problèmes où les solutions sont codées avec des valeurs réelles (Problème Continu) et les problèmes où les solutions sont codées avec des variables discrètes (problème Combinatoire) que nous nous intéressons dans notre thèse. . Il existe aussi des problèmes mixtes qui utilisent à la fois des variables continues et discrètes.
Un problème d’optimisation combinatoire est généralement caractérisé par un ensemble fini de solutions admissibles W et une fonction objectif F , associant une valeur à chaque solution admissible. La résolution du problème consiste à déterminer la ou les solution(s) de W minimisant ou maximisant F, c’est-à-dire l’optimum global .
Classification des méthodes d’optimisation
L’optimisation combinatoire occupe une place très importante en recherche opérationnelle, en mathématiques discrètes et en informatique. Bien que les problèmes d’optimisation combinatoire soient souvent faciles à définir, ils sont généralement difficiles à résoudre. Etant donnée l’importance de ces problèmes, de nombreuses méthodes de résolution ont été développées en recherche opérationnelle (RO) et en intelligence artificielle (IA).
Les méthodes exactes
Le terme de méthodes exactes regroupe l’ensemble des méthodes permettant d’obtenir la solution optimale d’un problème, en un temps « raisonnable ». Elles s’opposent aux heuristiques, car les méthodes exactes permettent d’obtenir théoriquement la solution optimale et non une solution approchée.
Les méthodes approchées
Les méthodes exactes permettent de trouver une ou plusieurs solutions dont l’optimalité est garantie. Dans certaines situations, on peut obtenir de solutions de bonnes qualités sans garantie d’optimalité mais avec un temps de calcul réduit (les méthodes approchées) [3] Les méthodes approchées constituent une alternative très intéressante pour traiter les problèmes d’optimisation de grande taille si l’optimalité n’est pas primordiale. En effet, ces méthodes sont utilisées depuis longtemps par de nombreux praticiens .
Les métaheuristiques
Au milieu des années 1970 des nouvelles méthodes sont apparues qui supervisent l’évolution de solutions fournies par des heuristiques. Ces méthodes assurent un compromis entre la diversification (possibilité de déterminer que la recherche se concentre sur de mauvaises zones de l’espace de recherche) et l’intensification (recherche des meilleures solutions dans la région de l’espace de recherche en cours d’analyse). Ces algorithmes sont appelés « métaheuristiques”. Au début des années 1980, ces méthodes ont été appliquées dans le but est de résoudre au mieux les problèmes dits d’optimisation difficile et de trouver des solutions dont la qualité est au-delà de ce qu’il aurait été possible de réaliser avec une simple heuristique. Elles partent de principes plus génériques que les heuristiques et sont susceptibles de s’appliquer à un cadre plus large de problèmes, tandis qu’une heuristique est particulière pour un problème donné .
Définitions des métaheuristiques
Le terme métaheuristique vient des mots grecs méta (au delà) ‘dans un niveau supérieur’ et heuriskein et qui signifie (trouver).Une heuristique est une méthode, conçue pour un problème d’optimisation donné, qui produit une solution non nécessairement optimale lorsqu’on lui fournit une instance de ce problème .
D’après Blum et Roli [23] il n’existe actuellement aucune définition communément acceptée pour les métaheuristiques.
Définition(l) : Une métaheuristique est formellement défini comme une génération itérative processus qui guide une heuristique subordonnée en combinant intelligemment différents concepts pour l’ exploration et l’exploitation de l’ espace de recherche , les stratégies d’apprentissage sont utilisés pour structurer l’information afin de trouver des solutions de manière efficace quasi- optimales [8].
Définition (2) : Les métaheuristiques sont des méthodes génériques de résolution approchée de problèmes d’optimisation. Elles permettent d’envisager une résolution approchée de nombreux problèmes d’optimisation différents, avec un minimum d’adaptation réalisée pour chaque problème. Parmi ces méthodes on trouve les algorithmes génétiques [10].
Définition (3) : Les métaheuristiques sont définies comme un processus itératif maitre qui guide et modifie des heuristiques subordonnées dans le but d’efficacement produire des solutions de haute qualité. Une métaheuristique peut manipuler une ou plusieurs solution complètes(ou incomplètes) a chaque itération. Les heuristiques subordonnées peuvent être des procédures de haut(ou bas) niveau, ou de simple recherche locale ou juste des méthodes de construction [11].
Caractéristiques des métaheuristiques
Les principales caractéristiques attachées aux métaheuristiques sont les suivantes:
➺ La plupart des métaheuristiques sont des algorithmes incertains utilisant des processus aléatoires comme moyens de récolter de l’information et de parcourir l’espace de recherche afin de trouver une solution satisfaisante.
➺ Les métaheuristiques ne donnent aucune garantie d’optimalité.
➺ Les métaheuristiques peuvent utiliser l’expérience acquise durant le processus de recherche pour guider les étapes suivantes du processus.
➺ En plus de cette base stochastique, les métaheuristiques sont généralement itératives, c’est à dire qu’un même schéma de recherche est appliqué plusieurs fois au cours de l’optimisation, et directes, c’est à dire qu’elles n’utilisent pas l’information du gradient de la fonction objectif.
➺ Elles sont inspirées par analogie avec la réalité : avec la physique (le recuit simulé), avec la biologie (les algorithmes génétiques) ou avec l’éthologie (les colonies de fourmis)…
➺ Les métaheuristiques peuvent contenir des mécanismes qui permettent d’éviter d’être piégé dans des zones de l’espace de recherche.
➺ Elles partagent aussi les mêmes inconvénients tels que la difficulté de réglage de ces paramètres .
|
Table des matières
Introduction générale
1 Généralités sur les métaheuristiques
1 Introduction
2 Définition d’un problème d’optimisation
3 Classification des méthodes d’optimisation
3.1 Les méthodes exactes
3.2 Les méthodes approchées
4 Les métaheuristiques
4.1 Introduction
4.2 Définitions des métaheuristiques
4.3 Caractéristiques des métaheuristiques
5 Classification des Métaheuristiques
5.1. Recherche Locale (Méthodes de trajectoire)
5.1.1. Le Recuit simulé (RS)
a. Principes du RS
b. Algorithme du R S
c. Domaines d’applications.
d. Avantages et inconvénients
5.1.2 Recherche tabou
5.2 Métaheuristiques à base de population
5 .2.1 Introduction
5.2.2 Algorithme génétique (AG)
a. Principe de base de l’AG
b. Processus de l’AG
c. Limites de l’AG
5.2.3 Les essaims particulaires
a. Principe de fonctionnement
b. Algorithme de base
6 Conclusion
2 Problèmes de sélection de variables
1 Introduction
2 Sélection de variables
2.1 Problématique
2.2 Difficulté de la sélection d’attributs
2.2.1 Dimensionnalité
2.2.2 Pertinence d’attributs
2.2.3 Redondance
2.3 Processus global de sélection de variables
2.3.1. Procédure de génération
a. Direction de recherche
b. Stratégie de recherche
2.3.2 Fonction d’évaluation
a. Information
b. Distance
c. Dépendance
d. Consistance
e. Précision
2.3.3 Critère d’arrêt
2.3.4 Procédure de validation
3 Approches de sélection de variables
3.1 Méthode par Filtre
3.2 Approches à adaptateur (Wrapper)
3.3 Approches intégrées (Embedded)
4 Métaheuristiques pour la sélection de variables
5 Conclusion
3 Implémentation de l’algorithme OP-VAR
1 Introduction
2 Description du jeu de données
2.1Description de la base de données de diabète
2.2 Description de la base de données Heart Statlog
2.3 Description de la base de données Hepatitis
3 Environnement de développement
4 Critères d’évaluation
5 Le model Op-Var
5.1 Description du classifieur SVM
5.1.1 Hyperplans séparateurs dans un problème à deux classes
5.2 Architecture du modèle
5.2.1 Conception du chromosome
5.2.2 Conception de la fonction de remise en forme
5.2.3 Étapes de base de la méthode GA-SVM
5.3 Choix des paramètres
5.4 L’approche GA-SVM dans la littérature
5.5 Aperçu sur l’interface Op-Var
6 Validation Expérimentale
6.1 Analyse des résultats
6.2 Etude comparative
6.2.1 Comparaison des résultats avec et sans sélection
6.2.2 Comparaison des résultats avec les méthodes Relief et Rank-Features
6.2.3 Comparaison avec les résultats de la littérature
7 Conclusion
Conclusion générale
Annexes
