Estimation of Noisy Cost Functions by Conventional and Adjusted Simulated Annealing Techniques
Thèse ou mémoire
2018-03 (octroi du grade: 2018-05-10)
Auteur·e·s
Directeur·trice·s de recherche
Cycle d'études
MaîtriseProgramme
InformatiqueMots-clés
- Optimization
- Simulated annealing
- Noisy simulated annealing
- Random noise
- Convergence speed
- Acceptance functions
- Discrete optimization
- Optimisation
- Recuit simulé
- Recuit simulé bruité
- Bruit aléatoire
- Fonctions d'acceptation
- Vitesse de convergence
- Optimisation discrète
- Applied Sciences - Operations Research / Sciences appliqués et technologie - Recherche opérationnelle (UMI : 0796)
Résumé·s
L'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. The 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.
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Il peut être utilisé dans le cadre d'une utilisation équitable et non commerciale, à des fins d'étude privée ou de recherche, de critique ou de compte-rendu comme le prévoit la Loi. Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.