Spelling suggestions: "subject:"[een] BILEVEL OPTIMIZATION"" "subject:"[enn] BILEVEL OPTIMIZATION""
21 |
Traffic prediction and bilevel network designMorin, Léonard Ryo 01 1900 (has links)
Cette thèse porte sur la modélisation du trafic dans les réseaux routiers et comment celle-ci est intégrée dans des modèles d'optimisation. Ces deux sujets ont évolué de manière plutôt disjointe: le trafic est prédit par des modèles mathématiques de plus en plus complexes, mais ce progrès n'a pas été incorporé dans les modèles de design de réseau dans lesquels les usagers de la route jouent un rôle crucial. Le but de cet ouvrage est d'intégrer des modèles d'utilités aléatoires calibrés avec de vraies données dans certains modèles biniveaux d'optimisation et ce, par une décomposition de Benders efficace. Cette décomposition particulière s'avère être généralisable par rapport à une grande classe de problèmes communs dans la litérature et permet d'en résoudre des exemples de grande taille.
Le premier article présente une méthodologie générale pour utiliser des données GPS d'une flotte de véhicules afin d'estimer les paramètres d'un modèle de demande dit recursive logit. Les traces GPS sont d'abord associées aux liens d'un réseau à l'aide d'un algorithme tenant compte de plusieurs facteurs. Les chemins formés par ces suites de liens et leurs caractéristiques sont utilisés afin d'estimer les paramètres d'un modèle de choix. Ces paramètres représentent la perception qu'ont les usagers de chacune de ces caractéristiques par rapport au choix de leur chemin. Les données utilisées dans cet article proviennent des véhicules appartenant à plusieurs compagnies de transport opérant principalement dans la région de Montréal.
Le deuxième article aborde l'intégration d'un modèle de choix de chemin avec utilités aléatoires dans une nouvelle formulation biniveau pour le problème de capture de flot de trafic. Le modèle proposé permet de représenter différents comportements des usagers par rapport à leur choix de chemin en définissant les utilités d'arcs appropriées. Ces utilités sont stochastiques ce qui contribue d'autant plus à capturer un comportement réaliste des usagers. Le modèle biniveau est rendu linéaire à travers l'ajout d'un terme lagrangien basé sur la dualité forte et ceci mène à une décomposition de Benders particulièrement efficace. Les expériences numériques sont principalement menés sur un réseau représentant la ville de Winnipeg ce qui démontre la possibilité de résoudre des problèmes de taille relativement grande.
Le troisième article démontre que l'approche du second article peut s'appliquer à une forme particulière de modèles biniveaux qui comprennent plusieurs problèmes différents. La décomposition est d'abord présentée dans un cadre général, puis dans un contexte où le second niveau du modèle biniveau est un problème de plus courts chemins. Afin d'établir que ce contexte inclut plusieurs applications, deux applications distinctes sont adaptées à la forme requise: le transport de matières dangeureuses et la capture de flot de trafic déterministe. Une troisième application, la conception et l'établissement de prix de réseau simultanés, est aussi présentée de manière similaire à l'Annexe B de cette thèse. / The subject of this thesis is the modeling of traffic in road networks and its integration in optimization models. In the literature, these two topics have to a large extent evolved independently: traffic is predicted more accurately by increasingly complex mathematical models, but this progress has not been incorporated in network design models where road users play a crucial role. The goal of this work is to integrate random utility models calibrated with real data into bilevel optimization models through an efficient Benders decomposition. This particular decomposition generalizes to a wide class of problems commonly found in the literature and can be used to solved large-scale instances.
The first article presents a general methodology to use GPS data gathered from a fleet of vehicles to estimate the parameters of a recursive logit demand model. The GPS traces are first matched to the arcs of a network through an algorithm taking into account various factors. The paths resulting from these sequences of arcs, along with their characteristics, are used to estimate parameters of a choice model. The parameters represent users' perception of each of these characteristics in regards to their path choice behaviour. The data used in this article comes from trucks used by a number of transportation companies operating mainly in the Montreal region.
The second article addresses the integration of a random utility maximization model in a new bilevel formulation for the general flow capture problem. The proposed model allows for a representation of different user behaviors in regards to their path choice by defining appropriate arc utilities. These arc utilities are stochastic which further contributes in capturing real user behavior. This bilevel model is linearized through the inclusion of a Lagrangian term based on strong duality which paves the way for a particularly efficient Benders decomposition. The numerical experiments are mostly conducted on a network representing the city of Winnipeg which demonstrates the ability to solve problems of a relatively large size.
The third article illustrates how the approach used in the second article can be generalized to a particular form of bilevel models which encompasses many different problems. The decomposition is first presented in a general setting and subsequently in a context where the lower level of the bilevel model is a shortest path problem. In order to demonstrate that this form is general, two distinct applications are adapted to fit the required form: hazmat transportation network design and general flow capture. A third application, joint network design and pricing, is also similarly explored in Appendix B of this thesis.
|
22 |
Model-based hyperparameter optimizationCrouther, Paul 04 1900 (has links)
The primary goal of this work is to propose a methodology for discovering hyperparameters.
Hyperparameters aid systems in convergence when well-tuned and handcrafted. However,
to this end, poorly chosen hyperparameters leave practitioners in limbo, between concerns
with implementation or improper choice in hyperparameter and system configuration. We
specifically analyze the choice of learning rate in stochastic gradient descent (SGD), a popular
algorithm. As a secondary goal, we attempt the discovery of fixed points using smoothing of
the loss landscape by exploiting assumptions about its distribution to improve the update
rule in SGD. Smoothing of the loss landscape has been shown to make convergence possible in
large-scale systems and difficult black-box optimization problems. However, we use stochastic
value gradients (SVG) to smooth the loss landscape by learning a surrogate model and then
backpropagate through this model to discover fixed points on the real task SGD is trying to
solve. Additionally, we construct a gym environment for testing model-free algorithms, such
as Proximal Policy Optimization (PPO) as a hyperparameter optimizer for SGD. For tasks,
we focus on a toy problem and analyze the convergence of SGD on MNIST using model-free
and model-based reinforcement learning methods for control. The model is learned from
the parameters of the true optimizer and used specifically for learning rates rather than for
prediction. In experiments, we perform in an online and offline setting. In the online setting,
we learn a surrogate model alongside the true optimizer, where hyperparameters are tuned
in real-time for the true optimizer. In the offline setting, we show that there is more potential
in the model-based learning methodology than in the model-free configuration due to this
surrogate model that smooths out the loss landscape and makes for more helpful gradients
during backpropagation. / L’objectif principal de ce travail est de proposer une méthodologie de découverte des hyperparamètres.
Les hyperparamètres aident les systèmes à converger lorsqu’ils sont bien réglés et
fabriqués à la main. Cependant, à cette fin, des hyperparamètres mal choisis laissent les praticiens
dans l’incertitude, entre soucis de mise en oeuvre ou mauvais choix d’hyperparamètre et
de configuration du système. Nous analysons spécifiquement le choix du taux d’apprentissage
dans la descente de gradient stochastique (SGD), un algorithme populaire. Comme objectif
secondaire, nous tentons de découvrir des points fixes en utilisant le lissage du paysage des
pertes en exploitant des hypothèses sur sa distribution pour améliorer la règle de mise à jour
dans SGD. Il a été démontré que le lissage du paysage des pertes rend la convergence possible
dans les systèmes à grande échelle et les problèmes difficiles d’optimisation de la boîte noire.
Cependant, nous utilisons des gradients de valeur stochastiques (SVG) pour lisser le paysage
des pertes en apprenant un modèle de substitution, puis rétropropager à travers ce modèle
pour découvrir des points fixes sur la tâche réelle que SGD essaie de résoudre. De plus, nous
construisons un environnement de gym pour tester des algorithmes sans modèle, tels que
Proximal Policy Optimization (PPO) en tant qu’optimiseur d’hyperparamètres pour SGD.
Pour les tâches, nous nous concentrons sur un problème de jouet et analysons la convergence
de SGD sur MNIST en utilisant des méthodes d’apprentissage par renforcement sans modèle
et basées sur un modèle pour le contrôle. Le modèle est appris à partir des paramètres du
véritable optimiseur et utilisé spécifiquement pour les taux d’apprentissage plutôt que pour
la prédiction. Dans les expériences, nous effectuons dans un cadre en ligne et hors ligne.
Dans le cadre en ligne, nous apprenons un modèle de substitution aux côtés du véritable
optimiseur, où les hyperparamètres sont réglés en temps réel pour le véritable optimiseur.
Dans le cadre hors ligne, nous montrons qu’il y a plus de potentiel dans la méthodologie
d’apprentissage basée sur un modèle que dans la configuration sans modèle en raison de ce
modèle de substitution qui lisse le paysage des pertes et crée des gradients plus utiles lors de
la rétropropagation.
|
Page generated in 0.0415 seconds