Estágio realizado no INESC-Porto e orientado pelo Eng.º Mauro Augusto da Rosa / Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores - Major Energia. Faculdade de Engenharia. Universidade do Porto. 2008

Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores - Major Energia. Faculdade de Engenharia. Universidade do Porto. 2008

Estágio realizado na Universidade de Aveiro e orientado pelo Prof. Doutor Nuno Lau / Tese de mestrado integrado. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 2008

Tese de doutoramento. Engenharia Industrial e Gestão. Faculdade de Engenharia. Universidade do Porto. 2008

Tese de doutoramento. Engenharia Electrotécnica e de Computadores. Faculdade de Engenharia. Universidade do Porto. 2005

Made available in DSpace on 2014-06-12T15:53:30Z (GMT). No. of bitstreams: 2 arquivo1920_1.pdf: 3817805 bytes, checksum: 7b50528318a4bbf365ddf3fc6ad1ca73 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Os algoritmos de busca meta-heurística vêm sendo pesquisados em inúmeros domínios, inclusive na resolução de restrições. Devido à sua capacidade de atuação em problemas que a solução é desconhecida, são utilizados em diversas situações. Os algoritmos evolutivos são uma família dos algoritmos de busca, que simulam o comportamento da natureza. Os problemas de satisfação de restrição (CSP) são compostos por um conjunto de conjunções de variáveis, caracterizando uma restrição. Valores são associados às variáveis, os quais devem satisfazer a restrição, caso contrário, são considerados inválidos. Problemas de resolução de restrição estão associados a diversos contextos, desde problemas de alocação de recursos a design de circuitos integrados. Algoritmos de busca meta-heurística vêm sendo utilizados para a solução de CSP, resolvendo o problema da limitação dos provadores de teoremas, que necessitam modelar uma teoria para serem capazes de encontrar uma solução. Neste trabalho, investigamos o uso do algoritmo de busca meta heurística em um tipo de teste de software (execução concólica) que é tratado como um problema de CSP. A execução concólica se baseia no teste simbólico, o qual extrai as decisões internas de um programa que formam uma restrição, também conhecidas como Path Condition (PC). Estas restrições são formadas a partir das variáveis de entrada, portanto, a solução de uma restrição determina as entradas necessárias para percorrer um determinado caminho no software. As técnicas clássicas utilizam provadores de teoremas, os quais são limitados a teoria suportada, e métodos de randomização, que geram valores aleatórios para as variáveis, reduzindo a complexidade da restrição. A presente dissertação teve como objetivo criar e analisar o desempenho de solucionadores baseados em algoritmos de busca meta-heurística, sendo comparados às técnicas clássicas utilizadas neste contexto. Os resultados mostraram que o uso de heurísticas de busca pode permitir a criação de novas técnicas de resolução de restrição, no contexto de teste simbólico

Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2017-05-05T12:33:32Z No. of bitstreams: 1 hedersoaresbernardino.pdf: 1908457 bytes, checksum: 7dfb54846a46eb894ddf55decf7be4a1 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-05-17T13:34:58Z (GMT) No. of bitstreams: 1 hedersoaresbernardino.pdf: 1908457 bytes, checksum: 7dfb54846a46eb894ddf55decf7be4a1 (MD5) / Made available in DSpace on 2017-05-17T13:34:58Z (GMT). No. of bitstreams: 1 hedersoaresbernardino.pdf: 1908457 bytes, checksum: 7dfb54846a46eb894ddf55decf7be4a1 (MD5) Previous issue date: 2008-02-29 / FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais / Neste trabalho são propostas, implementadas e testadas computacionalmente algumas possibilidades de hibridização de algoritmos genéticos e sistemas imunológicos artificiais visando a solução de problemas de otimização com restrições. Tais problemas aparecem frequentemente na modelagem computacional de problemas científicos e tecnológicos relevantes. Após breve formulação e caracterização da solução de um problema de otimiza- ção com restrições em Ɽn é feita uma introdução na modelagem estrutural e aos problemas de otimização desta área, mostrando sua importância e as dificuldades no desenvolvimento de métodos de resolução aproximados. São apresentadas então diversas meta-heurísticas bio-inspiradas para a resolu-ção destes problemas de otimização, em especial os algoritmos genéticos (AGs) e os sistemas imunológicos artificiais (SIAs). Em seguida, são propostas algumas possibilidades de hibridização de AGs e SIAs para a otimização restrita. Experimentos computacionais visando avaliar o desempenho dos procedimentos propostos são realizados considerando vários problemas-teste da literatura e, finalmente, são apresentadas conclusões e propostas para trabalhos futuros / In this work some possibilities of hibridization of genetic algorithms and artificial immune systems are proposed, computationally implemented, and tested in order to solve constrained optimization problems. Such problems arise frequently in the computational modeling of relevant scientific and technological problems. After a brief formulation and solution characterization for a constrained optimization problem in Ɽn, an introduction is made to structural modeling and the optimization problems in this area, showing their relevance and the dificulties arising in the development of approximate solution methods. Several bio-inspired meta-heuristics for solving such optimization problems are then presented with emphasis on genetic algorithms (GAs) and artiticial immune systems (AISs). Some possible GA-SIA hybrids are then proposed. In order to assess the performance of the proposed procedures, computational experiments are conducted considering several test-problems from the literature and, finally, conclusions as well as future work proposals are presented.

O presente trabalho trata da solução para o problema da elaboração de programações de transporte do sistema de distribuição de materiais da Força Aérea Brasileira (FAB). Essas programações de transporte consistem em definir os roteiros de entrega e coleta de materiais a serem realizadas simultaneamente em cada local de entrega/coleta a partir de um centro de distribuição, considerando-se a frota de veículos homogênea. Isto é característico de um Problema de Roteirização de Veículos com Coletas e Entregas Simultâneas (PRVCES). A gestão do sistema de distribuição física da FAB considera a complexidade desse sistema e os dados relativos às demandas de transporte de carga em cada um desses locais para elaborar as programações de transporte. Essas programações são elaboradas tendo em vista os limites de capacidade dos veículos, as características físicas das cargas e as prioridades de embarque. O gestor desse sistema possui boa visibilidade das demandas de transporte, porém, devido à grande quantidade de informações disponíveis e à elevada complexidade desse sistema, é impossível elaborarem-se manualmente programações de transporte que resultem em viagens de distribuição eficientes. O PRVCES foi resolvido por meio da meta-heurística Busca Dispersa (do inglês Scatter Search) integrada com a meta-heurística Descida em Vizinhança Variável (do inglês Variable Neighborhood Descent) utilizada como método de melhoria das soluções. Os resultados superaram ou se igualaram a alguns dos obtidos por outros autores para os mesmos problemas de teste com as mesmas restrições, o que demonstra que a Busca Dispersa implementada é competitiva para solucionar o PRVCES. Quanto à aplicação na FAB, os resultados mostraram que a utilização do método de solução desenvolvido resultará em programações de transporte elaboradas em curto tempo de processamento e que estas incidirão positivamente sobre a eficiência do sistema de distribuição de materiais da FAB. / This work deals with the solution to the problem of drawing up transport schedules in the material distribution system of the Brazilian Air Force (BAF). These transport schedules consist in defining the routes for material pickup and delivery to be accomplished simultaneously in each delivery/pickup location from a distribution center, considering a homogeneous fleet of vehicles. This is characteristic of a Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP). The management of the physical distribution of BAF considers the complexity of this system and the data regarding the cargo transport demands in each one of those locations to draw up transport schedules. These schedules are drawn up regarding the capacity limits of the vehicles, the physical characteristics of the cargoes and the shipping priorities. A good visibility of transport demands in each location is available to the manager of this system, but due to the great quantity of data to deal with and the high complexity of the physical distribution system of BAF, it is impossible to draw up transport schedules that result in efficient distribution trips. The VRPSDP was solved by means of the Scatter Search meta-heuristic integrated with the Variable Neighborhood Descent meta-heuristic as the solution improvement method. The results exceeded or equaled some of those obtained by other authors using the same test problems with the same restrictions, what indicates that the implemented Scatter Search is competitive to solve the VRPSDP. As for the application in the BAF, the results showed that using the solution method developed will result in schedules drawn up in short processing time and focused on the efficiency of the material distribution system of the BAF.

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.

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.