Signification des méthodes (méta) heuristiques

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!

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.

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:

• Recuit simulé : j'ai utilisé celui-ci dans un problème pour optimiser le placement des composants connectés sur une grille afin de minimiser le coût total de connexion par exemple.
• Essaim de particules
• Colonie de fourmis
• Recherche tabou

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