10 resultados para Global optimization, unconstrained optimization, constrained optimization
em Universit
Resumo:
Le problme de tarification qui nous intresse ici consiste maximiser le revenu gnr par les usagers d'un rseau de transport. Pour se rendre leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractrise (aux yeux de l'usager) par sa "dsutilit", une mesure de longueur gnralise tenant compte la fois des tarifs et des autres cots associs son utilisation. Ce problme a surtout t abord sous une modlisation dterministe de la demande selon laquelle seules des routes de dsutilit minimale se voient attribuer une mesure positive de flot. Le modle dterministe se prte bien une rsolution globale, mais pche par manque de ralisme. Nous considrons ici une extension probabiliste de ce modle, selon laquelle les usagers d'un rseau sont allous aux routes d'aprs un modle de choix discret logit. Bien que le problme de tarification qui en rsulte est non linaire et non convexe, il conserve nanmoins une forte composante combinatoire que nous exploitons des fins algorithmiques. Notre contribution se rpartit en trois articles. Dans le premier, nous abordons le problme d'un point de vue thorique pour le cas avec une paire origine-destination. Nous dveloppons une analyse de premier ordre qui exploite les proprits analytiques de l'affectation logit et dmontrons la validit de rgles de simplification de la topologie du rseau qui permettent de rduire la dimension du problme sans en modifier la solution. Nous tablissons ensuite l'unimodalit du problme pour une vaste gamme de topologies et nous gnralisons certains de nos rsultats au problme de la tarification d'une ligne de produits. Dans le deuxime article, nous abordons le problme d'un point de vue numrique pour le cas avec plusieurs paires origine-destination. Nous dveloppons des algorithmes qui exploitent l'information locale et la parent des formulations probabilistes et dterministes. Un des rsultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modles combinatoires dans l'approximation du revenu logit. Nos essais numriques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisime article, nous considrons l'extension du problme une demande htrogne. L'affectation de la demande y est donne par un modle de choix discret logit mixte o la sensibilit au prix d'un usager est alatoire. Sous cette modlisation, l'expression du revenu n'est pas analytique et ne peut tre value de faon exacte. Cependant, nous dmontrons que l'utilisation d'approximations non linaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modle, par le biais d'une interprtation conomique, et examinons plus particulirement la contribution au revenu des diffrents groupes d'usagers.
Resumo:
Les mtaheuristiques sont trs utilises dans le domaine de l'optimisation discrte. Elles permettent dobtenir une solution de bonne qualit en un temps raisonnable, pour des problmes qui sont de grande taille, complexes, et difficiles rsoudre. Souvent, les mtaheuristiques ont beaucoup de paramtres que lutilisateur doit ajuster manuellement pour un problme donn. L'objectif d'une mtaheuristique adaptative est de permettre l'ajustement automatique de certains paramtres par la mthode, en se basant sur linstance rsoudre. La mtaheuristique adaptative, en utilisant les connaissances pralables dans la comprhension du problme, des notions de l'apprentissage machine et des domaines associs, cre une mthode plus gnrale et automatique pour rsoudre des problmes. Loptimisation globale des complexes miniers vise tablir les mouvements des matriaux dans les mines et les flux de traitement afin de maximiser la valeur conomique du systme. Souvent, en raison du grand nombre de variables entires dans le modle, de la prsence de contraintes complexes et de contraintes non-linaires, il devient prohibitif de rsoudre ces modles en utilisant les optimiseurs disponibles dans lindustrie. Par consquent, les mtaheuristiques sont souvent utilises pour loptimisation de complexes miniers. Ce mmoire amliore un procd de recuit simul dvelopp par Goodfellow & Dimitrakopoulos (2016) pour loptimisation stochastique des complexes miniers stochastiques. La mthode dveloppe par les auteurs ncessite beaucoup de paramtres pour fonctionner. Un de ceux-ci est de savoir comment la mthode de recuit simul cherche dans le voisinage local de solutions. Ce mmoire implmente une mthode adaptative de recherche dans le voisinage pour amliorer la qualit d'une solution. Les rsultats numriques montrent une augmentation jusqu' 10% de la valeur de la fonction conomique.
Resumo:
Les centres dappels sont des lments cls de presque nimporte quelle grande organisation. Le problme de gestion du travail a reu beaucoup dattention dans la littrature. Une formulation typique se base sur des mesures de performance sur un horizon infini, et le problme daffectation dagents est habituellement rsolu en combinant des mthodes doptimisation et de simulation. Dans cette thse, nous considrons un problme daffection dagents pour des centres dappels soumis a des contraintes en probabilit. Nous introduisons une formulation qui exige que les contraintes de qualit de service (QoS) soient satisfaites avec une forte probabilit, et dfinissons une approximation de ce problme par moyenne chantillonnale dans un cadre de comptences multiples. Nous tablissons la convergence de la solution du problme approximatif vers celle du problme initial quand la taille de lchantillon croit. Pour le cas particulier o tous les agents ont toutes les comptences (un seul groupe dagents), nous concevons trois mthodes doptimisation bases sur la simulation pour le problme de moyenne chantillonnale. tant donn un niveau initial de personnel, nous augmentons le nombre dagents pour les priodes o les contraintes sont violes, et nous diminuons le nombre dagents pour les priodes telles que les contraintes soient toujours satisfaites aprs cette rduction. Des expriences numriques sont menes sur plusieurs modles de centre dappels faible occupation, au cours desquelles les algorithmes donnent de bonnes solutions, i.e. la plupart des contraintes en probabilit sont satisfaites, et nous ne pouvons pas rduire le personnel dans une priode donne sont introduire de violation de contraintes. Un avantage de ces algorithmes, par rapport dautres mthodes, est la facilit dimplmentation.
Resumo:
Lapprentissage supervis de rseaux hirarchiques grande chelle connat prsentement un succs fulgurant. Malgr cette effervescence, lapprentissage non-supervis reprsente toujours, selon plusieurs chercheurs, un lment cl de lIntelligence Artificielle, o les agents doivent apprendre partir dun nombre potentiellement limit de donnes. Cette thse sinscrit dans cette pense et aborde divers sujets de recherche lis au problme destimation de densit par lentremise des machines de Boltzmann (BM), modles graphiques probabilistes au coeur de lapprentissage profond. Nos contributions touchent les domaines de lchantillonnage, lestimation de fonctions de partition, loptimisation ainsi que lapprentissage de reprsentations invariantes. Cette thse dbute par lexposition dun nouvel algorithme d'chantillonnage adaptatif, qui ajuste (de fa con automatique) la temprature des chanes de Markov sous simulation, afin de maintenir une vitesse de convergence leve tout au long de lapprentissage. Lorsquutilis dans le contexte de lapprentissage par maximum de vraisemblance stochastique (SML), notre algorithme engendre une robustesse accrue face la slection du taux dapprentissage, ainsi quune meilleure vitesse de convergence. Nos rsultats sont prsent es dans le domaine des BMs, mais la mthode est gnrale et applicable lapprentissage de tout modle probabiliste exploitant lchantillonnage par chanes de Markov. Tandis que le gradient du maximum de vraisemblance peut-tre approxim par chantillonnage, lvaluation de la log-vraisemblance ncessite un estim de la fonction de partition. Contrairement aux approches traditionnelles qui considrent un modle donn comme une bote noire, nous proposons plutt dexploiter la dynamique de lapprentissage en estimant les changements successifs de log-partition encourus chaque mise jour des paramtres. Le problme destimation est reformul comme un problme dinfrence similaire au filtre de Kalman, mais sur un graphe bi-dimensionnel, o les dimensions correspondent aux axes du temps et au paramtre de temprature. Sur le thme de loptimisation, nous prsentons galement un algorithme permettant dappliquer, de manire efficace, le gradient naturel des machines de Boltzmann comportant des milliers dunits. Jusqu prsent, son adoption tait limite par son haut cot computationel ainsi que sa demande en mmoire. Notre algorithme, Metric-Free Natural Gradient (MFNG), permet dviter le calcul explicite de la matrice dinformation de Fisher (et son inverse) en exploitant un solveur linaire combin un produit matrice-vecteur efficace. Lalgorithme est prometteur: en terme du nombre dvaluations de fonctions, MFNG converge plus rapidement que SML. Son implmentation demeure malheureusement inefficace en temps de calcul. Ces travaux explorent galement les mcanismes sous-jacents lapprentissage de reprsentations invariantes. cette fin, nous utilisons la famille de machines de Boltzmann restreintes spike & slab (ssRBM), que nous modifions afin de pouvoir modliser des distributions binaires et parcimonieuses. Les variables latentes binaires de la ssRBM peuvent tre rendues invariantes un sous-espace vectoriel, en associant chacune delles, un vecteur de variables latentes continues (dnommes slabs). Ceci se traduit par une invariance accrue au niveau de la reprsentation et un meilleur taux de classification lorsque peu de donnes tiquetes sont disponibles. Nous terminons cette thse sur un sujet ambitieux: lapprentissage de reprsentations pouvant sparer les facteurs de variations prsents dans le signal dentre. Nous proposons une solution base de ssRBM bilinaire (avec deux groupes de facteurs latents) et formulons le problme comme lun de pooling dans des sous-espaces vectoriels complmentaires.
Resumo:
La survie des rseaux est un domaine d'tude technique trs intressant ainsi qu'une proccupation critique dans la conception des rseaux. Compte tenu du fait que de plus en plus de donnes sont transportes travers des rseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des rseaux consistent fournir une capacit supplmentaire dans un rseau et racheminer les flux automatiquement autour de la panne en utilisant cette disponibilit de capacit. Cette thse porte sur la conception de rseaux optiques intgrant des techniques de survie qui utilisent des schmas de protection bass sur les p-cycles. Plus prcisment, les p-cycles de protection par chemin sont exploits dans le contexte de pannes sur les liens. Notre tude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opration pour l'ensemble des requtes sont dfinis a priori. La majorit des travaux existants utilisent des heuristiques ou des mthodes de rsolution ayant de la difficult rsoudre des instances de grande taille. L'objectif de cette thse est double. D'une part, nous proposons des modles et des mthodes de rsolution capables d'aborder des problmes de plus grande taille que ceux dj prsents dans la littrature. D'autre part, grce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de gnration de colonnes, celle-ci tant adquate pour rsoudre des problmes de programmation linaire de grande taille. Dans ce projet, la gnration de colonnes est utilise comme une faon intelligente d'numrer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problme matre et le problme auxiliaire ainsi qu'un premier algorithme de gnration de colonnes pour la conception de rseaux proteges par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les mthodes existantes. Par la suite, une formulation plus compacte est propose pour le problme auxiliaire. De plus, nous prsentons une nouvelle mthode de dcomposition hirarchique qui apporte une grande amlioration de l'efficacit globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux mthodes heurisiques qui arrivent trouver des bonnes solutions. Nous nous attardons aussi une comparaison systmatique entre les p-cycles et les schmas classiques de protection partage. Nous effectuons donc une comparaison prcise en utilisant des formulations unifies et bases sur la gnration de colonnes pour obtenir des rsultats de bonne qualit. Par la suite, nous valuons empiriquement les versions oriente et non-oriente des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scnarios de trafic asymtrique. Nous montrons quel est le cot de protection additionnel engendr lorsque des systmes bidirectionnels sont employs dans de tels scnarios. Finalement, nous tudions une formulation de gnration de colonnes pour la conception de rseaux avec des p-cycles en prsence d'exigences de disponibilit et nous obtenons des premires bornes infrieures pour ce problme.
Resumo:
Lathrosclrose est une maladie qui cause, par laccumulation de plaques lipidiques, le durcissement de la paroi des artres et le rtrcissement de la lumire. Ces lsions sont gnralement localises sur les segments artriels coronariens, carotidiens, aortiques, rnaux, digestifs et priphriques. En ce qui concerne latteinte priphrique, celle des membres infrieurs est particulirement frquente. En effet, la svrit de ces lsions artrielles est souvent value par le degr dune stnose (rduction >50 % du diamtre de la lumire) en angiographie, imagerie par rsonnance magntique (IRM), tomodensitomtrie ou chographie. Cependant, pour planifier une intervention chirurgicale, une reprsentation gomtrique artrielle 3D est notamment prfrable. Les mthodes dimagerie par coupe (IRM et tomodensitomtrie) sont trs performantes pour gnrer une imagerie tridimensionnelle de bonne qualit mais leurs utilisations sont dispendieuses et invasives pour les patients. Lchographie 3D peut constituer une avenue trs prometteuse en imagerie pour la localisation et la quantification des stnoses. Cette modalit dimagerie offre des avantages distincts tels la commodit, des cots peu levs pour un diagnostic non invasif (sans irradiation ni agent de contraste nphrotoxique) et aussi loption danalyse en Doppler pour quantifier le flux sanguin. tant donn que les robots mdicaux ont dj t utiliss avec succs en chirurgie et en orthopdie, notre quipe a conu un nouveau systme robotique dchographie 3D pour dtecter et quantifier les stnoses des membres infrieurs. Avec cette nouvelle technologie, un radiologue fait lapprentissage manuel au robot dun balayage chographique du vaisseau concern. Par la suite, le robot rpte trs haute prcision la trajectoire apprise, contrle simultanment le processus dacquisition dimages chographiques un pas dchantillonnage constant et conserve de faon scuritaire la force applique par la sonde sur la peau du patient. Par consquent, la reconstruction dune gomtrie artrielle 3D des membres infrieurs partir de ce systme pourrait permettre une localisation et une quantification des stnoses trs grande fiabilit. Lobjectif de ce projet de recherche consistait donc valider et optimiser ce systme robotis dimagerie chographique 3D. La fiabilit dune gomtrie reconstruite en 3D partir dun systme rfrentiel robotique dpend beaucoup de la prcision du positionnement et de la procdure de calibration. De ce fait, la prcision pour le positionnement du bras robotique fut value travers son espace de travail avec un fantme spcialement conu pour simuler la configuration des artres des membres infrieurs (article 1 - chapitre 3). De plus, un fantme de fils croiss en forme de Z a t conu pour assurer une calibration prcise du systme robotique (article 2 - chapitre 4). Ces mthodes optimales ont t utilises pour valider le systme pour lapplication clinique et trouver la transformation qui convertit les coordonnes de limage chographique 2D dans le rfrentiel cartsien du bras robotis. partir de ces rsultats, tout objet balay par le systme robotique peut tre caractris pour une reconstruction 3D adquate. Des fantmes vasculaires compatibles avec plusieurs modalits dimagerie ont t utiliss pour simuler diffrentes reprsentations artrielles des membres infrieurs (article 2 - chapitre 4, article 3 - chapitre 5). La validation des gomtries reconstruites a t effectue l`aide d`analyses comparatives. La prcision pour localiser et quantifier les stnoses avec ce systme robotis dimagerie chographique 3D a aussi t dtermine. Ces valuations ont t ralises in vivo pour percevoir le potentiel de lutilisation dun tel systme en clinique (article 3- chapitre 5).
Resumo:
Mmoire numris par la Division de la gestion de documents et des archives de l'Universit de Montral
Resumo:
Contexte: La cardiopathie ischmique (IHD) reste une cause majeure de mortalit en Amrique du Nord. La thrapie cellulaire cardiaque (CCT) a merg comme une thrapie prometteuse pour aider gurir certaines malades cardiaques. Parmi les cellulaires avec proprits pluripotentes, les cellules stromales msenchymateuses (MSC) sont prometteuses. Cependant, plusieurs questions demeurent non rsolues et certaines dfis empchent l'application clinique de la CCT se dans l'IHD, tels que le faible taux de rtention cellulaire in situ, le suivi des cellules in vivo post-implantation et post-acheminements et l`apoptose. Ici, le traitement prliminaire des MSC avec des facteurs de croissance et leur couplage avec des nanoparticules (NP) seront tudis comme des mthodes pour optimiser MSC. Mthodes: Des MSCs provenant du rat (rMSC) et du cochon (pMSC) ont t isols partir de moelle osseuse. Les rMSC ont t prconditionnes avec SDF-1a, TSG-6 et PDGF-BB, et ensuite soumises une hypoxie, une privation de srum et a un stress oxydatif. Des tudes de cicatrisation ont galement t effectus avec rMSCs prconditionnes. En parallle, de nouvelles NP ferromagntiques lies aux silicones ont t synthtises. Les NPs ont t couples aux pMSCs suivant leur fonctionnalisation avec l`anticorps, CD44, un antigne de surface du MSC bien connu. Par la suite, les tudes de biocompatibilit ont t ralises sur pMSC-NP et en incluant des tests des processus cellulaires tels que la migration, l'adhsion, la prolifration et les proprits de la diffrenciation. Rsultats: Parmi toutes les cytokines testes, PDGF-BB a dmontr la plus grande capacit amliorer la survie de MSC dans des conditions d'hypoxie, de privation de srum et en reponse au stress oxydatif. La conjugaison de NP a attnu la migration et la prolifration des pMSCs, mais n`a pas chang leur capacit de diffrenciation. Enfin, la complexe du MSC-NP est dtectable par IRM. Conclusion: Nos donnes suggrent que de nouvelles stratgies, telles que traitement prliminaire de PDGF-BB et le couplage des nanoparticules ferromagntiques, peuvent tre considrs comme des avenues prometteuse pour optimiser les MSCs pour la CCT.
Resumo:
Parmi les mthodes destimation de paramtres de loi de probabilit en statistique, le maximum de vraisemblance est une des techniques les plus populaires, comme, sous des conditions legres, les estimateurs ainsi produits sont consistants et asymptotiquement efficaces. Les problmes de maximum de vraisemblance peuvent tre traits comme des problmes de programmation non linaires, ventuellement non convexe, pour lesquels deux grandes classes de mthodes de rsolution sont les techniques de rgion de confiance et les mthodes de recherche linaire. En outre, il est possible dexploiter la structure de ces problmes pour tenter dacclerer la convergence de ces mthodes, sous certaines hypothses. Dans ce travail, nous revisitons certaines approches classiques ou rcemment developpes en optimisation non linaire, dans le contexte particulier de lestimation de maximum de vraisemblance. Nous dveloppons galement de nouveaux algorithmes pour rsoudre ce problme, reconsidrant diffrentes techniques dapproximation de hessiens, et proposons de nouvelles mthodes de calcul de pas, en particulier dans le cadre des algorithmes de recherche linaire. Il sagit notamment dalgorithmes nous permettant de changer dapproximation de hessien et dadapter la longueur du pas dans une direction de recherche fixe. Finalement, nous valuons lefficacit numrique des mthodes proposes dans le cadre de lestimation de modles de choix discrets, en particulier les modles logit mlangs.
