No description available.

In this thesis we introduce and study an A-optimal minimax design criterion for two-level fractional factorial designs, which can be used to estimate a linear model with main effects and some interactions. The resulting designs are called A-optimal minimax designs, and they are robust against the misspecification of the terms in the linear model. They are also efficient, and often they are the same as A-optimal and D-optimal designs. Various theoretical results about A-optimal minimax designs are derived. A couple of search algorithms including a simulated annealing algorithm are discussed to search for optimal designs, and many interesting examples are presented in the thesis. / Graduate / 0463 / yinyue@uvic.ca

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

Tvarkaraščių sudarymo uždaviniai – viena iš sunkiau sprendžiamų problemų, kylančių įvairiose gamybinėse struktūrose, grupė. Darbo pradžioje supažindinama su bendrais tvarkaraščių sudarymo uždavinių bruožais ir jų sprendimo algoritmais. Detaliau nagrinėti šiame darbe parenkamas vienas sunkiausių gamybinių tvarkaraščių ir apskritai kombinatorinių optimizavimo uždavinių – darbo fabriko uždavinys (angl. job shop scheduling problem), kuris be abejo nėra tiksliai sprendžiamas per polinominį sprendimo laiką. Šio uždavinio pradiniai duomenys yra duotos darbų ir įrenginių aibės. Kiekvienas darbas apdorojamas specifine įrenginių tvarka. Uždavinio tikslas – minimizuoti visų darbų atlikimo laiką. Šiam uždaviniui spręsti pristatėme du apytikslius tabu – atkaitinimo modeliavimo bei paieškos kintamose aplinkose algoritmus, priklausančius metaeuristinių metodų šeimai. Iš tabu – atkaitinimo modeliavimo galima nesunkiai gauti paprastą tabu paiešką, tad prie dviejų minėtų algoritmų galima pridėti ir paprastąją tabu paiešką. Šiame darbe atlikta minėtų algoritmų programinė realizacija. Pristatytų algoritmų efektyvumui įvertinti ir algoritmų parametrų parinkimo rekomendacijoms pateikti, buvo pasirinkti gerai literatūroje žinomi bei sunkiau sprendžiami etaloniniai darbo fabriko uždavinių pavyzdžiai. Darbo pabaigoje pateikiamos minėtų algoritmų parametrų parinkimo rekomendacijos ir aptariamas algoritmų efektyvumas, kuris nagrinėtuose uždaviniuose nebuvo pastovus minėtų trijų algoritmų atvejais, t... [toliau žr. visą tekstą] / At the beginning of this work we introduce to the combinatorial optimization, scheduling problems and methods used to solve them. In computer science scheduling problems is considered strongly NP-complete. The combinatorial optimization problem considered in this paper is a static job shop problem scheduling arising in the manufacturing processes. In the static job shop scheduling problem, a finite number of jobs are to be processed by a finite number of machines. Each job consists of a prederminated sequence of task operations, each of which needs to be processed without preemption for a given period of time on a given machine. Tasks of the same job cannot be processed concurrently and each job must visit each machine exactly once. A schedule is an assignment of operation to time slots on a machine. The makespan is the maximum completion time of the jobs and the objective of the job shop scheduling problem is to find a schedule that minimizes the makespan. When the size of problem increases, the computational time of the exact methods grows exponentially. Therefore, the recent research on job shop and other scheduling problems is focused on heuristic algorithms. We also presented some meta-heuristic algorithms such as Tabu search – Simulated annealing (TS/SA), Tabu Search (TS), Variable Neighborhood Search (VNS) and showed their results on some job shop instances. At the end of this work we tell recommendations about choosing suitable parameters.

In this work minimally supported D-optimal designs for response surface models with spatially correlated errors are studied. The spatially correlated errors describe the correlation between two measurements depending on their distance d through the covariance function C(d)=exp(-rd). In one dimensional design space, the minimally supported D-optimal designs for polynomial models with spatially correlated errors include two end points and are symmetric to the center of the design region. Exact solutions for simple linear and quadratic regression models are presented. For models with third or higher order, numerical solutions are given. While in two dimensional design space, the minimally supported D-optimal designs are invariant under translation¡Brotation and reflection. Numerical results show that a regular triangle on the experimental region of a circle is a minimally supported D-optimal design for the first-order response surface model.

Recently, distributed detection has been intensively studied. The prevailing model for distributed detection (DD) is a system involving both distributed local sensors and a fusion center. In a DD system, multiple sensors work collaboratively to distinguish between two or more hypotheses, e.g., the presence or absence of a target. In this thesis, the classical DD problem is reexamined in the context of wireless sensor network applications. For minimize the error probability at the fusion center, we consider the conventional method that designs the optimal binary local sensor decision rule in a channel-aware system, i.e., it integrates the transmission channel characteristics for find the optimal binary local sensor decision threshold to minimize the error probability at the fusion center. And there have different optimal local sensor decision thresholds for different channel state information. Because of optimal multi-bit (soft) local sensor decision is more practical than optimal binary local sensor decision. Allowing for multi-bit local sensor output, we also consider another conventional method that designs the optimal multi-bit (soft) local sensor decision rule in a channel-aware system. However, to design the optimal local sensor decision rule, both of two conventional methods are easily trapped into local optimal thresholds, which are depended on the pre-selected initialization values. To overcome this difficulty, we consider several modified Simulated Annealing (SA) algorithms. Based on these modified SA algorithms and two conventional methods, we propose two novel SA algorithms for implementing the optimal local sensor decision rule. Computer simulation results show that the employments of two novel SA algorithms can avoid trapping into local optimal thresholds in both optimal binary local sensor decision problem and optimal multi-bit local sensor decision problem. And two novel SA algorithms offer superior performance with lower search points compared to conventional SA algorithm.

This thesis focuses on the design of field experiments with blocks to study treatment effects for a number of treatments. Small field plots are available but located in several blocks and each plot is assigned to a treatment in the experiment. Due to spatial correlation among the plots, the allocation of the treatments to plots has influence on the analysis of the treatment effects. When the spatial correlation is known, optimal allocations (designs) of the treatments to plots have been studied in the literature. However, the spatial correlation is usually unknown in practice, so we propose a robust criterion to study optimal designs of the treatments to plots. Neighbourhoods of correlation structures are introduced and a modified generalized least squares estimator is discussed. A simulated annealing algorithm is implemented to compute optimal/robust designs. Various results are obtained for different experimental settings. Some theoretical results are also proved in the thesis. / Graduate

Procedural level generation is a novel area of research within the field of computer graphics and game development. However, current research and implementations of procedural generation for cooperative games is sparse. Further study is required to validate the use of automatic level creation and to test additional methods of optimization for cooperative games. Additionally, despite many recent developments, many areas within the field of virtual reality remain underexplored. We propose a mathematically defined total cost function for controlling a procedural level generation algorithm for cooperative virtual reality games. This cost term controls an algorithm which gradually improves a generated solution over a series of iterations, bringing it to an optimal state. We present here two games with procedurally created levels and gameplay elements using this mathematical total cost function, as well as proposed experiments to validate the effectiveness of this content in encouraging cooperation and potential use cases for this technology.

Šiame darbe nagrinėjama negiljotininio, dvimačio, stačiakampių pjaustymo uždavinio atliekų minimizavimo problema ir jos sprendimo metodai. Dėl uždavinio kombinatorinio sudėtingumo neįmanoma tiksliai ir visais atvejais pateikti optimalų jo sprendinį, todėl pasirinkti apytiksliai sprendimo metodai. Uždavinys sprendžiamas metaeuristiniais hibridiniais genetiniu ir modeliuojamo atkaitinimo algoritmais apjungtais su euristiniais „Žemiausio kairėn užpildymo“ ir „Žemiausio tarpo“, kuris yra originali „Geriausiai tinkamo“ metodo modifikacija. Taip pat realizuojami minėti euristiniai algoritmai atskirai nuo hibridinių. Atliekama šių metodų lyginamoji analizė bei jų parametrų ir pradinių sąlygų parinkimo įtakos tyrimas sprendinio kokybei. Suformuojama ir pateikiama metodika pjaustymo uždavinių sprendimui. / A non – guillotinable, two – dimensional, rectangular cutting stock problem is being introduced in this paper and its solving methods either. Due to the combinatorial complexity of a problem, it is impossible to solve it optimally for every instance. Consequently an aproximate methods have been chosen. The problem is solved by metaheuristic genetic and simulated annealing methods hybridised with heuristic „Bottom Left Fill“ and „Lowest Gap“, which is an originally modified version of „Best Fit“ algorithm. The same heuristic algorithms are implemented separately from hybridised ones. A comparation analysis of these methods is done and the influence on solution quality depending on the selection of algorithms parameters and its initial conditions is considered. The methodology of solving cutting stock problems is being formulated and presented.

No description available.