Abstract FR:

La methode du recuit simule est une technique d'optimisation puissante et simple a mettre en uvre, qui a prouve son efficacite pour la recherche de solutions optimales ou proches de l'optimum dans de nombreuses applications pratiques. Mais, meme si l'on utilise des profils de recuit bien adaptes, le temps de calcul peut se reveler trop important. Plusieurs methodes de parallelisation de l'algorithme ont ete proposees, mais elles s'ecartent du comportement sequentiel de l'algorithme. Nous presentons une methode de parallelisation de l'algorithme du recuit simule independante du probleme, qui possede les memes qualites de convergence que l'algorithme sequentiel. Nous introduisons deux modes de parallelisation, suivant la valeur de la temperature, et nous modelisons analytiquement leur comportement, ce qui permet de prevoir l'acceleration de la methode quel que soit le probleme. Nous presentons en outre une architecture de processeur specialise qui permet d'accelerer l'execution de l'algorithme pour un probleme de placement simplifie. Les performances de l'algorithme parallele sont evaluees sur un probleme de placement simplifie a l'aide d'un reseau de transputers et les modeles ont ete compares aux resultats des experiences