Signification des méthodes (méta) heuristiques

10
  1. Pour l'optimisation, à partir de Wikipedia :

    En informatique, la métaheuristique désigne une méthode informatique qui optimise un problème en essayant itérativement d'améliorer une solution candidate par rapport à une mesure de qualité donnée. Les métaheuristiques font peu ou pas d'hypothèses sur l'optimisation du problème et peuvent rechercher de très grands espaces de solutions candidates. Cependant, les métaheuristiques ne garantissent pas qu'une solution optimale soit jamais trouvée. De nombreuses métaheuristiques mettent en œuvre une certaine forme d'optimisation stochastique.

    D'autres termes ayant une signification similaire à celle de métaheuristique sont: sans dérivé, recherche directe, boîte noire, ou bien simplement optimiseur heuristique. Plusieurs livres et articles d'enquête ont été publiés sur le sujet.

    • Je me demande comment savoir si une méthode d'optimisation est métaheuristique ou non? Par exemple,

      (1) La méthode simplex pour la programmation linéaire est-elle métaheuristique?

      (2) La majorité des méthodes de programmation non linéaire telles que la descente de gradient, la méthode du multiplicateur lagrangien, les méthodes de pénalité, les méthodes ponctuelles intérieures (méthodes de barrière), sont-elles métaheuristiques?

      (3) Toutes les méthodes sans gradient, telles que la méthode Nelder-Mead ou la méthode simplex en descente, sont-elles métaheuristiques?

    • Quelles sont certaines méthodes d'optimisation qui ne sont pas métaheuristiques?

  2. Plus généralement (au-delà de l'optimisation) pour les techniques de résolution de problèmes, de Wikipedia :

    Heuristique fait référence aux techniques basées sur l'expérience pour la résolution de problèmes, l'apprentissage et la découverte . Lorsqu'une recherche exhaustive n'est pas pratique, des méthodes heuristiques sont utilisées pour accélérer le processus de recherche d'une solution satisfaisante. Des exemples de cette méthode incluent l'utilisation d'une règle empirique, d'une supposition éclairée, d'un jugement intuitif ou du bon sens.

    En termes plus précis, les heuristiques sont des stratégies utilisant des informations facilement accessibles, quoique peu applicables, pour contrôler la résolution de problèmes chez les êtres humains et les machines.

    Je me demande comment comprendre le sens de "heuristique"?

    • comment savoir si une technique de «résolution de problèmes, d'apprentissage et de découverte» est heuristique ou non?

    • Quelles sont certaines techniques de «résolution de problèmes, d'apprentissage et de découverte» qui ne sont pas heuristiques?

Merci et salutations!

Tim
la source

Réponses:

7

L'heuristique est quelque chose qui fonctionne dans de nombreux cas dans la pratique, bien qu'il n'y ait aucun argument détaillé pour expliquer pourquoi cela devrait bien fonctionner.

La métaheuristique n'est pas un algorithme mais un schéma heuristique général ou une idée qui peut être utilisée dans des algorithmes spécifiques.

Par exemple, l'algorithme simplex pour la programmation linéaire n'est ni heuristique ni métaheuristique, car il a une théorie de convergence bien établie. Le sqame est valable pour la programmation séquentielle quadtatique ou les méthodes de point intérieur. (Les méthodes de point intérieur sont un schéma général, mais pas heuristique et donc pas une métaheuristique, car il y a une théorie assez forte qui lui est associée.)

L'algorithme Nelder-Mead = downhill simplex pour minimiser une fonction est une heuristique (il peut en fait échouer sur des problèmes assez simples dans des dimensions plus élevées), et la recherche taboue est une métaheuristique (car de nombreux algorithmes divers peuvent être écrits qui utilisent la recherche taboue, mais sont par ailleurs de qualité assez différente.

Arnold Neumaier
la source
Merci! (1) Donc, dire si une méthode est métaheuristique, c'est voir si elle a une théorie sur le moment où elle converge vers le véritable optimiseur? Si une méthode n'a pas encore une telle théorie, est-ce alors meatheuristic? S'il y a un jour une théorie pour cela, deviendra-t-elle métaheuristique à non métaheuristique? (2) "D'autres termes ayant une signification similaire à celle de métaheuristique sont: sans dérivé, recherche directe, boîte noire, ou bien simplement optimiseur heuristique." Je me demande si la métaheuristique n'utilise que des valeurs de fonction et si elle n'est pas dérivée? Est-ce la méthode de "recherche" dans votre réponse à ma autre question?
Tim
@Tim: métaheuristique signifie: (i) pas de théorie de convergence, et (ii) pas de recette définitive pour procéder mais plutôt des principes généraux. - sans dérivé (= recherche directe = boîte noire; différents noms pour les mêmes de différentes racines historiques) peuvent être heuristiques ou non; il indique simplement l'entrée que l'utilisateur doit fournir.
Arnold Neumaier
Merci! Je me demande si la métaheuristique n'utilise que des valeurs de fonction et si elle n'est pas dérivée?
Tim
@Tim: Probablement oui; Je ne connais rien de réellement appelé métaheuristique qui utilise des gradients.
Arnold Neumaier
7

Je ne vais pas répéter sur simplex et Nelder-Mead puisque @ArnoldNeumaier a déjà donné une très bonne explication, mais je voulais ajouter mes 2 cents.

L'une des meilleures citations que j'ai entendues il y a quelque temps pour décrire la différence entre heuristique et métaheuristique: une heuristique est une assez bonne règle. Une métaheuristique est une assez bonne règle pour trouver de très bonnes règles.

Vous devriez simplement le voir comme un moyen de trouver de bonnes heuristiques pour des problèmes spécifiques; fondamentalement, si vous vous posez l'une des questions suivantes, vous parlez d'un métaheuristique:

  • Comment dois-je modifier les paramètres de cette heuristique pour améliorer les performances sur ce problème?
  • Cette heuristique est-elle meilleure que cette heuristique?

Il existe un grand nombre de métaheuristiques que vous pouvez utiliser pour la résolution de problèmes, l'apprentissage et la découverte , à savoir:

Je trouve que la plupart des métaheuristiques sont quelque peu inspirées par des phénomènes naturels, difficiles à expliquer rigoureusement, mais qui ont de bonnes propriétés de convergence.

Voici un bon lien si vous souhaitez en savoir plus sur certaines autres techniques métaheuristiques

Charles Menguy
la source
Merci! Je ne suis pas sûr de comprendre "Une heuristique est une assez bonne règle. Une métaheuristique est une assez bonne règle pour trouver de très bonnes règles." Par exemple, le recuit simulé, l'essaim de particules, la colonie de fourmis et la recherche taboue sont-ils heuristiques ou métaheuristiques? S'ils sont l'un des deux, quels sont leurs homologues de l'autre?
Tim
Ce que vous devez comprendre de cette citation, c'est que l'heuristique et la métaheuristique ne sont ni exactes ni prouvées, donc "assez bonne règle". Une métaheuristique est à un niveau supérieur à une heuristique, et c'est à travers plusieurs itérations successives que vous pouvez trouver un ensemble de paramètres qui résoudra correctement un problème. Si vous saviez ce qu'était cet ensemble de paramètres depuis le début, il vous suffirait d'écrire une heuristique pour résoudre le problème. Mais comme vous ne le savez pas, vous devez utiliser un algorithme pour trouver ces paramètres pour votre heuristique: une métaheuristique. J'espère que cela clarifie.
Charles Menguy
Et les algorithmes que j'ai donnés ici sont tous des métaheuristiques, et vous pouvez trouver plus de détails sur le lien que j'ai donné. Je ne sais pas exactement ce que vous voulez dire pour vos homologues.
Charles Menguy
Par homologues, je veux dire, par exemple, si les algorithmes sont tous des métaheuristiques, alors les heuristiques sur lesquelles ils opèrent doivent être eux-mêmes plus des valeurs spécifiques pour leurs paramètres ajustables?
Tim
Prenons par exemple le recuit simulé. Ce qu'il fait en fin de compte, c'est une recherche sur une chaîne de Markov. La "règle" de l'heuristique serait de supposer qu'un état de la chaîne de Markov est la solution. Ce que fait la métaheuristique, c'est qu'elle recherchera la convergence dans la chaîne de Markov pour trouver l'état optimal qui décrit la solution. En général, je pense que vous ne devriez pas trop essayer de faire la distinction: utilisez l'heuristique quand il existe une solution "relativement" simple qui peut être facilement calculée, et utilisez les métaheuristiques lorsque l'espace de la solution est trop grand et que vous devez être plus intelligent résoudre le problème.
Charles Menguy