survie du plus fort

[invitec35bc9ea]

Bonjour,
pour une fonction , je voudrais trouver les x,y,z et t qui minimisent f.
La méthode que j'ai choisi est une idée de moi ou je me suis inspiré des algorithmes génétiques.
Si, ça marche bien avec une fonction à un seul argument x, je suis confronté au problème d'explosion combinatoire au delà.
Je ne penses pas que je suis le premier à avoir pensé à cette méthode mais j'ai du mal à chercher la bonne info pour pallier à ce problème de combinatoire, voir ameliorer la methode.
Peut etre l'un de vous arriverai-t-il à mettre un nom sur cette approche:
prenons le cas ou x varie au cours du temps. f varie egalement mais je la connait à chaque instant. x0 est connu
à chaque pas de temps i:
1. je génère n valeurs au tour de x(i-1)
2. j'evalue f pour chaque valeur
3. je garde le x dont l'image par f est la plus petite

ceci ressemble au mecanisme de "selection" des algos G: la survie du plus fort
et fait abstraction des autres mecanismes: croisement, mutation...

Tel que je l'ai fait, pour une seule variable, le probleme est résolu à chaque pas de temps en un temps n ex:200
et pour p varibles en un temps ex:


quelqu'un saurait il donner un nom à cette methode?
quels mots clefs pourraient etre pertinents pour voir si quelqu'un a déja réalisé ce type de filtrage? comment on a résolu l'explosion combinatoire? a-t-on amelioré la mathode?

merci
-----

[invite986312212]

regarde la methode de Nelder & Mead.

[invitea6f35777]

Bonjour,

Moi j'aurais plutôt suggéré la méthode du recuit simulé (qui utilise la méthode de Monté Carlo) qui se rapproche plus de ce que tu veux faire. Elle consiste grosso modo à dire qu'en un point on connaît le gradient et donc la direction de plus forte pente. Si on cherche un maximum ou un minimum il peut être bien de voyager dans cette direction ou l'opposée. Maintenant, pour ne par rester piegés dans un extremum local il faut pouvoir s'écarter de façon aléatoire du point ou l'on se trouve en dosant pour ne pas non plus se retrouver n'importe où. Par rapport à ta méthode la différence c'est qu'une seule direction est choisie aléatoirement et il n'y a pas d'explosion combinatoire.

[invitec35bc9ea]

Bonjour,
avec la methode que j'ai cité, à chaque pas de temps, j'obtiens de minimum directement.
alors que la methode du simplex ou le recuit simulé sont des methodes iteratives.
Comme, je cherche le minimum à chaque pas de temps, j'aimerais eviter tant que possible toute methode iterative.

[A voir en vidéo sur Futura]

[invite986312212]

et bien si tu trouves une methode non iterative capable de trouver le minimum d une fonction quelconque, c est la gloire assuree.

[invitea6f35777]

Tes pas de temps sont équivalentes à des itérations gros malin Les itérations dans les méthodes proposées sont équivalentes à des générations successives dans ta méthode génétique.

Dans les différentes méthodes le temps est considéré comme une dimension comme les autres, une simple variable de ta fonction à plusieurs variables. Si tu n'utilise pas d'itération ta méthode consiste à tirer au hazard des points, calculer la fonction en ces points prendre la valeur la plus petite et dire que c'est le minimum. Sans étape supplémentaire cela ne donne rien sauf si en cas de gros coup de bol tu tombes sur le vrai minimum dans les points que tu as choisis aléatoirement (la probabilité de cet évènement se calcule facilement, c'est exactement 0)

[invitec35bc9ea]

et bien si tu trouves une methode non iterative capable de trouver le minimum d une fonction quelconque, c est la gloire assuree.

ça existe dans un autre contexte: http://www.math.zju.edu.cn/webpagene...2724941137.pdf

Tes pas de temps sont équivalentes à des itérations gros malin

non,
à chaque pas de temps, la fonction change, donc son minimum egalement, et je cherche à trouver le minimum à chaque pas de temps.
le pas de temps etant fixe. si la methode d'optim iterative lancée à l'instant t(i) deborde au dessus det(i+1), je vais sauter un pas de temps ou je ne vais pas calculer le minimum, ou du moins l'approximer.

[invitec35bc9ea]

Si tu n'utilise pas d'itération ta méthode consiste à tirer au hazard des points, calculer la fonction en ces points prendre la valeur la plus petite et dire que c'est le minimum.

Au hazard non,

1. je génère n valeurs au tour de x(i-1)

si je sais borner le taux de variation de x entre deux pas de temps, la nouvelle valeur de x(i) est forcement parmis les valeurs que j'ai generé

[invitea6f35777]

dans un autre contexte

c'est précisément pour cela que Ambrosio a dit

d une fonction quelconque

puisque dans des cas particuliers il peut y avoir effectivement des algorithmes non itératifs mais là tu t'attaque au cas général.

Ce que je n'ai pas saisi dans ton algorithme c'est si pour un pas de temps tu génère une ou plusieurs générations (dans tout algo génétique il y a plusieurs générations).

Pour moi un algo itératif c'est juste qu'il doit être répété (réitéré) et cela n'a rien à voir avec le temps. Tout algorithme génétique est forcément itératif par définition.

[invitec35bc9ea]

Ce que je n'ai pas saisi dans ton algorithme c'est si pour un pas de temps tu génère une ou plusieurs générations (dans tout algo génétique il y a plusieurs générations).

Je n'ai pas dit que je faisais des algos G, mais que je m'en suis inspiré. et pour répondre à ta question, je génère une seule génération.