Submitted by camilla martins (camillasmmartins@gmail.com) on 2017-03-27T12:02:05Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_DesempenhoAlgoritmoGenetico.pdf: 2467772 bytes, checksum: 83f8441c8e8c099abbbb36d4048f3a61 (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2017-03-27T15:46:40Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_DesempenhoAlgoritmoGenetico.pdf: 2467772 bytes, checksum: 83f8441c8e8c099abbbb36d4048f3a61 (MD5) / Made available in DSpace on 2017-03-27T15:46:40Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_DesempenhoAlgoritmoGenetico.pdf: 2467772 bytes, checksum: 83f8441c8e8c099abbbb36d4048f3a61 (MD5) Previous issue date: 2015-06-30 / A ideia da infecção viral vem sendo utilizada nos Algoritmos Genéticos (AG) para melhorar a taxa de busca dos algoritmos, superando a convergência prematura por meio do controle da diversidade da população, visto que na natureza a recombinação genética por vírus apresenta alta velocidade de replicação e frequente mutação. [Romano 2009]. A meta-heurística denominada AGRI adotou como fonte de inspiração biológica a família retroviridae, cujos vírus são baseados em RNA e atendem à necessidade de maior variação alélica do AG, visto que o RNA não possui os mecanismos de correção em seu genoma para eliminar o material viral recombinado. Neste algoritmo, os vírus são tratados como uma população separada da população de indivíduos. A cada infecção, o material genético viral é transmitido verticalmente entre os hospedeiros difundindo trechos de soluções dos vírus com melhor desempenho por toda população. A diversidade viral é mantida por meio de um mecanismo que substitui todos o vírus fora da taxa de elitismo viral. Nessa técnica, a população viral evolui junto com a população cromossômica, pois os vírus ineficientes são criados a partir do material genético dos indivíduos mais adaptados e de outros genes novos. O AGRI segue os princípios biológicos em vários aspectos da infecção e multiplicação viral. Por exemplo: cria a primeira população viral sem o material genético da população somática; escolhe aleatoriamente os vírus que irão infectar um indivíduo, possibilitando que parte da população nunca seja infectada por alguns vírus e que certos vírus infectem mais indivíduos. Além disso, a partir da segunda geração do AG, os vírus substituídos são criados com material genético de dois indivíduos, e tem diferentes quantidades de genes. Nesta abordagem, a maximização do espaço de busca é realizado utilizando três mecanismos: alta variabilidade genética da população viral com tamanhos diferentes dos trechos de soluções; efetivação da infecção apenas quando há um aumento no fitness do indivíduo; e possibilidade de um indivíduo ser infectado por quaisquer dos vírus da população viral. Para analisar o efeito dos parâmetros da infecção viral do AGRI e seu desempenho em comparação com outras meta-heurísticas bem conceituadas, as seguintes funções de benchmarking relacionadas com problemas de minimização foram selecionadas: F1 (Shifted Sphere Function), F2 (Shifted Schwefel’s Problem), F3 (Shifted Rotated High Conditioned Elliptic Function) e F5 (Schwefel’s Problem 2.6 with Global Optimum on Bounds). Os resultados mostraram que para funções unimodais propostas, o AGRI tem boa performance em comparação com as outras meta-heurísticas selecionadas podendo alcançar o ótimo global ou boas soluções com poucas iterações. / Viral Infection is used to improve the performance in Genetic Algorithms (GA) by reducing premature convergence through the population diversity control, since viruses presents high replication and mutation rates in the nature. The metaheuristic called AGRI is inspired biologicaly in a viruses family based on RNA, which provide a high allelic variation to GA, since RNA doesn’t have genoma correction mechanisms to remove re-combined viral genetic material . In this algorithm, the viruses are a separate population. To each infection, the better performance viruses genomes are transmitted vertically spreading parts of solutions to GA population. The diversity viral is maintained through a mechanism that substitutes all viruses out of elitism viral rate. In this method, the virus population evolves along with GA population, so the inefficient viruses are created from genetic material of the better adapted individuals and other new genes. The algorithm AGRI follows biological principles in several viral infection and multiplication aspects. For example: it creates the first viral population without GA population genetic material; it sorts the viral population before infect an individual, making possible some viruses doesn’t infected a part of the population and other viruses infect more individuals. Since GA second-generation, the replaced viruses are created by both individuals genetic material and have different genes quantities. In this approach, the search space maximization is increased by three mechanisms: high viral population genetic variability by variety of sizes to solutions pieces; infection validation process that confirms the fitness increases in each individual and infection possibility by any viruses in the viral population. To analyse the AGRI’s viral infection parameters effects and comparate his performance with others high-performing metaheuristics, the following minimization benchmarking are selected: F1 (Shifted Sphere Function), F2 (Shifted Schwefel’s Problem), F3 (Shifted Rotated High Conditioned Elliptic Function) e F5 (Schwefel’s Problem 2.6 with Global Optimum on Bounds). The results to the functions unimodais proposed showed that AGRI has a good performance in comparison with others metaheuristics reaching in few iterations the global best or good results.

Neste trabalho são apresentadas contribuições para a estimação do desempenho elétrico na distribuição de energia elétrica, com implicações nos mais diversos problemas da operação e do planejamento da distribuição. Entende-se por desempenho elétrico, a avaliação dos parâmetros de congestionamento de redes, as perdas e o nível de tensão. A motivação deste trabalho está na agregação dos esforços advindos da campanha de medição compulsória das concessionárias de distribuição e da necessidade do órgão regulador de estabelecer parâmetros de avaliação do desempenho operacional das empresas, como previsto no documento intitulado “Procedimentos da Distribuição" da Aneel. A estimação do desempenho elétrico é formulada segundo um problema de otimização multiobjetivo onde as funções objetivo compõem uma avaliação de probabilidade de ocorrência e uma avaliação de proximidade dos parâmetros elétricos calculados com os valores obtidos por medição. Os valores das cargas são discretizados segundo probabilidades de ocorrência em cada intervalo, de modo que a formulação resulte em um problema de otimização combinatória multiobjetivo de dimensão exponencial. Propõe-se um procedimento de redução de rede, que diminua consideravelmente o espaço de decisões, e um procedimento de expansão de redes para recompô-la. Também são propostas heurísticas específicas para a obtenção de soluções com cargas diversificadas e desequilibradas. Para uma aplicação adequada destas heurísticas, propôs-se e aplicou-se um método evolucionário metaheurístico para composição das soluções factíveis, ordenadas de acordo com o conceito de dominância de Pareto. Para cada fronteira de dominância, ou conjunto de fronteiras, o aplicativo constrói a distribuição probabilística da corrente e fluxo de potência de cada trecho, o nível de tensão em todas as barras e as perdas técnicas totais do circuito. A formulação matemática de otimização é flexível o bastante para a aplicação prática, considerando os diversos estágios de implementação dos atuais sistemas supervisórios. O modelo evolucionário metaheurístico proposto foi aplicado para um caso ilustrativo evidenciando as suas potencialidades e os pontos a serem aprimorados. / This thesis aims at contributing for the estimation of electrical performance in the distribution of electrical energy. Electrical performance is assumed to be the evaluation of network congestion parameters, losses and voltage level. The development of this work was impelled due to distribution utilities compulsory measurement permanent campaigns, and due to the need of the regulatory agency in establishing operational performance standards, as stated in the Distribution Code of Aneel, the Brazilian Energy Regulatory Agency. The electrical performance estimation is formulated according to an optimization problem where the objective functions correspond to an evaluation of occurrence probability, and correspond to a proximity evaluation of calculated parameters with values obtained by measurement as well. Load values are discretized according to ocurrence probabilities within each interval, so that formulation results in a multiobjective combinatorial optimization of exponential dimension. Network reduction procedures to substantially reduce Decision Domain and network expansion procedures to recompose it are proposed. Specific heuristics are also proposed to get solutions with load diversity and unbalanced loads. In order to adequately apply these heuristics, a metaheuristic evolutionary method to build feasible solutions is proposed and applied, and ranked according to Pareto´s concept. For each dominance frontier or group of frontiers, the application builds the probabilistic: current and load flow distribution of for each branch, voltage level for each bar and circuit technical losses. The mathematical formulation of optimization is flexible enough to be effectively applied taking into account different levels of supervisory systems developed in the utilities. The metaheuristic evolutionary model proposed was applied to a representative case with main potentialities and weak points to be improved.

A capacidade das células para responder corretamente a sinais externos e perceber mudanças no seu microambiente é a base do desenvolvimento, reparação de tecidos e de imunidade, bem como a homeostase do tecido normal. Transdução de sinal é o principal meio pelo qual as células respondem a sinais externos de seu ambiente e coordenam alterações celulares complexas. O estudo das vias de sinalização molecular permite-nos tentar compreender o funcionamento dessas transduções de sinais e, consequentemente, as respostas celulares a estímulos externos. Uma abordagem adequada para tais estudos é o uso de modelos matemáticos para simular a cinética das reações químicas que descrevem uma dada via de sinalização, o que nos permite gerar predições testáveis de processos celulares. Construir modelos cinéticos preditivos de vias de sinalização molecular através de dados de alto rendimento produzidos utilizando técnicas ômicas (i.e., genômica, transcriptômica, (fosfo-)proteômica) constitui um dos atuais desafios enfrentados pelos pesquisadores na área de Biologia Molecular. Recentemente, para lidar com este desafio, o arcabouço de e-Science SigNetSim foi introduzido pelo Grupo de Biologia Computacional e de Bioinformática do Instituto Butantan. Esse arcabouço permite fazer a descrição de vias de sinalização molecular através da descrição da estrutura de um modelo através de um conjunto de reações químicas, que por sua vez é mapeado para um sistema de Equações Diferencias Ordinárias (EDOs), numericamente simuladas e avaliadas. Todavia, modificações na estrutura das vias precisam ser feitas manualmente, o qual restringe severamente o número de estruturas da via que precisam ser testadas, especialmente no caso de modelos grandes. Portanto, diante desse panorama, este trabalho propõe o desenvolvimento de um método para modificar vias de sinalização molecular. Esse método se baseia no uso de bancos de dados de interatomas para fornecer um conjunto de espécies químicas candidatas para serem incluídas na via de sinalização. Um componente integrado ao arcabouço SigNetSim capaz de testar diferentes hipóteses de modificação de vias foi desenvolvido neste projeto utilizando a metodologia de heurística incremental. Para avaliar a eficiência do componente implementado, utilizamos como estudo de caso um modelo de vias sinalização de MAPKs e PI3K/Akt para realizar testes experimentais e analisar os resultados obtidos. / The ability of cells to respond correctly external signals and to perceive changes in their microenvironment is the basis for development, tissue repair and immunity as well as normal tissue homeostasis. Signal transduction is the primary means by which cells respond to external signals from their environment and coordinate complex cellular changes. The study of molecular signaling pathways allows us to understand the operation of each process of cellular signal transduction. The use of mathematical models to simulate the kinetics of chemical reactions that describe a given signaling pathway, allow us to generate testable predictions of the cell processos. To Build Kinetic predictive models to molecular signaling pathways through massive data omics produced using modern techniques, Genomics, transcriptomics, (Phospho) proteomics, is one of the current challenges faced by researchers in the field of molecular biology. Recently, the \\textit SigNetSim e-Science was introduced by the Biological Computacional and Bioinformatical Group from the Butantan Institute to face this challenge. This \\textit makes the description of molecular signaling pathways through a set of chemical reactions, which are mapped into a system of ordinary differential equations, this system will be numerically simulated and evaluated . However, changes in the structure of the pathways need to be updated manually presented in this work, which severely restricts the number of track structures that need to be tested, especially for the large models. Therefore, given this background, we present the method to modify the molecular signaling pathways. This method relies on the use of interactome database to provide a set of chemical species candidates to be included in the signaling pathway. An component integrated to SigNetSim framework able to test different hypotheses of pathways modification was developed in this project using the incremental heuristic methodology. To evaluate the implemented component, we used the MAPKs and PI3K/Akt pathways model as case study, in order to perform experimental tests and to analyze the obtained results.

A teoria dos grafos é uma ferramenta matemática muito utilizada na resolução de problemas algorítmicos e computacionais em que se quer modelar conjuntos de elementos e relações entre estes elementos. Sistemas naturais e tecnológicos de diversos domínios podem ser representados matematicamente por grafos que possuem propriedades estatísticas bem conhecidas, sendo uma destas propriedades a distribuição de graus dos vértices do grafo seguindo a lei de potência (power law). Exemplos destes grafos, conhecidos como grafos power law são a internet, World-Wide Web, as redes sociais, redes biológicas. No contexto de problemas algorítmicos em grafos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos que pertencem à classe NP-Difícil (ou NP-Hard), mais especificamente no problema de cobertura por vértices. Neste trabalho será estudado experimentalmente o comportamento de um algoritmo baseado em uma estratégia gulosa para o problema de cobertura de vértices e compararemos com outro algoritmo de aproximação e com a solução exponencial ótima. Em particular esta solução será aplicada e analisada em redes complexas. / Graph theory is a mathematical tool used in solving many algorithmic and computational problems in that both sets of model elements and relationships between these elements. Most natural and technological systems can be mathematically modeled by graph having many well known properties, in particular the power law distribution of the vertex degree sequence. Examples of such graphs, called power law graphs are the Internet, World-Wide Web, social networks, biological networks. In the context of algorithmic problems on graphs, we are interested in problems in class NP-Hard, more specifically in the vertex cover problem. This work will be studied experimentally the behavior of an algorithm based on a greedy strategy for the vertex cover problem and compare with other approximation algorithms and with the exponential optimal solution. In particular this solution will be applied and analyzed in complex networks.

Neste trabalho é apresentada uma nova abordagem de algoritmo evolutivo multiobjetivo, denominado MOEA/NSM (do inglês, Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). O algoritmo preserva em geral, características de um algoritmo evolutivo, concentrando qualidades de outras abordagens de sucesso na literatura em uma única abordagem, para que elas trabalhem em conjunto, por meio de subpopulações. O objetivo do estudo foi combinar as principais características dos algoritmos NSGA-II, SPEA2 e MOEA/D, e incluir ainda uma técnica de busca local para melhorar a busca no espaço de objetivos. O algoritmo MOEA/NSM foi comparado às demais abordagens clássicas utilizando 9 datasets para o problema do caixeiro viajante biobjetivo. Além disso, foram realizados experimentos aplicando também a busca local nas abordagens clássicas, resultando em considerável melhora nos resultados para esses algoritmos. A partir das fronteiras de Pareto resultantes dos experimentos, foram aplicadas as métricas de avaliação por Hipervolume, Epsilon (ε), R2, EAF, além do teste de hipótese estatístico Shapiro-Wilk. Os resultados apontaram um melhor desempenho do MOEA/NSM em relação aos demais, mesmo aplicando a busca local nas outras abordagens. Nesse sentido, o MOEA/NSM pode ser considerado um algoritmo que consegue encontrar soluções não denominadas de qualidade, tanto quanto os algoritmos clássicos da literatura. / This work presents a new approach to the multiobjective evolutionary algorithm, called MOEA/NSM (Multiobjective Evolutionary Algorithm integrating NSGA-II, SPEA2 and MOEA/D features). The algorithm preserves, in general, the characteristics of an evolutionary algorithm, concentrating qualities of other approaches of success in the literature in a single approach, so that they work together, through subpopulations. The objective of the study was to combine the main characteristics of the NSGA-II, SPEA2 and MOEA/D algorithms, and also to include a local search technique to improve the objective space search. The MOEA/NSM algorithm was compared to the other classical approaches using 9 datasets for the biobjective traveling salesman problem. In addition, experiments were carried out also applying the local search in the classical approaches, resulting in a considerable improvement in the results for these algorithms. From the Pareto frontiers resulting from experiments, we applied the evaluation metrics by Hypervolume, Epsilon (ε), R2, EAF, in addition to the Shapiro-Wilk statistical hypothesis test. The results showed a better performance of the MOEA/NSM in relation to the others, even applying the local search in the others approaches. In this sense, the MOEA/NSM can be considered an algorithm that is able to find solutions not dominated of quality, as much as the classic algorithms of the literature.

Dissertação (mestrado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2010 / Bibliografia: f. [121]-128 / O estudo da teoria de controle tem cada dia mais desempenhado um papel fundamental na área tecnológica, contribuindo sempre para os avanços em engenharia. Por outro lado, os processos a serem controlados estão cada vez mais desafiadores no meio industrial / The study of the control theory has played each day a more fundamental role in the technological area, always contributing for advances in engineering. On the other hand, the controlled industrial processes are becoming more challenging, with nonlinear ch

VIANA, Gerardo Valdíso Rodrigues. Técnicas para construção de árvores filogenéticas. 2007. 203 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2007. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-20T12:05:20Z No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T11:50:34Z (GMT) No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) / Made available in DSpace on 2016-07-25T11:50:34Z (GMT). No. of bitstreams: 1 2007_tese_gvrviana.pdf: 3571043 bytes, checksum: 34853f08d8a8ac37e7c9e07dcf25de25 (MD5) Previous issue date: 2007 / Phylogenetic tree structures express similarities, ancestrality, and relationships between species or group of species, and are also known as evolutionary trees or phylogenies. Phylogenetic trees have leaves that represent species (taxons), and internal nodes that correspond to hypothetical ancestors of the species. In this thesis we rst present elements necessary to the comprehension of phylogenetic trees systematics, then ef cient algorithms to build them will be described. Molecular biology concepts, life evolution, and biological classi cation are important to the understanding of phylogenies. Phylogenetic information may provide important knowledge to biological research work, such as, organ transplantation from animals, and drug toxicologic tests performed in other species as a precise prediction to its application in human beings. To solve a phylogeny problem implies that a phylogenetic tree must be built from known data about a group of species, according to an optimization criterion. The approach to this problem involves two main steps: the rst refers to the discovery of perfect phylogenies, in the second step, information extracted from perfect phylogenies are used to infer more general ones. The techniques that are used in the second step take advantage of evolutionary hypothesis. The problem becomes NP-hard for a number of interesting hypothesis, what justify the use of inference methods based on heuristics, metaheuristics, and approximative algorithms. The description of an innovative technique based on local search with multiple start over a diversi ed neighborhood summarizes our contribution to solve the problem. Moreover, we used parallel programming in order to speed up the intensi cation stage of the search for the optimal solution. More precisely, we developed an ef cient algorithm to obtain approximate solutions for a phylogeny problem which infers an optimal phylogenetic tree from characteristics matrices of various species. The designed data structures and the binary data manipulation in some routines accelerate simulation and illustration of the experimentation tests. Well known instances have been used to compare the proposed algorithm results with those previously published. We hope that this work may arise researchers' interest to the topic and contribute to the Bioinformatics area. / Árvores filogenéticas são estruturas que expressam a similaridade, ancestralidade e relacionamentos entre as espécies ou grupo de espécies. Conhecidas como árvores evolucionárias ou simplesmente filogenias, as árvores filogenéticas possuem folhas que representam as espécies (táxons) e nós internos que correspondem aos seus ancestrais hipotéticos. Neste trabalho, além das informações necessárias para o entendimento de toda a sistemática filogenética, são apresentadas técnicas algorítmicas para construção destas árvores. Os conceitos básicos de biologia molecular, evolução da vida e classificação biológica, aqui descritos, permitem compreender o que é uma Filogenia e qual sua importância para a Biologia. As informações filogenéticas fornecem,por exemplo, subsídios importantes para decisões relativas aos transplantes de órgãos ou tecidos de outras espécies para o homem e para que testes de reação imunológica ou de toxicidade sejam feitos antes em outros sistemas biológicos similares ao ser humano. Resolver um Problema de Filogenia corresponde à construção de uma árvore filogenética a partir de dados conhecidos sobre as espécies em estudo, obedecendo a algum critério de otimização. A abordagem dada a esse problema envolve duas etapas, a primeira, referente aos casos em que as filogenias são perfeitas cujos procedimentos desenvolvidos serão utilizados na segunda etapa, quando deve ser criada uma técnica de inferência para a filogenia num caso geral. Essas técnicas consideram de forma peculiar as hipóteses sobre o processo de evolução. Para muitas hipóteses de interesse o problema se torna NP-Difícil, justificando-se o uso de métodos de inferência através de heurísticas, meta-heurísticas e algoritmos aproximativos. Nossa contribuição neste trabalho consiste em apresentar uma técnica de resolução desse problema baseada em buscas locais com partidas múltiplas em vizinhanças diversificadas. Foi utilizada a programação paralela para minimizar o tempo de execução no processo de intensificação da busca pela solução ótima do problema. Desta forma, desenvolvemos um algoritmo para obter soluções aproximadas para um Problema da Filogenia, no caso, para inferir, a partir de matrizes de características de várias espécies, uma árvore filogenética que mais se aproxima da história de sua evolução. Uma estrutura de dados escolhida adequadamente aliada à manipulação de dados em binário em algumas rotinas facilitaram a simulação e ilustração dos testes realizados. Instâncias com resultados conhecidos na literatura foram utilizadas para comprovar a performance do algoritmo. Esperamos com este trabalho despertar o interesse dos pesquisadores da área de Computação, consolidando, assim, o crescimento da Bioinformática.

Made available in DSpace on 2016-12-23T13:51:54Z (GMT). No. of bitstreams: 1 Cristiane Coutinho Meneguzzi.pdf: 2106158 bytes, checksum: 65c537220893be6e9c9d64b3001fef07 (MD5) Previous issue date: 2011-10-04 / On Forest field, studies in development of forest harvesting and transport still being the most emphasized subject, for being directly responsible for the final cost of wood. However, other different phases are a big potential for studies, as Forest Inventory. Information provided by the Forest Inventory are important for all planning of Forest Enterprise, as it bases any decision making involving forest resources. On this present research, was based on vehicle routing problem for planning this task. The vehicle routing problem and its variants has being largely studied on the last years, mainly for its applicability and efficiency for given solutions resulting in cost and distance reduction. The general objective of the present study is optimize the Inventory Forest planning from a vehicle routing problem and evaluate the importance of this technique on its productivity. Among the factors that influence this productivity, the spatial dispersion , basic feature of forest stands, it is one controllable factor from the use of technique that makes possible matches with planning. Studies shows that this match brings out significant results / Na área florestal, ainda é dada maior ênfase ao desenvolvimento de estudos envolvendo as etapas de colheita e transporte florestal, por serem diretamente responsáveis pelo custo final da madeira. Entretanto, diversas outras etapas possuem grande potencial para estudos, como é o caso do inventário florestal. Informações fornecidas pelo inventário florestal são importantes no planejamento de todo empreendimento florestal, pois subsidiam qualquer tomada de decisão envolvendo recursos florestais. Nesta pesquisa, utilizou-se o modelo de roteamento de veículos (PRV) no planejamento dessa atividade. O PRV e suas variantes vêm sendo amplamente estudados nos últimos anos, principalmente pela sua aplicabilidade e eficiência em gerar soluções apresentando redução de custo e/ou distâncias. O objetivo geral foi otimizar o planejamento da atividade de inventário florestal a partir de um modelo PRV e avaliar a importância do uso desta técnica no rendimento das atividades. Dentre os fatores que influenciam neste rendimento, a dispersão espacial, característica básica dos povoamentos florestais, é um fator controlável a partir do uso de técnicas que possibilitem associá-lo ao planejamento. Estudos mostram que essa associação traz resultados significativos

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com o passar do tempo, a demanda elétrica de diversas áreas varia tornando necessária a construção de novos geradores elétricos e a expansão da rede de transmissão de energia elétrica. Nesta dissertação, focamos no problema de expansão da rede de transmissão, assumindo que novos geradores estão construídos para suprir as novas demandas. Essa expansão exige altos investimentos que precisam ser cuidadosamente planejados. O problema pode ser modelado como um problema de otimização não linear inteira mista e pertence à classe dos problemas NP-difíceis. Desta forma, uma abordagem heurística pode ser adequada para a sua solução pois pode vir a fornecer boas soluções em tempo computacional aceitável. Esta dissertação se propõe a apresentar um estudo do problema de planejamento da expansão de redes de transmissão de energia elétrica estático e multiestágio. Mostramos o que já existe na literatura para o que é chamado de problema sem redimensionamento e as inovações feitas por nós para o problema com redimensionamento. Quanto aos métodos de solução, utilizamos a metaheurística GRASP para o problema estático e combinamos o GRASP com o procedimento Backward-Forward quando falamos em problema multiestágio. Nesta dissertação comparamos os resultados computacionais obtidos com resultados encontrados na literatura. / At times, the electrical load in diferent areas varies, claiming the construction of new electric generators and the expansion of the electrical transmission network. In this dissertation we focus on the transmission expansion planning problem, assuming that new generators are built to meet the new demands. This expansion requires large investments, which need to be carefully planned. This problem can be modeled as a mixed nonlinear programming problem, considered to be a NP-hard problem. Therefore a heuristic approach may be appropriate for its solution because it might be able to provide good solutions in satisfactory computational time. This dissertation intends to present a study of both the static and multistage transmission expansion planning problem. We present first a review of the most interesting works found in the technical literature. Then, we present metaheuristics for the static and multistage problems with re-design. These etaheuristics extend known algorithms for the problems without re-design. For the static problem, we extend a GRASP procedure and for the multistage problem, we embed the GRASP (or an exact method) into a backward-forward algorithm. We test our algorithms on real-based power transmission networks and compare them to the results found in the litterature.

The work proposed in this dissertation is the field of combinatorial optimization, which aims to find a solution to these types of problems at a low computational time and effectively. The combinatorial optimization studies a set of discrete solutions, which have a finite number of elements, to find the best viable solution to the problems of this magnitude. One of the main approaches that area is the Traveling Salesman Problem (TSP), mainly due to the size of possible solutions to the problem, so that is intractable computation by exhaustive search methods. Given all these features, this work is to study and develop evolutionary strategies for the resolution of the Problem of Traveling Salesman with Heterogeneous Demands (TSPHD), a variation of the classic TSP. The evolutionary strategies belong to the class of evolutionary computation, and methods of search based on the theory of the evolution of species, where the best individuals compete for survival. The evolutionary strategies differ from other optimization techniques, as the search is conducted in a population of solutions, not a single point. To solve the problem are proposed four evolutionary algorithms, using heuristics techniques and metaheurísticas for its implementation. The results were obtained from tests using instances of low density (low connection), and compared with the exact solution (optimal solution) and other progressive methods in the literature. These results are evaluated on the basis of their quality and time for its implementation. / O trabalho proposto nessa dissertação pertence à área de otimização combinatória, a qual visa encontrar uma solução para esses tipos de problema em um tempo computacional baixo e de forma eficaz. A otimização combinatória estuda um conjunto discreto de soluções, os quais possuem um número finito de elementos, para se poder encontrar a melhor solução viável para os problemas dessa grandeza. Uma das principais abordagens dessa área é o Problema do Caixeiro Viajante (PCV), principalmente devido à dimensão de possíveis soluções para o problema, fazendo com que seja intratável computacionalmente por métodos de buscas exaustivas. Face a todas essas características, este trabalho tem por objetivo estudar e desenvolver estratégias evolutivas para a resolução do Problema do Caixeiro Viajante com Demandas Heterogêneas (PCVDH), uma variação do PCV clássico. As estratégias evolutivas pertencem à classe da computação evolutiva, sendo métodos de busca inspirados na teoria da evolução das espécies, onde os melhores indivíduos competem pela sobrevivência. As estratégias evolutivas diferem das demais técnicas de otimização, pois a busca é realizada em uma população de soluções, não em um único ponto. Para a resolução do problema são propostos quatro algoritmos evolutivos, utilizando técnicas heurísticas e metaheurísticas para sua aplicação. Os resultados foram obtidos com testes utilizando instâncias de baixa densidade (baixa conexão), e comparados com a sua solução exata (solução ótima) e com outros métodos evolutivos encontrados na literatura. Esses resultados são avaliados com base na sua qualidade e tempo decorrido para sua execução.