Denna studie undersöker om det är möjligt att införa nåbarhetstestning i en baneditor. Testets syfte är att ersätta manuell testing, det vill säga att bankonstruktören inte ska behöva spela igenom banan för att säkerställa att denne kommer kunna nå alla nåbara positioner.För att kunna utföra studien skapas en enkel baneditor som testplattform. Vidare utförs en jämförande studie av flera alternativa algoritmer för att fastställa vilken som är mest passande för nåbarhetstestning i en baneditor.Resultatet från den jämförande studien visade att A* (A star) var den mest passande algoritmen för funktionen. Huruvida automatisk testning kan ersätta manuell testning är diskutabelt, men resultatet pekar på en ökad effektivitet i tid när det kommer till banbygge. / The following study examines whether it is possible to implement reachability testing in a map editor designed for 2D-platform games. The purpose of reachability testing is to replace manual testing, that being the level designer having to play through the map just to see if the player can reach all supposedly reachable positions in the map.A simple map editor is created to enable the implementation after which we perform a theoretical study in order to determine which algorithm would be best suited for the implementation of the reachability testing.The results comparing algorithms shows that A* (A star) worked best with the function. Whether or not manual testing can be replaced by automatic testing is open for debate, however the results points to an increase in time efficiency when it comes to level design.

Pour faire face à la concurrence, les entreprises cherchent à améliorer leurs performances industrielles. L’une des solutions à ce défi réside dans la détermination de la meilleure configuration des ateliers de production. Ce type de problème est connu en anglais par Facility Layout Problem « FLP». Dans ce contexte, notre travail propose une méthodologie pour la définition de la configuration d’atelier à travers une approche réaliste. Plus précisément, notre objectif est de prendre en compte les distances réelles parcourues par les pièces dans l’atelier et des contraintes liées au système qui n’ont pas encore été intégrées aux modèles proposés dans la littérature. Pour ce faire, notre première contribution scientifique consiste à développer une nouvelle méthodologie qui utilise l’algorithme A* pour identifier les distances les plus courtes entre les postes de travail de manière réaliste. La méthodologie proposée combine l’Algorithme Génétique (AG) et l’algorithme A* afin d’explorer des espaces de solutions. Pour se rapprocher de plus en plus des cas réels, notre deuxième contribution consiste à présenter une nouvelle formulation généralisée du FLP initialement étudié, en tenant compte de différentes formes et de dimensions des équipements ainsi que de l’atelier. Les résultats obtenus prouvent l’applicabilité et la faisabilité de cette approche dans diverses situations. Une étude comparative de l’approche proposée avec les essaims particulaires intégrés avec A* a prouvé la qualité de la première approche en terme de coût de transport. Finalement, notre troisième contribution consiste à traiter le FLP dans un espace 3D où des contraintes spatiales sont intégrées dans la phase de modélisation. La résolution est une extension de la méthodologie proposée pour le problème 2D, qui intègre donc l'algorithme A* et l’AG afin de générer diverses configurations dans l’espace 3D. Pour chacune de ces contributions, une analyse de sensibilité des différents paramètres d’AG utilisés a été faite à l’aide de simulations de Monte Carlo. / To face the competition, companies seek to improve their industrial performance. One of the solutions to this challenge lies in determining the best configuration of the production workshops. This type of problem is known in English by Facility Layout Problem "FLP". In this context, our work proposes a methodology for the definition of the workshop configuration through a realistic approach. More precisely, our goal is to take into account the actual distances traveled by the parts in the workshop and system-related constraints that have not yet been incorporated into the models proposed in the literature. To do this, our first scientific contribution is to develop a new methodology that uses the A* algorithm to identify the shortest distances between workstations in a realistic way. The proposed methodology combines the Genetic Algorithm (GA) and the algorithm A* to explore solution spaces. To get closer to real cases, our second contribution is to present a new generalized formulation of FLP initially studied, taking into account different shapes and dimensions of the equipment and the workshop. The results obtained prove the applicability and the feasibility of this approach in various situations. A comparative study of the proposed approach with particle swarms integrated with A * proved the quality of the first approach in terms of transport cost. Finally, our third contribution is to treat the FLP in a 3D space where spatial constraints are integrated into the modeling phase. The resolution is an extension of the proposed methodology for the 2D problem, which therefore integrates the A * algorithm and the AG to generate various configurations in the 3D space. For each of these contributions, a sensitivity analysis of the different AG parameters used was made using Monte Carlo simulations.

The objective of this thesis was to explore whether there are alternatives to the established search ranking algorithm Best Matching 25 (BM25) when searching for shorter documents, in particular for the search of titles. Five search engines were compared to BM25, three of them being variants of the BM25 algorithm and the other two being based on a binary independence model that does not take term frequency or length normalisation into account. The evaluation data consisted of titles of Wikipedia articles from the fair ranking track retrieved from the main conference in the field, Text REtrieval Conference (TREC), and user logs collected from user search queries from Spotify. It was found that none of the alternative models consistently outperformed the standard BM25 for a query q where the number of words in q ranges between 1 ≤ |q| ≤ 8. Yet, for shorter queries |q| ≤ 3, the binary independence model and BM25 adaptive term (BM25adpt) outperformed the standard BM25. Furthermore, a 1% increase in Mean Average Precision (MAP) score was acquired with a binary independence model and BM25adpt compared to BM25 when sampling queries from the user log data. However, because of the bias in the evaluation data together with the small percentage increase in MAP score, it was concluded that the potential benefit of using the methods explored in this thesis is not enough to justify switching from the BM25 algorithm when searching for titles. / Målet med avhandlingen var att undersöka om det finns alternativ till den vedertagna sökalgoritmen Best matching 25 (BM25) vid sökning bland kortare document, närmare bestämt vid titelsökning. Fem sökmotorer jämfördes med BM25, tre av dem var varianter av BM25 och de andra två varianter av en binär oberoende modell. Den senare modellen använder sig inte av ordfrekvens eller längdnormalisering i sin beräkning, till skillnad från de tidigare modellerna. Evalueringsdatan bestod av titlar från Wikipedia som hämtats från den främsta konferensen inom informationssökning, Text retrieval conference (TREC), och även användarloggar hämtade från användarsökningar från Spotifys datasamling. Ingen av de alternativa modellerna presterade konsekvent bättre än BM25 när antalet ord i söktexten q varierade mellan 1 ≤ |q| ≤ 8. För kortare söktexter |q| ≤ 3 kunde både en binär oberoende modell och en BM25 adaptive term-modell (BM25adpt) prestera bättre än BM25. Vidare så kunde man se en ökning på den genomsnittliga precisionen (MAP) på 1% både hos den binära oberoende modellen och BM25adpt-modellen jämfört med BM25 när flera stickprov från användarloggdatan gjordes. På grund av att evalueringsdatan har en bias tillsammans med att den potentiella ökningen av MAP endast når upp till 1% drogs slutsatsen att fördelen med att använda en annan modell inte rättfärdigar bytet från BM25 vid titelsökning.

Résumé indisponible. / A healthcare network or health system consists of all organizations, actions and people who participate to promote, restore or maintain people’s health. The health care systems in many developed countries are facing increasing costs. The major reason is the changing age distribution of the population with more elderly people in need of support. Increasing healthcare costs has created new alternatives to traditional hospitalization in which one is Home Health Care (HHC). Home health care or domiciliary care is the provision of health care and assistance to people in their own homes, according to a formal assessment of their needs. HHC has attained a specific place in healthcare network. HHC programs have now been successfully implemented in many countries. The purpose of HHC is to provide the care and support needed to assist patients to live independently in their own homes. HHC is primarily performed by means of personal visitations of healthcare workers to patients in their homes, where they provide care assistance according to patients’ needs. In this thesis we have considered different aspects of planning problems for home health care services. The efficient use of resources is necessary in continuous healthcare services. To meet the increased demand of HHC, operation research specialist can play an important role by solving the various combinatorial optimization problems arising in HHC. These problems can be tactical, strategic or operational with respect to planning horizon. Strategic problems are those which help in attaining long term goals or objectives, e.g. higher level of quality for HHC patients and efficient use of resources. These strategic objectives can be achieved through tactical i.e. medium term panning and operational planning i.e. short term planning. The main purpose of our thesis is to identify these potential optimization problems and solve them via recent metaheuristics. HHC is an alternative to traditional hospitalization and has got a significant share in the organization of healthcare in developed countries. The change in aging demographics, recent development in technology and the increase in the demand of healthcare services are major reasons for this rapid growth. Some studies show HHC as a tool to reduce costs of care, which is a major preoccupation in developed countries. Some others reveal that it leads to the improvement of patients’ satisfaction without increasing the resources. Home health care, i.e. visiting and nursing patients in their homes, is a flourishing realm in the medical industry. The number of companies has grown largely both in public and private sectors. The staffing needs for HHC companies have been expanded as well. Also they face the problem of assigning geographically dispersed patients to home healthcare workers and preparing daily schedules for these workers. The challenge of this problem is to combine aspects of vehicle routing and staff rostering. Both of them are well known NP- hard combinatorial optimization problems, it means the amount of computational time required to find solution increases exponentially with problem size. Home healthcare workers scheduling problem is difficult to solve optimally due to presence of large number of constraints. These are two types of constraints: hard constraints and soft constraints. The hard constraints are the restrictions to be fulfilled for the schedules to be applicable and soft constraints are preferences to improve the quality of these schedules. (...)

The progess in NMRQIP can be outlined in to four parts.1) Implementation of theoretical protocols on small number of qubits. 2) Demonstration of QIP on various NMR systems. 3) Designing and implementing the algorithms for mixed initial states. 4) Developing the techniques for coherent and decoherent control on higher number(up to 15) of qubits. This thesis contains some efforts in the direction of first three points. Quantum-state discrimination has important applications in the context of quantum communication and quantum cryptography. One of the characteristic features of quantum mechanics is that it is impossible to devise a measurement that can distinguish nonorthogonal states perfectly. However, one can distinguish them with a finite probability by an appropriate measurement strategy. In Chapter 2, we describe the implementation of a theoretical protocol of programmable quantum-state discriminator, on a two-qubit NMR System. The projective measurement is simulated by adding two experiments. This device does the unambiguous discrimination of a pair of states of the data qubit that are symmetrically located about a fixed state. The device is used to discriminate both linearly polarized states and eillipitically polarized states. The maximum probability of successful discrimination is achieved by suitably preparing the ancilla quubit. The last step of any QIP protocol is the readout. In NMR-QIP the readout is done by using density matrix tomography. It was first proposed by Ernst and co-workers that a two-dimensional method can be used to correlate input and output states. This method uses an extra (aniclla) qubit, whose transitions indicate the quantum states of the remaining qubits. The 2D spectrum of ancilla qubit represent the input and output states along F1 and F2 dimensions respectively. However the 2D method requires several t1 increments to achieve the required spectral width and resolution in the indirect dimension, hence leads to large experimental time. In chapter 3, the conventional 2D NMRQIP method is speeded-up by using Hadamard spectroscopy. The Hadamard method is used to implement various two-, three-qubit gates and qutrit gates. We also use Hadamard spectroscopy for information storage under spatial encoding and to implement a parallel search algorithm. Various slices of water sample can be spatially encoded by using a multi-frequency pulse under the field gradient. Thus the information of each slice is projected to the frequency space. Each slice represents a classical bit, where excitation and no excitation corresponds to the binary values 0 and 1 respectively. However one has to do the experiment for each binary information, by synthesizing a suitable multi-frequency pulse. In this work we show that by recording the data obtained by various Hadamard encoded multi-frequency pulses, one can suitably decode it to obtain any birnary information, without doing further experiments. Geometric phases depend only on the geometry of the path executed in the projective Hilbert space, and are therefore resilient to certain types of errors. This leads to the possibility of an intrinsically fault-tolerant quantum computation. In liquid state NMRQIP. Controlled phase shift gates are achieved by using qubit selective pulses and J evolutions, and also by using geometir phases. In order to achieve higher number of qubits in NMR, one explores dipolar couplings which are larger in magnitude, yielding strongly coupled spectra. In such systems since the Hamiltonian consists of terms, it is difficult to apply qubit selective pulses. However such systems have been used for NMRQIP by considering 2n eigen states as basis states of an n-qubit system. In chapter 4, it is shown that non-adiabatic geometric phases can be used to implement controlled phase shift gates in strongly dipolar coupled systems. A detailed theoretical explanation of non-adiabatic geometric phases in NMR is given, by using single transition operators. Using such controlled phase shift gates, the implementation of Deutsch-Jozsa and parity algorithms are demonstrated. Search algorithms play an important role in the filed of information processing. Grovers quantum search algorithm achieves polynomial speed-up over the classical search algorithm. Bruschweiler proposed a Liouville space search algorithm which achieve polymonial speed-up. This algorithm requires a weakly coupled system with a mixed initial state. In chapter 5 we modified the Bruschweiler’s algorithm, so that it can be implemented on a weakly as well as strongly coupled system. The experiments are performed on a strongly dipolar coupled four-qubit system. The experiments from four spin-1/2 nuclei of a molecule oriented in a liquid crystal matrix. Chapter 6 describes the implementation of controlled phase shift gates on a quadrupolar spin-7/2 nucleus, using non-adiabatic geometric phases. The eight energy levels of spin-7/2 nucleus, form a three qubit system. A general procedure is given, for implementing a controlled phase shift gate on a system consisting of any number of energy levels. Finally Collin’s version of three-qubit DJ algorithm using multi-frequency pulses, is implemented in the spin-7/2 system.

Cellular beams became increasingly popular as an efficient structural form in steel construction since their introduction. Their sophisticated design and profiling process provides greater flexibility in beam proportioning for strength, depth, size and location of circular holes. The purpose of manufacturing these beams is to increase overall beam depth, the moment of inertia and section modulus, which results in greater strength and rigidity. Cellular beams are used as primary or secondary floor beams in order to achieve long spans and service integration. They are also used as roof beams beyond the range of portal-frame construction, and are the perfect solution for curved roof applications, combining weight savings with a low-cost manufacturing process. The purpose of the current research is to study optimum design, ultimate load capacity under applied load and finite element analysis of non-composite cellular beams. The first part of the research program focuses on the optimum design of steel cellular beams using one of the stochastic search methods called &ldquo / harmony search algorithm&rdquo / . The minimum weight is taken as the design objective while the design constraints are implemented from the Steel Construction Institute. Design constraints include the displacement limitations, overall beam flexural capacity, beam shear capacity, overall beam buckling strength, web post flexure and buckling, vierendeel bending of upper and lower tees and local buckling of compression flange. The design methods adopted in this publication are consistent with BS5950. In the second part of the research, which is the experimental work, twelve non-composite cellular beams are tested to determine the ultimate load carrying capacities of these beams under using a hydraulic plug to apply point load. The tested cellular beam specimens have been designed by using harmony search algorithm. Finally, finite element analysis program is used to perform elastic buckling analysis and predict critical loads of all steel cellular beams. Finite element analysis results are then compared with experimental test results for each tested cellular beam.

Economic dispatch is an important optimization challenge in power systems. It helps to find the optimal output power of a number of generating units that satisfy the system load demand at the cheapest cost, considering equality and inequality constraints. Many nature inspired algorithms have been broadly applied to tackle it such as particle swarm optimization. In this dissertation, two improved particle swarm optimization techniques are proposed to solve economic dispatch problems. The first is a hybrid technique with Bat algorithm. Particle swarm optimization as the main optimizer integrates bat algorithm in order to boost its velocity and to adjust the improved solution. The second proposed approach is based on Cuckoo operations. Cuckoo search algorithm is a robust and powerful technique to solve optimization problems. The study investigates the effect of levy flight and random search operation in Cuckoo search in order to ameliorate the performance of the particle swarm optimization algorithm. The two improved particle swarm algorithms are firstly tested on a range of 10 standard benchmark functions and then applied to five different cases of economic dispatch problems comprising 6, 13, 15, 40 and 140 generating units. / Electrical and Mining Engineering / M. Tech. (Electrical Engineering)

This works proposes a novel methodology for Fault Section Estimation in Power Systems. This document describes a computational tool to assist operators of electrical system in decision-making, thus ensuring the reliability of the energy supply and the reduction of reestablishment time after of fault occurrence. The proposed methodology is based on the interpretation of alarms provided by the Supervisory and Data Acquisition System (SCADA) and the electrical characteristics of the system, as well as impedance of transmission lines and transformers, circuit breakers states and settings of distance protective relays. The methodology is deterministic and uses the interception between zones of distance protective relays as base for the section estimation and the circuit breaker states to associate physically isolated sections in the system after of fault occurrence, making use of a shortest path search algorithm. Possible fault scenarios were simulated on the IEEE-30 Bus System in order to validate the methodology. The results show that the approach can provide satisfactory solutions, even in cases of multiple faults or failure of protections devices. / Este trabalho propõe uma nova metodologia para a estimação da seção de falta em sistemas elétricos de potência. O presente documento descreve uma ferramenta computacional capaz de auxiliar os operadores do sistema elétrico na tomada de decisão, favorecendo a confiabilidade do fornecimento da energia e a redução do tempo de reestabelecimento quando da ocorrência de falta. A metodologia proposta esta baseada na interpretação dos alarmes fornecidos pelo Sistema de Supervisão e Aquisição de dados (SCADA) e nas características elétricas do sistema, assim como impedâncias de linhas de transmissão e transformadores; nos estados dos disjuntores e nos sinais e ajustes dos relés de proteção de distância. A metodologia é determinística e utiliza a intercepção entre as zonas de proteção dos relés de distância como base para a estimação da seção e os estados dos disjuntores para associar as seções fisicamente isoladas no sistema ante a ocorrência de falta, fazendo uso de um algoritmo de busca do caminho mais curto. Possíveis cenários de falta foram simulados no sistema IEEE-30 barras a fim de validar a metodologia. Os resultados mostram que a abordagem consegue fornecer soluções satisfatórias, mesmo em casos de faltas múltiplas ou em caso de falha de dispositivos de proteção.

Made available in DSpace on 2015-05-08T14:53:25Z (GMT). No. of bitstreams: 1 ArquivoTotalJoseAlmeida.pdf: 1891145 bytes, checksum: 15212c0ee3aea31416abaeb33cac710c (MD5) Previous issue date: 2013-08-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The research project studied, aimed to apply a forward search algorithm to aid decision making in multivariate statistical process control in the manufacture of crates in a company of plastic products. Besides, the use of principal components analysis (PCA) and the Hotelling T square chart can summarize relevant information of this process. Thus, they were produced two results of considerable importance: the scores of the principal components and an adapted Hotelling T square chart, highlighting the relationship between the ten variables analyzed. The forward search algorithm detects discordant points of the data clustering rest that, when are too far away or have very different characteristics, are called outliers. The BACON algorithm was used for the detection of such occurrences, which part of a small subset demonstrably free of the original data outliers and it goes adding new information, which is not outliers, to this initial subset until no information can more be absorbed. One of the advantages of using this algorithm is that it combats the masking and swamping phenomena that alter the mean and covariance estimates. The research results showed that, for the dataset studied, the BACON algorithm did not detected no dissenting point. A simulation was then developed, using a uniform distribution by obtaining random numbers within a range for modifying the mean and standard deviation values, in order to show that this method is effective in detecting these outliers. For this simulation, they were randomly changed 5% of the mean and the standard deviation values of the original data. The result of this simulation showed that the BACON algorithm is perfectly applicable to this case study, being indicated its use in other processes that simultaneously depend on several variables. / O projeto de pesquisa estudado teve o objetivo de aplicar um algoritmo de busca sucessiva para o auxílio à tomada de decisão no controle estatístico do processo multivariado, na fabricação de garrafeiras em uma empresa de produtos plásticos. Além disso, a utilização das técnicas de análise de componentes principais (ACP) e da carta T² de Hotelling pode sumarizar parte das informações relevantes desse processo. Produziram-se então dois resultados de considerável importância: os escores dos componentes principais e um gráfico T² de Hotelling adaptado, evidenciando a relação entre as dez variáveis analisadas. O algoritmo de busca sucessiva detecta pontos discordantes do restante do agrupamento de dados que, quando se encontram muito distantes ou têm características muito diferentes, são denominados outliers. O algoritmo BACON foi utilizado para a detecção de tais ocorrências, o qual parte de um pequeno subconjunto, comprovadamente livre de outliers, dos dados originais e vai adicionando novas informações, que também não são outliers, a esse subconjunto inicial até que nenhuma informação possa mais ser absorvida. Uma das vantagens da utilização desse algoritmo é que ele combate os fenômenos do mascaramento e do esmagamento que alteram as estimativas da média e da covariância. Os resultados da pesquisa mostraram que, para a o conjunto de dados estudados, o algoritmo BACON não detectou nenhum ponto discordante. Uma simulação foi então desenvolvida, utilizando uma distribuição uniforme através da obtenção de números aleatórios dentro de um intervalo para a modificação dos valores da média e do desvio-padrão, a fim de mostrar que tal método é eficaz na detecção desses pontos aberrantes. Para essa simulação, foram alterados aleatoriamente os valores da média e do desvio-padrão de 5% dos dados originais. O resultado dessa simulação mostrou que o algoritmo BACON é perfeitamente aplicável ao caso estudado, sendo indicada a sua utilização em outros processos produtivos que dependam simultaneamente de diversas variáveis.

This thesis presents two new routing problems, both with objective functions focused on relative positioning of teams during the routing horizon. The relative positioning results in temporal and spatial dependencies among routes and is quantified with a nonlinear dispersion metric, designed to evaluate the instantaneous distances among teams over a time interval. This metric allows the design of objective functions to approximate teams during routes execution, when minimized, or disperse them, when maximized. Both approximation and dispersion are important routing characteristics in some practical applications, and two new optimization problems are proposed with these opposite objectives. The first one is a variation of the Multiple Traveling Salesman Problem, and its goal is to find a set of tours where the salesmen travel close to each other, minimizing dispersion. A Local Search Genetic Algorithm is proposed to solve the problem. It includes specialized genetic operators and neighborhoods. A new set of benchmark instances is proposed, adapted for the new problem from literature instances. Computational results show that the proposed approach provides solutions with the desired characteristics of minimal dispersion. The second problem is a bi-objective arc routing problem in which routes must be constructed in order to maximize collected profit and dispersion of teams. The maximization of the dispersion metric fosters the scattering of the teams during routing procedure. Usually, profit and dispersion objectives are conflicting, and by using a bi-objective approach the decision maker is able to choose a trade-off between collecting profits and scattering teams. Two solution methods are proposed, a Multi-objective Genetic Algorithm and a Multi-objective Genetic Local Search Algorithm, both specialized in order to exploit the characteristics of the problem. It is demonstrated, by means of computational experiments on a new set of benchmark instances, that the proposed approach provides approximation sets with the desired characteristics. / Esta tese apresenta dois novos problemas de roteamento, ambos com funções objetivo voltadas para o posicionamento relativo das equipes durante o horizonte de roteamento. O posicionamento relativo resulta em uma dependência temporal e espacial entre rotas e é quantificado com uma métrica de dispersão não-linear, projetada para avaliar as distâncias instantâneas entre as equipes ao longo de um intervalo de tempo. Esta métrica permite a concepção de funções objetivo para aproximar as equipes durante a execução das rotas, quando minimizada, ou para dispersá-las, quando maximizada. Tanto a aproximação quanto a dispersão são características importantes de roteamento em algumas aplicações práticas, e dois novos problemas de otimização são propostos com esses objetivos opostos. O primeiro é uma variação do Problema de Múltiplos Caixeiros Viajantes, e seu objetivo é encontrar um conjunto de rotas em que os caixeiros viajam próximos uns dos outros, minimizando a dispersão. Um Algoritmo Genético com Busca Local é proposto para resolver o problema. Ele inclui operadores genéticos e vizinhanças especializados. Um novo conjunto de instâncias é proposto, adaptado para o novo problema de instâncias da literatura. Resultados computacionais mostram que a abordagem proposta proporciona soluções com as características desejadas de dispersão mínima. O segundo problema é um problema de roteamento de arcos biobjetivo em que as rotas devem ser construídas de modo a maximizar o lucro recolhido e o distanciamento entre as equipes. A maximização da métrica promove a dispersão das equipes durante a execução das rotas. Normalmente, os objetivos de lucro e dispersão são conflitantes, e com uma abordagem biobjetivo o tomador de decisão é capaz de avaliar a troca entre a coleta de lucros e a dispersão de equipes. Dois métodos de solução são propostos, um Algoritmo Genético Multiobjetivo e um Algoritmo Genético Multiobjetivo com Busca Local, ambos especializados para explorar as características do problema. É demonstrado, por meio de experimentos computacionais sobre um novo conjunto de instâncias, que a abordagem proposta fornece conjuntos de aproximação com as características desejadas.