Orientadora : Profa. Dra. Aurora Trinidad Ramirez Pozo / Coorientador : Prof. Dr. Roberto Santana / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 13/03/2017 / Inclui referências : f. 54-60 / Resumo: Proteínas são estruturas, compostas por aminoácidos, que exercem um papel importante na natureza. Estas estruturas são formadas a partir de um processo de dobramento, no qual uma sequência de aminoácidos inicialmente desdobrada irá adotar uma conformação/estrutura espacial única/nativa. Entretanto, o processo de dobramento ainda não é completamente compreendido e é considerado um dos maiores desafios das áreas de biologia, química, medicina e bioinformática. Este desafio é conhecido como o problema de dobramento de proteínas (PDP) e trata da predição de estruturas de proteínas. O PDP pode ser visto como um problema de minimização, pois é afirmado que a estrutura nativa de uma proteína é aquela que minimiza sua energia global livre. Dessa maneira, diversas estudos aplicam estratégias heurísticas para explorar modelos simplificados, tais como o modelo Hidrofóbico-Polar HP. Embora simplificado, HP possui um complexo espaço de busca e uma grande variabilidade de características entre as instâncias. Por conta de tal complexidade surge a demanda de estratégias que possuam mecanismos robustos para explorar de maneira adequada o espaço de busca. É nesse contexto que hiper-heurísticas se apresentam como boas opções para explorar o espaço de busca de problemas complexos. Nesta dissertação, são apresentadas duas abordagens para resolver o PDP. A primeira descreve uma abordagem biobjetiva explorando algoritmos evolucionários multi objetivos tradicionais. A segunda consiste no projeto automático de heurísticas de alto nível utilizando uma técnica de programação genética chamada evolução gramatical, a qual utiliza uma gramática para produzir programas de computador. As estratégias propostas foram aplicadas sobre um conjunto de benchmark com diferentes sequências de aminoácidos. Os resultados foram comparados com outros trabalhos que utilizam o mesmo conjunto de benchmark. Alguns resultados obtidos se mostraram promissores dessa maneira motivando novos estudos que desenvolvam estratégias adaptativas para o PDP. Palavras-chave: PDP, hiper heurísticas, evolução gramatical, otimização multi objetiva. / Abstract: Proteins are structures composed by amino acids that plays a important role in nature. These structures are built by a process called protein folding, where a sequence of amino-acids initially unfolded will obtain your native structure. However, the protein folding process is not entire understood and it is considered one of the most challenging problem from biology, chemistry, medicine and bio-informatics. This problem is knows as the protein folding problem (PFP) and handles the prediction of protein structures. The PFP is a minimization problem, because the proteins native structures are the one within minimum energy. Thus, many heuristics strategies make use of simplified models, such as the HP model, to find the proteins native structures within the HP model. Although simplified, the HP model has a complex search space and a great variability of characteristics between the instances. Thus, raises the demand of strategies with robust mechanisms to explore the search space properly. In this context, adaptive strategies fits well as good alternative to explore the fitness landscape from complex problems. In this dissertation, two approaches are presented to solve the PDP. The first one describes a bi objective approach applying traditional multi objective evolutionary algorithms. The second approach consists the automated design of high level heuristics using a genetic programming technique called grammatical evolution, which uses a grammar to produce computer programs. Both approaches proposed have been applied on a benchmark set with different amino acids sequences. The results have been compared with previous studies that used the same benchmark. In some cases the results obtained are promising which motivates the development of new adaptive strategies to solve the PFP. Keywords: PFP, hyper heuristics, grammatical evolution , multi objective optimization.

Made available in DSpace on 2014-06-11T19:35:40Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-02-28Bitstream added on 2014-06-13T20:07:10Z : No. of bitstreams: 1 000757731.pdf: 2807037 bytes, checksum: 5aa196a9569db15583f96a6a1fbce2c8 (MD5) / A presente pesquisa trata do desenvolvimento de um método de solução do problema de construção de linhas de trabalho para a área de escalonamento de pessoal. Foram investigados diversos artigos da área de programação de pessoal com o objetivo de escolher precisamente o tema da pesquisa. Este tema escolhido foi o da construção de linhas de trabalho para empresas de ônibus interurbanos no Brasil. De posse do tema escolhido, foram analisados os métodos usados para formular e resolver o problema. Como resultado foi decidido o uso de uma formulação de cobertura de conjuntos não unicusto para representar o problema em estudo e o uso de um método heurístico para resolver o mesmo. Esta heurística divide a solução do problema em duas fases. A primeira é a fase construtiva, em que o espaço de solução é montado e linhas de trabalho são investigadas e aquelas viáveis são agrupadas formando um conjunto de linhas viáveis e qualificadas. A segunda é a fase de otimização ou de busca local em que um algoritmo evolutivo, baseado em algoritmo genético, irá procurar a melhor solução dentro desse subconjunto de linhas viáveis e qualificadas obtidas na primeira fase. Estes dois procedimentos se repetem até que um critério de parada seja atingido. Testes computacionais foram realizados no sentido de demonstrar a eficácia e eficiência do método proposto. Em seguida, o problema da programação de dias de expediente e de folga, neste trabalho denominado problema de padrões de folga, é formulado e resolvido. Algumas propostas para integrar a solução do problema de criação de linhas de trabalho à do problema de padrões de folga são apresentadas e discutidas / This thesis deals with the development of a method for solving the problem of construction of lines of work for the application area of personnel scheduling. Several articles were analyzed in order to matching precisely the subject of the research. An in-depth review of the processes used for formulating and solving such a kind of problem in the literature was conducted. As a result, it was decided to formulating the problem as a non unicost set covering problem and to use a heuristic method to solve it. The proposed heuristic is a twofold algorithm. The first is the construction phase, in which the solution space is scanned and working lines are investigated and those feasible are grouped together forming a set of feasible and qualified lines. The second phase is the optimization or local search in which an evolutionary algorithm based on genetic algorithm will search for the best solution within this set of feasible and qualified lines obtained in the first phase. These two phases are repeated until a stop criterion is reached. Computational tests were performed to demonstrate the effectiveness and efficiency of the proposed method. Then, the tour scheduling problem is addressed in the context of finding shifts of work-days and days-off scheduling. Its resolved by deterministic techniques. Some methods are then discussed on how to integrating both of the solutions of the lines of work and the tour scheduling problems

Orientador : Aurora Trinidad Ramirez Pozo / Coorientador : Roberto Santana Hermida / Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 06/03/2017 / Inclui referências : f. 161-72 / Área de concentração : Computer Science / Resumo: Problemas multi-objetivo (MOPs) são caracterizados por terem duas ou mais funções objetivo a serem otimizadas simultaneamente. Nestes problemas, a meta é encontrar um conjunto de soluções não-dominadas geralmente chamado conjunto ótimo de Pareto cuja imagem no espaço de objetivos é chamada frente de Pareto. MOPs que apresentam mais de três funções objetivo a serem otimizadas são conhecidos como problemas com muitos objetivos (MaOPs) e vários estudos indicam que a capacidade de busca de algoritmos baseados em Pareto é severamente deteriorada nesses problemas. O desenvolvimento de otimizadores bio-inspirados para enfrentar MOPs e MaOPs é uma área que vem ganhando atenção na comunidade, no entanto, existem muitas oportunidades para inovar. O algoritmo de enxames de partículas multi-objetivo (MOPSO) é um dos algoritmos bio-inspirados adequados para ser modificado e melhorado, principalmente devido à sua simplicidade, flexibilidade e bons resultados. Para melhorar a capacidade de busca de MOPSOs, seguimos duas linhas de pesquisa diferentes: A primeira foca em métodos de líder e arquivamento. Trabalhos anteriores apontaram que esses componentes podem influenciar no desempenho do algoritmo, porém a seleção desses componentes pode ser dependente do problema. Uma alternativa para selecioná-los dinamicamente é empregando hiper-heurísticas. Ao combinar hiper-heurísticas e MOPSO, desenvolvemos um novo framework chamado H-MOPSO. A segunda linha de pesquisa também é baseada em trabalhos anteriores do grupo que focam em múltiplos enxames. Isso é feito selecionando como base o framework multi-enxame iterado (I-Multi), cujo procedimento de busca pode ser dividido em busca de diversidade e busca com múltiplos enxames, e a última usa agrupamento para dividir um enxame em vários sub-enxames. Para melhorar o desempenho do I-Multi, exploramos duas possibilidades: a primeira foi investigar o efeito de diferentes características do mecanismo de agrupamento do I-Multi. A segunda foi investigar alternativas para melhorar a convergência de cada sub-enxame, como hibridizá-lo com um algoritmo de estimativa de distribuição (EDA). Este trabalho com EDA aumentou nosso interesse nesta abordagem, portanto seguimos outra linha de pesquisa, investigando alternativas para criar versões multi-objetivo de um dos EDAs mais poderosos da literatura, chamado estratégia de evolução baseada na adaptação da matriz de covariância (CMA-ES). Para validar o nosso trabalho, vários estudos empíricos foram conduzidos para investigar a capacidade de busca das abordagens propostas. Em todos os estudos, nossos algoritmos investigados alcançaram resultados competitivos ou melhores do que algoritmos bem estabelecidos da literatura. Palavras-chave: multi-objetivo, algoritmo de estimativa de distribuição, otimização por enxame de partículas, multiplos enxames, híper-heuristicas. / Abstract: Multi-Objective Problems (MOPs) are characterized by having two or more objective functions to be simultaneously optimized. In these problems, the goal is to find a set of non-dominated solutions usually called Pareto optimal set whose image in the objective space is called Pareto front. MOPs presenting more than three objective functions to be optimized are known as Many-Objective Problems (MaOPs) and several studies indicate that the search ability of Pareto-based algorithms is severely deteriorated in such problems. The development of bio-inspired optimizers to tackle MOPs and MaOPs is a field that has been gaining attention in the community, however there are many opportunities to innovate. Multi-objective Particle Swarm Optimization (MOPSO) is one of the bio-inspired algorithms suitable to be modified and improved, mostly due to its simplicity, flexibility and good results. To enhance the search ability of MOPSOs, we followed two different research lines: The first focus on leader and archiving methods. Previous works have pointed that these components can influence the algorithm performance, however the selection of these components can be problem-dependent. An alternative to dynamically select them is by employing hyper-heuristics. By combining hyper-heuristics and MOPSO, we developed a new framework called H-MOPSO. The second research line, is also based on previous works of the group that focus on multi-swarm. This is done by selecting as base framework the iterated multi swarm (I-Multi) algorithm, whose search procedure can be divided into diversity and multi-swarm searches, and the latter employs clustering to split a swarm into several sub-swarms. In order to improve the performance of I-Multi, we explored two possibilities: the first was to further investigate the effect of different characteristics of the clustering mechanism of I-Multi. The second was to investigate alternatives to improve the convergence of each sub-swarm, like hybridizing it to an Estimation of Distribution Algorithm (EDA). This work on EDA increased our interest in this approach, hence we followed another research line by investigating alternatives to create multi-objective versions of one of the most powerful EDAs from the literature, the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). In order to validate our work, several empirical studies were conducted to investigate the search ability of the approaches proposed. In all studies, our investigated algorithms have reached competitive or better results than well established algorithms from the literature. Keywords: multi-objective, estimation of distribution algorithms, particle swarm optimization, multi-swarm, hyper-heuristics.

Orientadora: Profª. Drª. Deise M. Bertholdi Costa / Co-orientador: Prof. Dr. Luiz Fernando Nunes / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia. Defesa: Curitiba, 25/11/2011 / Inclui bibliografias / Resumo: O transporte, em geral, representa nos dias atuais, o maior percentual de custos do na atividade logística. Por isso, muitas empresas estão repensando seus processos para redução dos mesmos. A otimização da distribuição de produtos é um problema estudado há muito tempo por pesquisadores da área de matemática, pesquisa operacional e da computação. Este tipo de problema é dado como um típico problema de otimização combinatória. O Problema do Caixeiro Viajante (PCV) é um clássico deste tipo de problema. Assim, como o Problema de Roteamento de Veículos (PRV), o qual busca o menor caminho dentre N lugares de destino. Na literatura podem ser encontrados trabalhos e abordagens propostos, que utilizam formulações exatas, algoritmos heurísticos e metaheurísticos. O objetivo deste trabalho foi realizar um estudo de caso que envolvesse um número significativo de pontos visitados por algum tipo de veículo, visando analisar e comparar, em termos de desempenho computacional e qualidade das soluções obtidas, as Heurísticas de Construção e Melhoria de Rota e das Metaheurísticas Ant System, Simulated Annealing e Algoritmos Genéticos para o PCV. Também foi aplicado o algoritmo 2- opt para melhoria das rotas geradas. As técnicas foram aplicadas tendo em vista que a otimização das visitas e distribuição dos produtos pode reduzir custos e principalmente os atrasos nas entregas. Para implementação foram utilizados dados reais de uma distribuidora de produtos para uma determinada região da cidade de Curitiba (PR), Brasil. Através do aplicativo online, Google Earth foram obtidas as coordenadas geográficas dos pontos de visitação, que foram então convertidas para coordenadas cartesianas, para a utilização nos algoritmos. Os resultados obtidos foram comparados com as rotas reais praticadas na época por um dos representantes da referida distribuidora. / Abstract: Transport, in general, on average absorbs the highest percentage of costs than any other logistics activity, so many companies are rethinking their processes to reduce them. The optimization of the distribution of products is a problem that is studied for a long time by researchers in mathematics, operational research and computing. This type of problem is given as a typical combinatorial optimization problem. The Traveling Salesman Problem (TSP) is a classic of this, as well as the Vehicle Routing Problem (VRP), where it briefly conceptualizes in finding the shortest path from N places of destination. In the literature there are many jobs and proposed approaches, and some of these heuristics and metaheuristics will be studied and analyzed. The objective of this work was to perform a case study involving a significant number of points visited by some kind of vehicle in order to analyze and compare in terms of computational performance and quality of the solutions obtained, the Construction and Improvement Heuristics and Route Ant System metaheuristics, Simulated Annealing and Genetic Algorithms for the TSP, and has also applied the 2-opt algorithm for improving the routes generated, with a view that the optimization of the visits and distribuition product will reduce costs and above all, the delivery delays. We used real data from a distributor of products in a specific region of Curitiba (PR), Brazil. Using Google Earth has picked the geographical coordinates of points of visitation, which were converted to Cartesian coordinates, for application of the algorithms used. The results were compared with the true routes that are being used by a particular representative of that distributor.

Orientador: Edson Luiz França Senne / Banca: Galeno José de Sena / Banca: José Roberto Dale Luche / Banca: Anibal Tavares de Azevedo / Banca: Kelly Cristina Poldi / Resumo : A presente pesquisa trata do desenvolvimento de um método de solução do problema de construção de linhas de trabalho para a área de escalonamento de pessoal. Foram investigados diversos artigos da área de programação de pessoal com o objetivo de escolher precisamente o tema da pesquisa. Este tema escolhido foi o da construção de linhas de trabalho para empresas de ônibus interurbanos no Brasil. De posse do tema escolhido, foram analisados os métodos usados para formular e resolver o problema. Como resultado foi decidido o uso de uma formulação de cobertura de conjuntos não unicusto para representar o problema em estudo e o uso de um método heurístico para resolver o mesmo. Esta heurística divide a solução do problema em duas fases. A primeira é a fase construtiva, em que o espaço de solução é montado e linhas de trabalho são investigadas e aquelas viáveis são agrupadas formando um conjunto de linhas viáveis e qualificadas. A segunda é a fase de otimização ou de busca local em que um algoritmo evolutivo, baseado em algoritmo genético, irá procurar a melhor solução dentro desse subconjunto de linhas viáveis e qualificadas obtidas na primeira fase. Estes dois procedimentos se repetem até que um critério de parada seja atingido. Testes computacionais foram realizados no sentido de demonstrar a eficácia e eficiência do método proposto. Em seguida, o problema da programação de dias de expediente e de folga, neste trabalho denominado problema de padrões de folga, é formulado e resolvido. Algumas propostas para integrar a solução do problema de criação de linhas de trabalho à do problema de padrões de folga são apresentadas e discutidas / Abstract: This thesis deals with the development of a method for solving the problem of construction of lines of work for the application area of personnel scheduling. Several articles were analyzed in order to matching precisely the subject of the research. An in-depth review of the processes used for formulating and solving such a kind of problem in the literature was conducted. As a result, it was decided to formulating the problem as a non unicost set covering problem and to use a heuristic method to solve it. The proposed heuristic is a twofold algorithm. The first is the construction phase, in which the solution space is scanned and working lines are investigated and those feasible are grouped together forming a set of feasible and qualified lines. The second phase is the optimization or local search in which an evolutionary algorithm based on genetic algorithm will search for the best solution within this set of feasible and qualified lines obtained in the first phase. These two phases are repeated until a stop criterion is reached. Computational tests were performed to demonstrate the effectiveness and efficiency of the proposed method. Then, the tour scheduling problem is addressed in the context of finding shifts of work-days and days-off scheduling. Its resolved by deterministic techniques. Some methods are then discussed on how to integrating both of the solutions of the lines of work and the tour scheduling problems / Doutor

Orientador: Maria do Socorro Nogueira Rangel / Banca: Silvio Alexandre de Araujo / Banca: Kelly Cristina Poldi / Resumo: Neste trabalho apresentamos o problema de corte de estoque (PCE) e algumas de suas características e propriedades. Abordamos com mais detalhes o problema de corte de estoque bidimensional, guilhotinado, 2-estágios, exato e não-exato. Exibimos o modelo matemático do PCE e o método de geração de colunas proposto por Gilmore e Gomory na década de $60$. Apresentamos duas heurísticas residuais da literatura e sugerimos mudanças no método da ordenação dos padrões de corte de uma delas. Implementamos todo o algoritmo das heurísticas residuais utilizadas, realizamos testes computacionais usando três conjuntos de instâncias da literatura. As instâncias do Conjunto 1 foram geradas aleatoriamente e as dos Conjuntos 2 e 3 foram baseados em dados reais de uma fábrica de móveis. Os resultados obtidos com as heurísticas residuais foram comparadas com resultados disponíveis na literatura e resultados do Sistema CorteBiFur e do método branch-and-cut disponível no Cplex. Os resultados do estudo computacional indicam que a heurística residual estudada se mostra uma boa alternativa para ser implementada no sistema CorteBiFur / Abstract: In this research we presented the cutting stock problem (CSP), and some of its features and properties. The focus is the two-dimensional cutting stock problem, considering guillotine cuts and, two-staged cutting patterns and the exact and non-exact cases. We exhibit a mathematical model for the CSP and a method for its solution proposed by Gilmore and Gomory in the 1960's. We present two residual heuristics from the literature and we suggest some changes on the criterion of sorting the cutting patterns in one of them. We implemented all the heuristics used in this research. We performed computacional tests with three sets of instances available in the literature. The instances of the Set 1 were randomly generated and the instances of the Sets 2 e 3 were based on real data from a furniture industry. The results obtained with the residuals heuristics were compared with results avaiable in the literature, with results from the Software CorteBiFur and the branch-and-cut method available on Cplex. The results indicated that the residual heuristic we studied its a good choice to be implemented on the CorteBiFur / Mestre

Orientador: Rubén Augusto Romero Lázaro / Banca: José Roberto Sanches Mantovani / Banca: Sergio Azevedo de Oliveira / Banca: Luis Gustavo Wesz da Silva / Banca: João Bosco Augusto London Junior / Resumo: Este trabalho aborda o problema de planejamento da expansão da rede de transmissão (PERT) e utiliza o modelo CC no horizonte de planejamento estático, em duas variações: com restrições de segurança N-1 (PERTES) e a formulação usual, sem restrições de segurança (PERTE). As meta-heurísticas busca tabu, GRASP e busca local iterada foram implementadas utilizando o framework ParadisEO e os parâmetros foram ajustados com auxílio do software paramILS. Os algoritmos foram testados em 42 sistemas teste divididos em 6 grupos de sistemas: Garver 6 barras (4 sistemas teste), IEEE 24 barras (10 sistemas teste), Sul Brasileiro 46 barras (4 sistemas teste), Sudeste Brasileiro 79 barras (4 sistemas teste), Nordeste Brasileiro 87 barras (8 sistemas teste) e Colombiano 93 barras (12 sistemas teste). Os testes verificaram a viabilidade de utilizar o framework ParadisEO para implementação de meta-heurísticas para o PERT. Além disso, foi criado um conjunto de informações de referência para utilização em trabalhos futuros com os problemas PERTE e PERTES / Abstract: This work deals with the energy network transmission expansion planning problem (TEP) and uses two variations of the CC model on the static planning horizon: with N-1 security constraints (STEPS) and the usual formulation, without security constraints (STEP). The meta-heuristics tabu search (TS), GRASP and iterated local search (ILS) were implemented using the framework ParadisEO and the parameters tunning were made with the aid of paramILS. The algorithms were tested in 42 test systems divided into 6 groups: Garver 6 bars (4 test systems), IEEE 24 bars (10 test systems), 46 South Brazilian bars (4 test systems), Brazilian Southeast 79 bars (4 test systems), Brazilian Northeast 87 bars (8 test systems) and Colombian 93 bars (12 test systems). The tests showed the viability of ParadisEO framework to implement meta-heuristics for the TEP problem. In addition, a large benchmark for use in future STEP and SSTEP works was created. / Doutor

Orientador: Silvio Alexandre de Araujo / Banca: Maria do Socorro Nogueira Rangel / Banca: Kelly Cristina Poldi / Banca: Sonia Cristina Poltroniere Silva / Banca: Deisemara Ferreira / Resumo: Nesta tese, estamos interessados em tratar de maneira integrada dois conhecidos problemas da literatura. Esta integração é referida na literatura como problema integrado de dimensionamento de lotes e corte de estoque. A ideia consiste em considerar simultaneamente, as decisões relacionadas com ambos os problemas, de modo a capturar a interdependência entre estas decisões e, assim, obter uma melhor solução global. Propõe-se um modelo matemático geral para o problema integrado de dimensionamento de lotes e corte de estoque (GILSCS), que considera vários níveis de integração e nos permite classificar a literatura, em termos de modelos matemáticos, dos problemas integrados. A classificação é organizada a partir de dois principais aspectos de integração que são: a integração através dos períodos de tempo e a integração entre os níveis de produção. Em um horizonte de planejamento que considera vários períodos, o estoque fornece uma ligação entre os períodos. Esta integração, por períodos de tempo, constitui o primeiro tipo de integração. O problema geral também considera a produção em diferentes níveis: objetos são fabricados ou comprados e então são cortados para produzir peças menores e estas, por sua vez, constituem componentes para a produção dos produtos finais. A integração entre os diferentes níveis de produção consiste no segundo tipo de integração. A revisão da literatura também possibilita direcionar interessantes áreas para pesquisas futuras. O comportamento da solução... / Abstract: In this thesis, the subject of interest is in treating, in an integrated way, two wellknown problems in the literature. This integration is referred in the literature as the integrated lot-sizing and cutting stock problem. The basic idea is to consider, simultaneously, the decisions related to both problems so as to capture the interdependency between these decisions in order to obtain a better global solution. We propose a mathematical model for a general integrated lot-sizing and cutting stock (GILSCS) problem. This model considers multiple dimensions of integration and enables us to classify the current literature, in terms of mathematical models, in this field. The main classification of the literature is organized around two types of integration. In a planning horizon which consists of multiple periods, the inventory provides a link between the periods. This integration across time periods constitutes the first type of integration. The general problem also considers the production in different levels: objects are fabricated or purchased and then, they are cut to produce the pieces which are then assembled as components in the production of final products. The integration between these production levels constitutes the second type of integration. The literature review also enables us to point out interesting areas for future research. The behavior of a solution to this type of problem, with three levels of production and several time periods, is studied considering the ... / Doutor

Made available in DSpace on 2016-02-05T18:29:44Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-08-31. Added 1 bitstream(s) on 2016-02-05T18:33:07Z : No. of bitstreams: 1 000857581.pdf: 1412939 bytes, checksum: a0bc976f0ed13945de0da1c095f5ed56 (MD5) / Este trabalho aborda o problema de planejamento da expansão da rede de transmissão (PERT) e utiliza o modelo CC no horizonte de planejamento estático, em duas variações: com restrições de segurança N-1 (PERTES) e a formulação usual, sem restrições de segurança (PERTE). As meta-heurísticas busca tabu, GRASP e busca local iterada foram implementadas utilizando o framework ParadisEO e os parâmetros foram ajustados com auxílio do software paramILS. Os algoritmos foram testados em 42 sistemas teste divididos em 6 grupos de sistemas: Garver 6 barras (4 sistemas teste), IEEE 24 barras (10 sistemas teste), Sul Brasileiro 46 barras (4 sistemas teste), Sudeste Brasileiro 79 barras (4 sistemas teste), Nordeste Brasileiro 87 barras (8 sistemas teste) e Colombiano 93 barras (12 sistemas teste). Os testes verificaram a viabilidade de utilizar o framework ParadisEO para implementação de meta-heurísticas para o PERT. Além disso, foi criado um conjunto de informações de referência para utilização em trabalhos futuros com os problemas PERTE e PERTES / This work deals with the energy network transmission expansion planning problem (TEP) and uses two variations of the CC model on the static planning horizon: with N-1 security constraints (STEPS) and the usual formulation, without security constraints (STEP). The meta-heuristics tabu search (TS), GRASP and iterated local search (ILS) were implemented using the framework ParadisEO and the parameters tunning were made with the aid of paramILS. The algorithms were tested in 42 test systems divided into 6 groups: Garver 6 bars (4 test systems), IEEE 24 bars (10 test systems), 46 South Brazilian bars (4 test systems), Brazilian Southeast 79 bars (4 test systems), Brazilian Northeast 87 bars (8 test systems) and Colombian 93 bars (12 test systems). The tests showed the viability of ParadisEO framework to implement meta-heuristics for the TEP problem. In addition, a large benchmark for use in future STEP and SSTEP works was created.

Made available in DSpace on 2015-08-20T17:09:54Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-02-27. Added 1 bitstream(s) on 2015-08-20T17:26:08Z : No. of bitstreams: 1 000844053.pdf: 1930384 bytes, checksum: b701993782dfb0a3f9c5c18058859fe0 (MD5) / O problema da reconfiguração de sistemas de distribuição de energia elétrica consiste em determinar a topologia radial, que pode ser obtida por meio da abertura ou fechamento de chaves de seccionamento (normalmente fechadas) e de ligação (normalmente abertas), de forma que um objetivo seja atingido, geralmente a minimização das perdas, balanceamento das cargas, melhoria dos níveis de tensão ou isolamento de faltas. Além disto, a topologia ótima deve cum- prir com restrições operacionais, como o limite de tensão nas barras e os limites de correntes nos circuitos. O modelo deste problema é de programação não linear inteira mista, não convexo e de difícil solução através de técnicas clássicas de otimização, além disto, este problema apre- senta o fenômeno da explosão combinatória. Neste trabalho são apresentadas metodologias, baseadas na meta-heurística de busca em vizinhança variável, para resolver o problema da re- configuração de sistemas de distribuição de energia elétrica considerando vários níveis de de- manda e topologia fixa da rede, que visa encontrar uma única topologia ótima para operar nos vários níveis de demanda de um período. O objetivo considerado é a minimização do custo das perdas de energia. Foram desenvolvidas quatro formas do algoritmo de busca em vizinhança variável: Basic Variable Neighborhood Search (BVNS), Variable Neighborhood Descent (VND), Reduced Variable Neighborhood Search (RVNS) e General Variable Neighborhood Search (GVNS). Todos os programas foram escritos em linguagem FORTRAN. Os algoritmos propostos foram testados com os sistemas de 33, 84, 136, 415 e 10477 barras. Os resultados foram comparados com os existentes na literatura especializada e os obtidos pela resolução de um modelo de otimização, escrito em linguagem AMPL e resolvido com o solver comercial CPLEX / The distribution network reconfiguration problem consists in determining the radial to- pology, that can be obtained by opening and closing sectionalizing switches (normally closed switches) and tie switches (normally open switches), so that an objective is achieved, commonly loss minimization, load balancing, voltage levels improvement or fault isolation. Furthermore, the optimal topology must satisfy operational constraints, such as voltage levels on nodes and current magnitude on circuits. The model for this problem is a mixed-integer nonlinear pro- gramming problem, non-convex and hard to solve by classical optimization techniques, besides, this problem presents the combinatorial explosion phenomenon. This work presents methodol- ogies, based on the variable neighborhood search metaheuristic, to solve the distribution net- work reconfiguration problem with variable demand and fixed topology, which aims in finding only one optimal topology to operate on the various load levels during a period. The considered objective is the reduction of the cost of energy losses. Four variable neighborhood search algo- rithms were developed: Basic Variable Neighborhood Search (BVNS), Variable Neighborhood Descent (VND), Reduced Variable Neighborhood Search (RVNS) and General Variable Neigh- borhood Search (GVNS). All programs were implemented in FORTRAN. The proposed algo- rithms were tested with the 33, 84, 136, 415 and 10477-node systems. The results were com- pared with the best-known solutions presented in specialized literature and the solutions ob- tained from an optimization model, written in AMPL and solved with commercial solver CPLEX