A quasi-order is a relation on a set which is both reflexive and transitive, while a well-quasi-order has the additional property that there exist no infinite strictly descending chains nor infinite antichains. Well-quasi-orderings have many interesting applications to a variety of areas which includes the strength of certain logical systems, the termination of algorithms, and the classification of sets of graphs in terms of excluded minors. My thesis explores how well-quasi-orderings are related to these topics through examples of four known well-quasi-orderings which are given by Dickson's Lemma, Higmans's Lemma, Kruskal's Tree Theorem, and the Robertson-Seymour Theorem. The well-quasi-ordering conjecture for matroids is also discussed, and an original proof of Higman's Lemma is presented.

Interactively simulating visual appearance of natural objects under natural illumination is a fundamental problem in computer graphics. 3D computer games, geometry modeling, training and simulation, electronic commerce, visualization, lighting design, digital libraries, geographical information systems, economic and medical image processing are typical candidate applications. Recent advances in graphics hardware have enabled real-time rasterization of complex scenes under artificial lighting environment. Meanwhile, pre-computation based soft shadow algorithms are proven effective under low-frequency lighting environment. Under the most practical yet popular all-frequency natural lighting environment, however, real-time rendering of dynamic scenes still remains a challenging problem. In this dissertation, we propose a systematic approach to render dynamic glossy objects under the general all-frequency lighting environment. In our framework, lighting integration is reduced to two rather basic mathematical operations, efficiently computing multi-function product and product integral. The main contribution of our work is a novel mathematical representation and analysis of multi-function product and product integral in the wavelet domain. We show that, multi-function product integral in the primal is equivalent to summation of the product of basis coefficients and integral coefficients. In the dissertation, we give a novel Generalized Haar Integral Coefficient Theorem. We also present a set of efficient algorithms to compute multi-function product and product integral. In the dissertation, we demonstrate practical applications of these algorithms in the interactive rendering of dynamic glossy objects under distant time-variant all-frequency environment lighting with arbitrary view conditions. At each vertex, the shading integral is formulated as the product integral of multiple operand functions. By approximating operand functions in the wavelet domain, we demonstrate rendering dynamic glossy scenes interactively, which is orders of magnitude faster than previous work. As an important enhancement to the popular Pre-computation Based Radiance Transfer (PRT) approach, we present a novel Just-in-time Radiance Transfer (JRT) technique, and demonstrate its application in real-time realistic rendering of dynamic all-frequency shadows under general lighting environment. Our work is a significant step towards real-time rendering of arbitrary scenes under general lighting environment. It is also of great importance to general numerical analysis and signal processing.

This thesis discusses the development and performance of an algorithm created to calculate satellite attitude based on the comparison of satellite "physical feature" models to information derived from edge detection performed on imagery of the satellite. The quality of this imagery could range from the very clear, close-up imagery that may come from an unmanned satellite servicing mission to the faint, unclear imagery that may come from a ground-based telescope investigating a satellite anomaly. Satellite "physical feature" models describe where an edge is likely to appear in an image. These are usually defined by physical edges on the structure of the satellite or areas where there are distinct changes in material property. The theory behind this concept is discussed as well as two different approaches to implement it. Various simple examples are used to demonstrate the feasibility of the concept. These examples are well-controlled image simulations of simple physical models with known attitude. The algorithm attempts to perform the edge detection and edge registration of the simulated image and calculate the most likely attitude. Though complete autonomy was not achieved during this effort, the concept and approach show applicability.

In this work, we show how a variable-length genetic algorithm naturally evolves populations whose mean chromosome length grows shorter over time. A reduction in chromosome length occurs when selection is absent from the GA. Specifically, we divide the mating space into five distinct areas and provide a probabilistic and empirical analysis of the ability of matings in each area to produce children whose size is shorter than the parent generation's average size. Diversity of size within a GA's population is shown to be a necessary condition for a reduction in mean chromosome length to take place. We show how a finite variable-length GA under random selection pressure uses 1) diversity of size within the population, 2) over-production of shorter than average individuals, and 3) the imperfect nature of random sampling during selection to naturally reduce the average size of individuals within a population from one generation to the next. In addition to our findings, this work provides GA researchers and practitioners with 1) a number of mathematical tools for analyzing possible size reductions for various matings and 2) new ideas to explore in the area of bloat control.

Our work is closely connected with the problem of splitting of separatrices (breaking of homoclinic orbits) in a singularly perturbed model describing gravity water waves on a surface of finite depth. The singularly perturbed model is a family of singularly perturbed fourth-order nonlinear ordinary differential equations, parametrized by an external parameter (in addition to the small parameter of the perturbations). It is known that in general separatrices will not survive a singular perturbation. However, it was proven by Tovbis and Pelinovsky that there is a discrete set of exceptional values of the external parameter for which separatrices do survive the perturbation. Since our family of equations can be written in the Hamiltonian form, the question is whether or not survival of separatrices implies integrability of the corresponding equation. The complete integrability of the system is examined from two viewpoints: 1) the existence of a second first integral in involution (Liouville integrability), and 2) the existence of single-valued, meromorphic solutions (complex analytic integrability). In the latter case, a singular point analysis is done using the technique given by Ablowitz, Ramani, and Segur (the ARS algorithm) to determine whether the system is of Painlevé-type (P-type), lacking movable critical points. The system is shown by the algorithm to fail to be of P-type, a strong indication of nonintegrability.

Critical aspects of spacecraft missions, such as component organization, control algorithms, and trajectories, can be optimized using a variety of algorithms or solvers. Each solver has intrinsic strengths and weaknesses when applied to a given optimization problem. One way to mitigate limitations is to combine different solvers in an island model that allows these algorithms to share solutions. The program Spacecraft Trajectory Optimization Suite (STOpS) is an island model suite of heterogeneous and homogeneous Evolutionary Algorithms (EA) that analyze interplanetary trajectories for multiple gravity assist (MGA) missions. One limitation of STOpS and other spacecraft trajectory optimization programs (GMAT and Pygmo/Pagmo) is that they require a defined encounter body sequence to produce a constant length set of design variables. Early phase trajectory design would benefit from the ability to consider problems with an undefined encounter sequence as it would provide a set of diverse trajectories -- some of which might not have been considered during mission planning. The Hybrid Optimal Control Problem (HOCP) and the concept of hidden genes are explored with the most common EA, the Genetic Algorithm (GA), to compare how the methods perform with a Variable Size Design Space (VSDS). Test problems are altered so that the input to the cost function (the object being optimized) contains a set of continuous variables whose length depends on a corresponding set of discrete variables (e.g. the number of planet encounters determines the number of transfer time variables). Initial testing with a scalable problem (Branin's function) indicates that even though the HOCP consistently converges on an optimal solution, the expensive run time (due to algorithm collaboration) would only escalate in an island model system. The hidden gene mechanism only changes how the GA decodes variables, thus it does not impact run time and operates effectively in the island model. A Hidden Gene Genetic Algorithm ( HGGA) is tested with a simplified Mariner 10 (EVM) problem to determine the best parameter settings to use in an island model with the GTOP Cassini 1 (EVVEJS) problem. For an island model with all GAs there is improved performance when the different base algorithm settings are used. Similar to previous work, the model benefits from migration of solutions and using multiple algorithms or islands. For spacecraft trajectory optimization programs that have an unconstrained fly-by sequence, the design variable limits have the largest impact on the results. When the number of potential fly-by sequences is too large it prevents the solver from converging on an optimal solution. This work demonstrates HGGA is effective in the STOpS environment as well as with GTOP problems. Thus the hidden gene mechanism can be extended to other EAs with members containing design variables that function similarly. It is shown that the tuning of the HGGA is dependent on the specific constraints of the spacecraft trajectory problem at hand, thus there is no need to further explore the general capabilities of the algorithm.

There are many diverse applications that are mathematically modelled in terms of mixed discrete-continuous variables. The optimization of these models is typically difficult due to their combinatorial nature and potential existence of multiple local minima in the search space. Genetic algorithms (GAs) are powerful tools for solving such problems. GAs do not require gradient or Hessian information. However, to reach an optimal solution with a high degree of confidence, they typically require a large number of analyses during the optimization search. Performance of these methods is even more of an issue for problems that include continuous variables. The work here enhances the efficiency and accuracy of the GA with memory using multivariate approximations of the objective and constraint functions individually instead of direct approximations of the overall fitness function. The primary motivation for the proposed improvements is the nature of the fitness function in constrained engineering design optimization problems. Since GAs are algorithms for unconstrained optimization, constraints are typically incorporated into the problem formulation by augmenting the objective function of the original problem with penalty terms associated with individual constraint violations. The resulting fitness function is usually highly nonlinear and discontinuous, which makes the multivariate approximation highly inaccurate unless a large number of exact function evaluations are performed. Since the individual response functions in many engineering problems are mostly smooth functions of the continuous variables (although they can be highly nonlinear), high quality approximations to individual functions can be constructed without requiring a large number of function evaluations. The proposed modification improve the efficiency of the memory constructed in terms of the continuous variables. The dissertation presents the algorithmic implementation of the proposed memory scheme and demonstrates the efficiency of the proposed multivariate approximation procedure for the weight optimization of a segmented open cross section composite beam subjected to axial tension load. Results are generated to demonstrate the advantages of the proposed improvements to a standard genetic algorithm. / Ph. D.

During evacuations, emergency managers and departments of transportation seek to facilitate the movement of citizens out of impacted or threatened areas. One strategy they may consider is crossing elimination, which prohibits certain movements at intersections, that may be permissible under normal operating conditions. A few previous studies examined this strategy in conjunction with contra-flow operations, but fewer have considered crossing elimination by itself. This study helps fill the existing gap in knowledge of the individual effects of crossing elimination. A bi-level model that iterates between optimization and simulation is developed to determine the optimal configuration of intersection movements from a set of pre-specified possible configurations for intersections in a given area. At the upper level, evacuees' travel time is minimized and at the lower level, traffic is assigned to the network with the traffic assignment-simulation software DynusT. The overall model is solved with a simulated annealing heuristic and applied to a real case study to assess the impact of crossing elimination. Three scenarios are developed and examined using the solution method proposed in this research. These scenarios are developed using combinations of two elements: (1) Evacuee destination distributions, and (2) Evacuee departure time distributions. Results showed about 3-5 percent improvement in total evacuee travel time can be achieved in these scenarios. Availability of through movements at intersections and existing merging points in movement configurations are the two factors influencing the selection of movement configurations. / Master of Science

Safe and secure transportation of hazardous materials (hazmat) is a challenging issue in terms of optimizing risk to society and simultaneously making the shipment delivery economical. The most important safety concern of hazardous material transportation is accidents causing multiple causalities. The potential risk to society from hazmat transportation has led to the evolution of a new threat from terrorism. Malicious entities can turn hazmat vehicles into weapons causing explosions in high profile locations. The present research is divided into two parts. First, a neural network model is developed to identify when a hazmat truck deviates from its pre-specified path based on its location in the road network. The model identifies abnormal diversions in hazmat carriers' paths considering normal diversions arising due to incidents. The second part of this thesis develops a methodology for predicting different paths that could be taken by malicious entities heading towards a target after successfully hijacking a hazmat vehicle. The path prediction methodology and the neural network methodology are implemented on the network between Baltimore, Maryland and Washington, DC. The trained neural network model classified nodes in the network with a satisfactory performance .The path prediction algorithm was used to calculate the paths to two targets located at the International Dulles Airport and the National Mall in Washington, DC. Based on this research, the neural network methodology is a promising technology for detecting a hijacked vehicle in its initial stages of diversion from its pre-specified path. Possible paths to potential targets are plotted and points of overlap among paths are identified. Overlaps are critical locations where extra security measures can be taken for preventing destruction. Thus, integrating both models gives a comprehensive methodology for detecting the initial diversion and then predicting the possible paths of malicious entities towards targets and could provide an important tool for law enforcement agencies minimizing catastrophic events. / Master of Science

Genetic algorithms are well known for being expensive optimization tools, especially if the cost for the analysis of each individual design is high. In the past few years, significant effort has been put forth in addressing the high computational cost GAs. The research conducted in the first part of this thesis continues this effort by implementing new multiple elitist and variable elitist selection schemes for the creation of successive populations in the genetic search process. The new selection schemes allow the GA to take advantage of a greater amount of important genetic information that may be contained in the parent designs, information that is not utilized when using a traditional elitist method selection scheme. By varying the amount of information that may be passed to successive generations from the parent population, the explorative and exploitative characteristics of the GA can be adjusted throughout the genetic search also. The new schemes provided slight reductions in the computational cost of the GA and produced many designs with good fitness' in the final population, while maintaining a high level of reliability. Genetic algorithms can be easily adapted to many different optimization problems also. This capability is demonstrated by modifying the basic GA, which utilizes a single chromosome string, to include a second string so that composite laminates comprised of multiple materials can be studied with greater efficiently. By using two strings, only minor adjustments to the basic GA were required. The modified GA was used to simultaneously minimize the cost and weight of a simply supported composite plate under different combinations of axial loading. Two materials were used, with one significantly stronger, but more expensive than the other. The optimization formulation was implemented by using convex combinations of cost and weight objective functions into a single value for laminate fitness, and thus required no additional modifications to the GA. To obtain a Pareto-optimal set of designs, the influence of cost and weight on the overall fitness of a laminate configuration was adjusted from one extreme to the other by adjusting the scale factors accordingly. The modified GA provided a simple yet reliable means of designing high performance composite laminates at costs lower than laminates comprised of one material. / Master of Science