Adaptive Crowd Algorithms for Open-Ended Problems

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

Euphorbia tirucalli L.–Comprehensive Characterization of a Drought Tolerant Plant with a Potential as Biofuel Source

Of late, decrease in mineral oil supplies has stimulated research on use of biomass as an alternative energy source. Climate change has brought problems such as increased drought and erratic rains. This, together with a rise in land degeneration problems with concomitant loss in soil fertility has inspired the scientific world to look for alternative bio-energy species. Euphorbia tirucalli L., a tree with C3/CAM metabolism in leaves/stem, can be cultivated on marginal, arid land and could be a good alternative source of biofuel. We analyzed a broad variety of E. tirucalli plants collected from different countries for their genetic diversity using AFLP. Physiological responses to induced drought stress were determined in a number of genotypes by monitoring growth parameters and influence on photosynthesis. For future breeding of economically interesting genotypes, rubber content and biogas production were quantified. Cluster analysis shows that the studied genotypes are divided into two groups, African and mostly non-African genotypes. Different genotypes respond significantly different to various levels of water. Malate measurement indicates that there is induction of CAM in leaves following drought stress. Rubber content varies strongly between genotypes. An investigation of the biogas production capacities of six E. tirucalli genotypes reveals biogas yields higher than from rapeseed but lower than maize silage.

A science-oriented search engine could solve web problems

Lawrence and Giles [1] eloquently define the current problems with the World-Wide Web, but could "Nature" provide the solution ?

THE HEALTH OF YOUNG ADULTS WITH DISABILITIES IN THE UNITED STATES: THE COLLECTIVE ROLES OF RISK FACTORS IN SOCIAL ECOLOGIC FRAMEWORK

Background: Over the last few decades, the prevalence of young adults with disabilities (YAD) has steadily risen as a result of advances in medicine, clinical treatment, and biomedical technologythat enhanced their survival into adulthood. Despite investments in services, family supports, and insurance, they experience poor health status and barriers to successful transition into adulthood. Objectives: We investigated the collective roles of multi-faceted factors at intrapersonal, interpersonal and community levels within the social ecological framework on health related outcome including self-rated health (SRH) of YAD. The three specific aims are: 1) to examine sociodemographic differences and health insurance coverage in adolescence; 2) to investigate the role of social skills in relationships with family and peers developed in adolescence; and 3) to collectively explore the association of sociodemographic characteristics, social skills, and community participation in adolescence on SRH. Methods: Using longitudinal data (N=5,020) from the National Longitudinal Transition Study (NLTS2), we conducted multivariate logistic regression analyses to understand the association between insurance status as well as social skills in adolescence and YAD’s health related outcomes. Structural equation modeling (SEM) assessed the confluence of multi-faceted factors from the social ecological model that link to health in early adulthood. Results: Compared with YAD who had private insurance, YAD who had public health insurance in adolescence are at higher odds of experiencing poorer health related outcomes in self-rated health [adjusted odds ratio (aOR=2.89, 95% confidence interval (CI): 1.16, 7.23), problems with health (aOR=2.60, 95%CI: 1.26, 5.35), and missing social activities due to health problems (aOR=2.86, 95%CI: 1.39, 5.85). At the interpersonal level, overall social skills developed through relationship with family and peers in adolescence do not appear to have association with health related outcomes in early adulthood. Finally, at the community level, community participation in adolescence does not have an association with SRH in early adulthood. Conclusions: Having public health insurance coverage does not equate to good health. YAD need additional supports to achieve positive health outcomes. The findings in social skills and community participation suggest other potential factors may be at play for health related outcomes for YAD and the need for further investigation.

DIRECT NUMERICAL SIMULATION OF INCOMPRESSIBLE MULTIPHASE FLOW WITH PHASE CHANGE

Phase change problems arise in many practical applications such as air-conditioning and refrigeration, thermal energy storage systems and thermal management of electronic devices. The physical phenomenon in such applications are complex and are often difficult to be studied in detail with the help of only experimental techniques. The efforts to improve computational techniques for analyzing two-phase flow problems with phase change are therefore gaining momentum. The development of numerical methods for multiphase flow has been motivated generally by the need to account more accurately for (a) large topological changes such as phase breakup and merging, (b) sharp representation of the interface and its discontinuous properties and (c) accurate and mass conserving motion of the interface. In addition to these considerations, numerical simulation of multiphase flow with phase change introduces additional challenges related to discontinuities in the velocity and the temperature fields. Moreover, the velocity field is no longer divergence free. For phase change problems, the focus of developmental efforts has thus been on numerically attaining a proper conservation of energy across the interface in addition to the accurate treatment of fluxes of mass and momentum conservation as well as the associated interface advection. Among the initial efforts related to the simulation of bubble growth in film boiling applications the work in \cite{Welch1995} was based on the interface tracking method using a moving unstructured mesh. That study considered moderate interfacial deformations. A similar problem was subsequently studied using moving, boundary fitted grids \cite{Son1997}, again for regimes of relatively small topological changes. A hybrid interface tracking method with a moving interface grid overlapping a static Eulerian grid was developed \cite{Juric1998} for the computation of a range of phase change problems including, three-dimensional film boiling \cite{esmaeeli2004computations}, multimode two-dimensional pool boiling \cite{Esmaeeli2004} and film boiling on horizontal cylinders \cite{Esmaeeli2004a}. The handling of interface merging and pinch off however remains a challenge with methods that explicitly track the interface. As large topological changes are crucial for phase change problems, attention has turned in recent years to front capturing methods utilizing implicit interfaces that are more effective in treating complex interface deformations. The VOF (Volume of Fluid) method was adopted in \cite{Welch2000} to simulate the one-dimensional Stefan problem and the two-dimensional film boiling problem. The approach employed a specific model for mass transfer across the interface involving a mass source term within cells containing the interface. This VOF based approach was further coupled with the level set method in \cite{Son1998}, employing a smeared-out Heaviside function to avoid the numerical instability related to the source term. The coupled level set, volume of fluid method and the diffused interface approach was used for film boiling with water and R134a at the near critical pressure condition \cite{Tomar2005}. The effect of superheat and saturation pressure on the frequency of bubble formation were analyzed with this approach. The work in \cite{Gibou2007} used the ghost fluid and the level set methods for phase change simulations. A similar approach was adopted in \cite{Son2008} to study various boiling problems including three-dimensional film boiling on a horizontal cylinder, nucleate boiling in microcavity \cite{lee2010numerical} and flow boiling in a finned microchannel \cite{lee2012direct}. The work in \cite{tanguy2007level} also used the ghost fluid method and proposed an improved algorithm based on enforcing continuity and divergence-free condition for the extended velocity field. The work in \cite{sato2013sharp} employed a multiphase model based on volume fraction with interface sharpening scheme and derived a phase change model based on local interface area and mass flux. Among the front capturing methods, sharp interface methods have been found to be particularly effective both for implementing sharp jumps and for resolving the interfacial velocity field. However, sharp velocity jumps render the solution susceptible to erroneous oscillations in pressure and also lead to spurious interface velocities. To implement phase change, the work in \cite{Hardt2008} employed point mass source terms derived from a physical basis for the evaporating mass flux. To avoid numerical instability, the authors smeared the mass source by solving a pseudo time-step diffusion equation. This measure however led to mass conservation issues due to non-symmetric integration over the distributed mass source region. The problem of spurious pressure oscillations related to point mass sources was also investigated by \cite{Schlottke2008}. Although their method is based on the VOF, the large pressure peaks associated with sharp mass source was observed to be similar to that for the interface tracking method. Such spurious fluctuation in pressure are essentially undesirable because the effect is globally transmitted in incompressible flow. Hence, the pressure field formation due to phase change need to be implemented with greater accuracy than is reported in current literature. The accuracy of interface advection in the presence of interfacial mass flux (mass flux conservation) has been discussed in \cite{tanguy2007level,tanguy2014benchmarks}. The authors found that the method of extending one phase velocity to entire domain suggested by Nguyen et al. in \cite{nguyen2001boundary} suffers from a lack of mass flux conservation when the density difference is high. To improve the solution, the authors impose a divergence-free condition for the extended velocity field by solving a constant coefficient Poisson equation. The approach has shown good results with enclosed bubble or droplet but is not general for more complex flow and requires additional solution of the linear system of equations. In current thesis, an improved approach that addresses both the numerical oscillation of pressure and the spurious interface velocity field is presented by featuring (i) continuous velocity and density fields within a thin interfacial region and (ii) temporal velocity correction steps to avoid unphysical pressure source term. Also I propose a general (iii) mass flux projection correction for improved mass flux conservation. The pressure and the temperature gradient jump condition are treated sharply. A series of one-dimensional and two-dimensional problems are solved to verify the performance of the new algorithm. Two-dimensional and cylindrical film boiling problems are also demonstrated and show good qualitative agreement with the experimental observations and heat transfer correlations. Finally, a study on Taylor bubble flow with heat transfer and phase change in a small vertical tube in axisymmetric coordinates is carried out using the new multiphase, phase change method.

Exact Solution of Bayes and Minimax Change-Detection Problems

The challenge of detecting a change in the distribution of data is a sequential decision problem that is relevant to many engineering solutions, including quality control and machine and process monitoring. This dissertation develops techniques for exact solution of change-detection problems with discrete time and discrete observations. Change-detection problems are classified as Bayes or minimax based on the availability of information on the change-time distribution. A Bayes optimal solution uses prior information about the distribution of the change time to minimize the expected cost, whereas a minimax optimal solution minimizes the cost under the worst-case change-time distribution. Both types of problems are addressed. The most important result of the dissertation is the development of a polynomial-time algorithm for the solution of important classes of Markov Bayes change-detection problems. Existing techniques for epsilon-exact solution of partially observable Markov decision processes have complexity exponential in the number of observation symbols. A new algorithm, called constellation induction, exploits the concavity and Lipschitz continuity of the value function, and has complexity polynomial in the number of observation symbols. It is shown that change-detection problems with a geometric change-time distribution and identically- and independently-distributed observations before and after the change are solvable in polynomial time. Also, change-detection problems on hidden Markov models with a fixed number of recurrent states are solvable in polynomial time. A detailed implementation and analysis of the constellation-induction algorithm are provided. Exact solution methods are also established for several types of minimax change-detection problems. Finite-horizon problems with arbitrary observation distributions are modeled as extensive-form games and solved using linear programs. Infinite-horizon problems with linear penalty for detection delay and identically- and independently-distributed observations can be solved in polynomial time via epsilon-optimal parameterization of a cumulative-sum procedure. Finally, the properties of policies for change-detection problems are described and analyzed. Simple classes of formal languages are shown to be sufficient for epsilon-exact solution of change-detection problems, and methods for finding minimally sized policy representations are described.

Otimização da recolha de resíduos urbanos : caso de estudo de Aveiro

O elevado custo da operação de recolha de resíduos urbanos e a necessidade de cumprir metas dispostas em instrumentos legais são duas motivações que conduzem à necessidade de otimizar o serviço da recolha de resíduos. A otimização da recolha de resíduos é um problema de elevada complexidade de resolução que envolve a análise de redes de transporte. O presente trabalho propõe soluções de otimização da recolha de resíduos urbanos indiferenciados, a partir de um caso de estudo: o percurso RSU I 06 do município de Aveiro. Para este efeito, recorreu-se a uma aplicação informática de representação e análise geográfica: software ArcGIS denominada ArcMap e sua extensão Network Analyst, desenvolvida para calcular circuitos otimizados entre pontos de interesse. O trabalho realizado de aplicação do Network Analyst inclui a apresentação de duas das suas funcionalidades (Route e Vehicle Routing Problem). Em relação ao atual circuito de recolha e com base nos ensaios efetuados, foi possível concluir que esta aplicação permite obter circuitos de recolha otimizados mais curtos ou com menor duração. Contudo, ao nível da gestão permitiu concluir que, com a atual capacidade de contentorização, seria viável reduzir a frequência de recolha de seis vezes por semana para metade, dividindo a área de recolha em duas áreas, de acordo com as necessidades de cada local, reduzindo ainda mais o esforço de recolha. A aplicação do Network Analyst ao caso de estudo, permitiu concluir que é um software com muito interesse no processo de gestão da recolha de resíduos urbanos, apesar de apresentar algumas restrições de aplicação e que a qualidade/eficácia do procedimento de otimização depende da qualidade dos dados de entrada, em particular do descritivo geográfico disponível para os arruamentos e, em larga medida, também depende do modelo de gestão considerado.

The MUSE Machine -- an Architecture for Structured Data Flow Computation

Computers employing some degree of data flow organisation are now well established as providing a possible vehicle for concurrent computation. Although data-driven computation frees the architecture from the constraints of the single program counter, processor and global memory, inherent in the classic von Neumann computer, there can still be problems with the unconstrained generation of fresh result tokens if a pure data flow approach is adopted. The advantages of allowing serial processing for those parts of a program which are inherently serial, and of permitting a demand-driven, as well as data-driven, mode of operation are identified and described. The MUSE machine described here is a structured architecture supporting both serial and parallel processing which allows the abstract structure of a program to be mapped onto the machine in a logical way.

Similarity Measures for Exam Timetabling Problems

A large number of heuristic algorithms have been developed over the years which have been aimed at solving examination timetabling problems. However, many of these algorithms have been developed specifically to solve one particular problem instance or a small subset of instances related to a given real-life problem. Our aim is to develop a more general system which, when given any exam timetabling problem, will produce results which are comparative to those of a specially designed heuristic for that problem. We are investigating a Case based reasoning (CBR) technique to select from a set of algorithms which have been applied successfully to similar problem instances in the past. The assumption in CBR is that similar problems have similar solutions. For our system, the assumption is that an algorithm used to find a good solution to one problem will also produce a good result for a similar problem. The key to the success of the system will be our definition of similarity between two exam timetabling problems. The study will be carried out by running a series of tests using a simple Simulated Annealing Algorithm on a range of problems with differing levels of similarity and examining the data sets in detail. In this paper an initial investigation of the key factors which will be involved in this measure is presented with a discussion of how the definition of good impacts on this.

Similarity Measures for Exam Timetabling Problems

A large number of heuristic algorithms have been developed over the years which have been aimed at solving examination timetabling problems. However, many of these algorithms have been developed specifically to solve one particular problem instance or a small subset of instances related to a given real-life problem. Our aim is to develop a more general system which, when given any exam timetabling problem, will produce results which are comparative to those of a specially designed heuristic for that problem. We are investigating a Case based reasoning (CBR) technique to select from a set of algorithms which have been applied successfully to similar problem instances in the past. The assumption in CBR is that similar problems have similar solutions. For our system, the assumption is that an algorithm used to find a good solution to one problem will also produce a good result for a similar problem. The key to the success of the system will be our definition of similarity between two exam timetabling problems. The study will be carried out by running a series of tests using a simple Simulated Annealing Algorithm on a range of problems with differing levels of similarity and examining the data sets in detail. In this paper an initial investigation of the key factors which will be involved in this measure is presented with a discussion of how the definition of good impacts on this.

Transactions and schema evolution in a persistent object-oriented programming system

Applications are subject of a continuous evolution process with a profound impact on their underlining data model, hence requiring frequent updates in the applications' class structure and database structure as well. This twofold problem, schema evolution and instance adaptation, usually known as database evolution, is addressed in this thesis. Additionally, we address concurrency and error recovery problems with a novel meta-model and its aspect-oriented implementation. Modern object-oriented databases provide features that help programmers deal with object persistence, as well as all related problems such as database evolution, concurrency and error handling. In most systems there are transparent mechanisms to address these problems, nonetheless the database evolution problem still requires some human intervention, which consumes much of programmers' and database administrators' work effort. Earlier research works have demonstrated that aspect-oriented programming (AOP) techniques enable the development of flexible and pluggable systems. In these earlier works, the schema evolution and the instance adaptation problems were addressed as database management concerns. However, none of this research was focused on orthogonal persistent systems. We argue that AOP techniques are well suited to address these problems in orthogonal persistent systems. Regarding the concurrency and error recovery, earlier research showed that only syntactic obliviousness between the base program and aspects is possible. Our meta-model and framework follow an aspect-oriented approach focused on the object-oriented orthogonal persistent context. The proposed meta-model is characterized by its simplicity in order to achieve efficient and transparent database evolution mechanisms. Our meta-model supports multiple versions of a class structure by applying a class versioning strategy. Thus, enabling bidirectional application compatibility among versions of each class structure. That is to say, the database structure can be updated because earlier applications continue to work, as well as later applications that have only known the updated class structure. The specific characteristics of orthogonal persistent systems, as well as a metadata enrichment strategy within the application's source code, complete the inception of the meta-model and have motivated our research work. To test the feasibility of the approach, a prototype was developed. Our prototype is a framework that mediates the interaction between applications and the database, providing them with orthogonal persistence mechanisms. These mechanisms are introduced into applications as an {\it aspect} in the aspect-oriented sense. Objects do not require the extension of any super class, the implementation of an interface nor contain a particular annotation. Parametric type classes are also correctly handled by our framework. However, classes that belong to the programming environment must not be handled as versionable due to restrictions imposed by the Java Virtual Machine. Regarding concurrency support, the framework provides the applications with a multithreaded environment which supports database transactions and error recovery. The framework keeps applications oblivious to the database evolution problem, as well as persistence. Programmers can update the applications' class structure because the framework will produce a new version for it at the database metadata layer. Using our XML based pointcut/advice constructs, the framework's instance adaptation mechanism is extended, hence keeping the framework also oblivious to this problem. The potential developing gains provided by the prototype were benchmarked. In our case study, the results confirm that mechanisms' transparency has positive repercussions on the programmer's productivity, simplifying the entire evolution process at application and database levels. The meta-model itself also was benchmarked in terms of complexity and agility. Compared with other meta-models, it requires less meta-object modifications in each schema evolution step. Other types of tests were carried out in order to validate prototype and meta-model robustness. In order to perform these tests, we used an OO7 small size database due to its data model complexity. Since the developed prototype offers some features that were not observed in other known systems, performance benchmarks were not possible. However, the developed benchmark is now available to perform future performance comparisons with equivalent systems. In order to test our approach in a real world scenario, we developed a proof-of-concept application. This application was developed without any persistence mechanisms. Using our framework and minor changes applied to the application's source code, we added these mechanisms. Furthermore, we tested the application in a schema evolution scenario. This real world experience using our framework showed that applications remains oblivious to persistence and database evolution. In this case study, our framework proved to be a useful tool for programmers and database administrators. Performance issues and the single Java Virtual Machine concurrent model are the major limitations found in the framework.

A distributed, compact routing protocol for the Internet

The Internet has grown in size at rapid rates since BGP records began, and continues to do so. This has raised concerns about the scalability of the current BGP routing system, as the routing state at each router in a shortest-path routing protocol will grow at a supra-linearly rate as the network grows. The concerns are that the memory capacity of routers will not be able to keep up with demands, and that the growth of the Internet will become ever more cramped as more and more of the world seeks the benefits of being connected. Compact routing schemes, where the routing state grows only sub-linearly relative to the growth of the network, could solve this problem and ensure that router memory would not be a bottleneck to Internet growth. These schemes trade away shortest-path routing for scalable memory state, by allowing some paths to have a certain amount of bounded “stretch”. The most promising such scheme is Cowen Routing, which can provide scalable, compact routing state for Internet routing, while still providing shortest-path routing to nearly all other nodes, with only slightly stretched paths to a very small subset of the network. Currently, there is no fully distributed form of Cowen Routing that would be practical for the Internet. This dissertation describes a fully distributed and compact protocol for Cowen routing, using the k-core graph decomposition. Previous compact routing work showed the k-core graph decomposition is useful for Cowen Routing on the Internet, but no distributed form existed. This dissertation gives a distributed k-core algorithm optimised to be efficient on dynamic graphs, along with with proofs of its correctness. The performance and efficiency of this distributed k-core algorithm is evaluated on large, Internet AS graphs, with excellent results. This dissertation then goes on to describe a fully distributed and compact Cowen Routing protocol. This protocol being comprised of a landmark selection process for Cowen Routing using the k-core algorithm, with mechanisms to ensure compact state at all times, including at bootstrap; a local cluster routing process, with mechanisms for policy application and control of cluster sizes, ensuring again that state can remain compact at all times; and a landmark routing process is described with a prioritisation mechanism for announcements that ensures compact state at all times.

Linear non-local diffusion problems in metric measure spaces

The aim of this paper is to provide a comprehensive study of some linear non-local diffusion problems in metric measure spaces. These include, for example, open subsets in ℝN, graphs, manifolds, multi-structures and some fractal sets. For this, we study regularity, compactness, positivity and the spectrum of the stationary non-local operator. We then study the solutions of linear evolution non-local diffusion problems, with emphasis on similarities and differences with the standard heat equation in smooth domains. In particular, we prove weak and strong maximum principles and describe the asymptotic behaviour using spectral methods.

Systematic review and meta-analysis of interventions relevant for young offenders with mood disorders, anxiety disorders, or self-harm

Background: Mood and anxiety disorders, and problems with self harm are significant and serious issues that are common in young people in the Criminal Justice System. Aims: To examine whether interventions relevant to young offenders with mood or anxiety disorders, or problems with self harm are effective. Method: Systematic review and meta-analysis of data from randomised controlled trials relevant to young offenders experiencing these problems. Results: An exhaustive search of the worldwide literature (published and unpublished)yielded 10 studies suitable for inclusion in this review. Meta-analysis of data from three studies (with a total population of 171 individuals) revealed that group-based Cognitive Behaviour Therapy (CBT) may help to reduce symptoms of depression in young offenders. Conclusions: These preliminary findings suggest that group-based CBT may be useful for young offenders with such mental health problems, but larger high quality RCTs are now needed to bolster the evidence-base.

Energy norm a-posteriori error estimation for hp-adaptive discontinuous Galerkin methods for elliptic problems in three dimensions

We develop the energy norm a-posteriori error estimation for hp-version discontinuous Galerkin (DG) discretizations of elliptic boundary-value problems on 1-irregularly, isotropically refined affine hexahedral meshes in three dimensions. We derive a reliable and efficient indicator for the errors measured in terms of the natural energy norm. The ratio of the efficiency and reliability constants is independent of the local mesh sizes and weakly depending on the polynomial degrees. In our analysis we make use of an hp-version averaging operator in three dimensions, which we explicitly construct and analyze. We use our error indicator in an hp-adaptive refinement algorithm and illustrate its practical performance in a series of numerical examples. Our numerical results indicate that exponential rates of convergence are achieved for problems with smooth solutions, as well as for problems with isotropic corner singularities.