Testing Independence in High Dimensions & Identifiability of Graphical Models

Thesis (Ph.D.)--University of Washington, 2016-06

A hybrid genetic algorithm for the multi-depot vehicle routing problem

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.

Optimization of PCB component placements for the collect-and-place machines

This paper presents two hybrid genetic algorithms (HGAs) to optimize the component placement operation for the collect-and-place machines in printed circuit board (PCB) assembly. The component placement problem is to optimize (i) the assignment of components to a movable revolver head or assembly tour, (ii) the sequence of component placements on a stationary PCB in each tour, and (iii) the arrangement of component types to stationary feeders simultaneously. The objective of the problem is to minimize the total traveling time spent by the revolver head for assembling all components on the PCB. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method, the nearest neighbor heuristic, and the neighborhood frequency heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different population sizes. It is proved that the performance of HGA2 is superior to HGA1 in terms of the total assembly time.

The primal sketch revisited: locating and representing edges in human vision via Gaussian-derivative filtering

Marr's work offered guidelines on how to investigate vision (the theory - algorithm - implementation distinction), as well as specific proposals on how vision is done. Many of the latter have inevitably been superseded, but the approach was inspirational and remains so. Marr saw the computational study of vision as tightly linked to psychophysics and neurophysiology, but the last twenty years have seen some weakening of that integration. Because feature detection is a key stage in early human vision, we have returned to basic questions about representation of edges at coarse and fine scales. We describe an explicit model in the spirit of the primal sketch, but tightly constrained by psychophysical data. Results from two tasks (location-marking and blur-matching) point strongly to the central role played by second-derivative operators, as proposed by Marr and Hildreth. Edge location and blur are evaluated by finding the location and scale of the Gaussian-derivative `template' that best matches the second-derivative profile (`signature') of the edge. The system is scale-invariant, and accurately predicts blur-matching data for a wide variety of 1-D and 2-D images. By finding the best-fitting scale, it implements a form of local scale selection and circumvents the knotty problem of integrating filter outputs across scales. [Supported by BBSRC and the Wellcome Trust]

Magneto-Electric Nano-Particles for Non-Invasive Brain Stimulation

This paper for the first time discusses a computational study of using magneto-electric (ME) nanoparticles to artificially stimulate the neural activity deep in the brain. The new technology provides a unique way to couple electric signals in the neural network to the magnetic dipoles in the nanoparticles with the purpose to enable a non-invasive approach. Simulations of the effect of ME nanoparticles for non-invasively stimulating the brain of a patient with Parkinson’s Disease to bring the pulsed sequences of the electric field to the levels comparable to those of healthy people show that the optimized values for the concentration of the 20-nm nanoparticles (with the magneto-electric (ME) coefficient of 100 V cm21 Oe21 in the aqueous solution) is 36106 particles/cc, and the frequency of the externally applied 300-Oe magnetic field is 80 Hz.

Generalized atoms in molecules approach (GAIM approach)

This thesis involves two parts. The first is a new-proposed theoretical approach called generalized atoms in molecules (GAIM). The second is a computational study on the deamination reaction of adenine with OH⁻/nH₂O (n=0, 1, 2, 3) and 3H₂O. The GAIM approach aims to solve the energy of each atom variationally in the first step and then to build the energy of a molecule from each atom. Thus the energy of a diatomic molecule (A-B) is formulated as a sum of its atomic energies, EA and EB. Each of these atomic energies is expressed as, EA = Hᴬ + Vₑₑᴬᴬ + 1/2Vₑₑᴬ<>ᴮ EB = Hᴮ + Vₑₑᴮᴮ + 1/2Vₑₑᴬ<>ᴮ where; Hᴬ and Hᴮ are the kinetic and nuclear attraction energy of electrons of atoms A and B, respectively; Vₑₑᴬᴬ and Vₑₑᴮᴮ are the interaction energy between the electrons on atoms A and B, respectively; and Vₑₑᴬ<>ᴮ is the interaction energy between the electrons of atom A with the electrons of atom B. The energy of the molecule is then minimized subject to the following constraint, |ρA(r)dr + |ρB(r)dr = N where ρA(r) and ρB(r) are the electron densities of atoms A and B, respectively, and N is the number of electrons. The initial testing of the performance of GAIM was done through calculating dissociation curves for H₂, LiH, Li₂, BH, HF, HCl, N₂, F₂, and Cl₂. The numerical results show that GAIM performs very well with H₂, LiH, Li₂, BH, HF, and HCl. GAIM shows convergence problems with N₂, F₂, and Cl₂ due to difficulties in reordering the degenerate atomic orbitals Pₓ, Py, and Pz in N, F, and Cl atoms. Further work for the development of GAIM is required. Deamination of adenine results in one of several forms of premutagenic lesions occurring in DNA. In this thesis, mechanisms for the deamination reaction of adenine with OH⁻/nH₂O, (n = 0, 1, 2, 3) and 3H₂O were investigated. HF/6-31G(d), B3LYP/6-31G(d), MP2/6-31G(d), and B3LYP/6-31+G(d) levels of theory were employed to optimize all the geometries. Energies were calculated at the G3MP2B3 and CBS-QB3 levels of theory. The effect of solvent (water) was computed using the polarizable continuum model (PCM). Intrinsic reaction coordinate (IRC) calculations were performed for all transition states. Five pathways were investigated for the deamination reaction of adenine with OH⁻/nH₂O and 3H₂O. The first four pathways (A-D) begin with by deprotonation at the amino group of adenine by OH⁻, while pathway E is initiated by tautomerization of adenine. For all pathways, the next two steps involve the formation of a tetrahedral intermediate followed by dissociation to yield products via a 1,3-hydrogen shift. Deamination with a single OH⁻ has a high activation barrier (190 kJ mol⁻¹ using G3MP2B3 level) for the rate-determining step. Addition of one water molecule reduces this barrier by 68 kJ mol⁻¹ calculated at G3MP2B3 level. Adding more water molecules decreases the overall activation energy of the reaction, but the effect becomes smaller with each additional water molecule. The most plausible mechanism is pathway E, the deamination reaction of adenine with 3H₂O, which has an overall G3MP2B3 activation energy of 139 and 137 kJ mol⁻¹ in the gas phase and PCM, respectively. This barrier is lower than that for the deamination with OH⁻/3H₂O by 6 and 2 kJ mol⁻¹ in the gas phase and PCM, respectively.

Aspects of Chiral Symmetry Breaking in Lattice QCD

Thesis (Ph.D.)--University of Washington, 2016-08

Large eddy simulation of shock boundary layer interaction control using micro-vortex generators

The performance of supersonic engine inlets and external aerodynamic surfaces can be critically affected by shock wave / boundary layer interactions (SBLIs), whose severe adverse pressure gradients can cause boundary layer separation. Currently such problems are avoided primarily through the use of boundary layer bleed/suction which can be a source of significant performance degradation. This study investigates a novel type of flow control device called micro-vortex generators (µVGs) which may offer similar control benefits without the bleed penalties. µVGs have the ability to alter the near-wall structure of compressible turbulent boundary layers to provide increased mixing of high speed fluid which improves the boundary layer health when subjected to flow disturbance. Due to their small size,µVGs are embedded in the boundary layer which provide reduced drag compared to the traditional vortex generators while they are cost-effective, physically robust and do not require a power source. To examine the potential of µVGs, a detailed experimental and computational study of micro-ramps in a supersonic boundary layer at Mach 3 subjected to an oblique shock was undertaken. The experiments employed a flat plate boundary layer with an impinging oblique shock with downstream total pressure measurements. The moderate Reynolds number of 3,800 based on displacement thickness allowed the computations to use Large Eddy Simulations without the subgrid stress model (LES-nSGS). The LES predictions indicated that the shock changes the structure of the turbulent eddies and the primary vortices generated from the micro-ramp. Furthermore, they generally reproduced the experimentally obtained mean velocity profiles, unlike similarly-resolved RANS computations. The experiments and the LES results indicate that the micro-ramps, whose height is h≈0.5δ, can significantly reduce boundary layer thickness and improve downstream boundary layer health as measured by the incompressible shape factor, H. Regions directly behind the ramp centerline tended to have increased boundary layer thickness indicating the significant three-dimensionality of the flow field. Compared to baseline sizes, smaller micro-ramps yielded improved total pressure recovery. Moving the smaller ramps closer to the shock interaction also reduced the displacement thickness and the separated area. This effect is attributed to decreased wave drag and the closer proximity of the vortex pairs to the wall. In the second part of the study, various types of µVGs are investigated including micro-ramps and micro-vanes. The results showed that vortices generated from µVGs can partially eliminate shock induced flow separation and can continue to entrain high momentum flux for boundary layer recovery downstream. The micro-ramps resulted in thinner downstream displacement thickness in comparison to the micro-vanes. However, the strength of the streamwise vorticity for the micro-ramps decayed faster due to dissipation especially after the shock interaction. In addition, the close spanwise distance between each vortex for the ramp geometry causes the vortex cores to move upwards from the wall due to induced upwash effects. Micro-vanes, on the other hand, yielded an increased spanwise spacing of the streamwise vortices at the point of formation. This resulted in streamwise vortices staying closer to the wall with less circulation decay, and the reduction in overall flow separation is attributed to these effects. Two hybrid concepts, named “thick-vane” and “split-ramp”, were also studied where the former is a vane with side supports and the latter has a uniform spacing along the centerline of the baseline ramp. These geometries behaved similar to the micro-vanes in terms of the streamwise vorticity and the ability to reduce flow separation, but are more physically robust than the thin vanes. Next, Mach number effect on flow past the micro-ramps (h~0.5δ) are examined in a supersonic boundary layer at M=1.4, 2.2 and 3.0, but with no shock waves present. The LES results indicate that micro-ramps have a greater impact at lower Mach number near the device but its influence decays faster than that for the higher Mach number cases. This may be due to the additional dissipation caused by the primary vortices with smaller effective diameter at the lower Mach number such that their coherency is easily lost causing the streamwise vorticity and the turbulent kinetic energy to decay quickly. The normal distance between the vortex core and the wall had similar growth indicating weak correlation with the Mach number; however, the spanwise distance between the two counter-rotating cores further increases with lower Mach number. Finally, various µVGs which include micro-ramp, split-ramp and a new hybrid concept “ramped-vane” are investigated under normal shock conditions at Mach number of 1.3. In particular, the ramped-vane was studied extensively by varying its size, interior spacing of the device and streamwise position respect to the shock. The ramped-vane provided increased vorticity compared to the micro-ramp and the split-ramp. This significantly reduced the separation length downstream of the device centerline where a larger ramped-vane with increased trailing edge gap yielded a fully attached flow at the centerline of separation region. The results from coarse-resolution LES studies show that the larger ramped-vane provided the most reductions in the turbulent kinetic energy and pressure fluctuation compared to other devices downstream of the shock. Additional benefits include negligible drag while the reductions in displacement thickness and shape factor were seen compared to other devices. Increased wall shear stress and pressure recovery were found with the larger ramped-vane in the baseline resolution LES studies which also gave decreased amplitudes of the pressure fluctuations downstream of the shock.

Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

DIFFUSE-INTERFACE FIELD APPROACH TO MODELING SELF-ASSEMBLY OF HETEROGENEOUS COLLOIDAL SYSTEMS AND RELATED DIPOLE-DIPOLE INTERACTION PHENOMENA

Colloid self-assembly under external control is a new route to fabrication of advanced materials with novel microstructures and appealing functionalities. The kinetic processes of colloidal self-assembly have attracted great interests also because they are similar to many atomic level kinetic processes of materials. In the past decades, rapid technological progresses have been achieved on producing shape-anisotropic, patchy, core-shell structured particles and particles with electric/magnetic charges/dipoles, which greatly enriched the self-assembled structures. Multi-phase carrier liquids offer new route to controlling colloidal self-assembly. Therefore, heterogeneity is the essential characteristics of colloid system, while so far there still lacks a model that is able to efficiently incorporate these possible heterogeneities. This thesis is mainly devoted to development of a model and computational study on the complex colloid system through a diffuse-interface field approach (DIFA), recently developed by Wang et al. This meso-scale model is able to describe arbitrary particle shape and arbitrary charge/dipole distribution on the surface or body of particles. Within the framework of DIFA, a Gibbs-Duhem-type formula is introduced to treat Laplace pressure in multi-liquid-phase colloidal system and it obeys Young-Laplace equation. The model is thus capable to quantitatively study important capillarity related phenomena. Extensive computer simulations are performed to study the fundamental behavior of heterogeneous colloidal system. The role of Laplace pressure is revealed in determining the mechanical equilibrium of shape-anisotropic particles at fluid interfaces. In particular, it is found that the Laplace pressure plays a critical role in maintaining the stability of capillary bridges between close particles, which sheds light on a novel route to in situ firming compact but fragile colloidal microstructures via capillary bridges. Simulation results also show that competition between like-charge repulsion, dipole-dipole interaction and Brownian motion dictates the degree of aggregation of heterogeneously charged particles. Assembly and alignment of particles with magnetic dipoles under external field is studied. Finally, extended studies on the role of dipole-dipole interaction are performed for ferromagnetic and ferroelectric domain phenomena. The results reveal that the internal field generated by dipoles competes with external field to determine the dipole-domain evolution in ferroic materials.

Liquid Mixtures Involving Hydrogenated and Fluorinated Alcohols: Thermodynamics, Spectroscopy, and Simulation

This article reports a combined thermodynamic, spectroscopic, and computational study on the interactions and structure of binary mixtures of hydrogenated and fluorinated substances that simultaneously interact through strong hydrogen bonding. Four binary mixtures of hydrogenated and fluorinated alcohols have been studied, namely, (ethanol + 2,2,2-trifluoroethanol (TFE)), (ethanol + 2,2,3,3,4,4,4-heptafluoro-1-butanol), (1-butanol (BuOH) + TFE), and (BuOH + 2,2,3,3,4,4,4-heptafluoro-1-butanol). Excess molar volumes and vibrational spectra of all four binary mixtures have been measured as a function of composition at 298 K, and molecular dynamics simulations have been performed. The systems display a complex behavior when compared with mixtures of hydrogenated alcohols and mixtures of alkanes and perfluoroalkanes. The combined analysis of the results from different approaches indicates that this results from a balance between preferential hydrogen bonding between the hydrogenated and fluorinated alcohols and the unfavorable dispersion forces between the hydrogenated and fluorinated chains. As the chain length increases, the contribution of dispersion increases and overcomes the contribution of H-bonds. In terms of the liquid structure, the simulations suggest the possibility of segregation between the hydrogenated and fluorinated segments, a hypothesis corroborated by the spectroscopic results. Furthermore, a quantitative analysis of the infrared spectra reveals that the presence of fluorinated groups induces conformational changes in the hydrogenated chains from the usually preferred all-trans to more globular arrangements involving gauche conformations. Conformational rearrangements at the CCOH dihedral angle upon mixing are also disclosed by the spectra.

Theoretical and experimental studies of gold catalysts for glucose oxidation

The glucaric acid (GLA) has been identified as a “top value-added chemical from biomass” that can be employed for many uses; for instance, it could be a precursor of adipic acid, a monomer of Nylon-6,6. GLA can be synthetized by the oxidation of glucose (GLU), passing through the intermediate gluconic acid (GLO). In recent years, a new process has been sought to obtain GLA in an economic and environmental sustainable way, in order to replace the current use of HNO3 as a stoichiometric oxidant, or electrocatalysis and biochemical synthesis, which show several disadvantages. Thereby, this work is focused on the study of catalysts based on gold nanoparticles supported on activated carbon for the oxidation reaction of GLU to GLA using O2 as an oxidant agent and NaOH as base. The sol-immobilization method leads us to obtain small and well dispersed nanoparticles, characterized by UV-Vis, XRD and TEM techniques. Repeating the reaction on different batches of catalyst, both the synthesis and the reaction were confirmed to be reproducible. The effect of the reaction time feeding GLO as reagent was studied: the results show that the conversion of GLO increases as the reaction time increases; however, the yields of GLA and others increase up to 1 hour, and then they remain constant. In order to obtain information on the catalytic mechanism at the atomistic level, a computational study based on density functional theory and atomistic modeling of the gold nano-catalyst were performed. Highly symmetric (icosahedral and cubo-octahedral) and distorted Au55 nanoparticles have been optimized along with Au(111) and Au(100) surfaces. Distorted structures were found to be more stable than symmetrical ones due to relativistic effects. On these various models the adsorptions of various species involved in the catalysis have been studied, including OH- species, GLU and GLO. The study carried out aims to provide a method for approaching to the study of nanoparticellary catalytic systems.

Ca(2+) binding to c-state of adenine nucleotide translocase (ANT)-surrounding cardiolipins enhances (ANT)-Cys(56) relative mobility: A computational-based mitochondrial permeability transition study

The oxidation of critical cysteines/related thiols of adenine nucleotide translocase (ANT) is believed to be an important event of the Ca(2+)-induced mitochondrial permeability transition (MPT), a process mediated by a cyclosporine A/ADP-sensitive permeability transition pores (PTP) opening. We addressed the ANT-Cys(56) relative mobility status resulting from the interaction of ANT/surrounding cardiolipins with Ca(2+) and/or ADP by means of computational chemistry analysis (Molecular Interaction Fields and Molecular Dynamics studies), supported by classic mitochondrial swelling assays. The following events were predicted: (i) Ca(2+) interacts preferentially with the ANT surrounding cardiolipins bound to the H4 helix of translocase, (ii) weakens the cardiolipins/ANT interactions and (iii) destabilizes the initial ANT-Cys(56) residue increasing its relative mobility. The binding of ADP that stabilizes the conformation ""m"" of ANT and/or cardiolipin, respectively to H5 and H4 helices, could stabilize their contacts with the short helix h56 that includes Cys(56), accounting for reducing its relative mobility. The results suggest that Ca(2+) binding to adenine nucleotide translocase (ANT)-surrounding cardiolipins in c-state of the translocase enhances (ANT)-Cys(56) relative mobility and that this may constitute a potential critical step of Ca(2+)-induced PTP opening. (C) 2009 Elsevier B.V. All rights reserved.

Computational tools for the study of allergens

Allergy is a major cause of morbidity worldwide. The number of characterized allergens and related information is increasing rapidly creating demands for advanced information storage, retrieval and analysis. Bioinformatics provides useful tools for analysing allergens and these are complementary to traditional laboratory techniques for the study of allergens. Specific applications include structural analysis of allergens, identification of B- and T-cell epitopes, assessment of allergenicity and cross-reactivity, and genome analysis. In this paper, the most important bioinformatic tools and methods with relevance to the study of allergy have been reviewed.

Data fusion with computational intelligence techniques: a case study of fuzzy inference for terrain assessment

Dissertação apresentada para obtenção do Grau de Mestre em Engenharia Electrotécnica e de Computadores, pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia