Quelle est la différence entre heuristique et métaheuristique?
Après quelques recherches sur les algorithmes j'ai trouvé deux termes qui me confond. J'ai lu au moins 20 articles et pourtant, il n'y a pas de définition claire à ce sujet non plus. J'espère que quelqu'un pourra m'aider à faire la différence entre les algorithmes heuristiques et métaheuristiques. Et si possible, en ajouter la source.
ps: je sais déjà ce qu'est la signification des mots, mais je ne sais pas quelle est la différence exacte entre eux en informatique.
merci à avance
3 réponses
vous pourriez penser à un heuristique comme une solution approximative (pas d'approximation) à un problème. La différence entre approximatif et approximatif est que le premier est d'obtenir une bonne idée de la solution d'un problème, mais que vous ne savez pas vraiment comment bon il est. La deuxième est une solution qui permet de prouver sa proximité à la solution optimale.
ainsi, l'heuristique est souvent dépendante du problème, c'est-à-dire que vous définissez un heuristique pour un donné problème. Métaheuristiques sont problème indépendant de techniques qui peuvent être appliquées à un large éventail de problèmes. Un heuristique est, par exemple, le choix d'un élément aléatoire pour pivoter dans Quicksort. Un métaheuriste ne sait rien du problème qu'il va appliquer, il peut traiter les fonctions comme des boîtes noires.
on pourrait dire qu'un heuristique exploite l'information dépendante du problème pour trouver une solution "assez bonne" à un problème spécifique, alors que les métaheuristiques sont, comme les modèles de conception, générales des idées algorithmiques qui peuvent être appliquées à une vaste gamme de problèmes.
afin de donner un bon devis, par rapport à Alejandro réponse:
" un métaheuristique est un cadre algorithmique de haut niveau indépendant des problèmes qui fournit un ensemble de lignes directrices ou de stratégies pour développer des algorithmes d'optimisation heuristique [...] Une mise en œuvre par problème d'un algorithme d'optimisation heuristique selon les lignes directrices exprimées dans un cadre métaheuristique est également appelée métaheuristique " (Sörensen, Glover, http://scholarpedia.org/article/Metaheuristics)
Pour être totalement complet. Il faut distinguer les algorithmes exacts, approximatifs et heuristiques. Un algorithme exact trouve une solution exacte. Un algorithme approximatif devrait trouver une solution approximative, dans un délai acceptable, et indiquer sa plage de divergence avec la solution optimale supposée. Une heuristique trouver simplement une bonne solution, dans un délai acceptable.
par l'exemple D'Alejandro quicksort ne semble pas tout à fait adéquat pour deux ou trois raisons différentes.
- en fait, l'heuristique et la métaheuristique font partie du domaine de l'optimisation. Le problème qu'ils essaient de résoudre est donc de rechercher un optimum, pas de tri.
- les heuristiques sont généralement utilisées lorsque les problèmes que vous voulez aborder sont trop complexes, au sens computationnel - ce qui n'est pas le cas du problème de tri.
- ce qui a été pointé à travers l'exemple de quicksort, si je comprends bien, est l'élément aléatoire. En principe, vous pouvez avoir heuristique déterministe - Je n'ai jamais rencontré une métaheuristique déterministe, mais on pourrait probablement le coder. Il pourrait être un peu "jouer avec les mots" mais, l'élément aléatoire plus correctement caractérise "recherche stochastique" de (méta)heuristiques.
Pour une explication détaillée, voir:
une métaheuristique est un algorithme de haut niveau indépendant du problème cadre qui fournit un ensemble de lignes directrices ou les stratégies à développer heuristiques algorithmes d'optimisation. Le terme est également utilisé pour désigner un mise en œuvre d'une optimisation heuristique par problème algorithme selon les directives exprimées dans un tel cadre (Sörensen, 2015).
les heuristiques sont les lignes directrices, la métaheurtique est le cadre qui les utilise.