The main topic of this PhD thesis is metaheuristic algorithm in wider scope. The first chapters are dedicated to a description of broader context of metaheuristics, i.e. various optimization classes, determination of their omplexity and different approaches to their solutions. The consequent discussion about metaheuristics and their typical characteristics is followed by several selected examples of metaheuristics concepts. The observed characteristics serve as a base for building general metaheuristics model which is suitable for developing brand new or hybrid algorithms. The thesis is concluded by illustration of author’s publications with discussion about their adaptation to the proposed model. On the attached CD, there is also available a program implementation of the created model.

A programação concorrente é cada vez mais utilizada nos sistemas atuais com o objetivo de reduzir custos e obter maior eficiência no processamento. Com a importância da programação concorrente é imprescindível que programas que implementam esse paradigma apresentem boa qualidade e estejam livres de defeitos. Assim,diferentes técnicas e critérios de teste vêm sendo definidos para apoiar a validação de aplicações desenvolvidas nesse paradigma. Nesse contexto, a geração automática de dados de teste é importante, pois permite reduzir o custo na geração e seleção de dados relevantes. O uso de técnicas meta-heurísticas tem sido uma área de grande interesse entre os pesquisadores para geração de dados, pois essas técnicas apresentam abordagens aplicáveis a problemas complexos e de difícil solução. Considerando esse aspecto, este trabalho apresenta uma abordagem de geração automática de dados para o teste estrutural de programas concorrentes em MPI (Message Passing Interface). A meta-heurística usada foi Algoritmo Genético em que a busca é guiada por critérios de teste que consideram características implícitas de programas concorrentes. O desempenho da abordagem foi avaliado por meio da cobertura dos dados detestes, da eficácia em revelar defeitos e do custo de execução. Para comparação, a geração aleatória foi considerada. Os resultados indicaram que é promissor usar geração de dados de teste no contexto de programas concorrentes, com resultados interessantes em relação à eficácia e cobertura dos requisitos de teste. / Concurrent programming has been increasingly used in current systems in order to reduce costs and obtain higher processing efficiency and, consequently, it is expected that these systems have high quallity. Therefore, different techniques and testing criteria have been proposed aiming to support the verification and validation of the concurrent applications. In this context, the automated data test generation allows to reduce the testing costs during the generation and selection of data tests. Metaheuristic technique has been widely investigated to support the data test generation because this technique has presented good results to complex and costly problems. In this work, we present an approach to the automated data test generation for message passing concurrent programs in MPI (Message Passing Interface). The generation of data test is performed using the genetic algorithm metaheuristic technique, guiding by structural testing criteria. An experimental study was conducted to evaluate the proposed approach, analyzing the effectiveness and application cost. The results indicate that the genetic algorithm is a promising approach to automated test data generation for concurrent programs, presenting good results in relation to effectiveness and data test coverage.

This study aims to answer whether a heuristic that trades cycles between the tours in a solution would show good results when trying to solve the Weighted k-Chinese Postman Problem for undirected graphs, of varying size, representing neighbourhoods in Sweden.A tabu search heuristic was implemented with each iteration consisting of giving a cycle from the most expensive tour to the cheapest. The heuristic performed increasingly well for graphs of increasing size, although the solution quality decreased when increasing the number of tours to be used in the solution. It is suspected that the cause for this behavior is due to the heuristic only giving cycles from the most expensive tour, not considering trading cycles from other tours in the solution. It is believed that a heuristic considering more than only the most expensive tour when trading cycles would produce even better solutions.

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2016-05-09T16:17:46Z No. of bitstreams: 1 Vinicius José Schmidt_.pdf: 1328036 bytes, checksum: 6da7dd7865c3b2470fda338536aa5d69 (MD5) / Made available in DSpace on 2016-05-09T16:17:46Z (GMT). No. of bitstreams: 1 Vinicius José Schmidt_.pdf: 1328036 bytes, checksum: 6da7dd7865c3b2470fda338536aa5d69 (MD5) Previous issue date: 2016-02-29 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho apresenta um modelo de metaheurística baseado em interação social de agentes inteligentes, utilizando-se do aprendizado social reproduzido por uma população de agentes para alcançar a otimização de problemas. O método aqui descrito é focado em interação social de seres humanos, tais como: comparação de status social, tendência da sociedade baseada nas pessoas mais influentes, troca de conhecimento, pessoas menos influentes seguindo os mais influentes no seu grupo e a busca de uma pessoa pelo local onde ela alcança seu melhor desempenho. A influência de um agente é medida através de seu status social, sendo assim, cada agente possui um raio de influência proporcional ao seu status. Esses conceitos foram modelados para a criação da técnica, sendo o aprendizado entre agentes ocorrido quando um agente menos influente encontra-se na região de influência de um agente mais bem-sucedido que ele. Resultados de testes, tanto de benchmark quanto de problemas reais, são apresentados e discutidos. Os testes indicam que a metaheurística é um modelo populacional promissor. / This work presents a metaheuristic model based on intelligent agents social interaction, using the social learning of a population of agents to achieve problems optimization. The method described here is based on humans social interaction, such as: comparison of social status, trend of society based on the most influential people, knowledge exchange, less influential people following the ones with most influential in their group and the search of a person where he achieves its best performance. An agent’s influence is measured through its social status, therefore, each agent have an influence radius proportional to its status. These concepts were modeled to create the technique, the learning among agents occurs when a less influential agent is located inside the influence region of an agent with more social status than him. Tests results, benchmark and real life problems, are presented and discussed. Those tests indicate that the model is a promising population metaheuristic.

O estudo da proteção em sistemas elétricos de potência representa um tópico de grande relevância proporcionando continuidade do serviço e segurança da operação. Hoje, a coordenação de relés direcionais de sobrecorrente (RDSs) é realizada usando formulações matemáticas que basicamente levam em consideração o tempo de operação dos dispositivos e o atendimento ao intervalo de tempo de coordenação (ITC). Nesta tese tem sido realizada a coordenação e seletividade entre RDSs considerando a otimização simultânea das unidades temporizada e instantânea de fase e neutro, contingências em circuitos mutuamente acoplados e ajuste automático das curvas. Algumas questões como os critérios de curtos-circuitos e tratamento topológico para circuitos interligados são também discutidas. Inicialmente, os estudos foram tratados como Otimização Monobjetivo (soma ponderada) minimizando a soma do tempo dos relés primários quando aplicado um curto-circuito do tipo close-in, na barra remota e a soma dos ajustes da unidade de sobrecorrente instantânea. Em sequência duas abordagens envolvendo um aspecto multiobjetivo são propostas. A primeira minimiza o tempo de operação de todos dispositivos de proteção, enquanto maximiza um índice de coordenação, ocasionando então em ITC variável. Já a segunda, além de minimizar o tempo de operação, o número de ajustes permitidos a serem alterados é limitado pelo operador, se a coordenação de todos elementos envolvidos for inviável. Os ajustes dos RDSs são obtidos por meio de algoritmos meta-heurísticos (derivados do Particle Swarm Optimization e Non-dominated Sorting Genetic Algorithm-II. Os métodos modernos ou inteligentes, concebidos a partir de conceitos de inteligência artificial, têm evoluído rapidamente e permitem a obtenção de excelentes soluções com a confiabilidade adequada para aplicações em engenharia. A eficácia e robustez do método são realizadas em um sistema de transmissão pertencente à área de uma concessionária brasileira. Por fim, os resultados foram bem satisfatórios visto que o emprego da unidade instantânea e múltiplas curvas diminuiu substancialmente a soma de tempo de atuação dos dispositivos de proteção, contribuindo para minimizar o trabalho empregado pelo engenheiro de proteção com segurança e rica informação técnica. Ademais, as estratégias multiobjetivos auxiliam o operador na tomada de decisão uma vez que cada solução encontrada atende específicas restrições oriundas do equipamentos empregados ou estados contingenciais da rede. / The study of power system protection represents a highly relevant topic providing continuity of service and safety of operation. Today, the coordination of directional overcurrent relays (DORs) is performed using mathematical formulations that basically take into account the operation time of the devices and the coordination time interval (CTI). In this thesis, coordination and selectivity between DORs have been performed considering the simultaneous optimization of the instantaneous and time overcurrent unit (both phase and ground), contingencies in coupled mutually circuits and automatic determination of the curves. Some issues are also discussed such as criteria for short-circuit calculation and topological treatment for interconnected circuits. Initially, the studies were considered as being a case of Monobjective Optimization (weighted sum) by minimizing the sum of operation time of primary relays when occur close-in and line-end faults and also the sum of the instantaneous overcurrent unit. In sequence are proposed two approaches involving multiobjective aspect. The first minimizes the operating time of all protection devices, while maximizing a coordination index (here, CTI is non-fixed). The second, besides minimizing the operating time, the number of settings allowed to alter is limited by operator, if the coordination of all elements involved is not possible in practice. The settings of DORs have been found by using meta-heuristic algorithms (derived from Particle Swarm Optimization and Non-dominated Sorting Genetic Algorithm-II). Modern or intelligent methods, conceived from artificial intelligence, have evolved rapidly and obtained excellent solutions with the acceptable reliability for engineering applications. The test has been carried out on a transmission network from a Brazilian utility. Finally, the results were well satisfactory because using the instantaneous unit and multiple curves substantially reduced the sum of operating time of the protective devices, contributing to decrease workload of protection engineers with safety and rich technical information. In addition, the multiobjective strategies help the operator in the decision making since each solution satisfies specific constraints coming from used equipment or contingency states of the existing network.

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.

O estudo da proteção em sistemas elétricos de potência representa um tópico de grande relevância proporcionando continuidade do serviço e segurança da operação. Hoje, a coordenação de relés direcionais de sobrecorrente (RDSs) é realizada usando formulações matemáticas que basicamente levam em consideração o tempo de operação dos dispositivos e o atendimento ao intervalo de tempo de coordenação (ITC). Nesta tese tem sido realizada a coordenação e seletividade entre RDSs considerando a otimização simultânea das unidades temporizada e instantânea de fase e neutro, contingências em circuitos mutuamente acoplados e ajuste automático das curvas. Algumas questões como os critérios de curtos-circuitos e tratamento topológico para circuitos interligados são também discutidas. Inicialmente, os estudos foram tratados como Otimização Monobjetivo (soma ponderada) minimizando a soma do tempo dos relés primários quando aplicado um curto-circuito do tipo close-in, na barra remota e a soma dos ajustes da unidade de sobrecorrente instantânea. Em sequência duas abordagens envolvendo um aspecto multiobjetivo são propostas. A primeira minimiza o tempo de operação de todos dispositivos de proteção, enquanto maximiza um índice de coordenação, ocasionando então em ITC variável. Já a segunda, além de minimizar o tempo de operação, o número de ajustes permitidos a serem alterados é limitado pelo operador, se a coordenação de todos elementos envolvidos for inviável. Os ajustes dos RDSs são obtidos por meio de algoritmos meta-heurísticos (derivados do Particle Swarm Optimization e Non-dominated Sorting Genetic Algorithm-II. Os métodos modernos ou inteligentes, concebidos a partir de conceitos de inteligência artificial, têm evoluído rapidamente e permitem a obtenção de excelentes soluções com a confiabilidade adequada para aplicações em engenharia. A eficácia e robustez do método são realizadas em um sistema de transmissão pertencente à área de uma concessionária brasileira. Por fim, os resultados foram bem satisfatórios visto que o emprego da unidade instantânea e múltiplas curvas diminuiu substancialmente a soma de tempo de atuação dos dispositivos de proteção, contribuindo para minimizar o trabalho empregado pelo engenheiro de proteção com segurança e rica informação técnica. Ademais, as estratégias multiobjetivos auxiliam o operador na tomada de decisão uma vez que cada solução encontrada atende específicas restrições oriundas do equipamentos empregados ou estados contingenciais da rede. / The study of power system protection represents a highly relevant topic providing continuity of service and safety of operation. Today, the coordination of directional overcurrent relays (DORs) is performed using mathematical formulations that basically take into account the operation time of the devices and the coordination time interval (CTI). In this thesis, coordination and selectivity between DORs have been performed considering the simultaneous optimization of the instantaneous and time overcurrent unit (both phase and ground), contingencies in coupled mutually circuits and automatic determination of the curves. Some issues are also discussed such as criteria for short-circuit calculation and topological treatment for interconnected circuits. Initially, the studies were considered as being a case of Monobjective Optimization (weighted sum) by minimizing the sum of operation time of primary relays when occur close-in and line-end faults and also the sum of the instantaneous overcurrent unit. In sequence are proposed two approaches involving multiobjective aspect. The first minimizes the operating time of all protection devices, while maximizing a coordination index (here, CTI is non-fixed). The second, besides minimizing the operating time, the number of settings allowed to alter is limited by operator, if the coordination of all elements involved is not possible in practice. The settings of DORs have been found by using meta-heuristic algorithms (derived from Particle Swarm Optimization and Non-dominated Sorting Genetic Algorithm-II). Modern or intelligent methods, conceived from artificial intelligence, have evolved rapidly and obtained excellent solutions with the acceptable reliability for engineering applications. The test has been carried out on a transmission network from a Brazilian utility. Finally, the results were well satisfactory because using the instantaneous unit and multiple curves substantially reduced the sum of operating time of the protective devices, contributing to decrease workload of protection engineers with safety and rich technical information. In addition, the multiobjective strategies help the operator in the decision making since each solution satisfies specific constraints coming from used equipment or contingency states of the existing network.

L'objectif de cette thèse est de proposer des algorithmes d'optimisation efficaces pour un système de tranport en commun à la demande proposé par Padam Mobility, une start-up Parisienne. Après avoir modélisé le problème comme un DARP dynamique, trois modules d'optimisation sont présentés : un module online destiné à répondre aux requêtes en temps réel, un module de réinsertion pour insérer les requêtes rejetées par le module online et enfin un module offline basé sur une métaheuristique permettant d'optimiser en continue les itinéraires. / The purpose of this thesis is to propose efficient optimization algorithms for an on-demand common transportation system operated by Padam Mobility, a Parisian company. Formalised as a dynamic DARP, we propose three optimisation modules to tackle the underlying problem : an online module to answer real-time requests, a reinsertion module to re-insert rejected requests and a metaheuristic-based offline module to continuously optimize the rides. The proposed methods are directly implemented in the company system and extensively tested on real instances.

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.

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.