Recuit simulé

[Anonyme]

Bonjour,

Je dois implémenter le recuit simulé sur un problème de placement de
terminaux et de concentrateurs. Je veux essayer de relier de façon
optimale (i.e qui coute le moins cher possible) des concentrateurs à des
terminaux.

Je dois faire des tests sur cet algorithme, et le comparer au multistart
local search.

Je cherche donc un exemple qui me permet de comparer de façon
intelligente ces deux méthodes.
Par exemple dans un article du web, pour comparer le recuit simulé à la
relaxation lagrangienne, les auteurs ont fait des tests sur plusieurs
centaines de terminaux et ils ont trouvés que le recuit simulé était
plus efficace dans lorsque le nombre de terminaux était inférieur à 200.

Je voudrais trouver un exemple, le plus petit possible vu que c'est moi
qui devrait rentrer les valeurs, qui compare bien les deux méthodes.

Pour rappel, le principe des algos est le suivant :
but : minimiser une fonction (par exemple le cout d'installation des
terminaux)
recuit simulé : on part d'une solution, et on modifie quelques valeurs
pour donner une autre solution réalisable (par exemple le terminal1 qui
était relié au concentrateur2 est maintenant relié au concentrateur3).
Si la valeur de cette solution est inférieur à celle du début, on la
prend. Sinon, et c'est la tout l'intéret, suivant une proba on prend ou
non cette solution.
Le recuit accepte donc des "dégradations" de la solution, et au final
l'expérience montre qu'on arrive à une solution très proche de l'optimum.

multistart: on part d'une solution, on modifie le voisinage. Si cette
solution est meilleure que la précédente, on la prend. Le résultat final
dépend fortement de la solution de départ, donc on applique l'algo avec
différentes solutions de départ.

[Anonyme]

"Michelle" a écrit dans le message de news:
42389e3a$0$27999$626a14ce@news.free.fr...
> Bonjour,
>
> Je dois implémenter le recuit simulé sur un problème de placement de
> terminaux et de concentrateurs. Je veux essayer de relier de façon
> optimale (i.e qui coute le moins cher possible) des concentrateurs à des
> terminaux.
>
> Je dois faire des tests sur cet algorithme, et le comparer au multistart
> local search.
>
> Je cherche donc un exemple qui me permet de comparer de façon intelligente
> ces deux méthodes.
> Par exemple dans un article du web, pour comparer le recuit simulé à la
> relaxation lagrangienne, les auteurs ont fait des tests sur plusieurs
> centaines de terminaux et ils ont trouvés que le recuit simulé était plus
> efficace dans lorsque le nombre de terminaux était inférieur à 200.
>
> Je voudrais trouver un exemple, le plus petit possible vu que c'est moi
> qui devrait rentrer les valeurs, qui compare bien les deux méthodes.
>
> Pour rappel, le principe des algos est le suivant :
> but : minimiser une fonction (par exemple le cout d'installation des
> terminaux)
> recuit simulé : on part d'une solution, et on modifie quelques valeurs
> pour donner une autre solution réalisable (par exemple le terminal1 qui
> était relié au concentrateur2 est maintenant relié au concentrateur3). Si
> la valeur de cette solution est inférieur à celle du début, on la prend.
> Sinon, et c'est la tout l'intéret, suivant une proba on prend ou non cette
> solution.
> Le recuit accepte donc des "dégradations" de la solution, et au final
> l'expérience montre qu'on arrive à une solution très proche de l'optimum.
>
> multistart: on part d'une solution, on modifie le voisinage. Si cette
> solution est meilleure que la précédente, on la prend. Le résultat final
> dépend fortement de la solution de départ, donc on applique l'algo avec
> différentes solutions de départ.

Je vois que vous n'avez toujours pas de réponse...
Je pense que ce forum n'est guère approprié...
Personnellement, je ne connaissais pas ces méthodes d'optimisation.
J'avais eu connaissance de la méthode dite par "essaims particulaires".
Je viens de chercher par Google des renseignements sur vos deux méthodes.
Elles ont été appliquées semble-t-il au problème du voyageur de commerce.
Mais je ne vois pas bien votre problème, le genre d'exemple que vous
voulez...

A.J.