Quelle est la différence entre les méthodes heuristiques et métaheuristiques?

Après quelques recherches sur les algorithmes j'ai trouvé deux termes qui me confond.
J'ai lu au moins 20 articles et encore, il n'y a pas de définition claire sur soit.
J'espère que quelqu'un peut m'aider à faire la différence entre les méthodes heuristiques et métaheuristiques algorithmes.
Et si possible, ajoutez la source.

ps: je connais déjà le sens des mots, mais je ne sais pas ce que la différence exacte entre eux en informatique.

merci d'avance

  • Cela dépend vraiment du contexte. Les heuristiques sont des règles utiles qui se rapprochent de la réponse parfaite/comportement. Sans contexte, l'ajout de méta-les à ne pas lui donner une signification particulière, cela signifie juste que c'est de la méta, c'est à dire des heuristiques sur des heuristiques.
  • C'est dans le contexte des algorithmes
  • Cela dépend toujours du contexte, d'une façon qui signifie que vous n'obtiendrez jamais de réponse claire, parce qu'ils ne sont pas en ligne droite définie. Dans IA cercles, une heuristique est une "bonne estimation" de la fonction utilisée comme un bloc de construction d'un plus grand (généralement à la recherche de l'algorithme. Une méta-heuristique est une sorte de "deviner" le système en lui-même qui continue de peaufiner ses suppositions. Mais c'est juste mon point de vue, ces choses sont si undefined que même les papiers de faire des évaluations comparatives des heuristiques vs méta-heuristiques, soit ne pas définir, ou d'offrir uniquement des définitions imprécises. En fait, vous savez lorsque vous voyez un.
  • Merci je comprends maintenant 😉
InformationsquelleAutor Nico Liu | 2012-05-04
  1. 35

    Vous pourriez penser à une heuristique comme un approximatif (pas d'approximation de la solution à un problème. La différence entre approximative et le rapprochement est que le premier est au sujet d'obtenir une bonne estimation de la solution d'un problème, mais que vous ne savez pas vraiment comment il est bon. La deuxième est une solution qui permet de prouver sa proximité à la solution optimale.

    Donc, les heuristiques sont souvent dépendante du problème, qui est, vous définissez une heuristique pour un problème donné. Métaheuristiques sont problème indépendant de techniques qui peuvent être appliquées à un large éventail de problèmes. Une heuristique est, par exemple, le choix d'un élément aléatoire pour le faire pivoter dans le Quicksort. Un metaheuristic ne connaît rien au problème, il sera appliqué, il peut traiter des fonctions comme des boîtes noires.

    On pourrait dire qu'une heuristique exploits dépendante du problème de l'information pour trouver un "suffisamment bonne" solution à un problème spécifique, tandis que les métaheuristiques sont, comme les modèles de conception générale algorithmique des idées qui peuvent être appliquées à un large éventail de problèmes.

    • Avez-vous aussi une source à ce sujet?
    • Il y a un excellent livre d'introduction à la méta-heuristiques par El-Ghazali Talbi. Il déclare plus ou moins de cette même opinion dans l'introduction. Check it out.
    • Donc, étant donné ce que vous avez dit, NSGAII est une méta-heuristique de l'algorithme, car il pourrait être applicable à de nombreux problèmes, même avec mon propre problème complexe, mais si j'écris mon propre algorithme exploiter mon propre problème complexe de l'information, cela signifie qu'il est un algorithme heuristique? Ai-je eu le sens et les différences? (Désolé pour les mauvais en anglais)
    • NSGAII est une variante de l'algorithme génétique, et donc généralement de problèmes indépendants. Comme Touki dit, une mise en œuvre spécifique d'une méta-heuristique (par opposition à l'abstraction de la mise en œuvre trouvée dans un livre) est également une méta-heuristique, même si vous devez prendre des décisions relatives à la représentation, les fonctions de coût, etc., qui sont souvent dépendante du problème. Encore, dans ce cas, vous êtes "instanciation" une méta-heuristique dans votre propre problème, comme pour le remplissage d'un modèle. La différence est que vous n'êtes pas exploiter les informations spécifiques à la structure du problème de la conception d'une solution.
    • Ok, donc, si l'algorithme est liée au problème par le biais des variables, des paramètres qui sont en quelque sorte partagé entre eux, nous ne sommes pas plus parler de méta-heuristiques. Est ce que le droit?
    • pas sûr si je comprends votre déclaration. Si l'algorithme exploite les informations (implicites ou explicites) sur la structure du problème qui n'est pas commun pour un large éventail d' (optimisation) des problèmes, puis de son spécifique heuristique. Comme je l'ai dit avant, les différences sont subtiles et la frontière est assez floue.
    • Mmmm, je vois, c'est le cas, l'algorithme pourrait être considéré comme une heuristique. Que faire si je vais modifier un méta-herustic (comme NSGAII) afin de le rendre auto-adaptative par le changement dynamique de son Opérateur de Mutation? Serait-il encore rester une méta-heuristique? (Il semble que ce sujet est proche de l'infini)
    • Oui, je pense qu'il serait tant qu'il conserve son applicabilité à un large éventail de problèmes d'optimisation. Il y a beaucoup d'auto-adaptation de la méta-heuristiques là, CMA-ES de cours de l'un au dessus de ma tête.

    InformationsquelleAutor Alejandro Piad
  2. 7

    Afin de donner un bon devis, par rapport à Alejandro réponse:

    « Un metaheuristic est un problème indépendant de la algorithmiques qui fournit un ensemble de lignes directrices ou des stratégies pour développer des heuristiques algorithmes d'optimisation [...] Un problème spécifique à la mise en œuvre d'une heuristique d'optimisation de l'algorithme selon les directives exprimées dans un metaheuristic cadre est aussi appelé un metaheuristic » (Sörensen, Glover sur http://scholarpedia.org/article/Metaheuristics)

    Être entièrement terminée. Nous devons faire la distinction entre exacte, approximative et heuristiques algorithmes. Exacte de l'algorithme trouve une solution exacte. Un algorithme approximatif devrait trouver une solution approximative, dans un délai acceptable, ainsi que son écart de gamme avec la prétendue solution optimale. Une heuristique tout simplement de trouver une solution acceptable, dans un délai acceptable.

    Par la voie, Alejandro quicksort l'exemple ne semble pas tout à fait suffisant pour deux ou trois raisons différentes.

    1. En fait, les heuristiques et métaheuristiques sont le cadre de l'optimisation du champ. Le problème qu'ils essaient de résoudre est donc de rechercher un optimum, pas de tri.
    2. Heuristiques sont généralement utiliser lorsque les problèmes que vous voulez aborder est trop complexe, dans le calcul du sens - ce qui n'est pas le cas de problème de tri.
    3. Ce qui est indiqué à travers l'exemple de quicksort, si je comprends bien, est l'élément aléatoire. En principe, vous pouvez avoir déterministe des heuristiques je n'ai jamais rencontré un déterministe métaheuristiques, mais probablement, on pourrait le code. 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.
    • Hum, je pense, une étoile est Un possible déterministe heuristiques ?
    • pour votre perspicace ajouts. Veux juste souligner que, même si un constipé exemple, vous pouvez formuler tri que de trouver la permutation qui minimise le nombre d'inversions. Avec cette formule, vous pouvez appliquer n'importe quelle combinatoire méta-heuristiques (par exemple, de Gaz ou de SA) pour le résoudre. Bien sûr, Quicksort fonctionnerait beaucoup mieux, car il exploite le problème de la structure. En ce sens, peut-être Quicksort lui-même peut être considéré comme une heuristique pour le problème du tri. Je sais, ce n'est pas utile de formulation dans la pratique, mais qui sert le but de signaler les différences.
    • Que d'un côté, voir Nelder-Mead comme un exemple d'un algorithme qui à mon humble avis peut être considéré comme un méta-heuristique (large applicabilité à un large éventail de boîte noire de problèmes d'optimisation), et son complètement déterministe. Est heuristique parce que, contraire-à-dire, la méthode Simple il ne garantit pas de converger vers l'optimum global.
    InformationsquelleAutor Touki
  3. 2

    Pour une explication détaillée, voir:

    Sörensen, K. (2015). Métaheuristiques—la métaphore exposés. Opérations internationales en Recherche Opérationnelle, 22(1), 3-18.

    Un metaheuristic est un problème indépendant de l'algorithmique
    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
    problème spécifique à la mise en œuvre d'un algorithme d'optimisation heuristique
    selon les directives exprimées dans un tel cadre (Sörensen,
    2015).

    Les heuristiques sont les lignes directrices, metaheurstics est le cadre qui les utilise.

    InformationsquelleAutor dorien