Discussion:Métaheuristique

Pourquoi avoir nommé cela des métaheuristiques ? À ce que je lis dans l'article, il s'agit simplement d'heuristiques au sens le plus courant du terme. 212.198.57.89 1 oct 2004 à 00:44 (CEST)

C'est le terme consacré dans le milieu de la recherche. À l'origine on parlait de métaheuristiques (ou méta-heuristiques) pour des méthodes qui rassemblaient plusieurs heuristique. Le terme a maintenant une connotation un peu plus large, et fait généralement référence à des algorithmes stochastiques sans garantie de résultats. La plupart du temps ces méthodes sont utiles sur des problèmes d'optimisation difficile par opposition aux problèmes que l'on peut résoudre par des méthodes exactes ou des heuristiques. Une petite recherche sur Google sur métaheuristiques éclaircira le sujet. nojhan 1 oct 2004 à 12:28 (CEST)

Pourquoi ne pas le rajouter dans la définition

Cette éclairage de Nojhan sur la différence entre heuristique et métaheuristique est extrèmement instructive et me semble mériter d'être dans le corps de l'article. PCouderc

C'est chose faite. N☸Jhan 23 novembre 2005 à 11:44 (CET)

J'ai pris plaisir à lire cet article. Je me permets de faire quelques suggestions :

1. Attention à définir les concepts avant leur utilisation. Par exemple, qu'est ce qu'une recherche globale ou locale ?
2. Je connais les métaheuristiques à travers les problèmes inverses. Donc ma vision n'est surement que partielle et déformée. Le débat sur l'utilisation de ces méthodes dans mon domaine (elles sont assez en vogue), outre la mesure quantitative de la réalisation de la convergence, est la difficulté d'estimer l'erreur et la résolution associées.
3. Quel est l'influence de la dimension de l'espace de recherche (par ex. plusieurs dizaines) sur l'efficacité de ces méthodes ?
4. Il est écrit dans l'article que toutes les méthodes se valent plus ou moins. En pratique surement mais d'un point de vue théorique, la convergence peut etre démontrée mathématiquement pour certaines (par ex. recuit simulé) mais pas pour d'autres (par ex. algorithme génétique). Enfin je n'ai pas de référence sous la main et c'est un souvenir lointain de mes cours.
5. Il est vrai qu'il existe beaucoup de méthodes et qu'il est impossible de toutes les citer. Mais j'ai un faible pour le downhill simplex et les méthodes par tesselation progressive de l'espace de recherche.
   

En tout cas bel effort sur un sujet pas très facile. andre 16 février 2007 à 13:08 (CET)

Merci, n'hésitez pas à participer à la rédaction de l'article !

1. Bonne remarque, je vais tâcher d'améliorer ça.
2. Oui, les méthodologies de tests et de validations étaient le parent pauvre de la recherche dans le domaine, mais un mouvement général s'opère depuis quelques années dans le bon sens. Je vais tâcher de développer un peu cette partie, d'excellents articles et un livre sont parus récemment sur le sujet.
3. Très lourde. On peut considérer que maintenir une efficacité constante sur des problèmes à variables indépendantes consiste à garder la même densité d'échantillonnage. On a donc un problème de nombre de points en p^v, ce qui ne facilite pas l'utilisation. Maintenant, en pratique le nb de points peut être très réduit, en acceptant une dégradation des performances, en réglant au plus fin les paramètres, en ajoutant des informations sur le problème, etc. En pratique, je dirais que jusqu'à 100 variables, ça se règle sans trop de problème.
4. En fait, on peut démontrer la convergence pour à peu près n'importe quelle métaheuristique, avec juste plus ou moins de facilité (puisqu'en fait, c'est surtout l'ergodicité qui joue). Par contre, ce qui est vraiment difficile, c'est de donner une borne. Ceci étant dit, vu les problèmes sur lesquels on utilise les métaheuristiques, la convergence n'est pas forcément une condition à l'efficacité : savoir que l'algo se comportera au pire comme une recherche aléatoire ne nous dit pas s'il sera efficace en pratique.
5. Il ne reste qu'à écrire les articles, je propose : Simplexe de Nelder-Mead et Tesselation (optimisation) :-) nojhan→☸ 16 février 2007 à 20:48 (CET)

Proposition d'article de qualité refusée le 8 mars 2007

Cet article a été proposé comme article de qualité mais a été rejeté car ne satisfaisait pas les critères de sélection dans sa version du 8 mars 2007 (historique).
Si vous désirez reprendre l'article pour l'améliorer, vous trouverez les remarques que firent les wikipédiens dans la page de vote.

Merci pour cet article, après lecture j'aurai quelques "remarques"

Merci pour cet article, après lecture j'aurai quelques "remarques"

• Dans la rubrique "Voisinage" la notion n'est pas vraiment expliquée,

cela parle du fait que c'est utilisé, que c'est primordiale pour les combinatoires, etc.

• Dans la rubrique "Parcours et Population" le schéma et inversé par

rapport à l'explication dans le texte (et non la légende du schéma) cela peut mettre en erreur au départ. Le schéma parle en premier de population alors que le texte démarre avec le parcours.

Encore merci pour cet article et j'espère avoir apporté une "petite" idée d'amélioration

Élimination de liens rouges

J'ai pris aussi plaisir à lire cet article et comme il me semblait qu'il pouvait être éligible comme article de qualité si le nombre de liens rouges diminué, je me suis lancé dans la recherche d'article pouvant servir à combler cette lacune.

Cependant dans ma tentative de réduire le nombre de lien rouge, j'ai mis des redirections à partir des articles : Algorithme évolutionnaire vers Algorithme génétique et programmation évolutionnaire vers Programmation génétique, me basant pour cela sur l'introduction de Algorithme génétique: "Les algorithmes génétiques (parfois appelés algorithmes évolutionnaires) (...)". Cependant en continuant mes recherches sur Wikipedia je suis tomber sur cette article: Algorithme évolutif dont l'introduction m'a fait douté de mon choix. On ce qui concerne la redirection de programmation évolutionnaire vers Programmation génétique, je me suis dit, peut-être à tort, que la phrase d'introduction de Algorithme génétique pouvait tout aussi expliquer cette différence de vocabulaire. Alors les questions sont:

1. existe-t-il vraiment une distinction entre Algorithme génétique, Algorithme évolutionnaire et Algorithme évolutif?

si oui alors il serait bon de vérifier l'utilisation de ces mots dans l'article présent et modifier l'article Algorithme génétique, si non alors il serait bon de procéder à une fusion des articles concernés avec une redirection à partir des différents articles équivalant vers l'article Algorithme génétique.

1. Existe-t-il la même distinction entre Programmation évolutionnaire et Programmation génétique?

N'ayant pas le temps, ni les connaissances nécessaires, quelqu'un les ayant serait bien aimable d'y répondre fut le nombre d'occurrence dans l'article de Algorithme évolutionnaire. Autres questions :

1. N'est-il pas possible de définir optimum comme un extremum global de l'image d'une fonction? Dès lors on aurait un lien vers extremum qui existe déjà, ou bien pourrait-on faire pointer optimum sur Optimisation (mathématiques)?
2. Est le lien rouge pointant sur Discret ne pourrait-il pas plutôt pointer sur Mathématiques discrètes? Ou plutôt vers Point isolé?
3. Concernant le lien rouge Fonction objectif, que recouvre-t-il réellement?

Ces questions permettront je pense de contourner quelques impasses. Et je présente mes excuses à ceux qui penseront que j'aurais du tout d'abord poser ces questions avant de procéder aux redirections.

Lujan 4 juillet 2007 à 13:27 (CEST)

L'article devant servir de point d'entré est (en l'état) Algorithme évolutif, qui liste les différents groupes liés. Cependant, le renommage de "évolutionnaire" en "évolutif" parait certes plus correct en français, mais est trompeur. En effet, le terme anglais est "evolutionnary algorithm" et pas "evolving algorithm" pour une raison simple : l'algorithme n'évolue pas (il n'est donc pas "évolutif") mais a un rapport avec la théorie-de-l'évolution-des-espèces. Dans les faits, le terme "algorithme évolutif" est inexistant (à ma connaissance) dans la littérature spécialisée, où l'on trouve les termes "évolutionnaires" ou "évolutionnistes" (cf. les références françaises indiquées).

Sur le fond, si on veut être tout à fait strict, la classe des algorithmes évolutionnaires regroupe toutes les autres (algorithmes génétiques, programmation évolutionnaire, stratégies d'évolution et programmation évolutionnaire, historiquement tous des algos différents). Cependant, la différence est vraiment d'ordre historique aujourd'hui, puisque, dans chaque domaine, on importe allègrement des idées d'autres méthodes. Goldberg, par exemple, préfère parler d'algorithme génétique pour tous, puisque c'est le terme le plus connu, bien que les premiers algorithmes du genre furent les stratégies d'évolution.

Donc, au sens strict, l'intro sur les AG est trompeuse (de toute façon, l'article doit être repris, c'est le prochain sur ma liste). Cependant, je ne suis pas opposé à une fusion de tout ces articles en un seul, ça pourrait permettre une clarification... à discuter, sans doute.

Sur les autres questions :

1. « extremum global de l'image d'une fonction » : oui, très bien,
2. sur Mathématiques discrètes,
3. bonne question, il serait possible de faire un article sur la façon de formaliser des problèmes d'optimisation, mais je ne sais pas si c'est vraiment utile... on peut rediriger sur Optimisation (mathématiques) en attendant.

nojhan→☸ 9 août 2007 à 16:25 (CEST)

Merci pour ces éclaircissements,

J'ai fais les modifications 1,2 et 3. En ce qui concerne la proposition 3, le passage de l'introduction "la fonction f est appelée la fonction objectif" de définit parfaitement ce qu'est cette fonction, mais il est vrai que l'on a pas alors de lien direct, il faut chercher un peu l'information ... Une introduction plus courte et la transformation de la longue introduction de Optimisation (mathématiques) serait peut-être une bonne chose...

Je comprends tout à fait que ce soit plutôt des considérations d'ordre historique, de linguistique et un peu de mode qui soit en jeu dans la différentiation de "algorithme évolutionnaire" de "algorithme génétique". De la même manière on a la théorie de l'évolution qui s'est trouvée conforter par la découverte de la génétique ainsi que par les découvertes en génétique, et celle-ci renforce la compréhension de l'évolution. Et j'ai un peu l'impression aussi que "génétique" a une utilisation "effet de mode". Passons. Je pense que suivant tes explications 2 options sont d'ores et déjà possible:

1. faire pointer Algorithme évolutionnaire vers Algorithme évolutif et non pas vers Algorithme génétique,
2. faire en sorte que Algorithme évolutif redirige vers Algorithme évolutionnaire et que le contenu de Algorithme évolutif y apparaisse, pour celà:
   1. renommer "Algorithme évolutif" sous un autre nom (par ex "Algorithme évolutif 1")
   2. renommer "Algorithme évolutionnaire" en "Algorithme évolutif" et changer la redirection vers Algorithme évolutionnaire
   3. renommer "Algorithme évolutif 1" en "Algorithme évolutionnaire" et changer l'introduction en conséquence.

Il faut aussi alors supprimer le passage "(parfois appelés algorithmes évolutionnaires)" de l'introduction de Algorithme génétique.

Pour finir quelqu'un (et je ne suis pas volontaire désolé) devrait revoir soigneusement les différentes occurrences de Algorithme évolutionnaire, Algorithme évolutif et Algorithme génétique de l'article présent et s'assurer qu'il n'y est pas eut de confusion.

Lujan 10 août 2007 à 16:10 (CEST)