Show item record

dc.contributor.advisorBastin, Fabian
dc.contributor.authorAbodinar, Laila
dc.date.accessioned2019-03-05T20:26:01Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2019-03-05T20:26:01Z
dc.date.issued2018-05-10
dc.date.submitted2018-03
dc.identifier.urihttp://hdl.handle.net/1866/21465
dc.subjectOptimizationfr
dc.subjectSimulated annealingfr
dc.subjectNoisy simulated annealingfr
dc.subjectRandom noisefr
dc.subjectConvergence speedfr
dc.subjectAcceptance functionsfr
dc.subjectDiscrete optimizationfr
dc.subjectOptimisationfr
dc.subjectRecuit simuléfr
dc.subjectRecuit simulé bruitéfr
dc.subjectBruit aléatoirefr
dc.subjectFonctions d'acceptationfr
dc.subjectVitesse de convergencefr
dc.subjectOptimisation discrètefr
dc.subject.otherApplied Sciences - Operations Research / Sciences appliqués et technologie - Recherche opérationnelle (UMI : 0796)fr
dc.titleEstimation of Noisy Cost Functions by Conventional and Adjusted Simulated Annealing Techniquesfr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sfr
etd.degree.nameM. Sc.fr
dcterms.abstractL'algorithme de recuit simulé est largement utilisé dans la communauté d'optimisation pour résoudre divers types de problèmes, discrets et continus. L'objectif de cette thèse est d'analyser le recuit simulé dans des environnements déterministes et stochastiques pour des problèmes discrets. Les objectifs précis sont de classer des problèmes clés, d'offrir des suggestions et des recommandations à suivre en utilisant l'algorithme de recuit simulé et de recuit simulé sous bruit. Plus spécifiquement, des problèmes apparaissent en optimisation en présence de bruit, et sur la manière de le contrôler. Nous proposons la méthode de recuit simulé bruité (NSA: Noisy Simulated Annealing), basée sur la modification de l'algorithme de Metropolis-Hastings présentée par Ceperlay and Dewing, qui surpasse les techniques de recuit simulé analogues, délivrant des solutions numériques similaires, à coût réduit. Nous considérons les principales approches qui traitent le bruit dans le cadre du recuit simulé afin d'en extraire leurs attributs distinctifs et de produire une comparaison plus pertinente. Nous évaluons ensuite les performances numériques de l'approche sur des instances du problème du voyageur de commerce. Les résultats obtenus montrent un clair avantage pour le recuit simulé bruité, en présence de bruit.fr
dcterms.abstractThe Simulated Annealing (SA) algorithm is extensively used in the optimization community for solving various kinds of problems, discrete and continuous. This thesis aims to analyze SA in both deterministic and stochastic environments for discrete problems. Precise objectives are to classify key problems, offer suggestions and recommendations to be undertaken by using SA and Simulated Annealing Under Noise (SAUN). More specifically, problems appear in optimization due to the existence of noise when evaluating the objective function, and how to control this noise. We propose a method, called Noisy Simulated Annealing (NSA), based on the Metropolis-Hasting algorithm modification presented by Ceperlay and Dewing, that outperforms analogous SA techniques, delivering similar numerical solutions, at a reduced cost. We consider the main approaches in the SA setting that handle noise in order to extract their distinctive attributes and make the comparison more relevant. We next assess the numerical performance of the approach on traveling salesman problem instances. The outcomes of our tests show a clear advantage for NSA when solving different problems to get high-quality solutions in presence of noise.fr
dcterms.languageengfr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record