heuristique ? C'est quoi?

salut matheux,

une heuristique, c'est une méthode "approchée" (=non exacte) permettant de résoudre divers problèmes, comme l'optimisation par exemple.

T'as pas une question plus précise ?.. un exemple ?..

je ne comprend pas non plus ta question la ?
toute les methode algorithmique de recherche d'optimum sont plus ou moins basé sur des aproximation succesivent non ?

Je vais essayer de préciser mon problème.

J'ai une fonction à optimiser, assez complexe, c'est pourquoi je ne l'expose pas, il faudrait introduire plusieurs notions spécifiques.
Cette fonction est non linéaire, non convexe et non concave, comme je l'ai précisé. La plupart des programmes non-linéaires peuvent se résoudre par des techniques genre descente du gradient (réduit, généralisé), points intérieurs,...

Ce sont des méthodes que j'appelle (à tort peut-être des méthodes exactes). D'autres méthodes d'optimisation font intervenir de "l'aléatoire" (recuit, algo génétique).

Ma question, formulée autrement et de manière plus restrictive:

-Y a-t-il des conditions spécifiques pour que les méthodes "classiques" (celles qui ne font pas intervenir d'aléatoire) puissent fonctionner?

Notamment, la convexité ou la concavité font-elles partie de ces conditions?

merci

Déjà, "optimiser une fonction" je ne sais pas ce que ça veut dire.

Apparemment tu fais du calcul numérique et je n'y connais strictement rien.

pour stokastik:

Par "opimiser une fonction", j'entends bien sûr chercher l'optimum de la fonction. C'est vrai que j'ai fais une maxi abus de language là!!

et oui c'est du calcul numérique...le problème, c'est que je m'y connais pas des masses là-dedans moi non plus...

merci quand même

Je suis justement sur le meme probleme en ce moment :


-La methode du gradient marche quelque soit ta fonction, a condition de bien choisir le coefcient par lequel tu multiplie le gradient avant de l'ajouter (et si tu peut te permettre d'optimiser ce coef alors ne t'en prive pas mais si ta fonction est vraiment compliqué c'est pas toujour possilbe...)


-les methode basé sur la methode de Newton, sont en general plus sensible et risque d'avantage de divergé si ta fonction est pas assez "propre"

-Levenberg-Marquardt euh... ba j'ai pas reussit a la mettre en oeuvre sur mon probleme donc j'en sais rien

Toutes ces methodes on un enorme defaut pour ce qui est des fonctions non convexe : elle risque de ne pas convergé vers le minima absolu, mais vers un minimam local le plus proche des conditions initial que tu choisira.

cependant ce n'est pas toujour vrai : moi par exemple je m'interesse a la position d'equilibre de n bille chargé ce deplacant a la surface d'une sphere ma fonction (l'energie potentielle electrique de mes billes) a de tres nombreux minima locaux mais ils doivent etre sufisement peu marqué pour que la methode du gradient ne converge JAMMAIS vers eux mais toujour vers le minima absolu...

cependant les methodes "newton-like" diverge assez grosièrement, (et les rare cas ou elle converge elle le font tres lentement car il se trouve que mon Hessien a un determinant nul au point d'equilibre... mais ceci est une autre histoire...)



je n'ai pas testé la methode du recuit sur mon probleme car elle est beaucoup trop lente (surtous quand on aproche du resultat...)  et j'ai deja une methode basé sur le PFD qui a a peu pres les meme caracteristiques... mais a priori avec ces methodes tu a l'assurance de toujour convergé vers le minimam absolu


pour ceux qui est des methodes "genetique" il me semblait qu'elle ne s'appliquait que sur des ensemble finit ? (type le probleme du voyageur de comerce) non ?


mais en regle general, le seul moyen c'est de tester les methodes et de regarder ce qui ce passe...

NB : si qqn a trouvé comment contourner le pb du Hessien nul sa m'interesse ^^

Merci pour ces précisions Ksilver

Je suis un peu dans ton cas, à savoir que ma fonction objective risque de comporter beaucoup d'optima locaux.

Je m'intéresse à minimiser une erreur de prédiction d'un modèle statistique. L'ennui est que dans mon cas, chaque observation est décrite par une matrice et non par un vecteur...

Pour la descente du gradient, effectivement, le choix du coeff est important. J'ai déjà pu le tester, j'avais choisi de petits coeff multiplicatifs (entre 0.1 et 0.3)..mais ça ne donne pas d'excellents résultats, et de plus les solutions obtenues étaient très variables...Avec des coeffs plus grands, c'était encore pire. Tu parles d'optimisation de ce coeff, j'ai jamais vu ça. Faut que je me renseigne.

Je pense que je vais tester le recuit simulé (facile à programmer). D'ailleurs, si t'as des références qui comparent différentes méthodes d'optimisation, ça m'intéresse, je n'en ai pas trouvé.

Pour les algo génétiques, le fait d'être sur un ensemble infini n'est pas un problème, la seule contrainte étant que l'arrêt de l'algo doit s'effectuer par un nombre préfixé d'itérations...

L'ennui dans toutes ces méthodes est que l'on est toujours contraints de choisir un ou plusieurs paramètres.

Merci en tout cas

pour l'optimisation du coeficient en gros sa consiste en :

tu a ta fonction F, et son gradient G en un point Xn donné, tu considere la fonction g de R -> R qui a alpha -> F(Xn+a*G)

tu peut chercher le minima de la fonction g par les methodes usuelle de minimisation de fonction sur R, ce minimum est evidement le meilleur coeficient que tu peut choisir pour ton gradient

maintenant etant donné que la fonction g est souvent assez moche elle meme la recherche de ce minima est souvent assez complexe mais pour certain fonction c'est extremement efficace...



une autre methode consiste a prendre comme coeficient (Gt*G)/(Gt*H*G), ou Gt est le gradient transposé et H le Hessien, sa revient a faire une iteration de la methode de newton "le long du gradient" (dans l'esprit de la methode precedente) evidement le calcule de ce coeficient est tres long, mais quand sa marche sa demande beaucoup moin d'iteration que la methode du gradient "de base" (ceci dit, avec mon probleme de Hessien dont le determinant tend vers 0 sa fonction pas tres bien chez moi, meme si sa me permet d'evaluer un coeficient intelligent... mais j'imagine que dans l'absolu sa doit pas trop mal marché)

euh evidement, quand je dis que c'est le "meilleur coeficient que tu peut choisir"... il faut refaire cette operation a chaque iteration (qui deviendront par contre tres peu nombreuse si tu arrive a mettre cela en place...)

Ok, mais ça à l'air d'augmenter carrément la complexité de l'algo (qui est déjà assez long).

Je vais voir tout ça et résoudre ces problèmes la semaine prochaine. En tout cas , merci beaucoup Ksilver!

sur mon probleme prendre Gt*G/(Gt*H*G) comme coeficient a plutot tendance a acceleré le temps neccesaire a ce raproché du minima au debut... apres sa ralentit serieusement mais sa doit etre a cause de probleme avec le Hessien...
en General ce que je fais c'est que je commence en prenant comme coeficient Gt*G/(Gt*H*G), je me raproche assez vite du minima, et une fois que la valeur de Gt*G/(Gt*H*G) est a peu pres stable j'arrete le calcule du coeficient et je remplace par une constante qui ressemble a cette valeur, c'est ce qui marche le mieux chez moi... mais la c'est du bidouillage a la main, qui marche plutot bien sur mon probleme mais qui est pas du tous une methode general d'optimisation.

bonne chance ^^

Bonjour,

Entre la methode heuristique et la méthode algorithmique, il y a aussi la methode heurithmique...

Sweet dreams are made of these...