Wireless sensor networks (WSN) increasingly permeate modern societies nowadays. But in spite of their plethora of successful applications, WSN are often unable to surmount many operational challenges that unexpectedly arise during their lifetime. Fortunately, robotic agents can now assist a WSN in various ways. This thesis illustrates how mobile robots which are able to carry a limited number of sensors can help the network react to sensor faults, either during or after its deployment in the monitoring region. Two scenarios are envisioned. In the first one, carrier robots surround a point of interest with multiple sensor layers (focused coverage formation). We put forward the first known algorithm of its kind in literature. It is energy-efficient, fault-reactive and aware of the bounded robot cargo capacity. The second one is that of replacing damaged sensing units with spare, functional ones (coverage repair), which gives rise to the formulation of two novel combinatorial optimization problems. Three nature-inspired metaheuristic approaches that run at a centralized location are proposed. They are able to find good-quality solutions in a short time. Two frameworks for the identification of the damaged nodes are considered. The first one leans upon diagnosable systems, i.e. existing distributed detection models in which individual units perform tests upon each other. Two swarm intelligence algorithms are designed to quickly and reliably spot faulty sensors in this context. The second one is an evolving risk management framework for WSNs that is entirely formulated in this thesis.

Adaptive traffic signal control is the process by which the timing of a traffic signal is continuously adjusted based on the changing arrival patterns of vehicles at an intersection, usually with the goal of optimizing a given measure of effectiveness. Herein, a methodology is developed in which the characteristics of a traffic signal cycle are optimized at the conclusion of every phase based on the arrival times of vehicles to an intersection, using stopped delay as the measure of effectiveness. This optimization is solved using metaheuristic search procedures, namely tabu search, and embedded in an algorithm in which current vehicle arrival times are detected, arrival patterns over a specified horizon are predicted, the traffic signal timing is optimized, and the timings are sent to a traffic signal controller. The methodology is shown to provide improvement in performance for a number of intersection configurations and traffic regimes over traditional forms of traffic signal control, and the metaheuristic search is demonstrated to significantly reduce the computation time for a solution as compared with other search procedures. / text

The two-dimension packing problem is concerned with the arrangement of items without overlaps inside a container. In particular we have considered the case when the items are circular objects, some of the general examples that can be found in the industry are related with packing, storing and transportation of circular objects. Although there are several approaches we want to investigate the use of formulation space search. Formulation space search is a fairly recent method that provides an easy way to escape from local optima for non-linear problems allowing to achieve better results. Despite the fact that it has been implemented to solve the packing problem with identical circles, we present an improved implementation of the formulation space search that gives better results for the case of identical and non-identical circles, also considering that they are packed inside different shaped containers, for which we provide the needed modifications for an appropriate implementation. The containers considered are: the unit circle, the unit square, two rectangles with different dimension (length 5, width 1 and length 10 width 1), a right-isosceles triangle, a semicircle and a right-circular quadrant. Results from the tests conducted shown several improvements over the best previously known for the case of identical circles inside three different containers: a right-isosceles triangle, a semicircle and a circular quadrant. In order to extend the scope of the formulation space search approach we used it to solve mixed-integer non-linear problems, in particular those with zero-one variables. Our findings suggest that our implementation provides a competitive way to solve these kind of problems.

Wireless sensor networks (WSN) increasingly permeate modern societies nowadays. But in spite of their plethora of successful applications, WSN are often unable to surmount many operational challenges that unexpectedly arise during their lifetime. Fortunately, robotic agents can now assist a WSN in various ways. This thesis illustrates how mobile robots which are able to carry a limited number of sensors can help the network react to sensor faults, either during or after its deployment in the monitoring region. Two scenarios are envisioned. In the first one, carrier robots surround a point of interest with multiple sensor layers (focused coverage formation). We put forward the first known algorithm of its kind in literature. It is energy-efficient, fault-reactive and aware of the bounded robot cargo capacity. The second one is that of replacing damaged sensing units with spare, functional ones (coverage repair), which gives rise to the formulation of two novel combinatorial optimization problems. Three nature-inspired metaheuristic approaches that run at a centralized location are proposed. They are able to find good-quality solutions in a short time. Two frameworks for the identification of the damaged nodes are considered. The first one leans upon diagnosable systems, i.e. existing distributed detection models in which individual units perform tests upon each other. Two swarm intelligence algorithms are designed to quickly and reliably spot faulty sensors in this context. The second one is an evolving risk management framework for WSNs that is entirely formulated in this thesis.

Combinatorial optimisation problems (COPs) pervade human society: scheduling, design, layout, distribution, timetabling, resource allocation and project management all feature problems where the solution is some combination of elements, the overall value of which needs to be either maximised or minimised (i.e., optimised), typically subject to a number of constraints. Thus, techniques to efficiently solve such problems are an important area of research. A popular group of optimisation algorithms are the metaheuristics, approaches that specify how to search the space of solutions in a problem independent way so that high quality solutions are likely to result in a reasonable amount of computational time. Although metaheuristic algorithms are specified in a problem independent manner, they must be tailored to suit each particular problem to which they are applied. This thesis investigates a number of aspects of the application of the relatively new Ant Colony Optimisation (ACO) metaheuristic to different COPs.The standard ACO metaheuristic is a constructive algorithm loosely based on the foraging behaviour of ant colonies, which are able to find the shortest path to a food source by indirect communication through pheromones. ACO’s artificial pheromone represents a model of the solution components that its artificial ants use to construct solutions. Developing an appropriate pheromone representation is a key aspect of the application of ACO to a problem. An examination of existing ACO applications and the constructive approach more generally reveals how the metaheuristic can be applied more systematically across a range of COPs. The two main issues addressed in this thesis are biases inherent in the constructive process and the systematic selection of pheromone representations.The systematisation of ACO should lead to more consistently high performance of the algorithm across different problems. Additionally, it supports the creation of a generalised ACO system, capable of adapting itself to suit many different combinatorial problems without the need for manual intervention.

Mémoire (M.Inf.)-- Université du Québec à Chicoutimi, 2002. / Document électronique également accessible en format PDF. CaQCU

Thesis (MEng)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The cross-entropy method for multi-objective optimisation (MOO CEM) was recently introduced by Bekker & Aldrich (2010) and Bekker (2012). Results presented by both show great promise. The MOO CEM assumes that decision variables are independent. As a consequence, the question arises: under which circumstances would an algorithm that accounts for relationships between decision variables outperform the MOO CEM? Two algorithms reported to account for relationships between decision variables, the multi-objective covariance matrix adaptation evolution strategy (MOCMA- ES) and Pareto di erential evolution (PDE), are selected for comparison. In addition, two hybrid algorithms (Hybrid 1 and Hybrid 2) based on the MOO CEM are created. These ve algorithms are applied to a set of 46 continuous problems, six instances of the mission-ready resource (MRR) problem, and three instances of a dynamic, stochastic bu er allocation problem (BAP). Performance is measured using the hypervolume indicator and Mann-Whitney U-tests. One of the primary ndings is that accounting for relationships between decision variables is bene cial when solving small to medium-sized problems. In these cases, the MO-CMA-ES typically outperforms the other algorithms. However, on large problems, Hybrid 1 and the MOO CEM typically perform best. / AFRIKAANSE OPSOMMING: Die kruis-entropie metode vir meerdoelige optimering (MOO CEM) is onlangs deur Bekker & Aldrich (2010) en Bekker (2012) bekendgestel. Hul resultate is belowend. Die MOO CEM neem aan dat besluitnemingsveranderlikes onafhanklik is van mekaar. Gevolglik ontstaan die vraag: onder watter omstandighede sal 'n optimeringsalgoritme wat moontlike verhoudings tussen besluitnemingsveranderlikes in ag neem, beter vaar as die MOO CEM? Twee bestaande algoritmes, beide gerapporteer vir hul vermo e om moontlike verhoudings tussen besluitnemingsveranderlikes in ag te neem, naamlik die meerdoelige optimering kovariansiematriksaanpassing-evolusiestrategie (MO-CMA-ES) en Pareto afgeleide evolusie (PDE), word met die MOO CEM vergelyk. Twee nuwe hibriedalgoritmes (Hibried 1 en Hibried 2) word ook ter wille van di e vergelyking geskep. Die vyf algoritmes word op 'n stel van 46 kontinue probleme, ses statiese kombinatoriese gevalle en drie dinamies, stogastiese gevalle toegepas. Die prestasie van die algoritmes word deur middel van die hipervolume-aanwyser en Mann-Whitney U-toetse gemeet. 'n Prim^ere bevinding is dat dit voordelig is om moontlike verhoudings tussen besluitnemingsveranderlikes in ag te neem wanneer klein na medium-grootte probleme opgelos word. Vir hierdie gevalle presteer die MO-CMA-ES tipies beter as die ander algoritmes. Vir groot probleme presteer Hibried 1 en die MOO CEM beter as die ander algoritmes. / National Research Foundation

Orientador: José Roberto Sanches Mantovani / Resumo: Neste trabalho é proposto o desenvolvimento de uma ferramenta computacional para o planeja-mento e despacho ótimo de fontes de potência ativa, considerando as incertezas das cargas (le-ve, nominal e pesada) e fontes de energia renováveis não despacháveis através de uma aborda-gem probabilística. O modelo matemático é um problema de programação não linear inteiro misto, multiobjetivo, não convexo e probabilístico na sua forma original sem a necessidade de realizar qualquer tipo de simplificação ou linearização tanto das funções objetivo como das res-trições. Um algoritmo baseado na meta-heurística Non-dominated Sorting Genetic Algorithm (NSGA-II) é proposto para resolver o problema de maneira eficaz. Os resultados obtidos com as simulações realizadas usando a implementação computacional nos sistemas de testes IEEE30 barras e IEEE118 barras mostram a eficiência e robustez da metodologia proposta. / Abstract: This work proposes the development of a computational tool for the planning and optimal dispatch of active power sources, considering the uncertainties of the loads (light, nominal and heavy) and non-dispatchable renewable energy sources through a probabilistic approach. The mathematical model is a multi-objective mixed-integer nonlinear programing problem, that is nonconvex and probabilistic in its original form, without the need to perform any kind of simplification or linearization of both objective functions and constraints. An algorithm based on the Non-dominated Sorting Genetic Algorithm (NSGA-II) meta-heuristic is pro-posed to solve the problem effectively. The results obtained with the simulations performed using the computational implementation in the IEEE30 bus and IEEE118 bus test systems show the efficiency and robustness of the proposed methodology. / Doutor

Submitted by Lara Oliveira (lara@ufersa.edu.br) on 2017-04-17T22:15:28Z No. of bitstreams: 1 AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-26T12:14:12Z (GMT) No. of bitstreams: 1 AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Approved for entry into archive by Vanessa Christiane (referencia@ufersa.edu.br) on 2017-04-26T12:16:44Z (GMT) No. of bitstreams: 1 AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) / Made available in DSpace on 2017-04-26T12:19:14Z (GMT). No. of bitstreams: 1 AlexsandroTSS_DISSERT.pdf: 2805904 bytes, checksum: d89eac5a3d1bbff746e28effc0f94ba8 (MD5) Previous issue date: 2016-07-20 / The use of metaheuristics for solving combinatorial optimization problems belong to NP-Hard class is becoming increasingly common, and second Temponi (2007 apud RIBEIRO, 1996) a metaheurist should be modeled according to the problem she was designed to solve. This most often requires many changes when you have to apply the same metaheuristic to various types of combinatorial optimization problems. In this work we propose a framework for use of a hybrid metaheuristic proposed by Almeida (2014) who used the GRASP Reactive along with a reinforcement learning technique (called GR-learning). Specifically, the Q-learning algorithm that was used to learn over which the iterations value for the parameter α (alpha) used during the construction phase of GRASP. The GR-Learning was used to solve the problem of p-centers applied to Public Security in the city of Mossoró/RN. To validate the effectiveness of the framework proposed it was used to solve two classical problems of combinatorial optimi-zation: The Hub Location Problem (HLP), and the Cutting Stock Problem (CSP). To validate the results obtained we used instances with results known in the literature and in addition has created an instance with data from the Brazilian airline industry. The results showed that the proposed framework was quite competitive when compared to other results of different algo-rithms known in the literature as got great value in almost all instances of HLP as well as new values (better than those obtained with other algorithms known in the literature) for some ins-tances of CSP / A utilização de metaheurísticas para resolução de problemas de otimização combinatória per-tencentes à classe NP-Difícil vem se tornando cada vez mais comum, e segundo Temponi (2007 apud RIBEIRO, 1996) uma metaheurística deve ser modelada de acordo com o proble-ma que ela foi projetada para resolver. Isto na maioria vezes requer muitas alterações quando se tem que aplicar uma mesma metaheurística a diversos tipos de problemas de otimização combinatória. Neste trabalho foi proposto um framework para utilização de uma metaheurísti-ca híbrida proposta por Almeida (2014) que utilizou a metaheurística GRASP Reativo junta-mente com uma técnica de aprendizagem por reforço (denominada GR-Learning). Especifi-camente, o algoritmo Q-learning, que foi utilizado para aprender com o passar das iterações qual valor para o parâmetro α (alfa) utilizar durante a fase de construção da GRASP. O GR-Learning foi utilizado para resolver o problema dos p-Centros aplicado a Segurança Pública na Cidade de Mossoró/RN. Para validar a eficácia do framework proposto o mesmo foi utili-zado para resolver dois problemas clássicos de otimização combinatória: O Problema de Lo-calização de Hubs (do inglês Hub Location Problem - HLP) e o Problema de Corte e Estoque – PCE (do inglês Cutting Stock Problem - CSP). Para validação dos resultados obtidos foram utilizadas instâncias com resultados já conhecidos na literatura e adicionalmente foi criada uma instância com dados do setor aeroviário Brasileiro. Os resultados obtidos mostraram que o framework proposto foi bastante competitivo quando comparado a outros resultados de di-versos algoritmos já conhecidos na literatura, pois obteve o valor ótimo em quase todas as instâncias do HLP como também novos valores (melhores que os obtidos com outros algorit-mos já conhecido na literatura) para algumas instâncias do CSP / 2017-04-17

Hoje em dia, desenvolvedores de sistemas embarcados enfrentam uma crescente complexidade de projeto, tanto nas aplicações quanto nas plataformas usadas para executá-las. O uso de plataformas complexas faz com que os engenheiros precisem fazer escolhas não-triviais, e muitas vezes contra-intuitivas durante a fase de projeto. Para permitir que os projetistas gerenciem esta complexidade, o uso de metodologias baseadas em modelos tem atraído atenção, e dentro deste contexto, a metodologia HIPAO2 está sendo desenvolvida dentro da UFRGS. Dentre os problemas que os engenheiros precisam enfrentar, o mapeamento entre tarefas e processadores em sistemas multiprocessados heterogêneos é um problema NP-completo, onde o espaço de projeto rapidamente se torna grande demais para que seja explorado satisfatoriamente de maneira manual. Este trabalho detalha a extensão das ferramentas que suportam a metodologia HIPAO2, de maneira a incluir facilidades de Exploração de Espaço de Projeto semi-automática para a solução deste problema. A ferramenta proposta faz uso de um algoritmo genético multiobjetivo para evidenciar tradeoffs existentes no projeto, e algoritmos de análise de aplicações modeladas como synchronous dataflow para avaliar possíveis mapeamentos sem um custo computacional proibitivo. / Designers of today’s embedded systems are faced with increasing complexity both in the applications being developed and the platforms they run on. The use of complex platforms means that the engineers need to make non-trivial and many times non-intuitive decisions during the design phase. To help developers work with this complexity, model-driven techniques are gaining attention, and in this context, the HIPAO2 model-driven engineering methodology is being developed at UFRGS. Among the problems that designers must solve, the task-to-processor mapping in heterogeneous multiprocessor systems is an NP-complete problem and the design space will quickly become too large to be explored adequately by humans. This work details the extension of the tools that support HIPAO2 to include semiautomatic Design-Space Exploration capabilities for the mapping problem. The proposed tool includes the use of a multiobjective genetic algorithm to make tradeoffs explicit to the designers; it also uses synchronous dataflow analysis algorithms to evaluate potential alternatives with a reasonable computational cost.