Histogram filtering as a tool in variational Monte Carlo optimization

Optimization of wave functions in quantum Monte Carlo is a difficult task because the statistical uncertainty inherent to the technique makes the absolute determination of the global minimum difficult. To optimize these wave functions we generate a large number of possible minima using many independently generated Monte Carlo ensembles and perform a conjugate gradient optimization. Then we construct histograms of the resulting nominally optimal parameter sets and "filter" them to identify which parameter sets "go together" to generate a local minimum. We follow with correlated-sampling verification runs to find the global minimum. We illustrate this technique for variance and variational energy optimization for a variety of wave functions for small systellls. For such optimized wave functions we calculate the variational energy and variance as well as various non-differential properties. The optimizations are either on par with or superior to determinations in the literature. Furthermore, we show that this technique is sufficiently robust that for molecules one may determine the optimal geometry at tIle same time as one optimizes the variational energy.

Optimization of the valence energy variance of the CuH molecule

We developed the concept of split-'t to deal with the large molecules (in terms of the number of electrons and nuclear charge Z). This naturally leads to partitioning the local energy into components due to each electron shell. The minimization of the variation of the valence shell local energy is used to optimize a simple two parameter CuH wave function. Molecular properties (spectroscopic constants and the dipole moment) are calculated for the optimized and nearly optimized wave functions using the Variational Quantum Monte Carlo method. Our best results are comparable to those from the single and double configuration interaction (SDCI) method.

Optimization of trial wave functions for use in quantum Monte Carlo with application to LiH

Methods for both partial and full optimization of wavefunction parameters are explored, and these are applied to the LiH molecule. A partial optimization can be easily performed with little difficulty. But to perform a full optimization we must avoid a wrong minimum, and deal with linear-dependency, time step-dependency and ensemble-dependency problems. Five basis sets are examined. The optimized wavefunction with a 3-function set gives a variational energy of -7.998 + 0.005 a.u., which is comparable to that (-7.990 + 0.003) 1 of Reynold's unoptimized \fin ( a double-~ set of eight functions). The optimized wavefunction with a double~ plus 3dz2 set gives ari energy of -8.052 + 0.003 a.u., which is comparable with the fixed-node energy (-8.059 + 0.004)1 of the \fin. The optimized double-~ function itself gives an energy of -8.049 + 0.002 a.u. Each number above was obtained on a Bourrghs 7900 mainframe computer with 14 -15 hrs CPU time.

Particle swarm optimization for two-connected networks with bounded rings

The Two-Connected Network with Bounded Ring (2CNBR) problem is a network design problem addressing the connection of servers to create a survivable network with limited redirections in the event of failures. Particle Swarm Optimization (PSO) is a stochastic population-based optimization technique modeled on the social behaviour of flocking birds or schooling fish. This thesis applies PSO to the 2CNBR problem. As PSO is originally designed to handle a continuous solution space, modification of the algorithm was necessary in order to adapt it for such a highly constrained discrete combinatorial optimization problem. Presented are an indirect transcription scheme for applying PSO to such discrete optimization problems and an oscillating mechanism for averting stagnation.

Bio-inspired optimization & sampling technique for side-chain packing in MCCE

The prediction of proteins' conformation helps to understand their exhibited functions, allows for modeling and allows for the possible synthesis of the studied protein. Our research is focused on a sub-problem of protein folding known as side-chain packing. Its computational complexity has been proven to be NP-Hard. The motivation behind our study is to offer the scientific community a means to obtain faster conformation approximations for small to large proteins over currently available methods. As the size of proteins increases, current techniques become unusable due to the exponential nature of the problem. We investigated the capabilities of a hybrid genetic algorithm / simulated annealing technique to predict the low-energy conformational states of various sized proteins and to generate statistical distributions of the studied proteins' molecular ensemble for pKa predictions. Our algorithm produced errors to experimental results within .acceptable margins and offered considerable speed up depending on the protein and on the rotameric states' resolution used.

(A) Optimization of solid body phase synthesis of RNA using the Cpep chemistry. (B) Synthesis of BODIPY labeled oligonucleotides

(A) Solid phase synthesis of oligonucleotides are well documented and are extensively studied as the demands continue to rise with the development of antisense, anti-gene, RNA interference, and aptamers. Although synthesis of RNA sequences faces many challenges, most notably the choice of the 2' -hydroxy protecting group, modified 2' -O-Cpep protected ribonucleotides were synthesized as alternitive building blocks. Altering phosphitylation procedures to incorporate 3' -N,N-diethyl phosphoramidites enhanced the overall reactivity, thus, increased the coupling efficiency without loss of integrety. Furthermore, technical optimizations of solid phase synthesis cycles were carried out to allow for successful synthesis of a homo UIO sequences with a stepwise coupling efficiency reaching 99% and a final yield of 91 %. (B) Over the past few decades, dipyrrometheneboron difluoride (BODIPY) has gained recognition as one of the most versatile fluorophores. Currently, BODIPY labeling of oligonucleotides are carried out post-synthetically and to date, there lacks a method that allows for direct incorporation of BODIPY into oligonucleotides during solid phase synthesis. Therefore, synthesis of BODIPY derived phosphoramidites will provide an alternative method in obtaining fluorescently labelled oligonucleotides. A method for the synthesis and incorporation of the BODIPY analogues into oligonucleotides by phosphoramidite chemistry-based solid phase DNA synthesis is reported here. Using this approach, BODIPY-labeled TlO homopolymer and ISIS 5132 were successfully synthesized.

Generating Aesthetically Pleasing Images in a Virtual Environment using Particle Swarm Optimization

This research focuses on generating aesthetically pleasing images in virtual environments using the particle swarm optimization (PSO) algorithm. The PSO is a stochastic population based search algorithm that is inspired by the flocking behavior of birds. In this research, we implement swarms of cameras flying through a virtual world in search of an image that is aesthetically pleasing. Virtual world exploration using particle swarm optimization is considered to be a new research area and is of interest to both the scientific and artistic communities. Aesthetic rules such as rule of thirds, subject matter, colour similarity and horizon line are all analyzed together as a multi-objective problem to analyze and solve with rendered images. A new multi-objective PSO algorithm, the sum of ranks PSO, is introduced. It is empirically compared to other single-objective and multi-objective swarm algorithms. An advantage of the sum of ranks PSO is that it is useful for solving high-dimensional problems within the context of this research. Throughout many experiments, we show that our approach is capable of automatically producing images satisfying a variety of supplied aesthetic criteria.

Characterizing Dynamic Optimization Benchmarks for the Comparison of Multi-Modal Tracking Algorithms

Population-based metaheuristics, such as particle swarm optimization (PSO), have been employed to solve many real-world optimization problems. Although it is of- ten sufficient to find a single solution to these problems, there does exist those cases where identifying multiple, diverse solutions can be beneficial or even required. Some of these problems are further complicated by a change in their objective function over time. This type of optimization is referred to as dynamic, multi-modal optimization. Algorithms which exploit multiple optima in a search space are identified as niching algorithms. Although numerous dynamic, niching algorithms have been developed, their performance is often measured solely on their ability to find a single, global optimum. Furthermore, the comparisons often use synthetic benchmarks whose landscape characteristics are generally limited and unknown. This thesis provides a landscape analysis of the dynamic benchmark functions commonly developed for multi-modal optimization. The benchmark analysis results reveal that the mechanisms responsible for dynamism in the current dynamic bench- marks do not significantly affect landscape features, thus suggesting a lack of representation for problems whose landscape features vary over time. This analysis is used in a comparison of current niching algorithms to identify the effects that specific landscape features have on niching performance. Two performance metrics are proposed to measure both the scalability and accuracy of the niching algorithms. The algorithm comparison results demonstrate the algorithms best suited for a variety of dynamic environments. This comparison also examines each of the algorithms in terms of their niching behaviours and analyzing the range and trade-off between scalability and accuracy when tuning the algorithms respective parameters. These results contribute to the understanding of current niching techniques as well as the problem features that ultimately dictate their success.

A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization

Many real-world optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multi-objective problems (MOPs). Over the past few decades, a plethora of multi-objective algorithms have been proposed, often tested on MOPs possessing two or three objectives. Unfortunately, when tasked with solving MOPs with four or more objectives, referred to as many-objective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a well-spread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for large-scale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of many-objective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming state-of-the-art many-objective algorithms.

Gestion adaptative des ressources dans les réseaux maillés sans fil à multiples-radios multiples-canaux

Depuis quelques années, la recherche dans le domaine des réseaux maillés sans fil ("Wireless Mesh Network (WMN)" en anglais) suscite un grand intérêt auprès de la communauté des chercheurs en télécommunications. Ceci est dû aux nombreux avantages que la technologie WMN offre, telles que l'installation facile et peu coûteuse, la connectivité fiable et l'interopérabilité flexible avec d'autres réseaux existants (réseaux Wi-Fi, réseaux WiMax, réseaux cellulaires, réseaux de capteurs, etc.). Cependant, plusieurs problèmes restent encore à résoudre comme le passage à l'échelle, la sécurité, la qualité de service (QdS), la gestion des ressources, etc. Ces problèmes persistent pour les WMNs, d'autant plus que le nombre des utilisateurs va en se multipliant. Il faut donc penser à améliorer les protocoles existants ou à en concevoir de nouveaux. L'objectif de notre recherche est de résoudre certaines des limitations rencontrées à l'heure actuelle dans les WMNs et d'améliorer la QdS des applications multimédia temps-réel (par exemple, la voix). Le travail de recherche de cette thèse sera divisé essentiellement en trois principaux volets: le contrôle d‟admission du trafic, la différentiation du trafic et la réaffectation adaptative des canaux lors de la présence du trafic en relève ("handoff" en anglais). Dans le premier volet, nous proposons un mécanisme distribué de contrôle d'admission se basant sur le concept des cliques (une clique correspond à un sous-ensemble de liens logiques qui interfèrent les uns avec les autres) dans un réseau à multiples-sauts, multiples-radios et multiples-canaux, appelé RCAC. Nous proposons en particulier un modèle analytique qui calcule le ratio approprié d'admission du trafic et qui garantit une probabilité de perte de paquets dans le réseau n'excédant pas un seuil prédéfini. Le mécanisme RCAC permet d‟assurer la QdS requise pour les flux entrants, sans dégrader la QdS des flux existants. Il permet aussi d‟assurer la QdS en termes de longueur du délai de bout en bout pour les divers flux. Le deuxième volet traite de la différentiation de services dans le protocole IEEE 802.11s afin de permettre une meilleure QdS, notamment pour les applications avec des contraintes temporelles (par exemple, voix, visioconférence). À cet égard, nous proposons un mécanisme d'ajustement de tranches de temps ("time-slots"), selon la classe de service, ED-MDA (Enhanced Differentiated-Mesh Deterministic Access), combiné à un algorithme efficace de contrôle d'admission EAC (Efficient Admission Control), afin de permettre une utilisation élevée et efficace des ressources. Le mécanisme EAC prend en compte le trafic en relève et lui attribue une priorité supérieure par rapport au nouveau trafic pour minimiser les interruptions de communications en cours. Dans le troisième volet, nous nous intéressons à minimiser le surcoût et le délai de re-routage des utilisateurs mobiles et/ou des applications multimédia en réaffectant les canaux dans les WMNs à Multiples-Radios (MR-WMNs). En premier lieu, nous proposons un modèle d'optimisation qui maximise le débit, améliore l'équité entre utilisateurs et minimise le surcoût dû à la relève des appels. Ce modèle a été résolu par le logiciel CPLEX pour un nombre limité de noeuds. En second lieu, nous élaborons des heuristiques/méta-heuristiques centralisées pour permettre de résoudre ce modèle pour des réseaux de taille réelle. Finalement, nous proposons un algorithme pour réaffecter en temps-réel et de façon prudente les canaux aux interfaces. Cet algorithme a pour objectif de minimiser le surcoût et le délai du re-routage spécialement du trafic dynamique généré par les appels en relève. Ensuite, ce mécanisme est amélioré en prenant en compte l‟équilibrage de la charge entre cliques.

Optimization and validation of a new 3D-US imaging robot to detect, localize and quantify lower limb arterial stenoses

L’athérosclérose est une maladie qui cause, par l’accumulation de plaques lipidiques, le durcissement de la paroi des artères et le rétrécissement de la lumière. Ces lésions sont généralement localisées sur les segments artériels coronariens, carotidiens, aortiques, rénaux, digestifs et périphériques. En ce qui concerne l’atteinte périphérique, celle des membres inférieurs est particulièrement fréquente. En effet, la sévérité de ces lésions artérielles est souvent évaluée par le degré d’une sténose (réduction >50 % du diamètre de la lumière) en angiographie, imagerie par résonnance magnétique (IRM), tomodensitométrie ou échographie. Cependant, pour planifier une intervention chirurgicale, une représentation géométrique artérielle 3D est notamment préférable. Les méthodes d’imagerie par coupe (IRM et tomodensitométrie) sont très performantes pour générer une imagerie tridimensionnelle de bonne qualité mais leurs utilisations sont dispendieuses et invasives pour les patients. L’échographie 3D peut constituer une avenue très prometteuse en imagerie pour la localisation et la quantification des sténoses. Cette modalité d’imagerie offre des avantages distincts tels la commodité, des coûts peu élevés pour un diagnostic non invasif (sans irradiation ni agent de contraste néphrotoxique) et aussi l’option d’analyse en Doppler pour quantifier le flux sanguin. Étant donné que les robots médicaux ont déjà été utilisés avec succès en chirurgie et en orthopédie, notre équipe a conçu un nouveau système robotique d’échographie 3D pour détecter et quantifier les sténoses des membres inférieurs. Avec cette nouvelle technologie, un radiologue fait l’apprentissage manuel au robot d’un balayage échographique du vaisseau concerné. Par la suite, le robot répète à très haute précision la trajectoire apprise, contrôle simultanément le processus d’acquisition d’images échographiques à un pas d’échantillonnage constant et conserve de façon sécuritaire la force appliquée par la sonde sur la peau du patient. Par conséquent, la reconstruction d’une géométrie artérielle 3D des membres inférieurs à partir de ce système pourrait permettre une localisation et une quantification des sténoses à très grande fiabilité. L’objectif de ce projet de recherche consistait donc à valider et optimiser ce système robotisé d’imagerie échographique 3D. La fiabilité d’une géométrie reconstruite en 3D à partir d’un système référentiel robotique dépend beaucoup de la précision du positionnement et de la procédure de calibration. De ce fait, la précision pour le positionnement du bras robotique fut évaluée à travers son espace de travail avec un fantôme spécialement conçu pour simuler la configuration des artères des membres inférieurs (article 1 - chapitre 3). De plus, un fantôme de fils croisés en forme de Z a été conçu pour assurer une calibration précise du système robotique (article 2 - chapitre 4). Ces méthodes optimales ont été utilisées pour valider le système pour l’application clinique et trouver la transformation qui convertit les coordonnées de l’image échographique 2D dans le référentiel cartésien du bras robotisé. À partir de ces résultats, tout objet balayé par le système robotique peut être caractérisé pour une reconstruction 3D adéquate. Des fantômes vasculaires compatibles avec plusieurs modalités d’imagerie ont été utilisés pour simuler différentes représentations artérielles des membres inférieurs (article 2 - chapitre 4, article 3 - chapitre 5). La validation des géométries reconstruites a été effectuée à l`aide d`analyses comparatives. La précision pour localiser et quantifier les sténoses avec ce système robotisé d’imagerie échographique 3D a aussi été déterminée. Ces évaluations ont été réalisées in vivo pour percevoir le potentiel de l’utilisation d’un tel système en clinique (article 3- chapitre 5).

Tarification logit dans un réseau

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau 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 caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers.

C.A.M.E.L.E.O. : a cultural adaptation methodology for E-learning environment optimization

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

New simulation schemes for the Heston model

Les titres financiers sont souvent modélisés par des équations différentielles stochastiques (ÉDS). Ces équations peuvent décrire le comportement de l'actif, et aussi parfois certains paramètres du modèle. Par exemple, le modèle de Heston (1993), qui s'inscrit dans la catégorie des modèles à volatilité stochastique, décrit le comportement de l'actif et de la variance de ce dernier. Le modèle de Heston est très intéressant puisqu'il admet des formules semi-analytiques pour certains produits dérivés, ainsi qu'un certain réalisme. Cependant, la plupart des algorithmes de simulation pour ce modèle font face à quelques problèmes lorsque la condition de Feller (1951) n'est pas respectée. Dans ce mémoire, nous introduisons trois nouveaux algorithmes de simulation pour le modèle de Heston. Ces nouveaux algorithmes visent à accélérer le célèbre algorithme de Broadie et Kaya (2006); pour ce faire, nous utiliserons, entre autres, des méthodes de Monte Carlo par chaînes de Markov (MCMC) et des approximations. Dans le premier algorithme, nous modifions la seconde étape de la méthode de Broadie et Kaya afin de l'accélérer. Alors, au lieu d'utiliser la méthode de Newton du second ordre et l'approche d'inversion, nous utilisons l'algorithme de Metropolis-Hastings (voir Hastings (1970)). Le second algorithme est une amélioration du premier. Au lieu d'utiliser la vraie densité de la variance intégrée, nous utilisons l'approximation de Smith (2007). Cette amélioration diminue la dimension de l'équation caractéristique et accélère l'algorithme. Notre dernier algorithme n'est pas basé sur une méthode MCMC. Cependant, nous essayons toujours d'accélérer la seconde étape de la méthode de Broadie et Kaya (2006). Afin de réussir ceci, nous utilisons une variable aléatoire gamma dont les moments sont appariés à la vraie variable aléatoire de la variance intégrée par rapport au temps. Selon Stewart et al. (2007), il est possible d'approximer une convolution de variables aléatoires gamma (qui ressemble beaucoup à la représentation donnée par Glasserman et Kim (2008) si le pas de temps est petit) par une simple variable aléatoire gamma.