Terminologie:
Heuristique, du grec εὑρίσκειν / heuriskein, qui signifie « trouver ».
méta, du grec μετά veut dire « au-delà » ou « à un plus haut niveau »).
En effet, une heuristique est spécifique à un problème donné.
Une méta-heuristique est une méthodes générique pouvant optimiser une large gamme de problèmes différents, sans nécessiter de changements profonds dans l’algorithme employé.
Autrement dit : Les méta-heuristiques sont une forme d’algorithmes d’optimisation stochastique, hybridés avec une recherche locale. Le terme méta est donc pris au sens où les algorithmes peuvent regrouper plusieurs heuristiques
Pourquoi l’Heuristique?
En effet, les méthodes d’optimisation exactes peuvent être avec une très grande complexité mathématique qui se traduit par des temps de calculs souvent longs.
En pratique, une solution à un problème d’optimisation doit être proposée dans des temps raisonnables, donc on peut se contenter d’une solution approchée (la qualité de la solution est diminuée).
Une heuristique, c'est généralement une stratégie de résolution empirique qui exploite la structure d'un problème. Généralement sous-optimale, mais converge rapidement vers une bonne solution.
Une heuristique est une stratégie de bon sens (selon la structure spécifique du problème ) pour se déplacer intelligemment dans l’espace des solutions, afin d’obtenir une solution approchée, la meilleure possible, dans un délai de temps raisonnable.
Deux types d’heuristiques sont principalement utilisées :
Les heuristiques de construction (par exemple les méthodes gloutonnes), qui construisent itérativement une solution,
Les heuristiques de descente, qui à partir d’une solution donnée cherchent un optimum local.
Les heuristiques sont dépendantes du problème à résoudre, principalement dans le choix du voisinage (donc dans le déplacement dans l’espace des solutions).
Des heuristiques plus poussées ont été mises au point et ont données naissance à une nouvelle famille d’algorithmes : les méta-heuristiques.
Le but d’une méta-heuristique, est de réussir à trouver un optimum global.
Des heuristiques plus poussées ont été mises au point et ont données naissance à une nouvelle famille d’algorithmes : les méta-heuristiques.
Le but d’une méta-heuristique, est de réussir à trouver un optimum global. Pour cela, l’idée est à la fois de parcourir l’espace de recherche, et d’explorer les zones qui paraissent prometteuses ; mais sans être « piégé » par un optimum local.
Les méta-heuristiques sont souvent inspirées de processus naturels et sont de plus en plus hybridées avec d’autres méthodes de recherche opérationnelle.
Une métaheuristique, c'est (généralement) une marche aléatoire dans l'espace de recherche guidée par des heuristiques. Comme l'explique candide (et le préfixe "méta"), ce sont des algos ultra-génériques qui a priori s'appliquent à de nombreuses catégories de problèmes différents. Un peu à l'opposé d'une heuristique qui reste très spécifique pour un problème donné.
Différence entre heuristique et metaheuristique
Une métaheuristique, c'est (généralement) une marche aléatoire dans l'espace de recherche guidée par des heuristiques. Comme l‘indique préfixe "méta", ce sont des algorithmes ultra-génériques qui a priori s'appliquent à de nombreuses catégories de problèmes différents. Un peu à l'opposé d'une heuristique qui reste très spécifique pour un problème donné.
Une heuristique est juste une méthode de résolution individuelle (une idée). Une méta-heurisitque est juste une heuristique générique c'est-à-dire une heuristique qui peut s’appliquer pour résoudre un nombre plus large de problèmes.
Exemple d’application : problème du voyageur de commerce (TSP)
Le problème du voyageur de commerce (TSP: en anglais Travelling Salesman Problem) est un problème classique d’optimisation combinatoire NP-complet qui est toujours traité en recherche scientifique pour lui trouver une bonne solution.
Les algorithmes exactes utilisées pour la résolution du TSP ont une complexité en temps qui croît exponentiellement avec n (la taille du problème ou le nombre de villes).
Plusieurs méthodes approchées (d’approximation-heuristiques) ont été proposées qui trouvent une solution approchée en temps raisonnable.
Par exemple, Le recuit simulé peut être appliqué au problème du voyageur de commerce.
Un voyageur de commerce désire visiter un certain nombre de villes, débutant et finissant son parcours dans la même ville en visitant chacune des autres villes une et une seule fois. Il désire sélectionner la tournée qui minimise la distance totale parcourue.
Références Bibliographiques
www-lisic.univ-littoral.fr/~v...
rfia2012.files.wordpress.com/...
ftp://ftp.fsr.ac.ma/cours/maths/Souad%20Bernoussi/Cours%20C2SI.pdf
fr.wikipedia.org/wiki/M%C3%A9....
Негізгі бет Ғылым және технология Méthodes d'Optimisation différence entre Heuristique et Meta-heuristique Partie 1
Пікірлер: 18