Généralités sur les métaheuristiques

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 [9]. Cependant il peut exister des solutions intermédiaires, qui sont également des optimums, mais uniquement pour un sous-espace restreint de l’espace de recherche : on parle alors d’optimums locaux.

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). Ces méthodes peuvent être classées sommairement en deux grandes catégories illustrées dans la figure 1.3 :
٠ Les méthodes exactes (complètes) qui garantissent la complétude de la résolution.
٠ Les méthodes approchées (incomplètes) qui perdent la complétude pour gagner en efficacité. [4]

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 

Introduction 

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é [7].

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 [4].

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 .

Classification des Métaheuristiques

Bien que les métaheuristiques partagent plusieurs caractéristiques communes, il existe cependant des points différences entre ces approches. Les métaheuristiques peuvent être classées selon :
➤ Le principe de fonctionnement durant la recherche de la solution (i.e La manipulation d’une solution à la fois (recherche locale ou méthodes de trajectoire) ou un ensemble des solutions (à base de population)).
➤ Leur origine (Inspiration de la nature ou non).
➤ Utilisation de l’historique de la recherche (mémoire).

Recherche Locale (Méthodes de trajectoire) 

Les métaheuristiques de recherche locale ou les méthodes itératives à solution unique sont basées sur un algorithme de recherche de voisinage qui commence avec une solution initiale, puis l’améliore à pas en choisissant une nouvelle solution dans son voisinage, le voisinage d’une solution est défini en fonction du problème à résoudre : passent d’une solution s à une autre dans l’espace des solutions candidates (l’espace de recherche) qu’on note S, jusqu’à ce qu’une solution considérée comme optimale soit trouvée ou que le temps réparti soit dépassé. Nous présenterons ici les méthodes les plus classiques et les plus utilisées qui sont : le recuit simulé, la recherche tabou et la méthode de descente (recherche locale).

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
Bibliographie

Télécharger le rapport complet