Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T17:20:46Z (GMT). No. of bitstreams: 1 Silva_FabricioLuisSantosda_M.pdf: 657410 bytes, checksum: 65ac7a297f6547a9ac70dfa42604f1ce (MD5) Previous issue date: 2010 / Resumo: Neste trabalho lidamos com o problema de Empacotamento em Faixa Bidimensional considerando o caso em que os itens devem ser dispostos de forma a manter o empacotamento estável e satisfazer uma ordem de descarregamento imposta. Consideramos o caso em que a orientação dos itens é fixa. Definimos uma metodologia para analisar a estabilidade do empacotamento observando as condições de equilíbrio estático para corpos rígidos. Desenvolvemos heurísticas e formulamos um programa linear inteiro para o problema de Empacotamento em Faixa sujeito a tais restrições. A resolução da formulação inteira ocorre através de uma estratégia do tipo branch-and-cut. As restrições de estabilidade foram inseridas como planos de corte de maneira a remover empacotamentos que não são estáveis. Em nossos experimentos computacionais, vemos que o modelo proposto é adequado para lidar com instâncias de pequeno até médio porte, dentro de um tempo computacional razoável / Abstract: This paper investigates the Two-Dimensional Strip Packing Problem considering the case in which the items should be arranged to form a stable packing and satisfy an order of unloading, so that after unloading, the packing is still stable. We consider the case where the items are oriented and rotations are not allowed. We present a methodology to analyze the stability of the packing observing the conditions for static equilibrium of rigid bodies. We present heuristics and formulate an integer linear programming model for the Strip Packing problem considering such constraints. To solve the integer formulation, we develop a branch-and-cut approach. For each integer solution obtained during the branch-and-cut algorithm, corresponding to a non-stable packing, we insert a cutting plane for which this integer solution is not satisfied. In our computational experiments, we see that the proposed model is suitable to deal with small and mid-sized instances. Some optimal solutions were obtained after few hours of CPU processing / Mestrado / Mestre em Ciência da Computação

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T02:04:53Z (GMT). No. of bitstreams: 1 Biller_PrisciladoNascimento_M.pdf: 16893114 bytes, checksum: 4346a38c95f6bb748d840f487e61890b (MD5) Previous issue date: 2012 / Resumo: Os rearranjos são eventos evolutivos que alteram de diferentes formas a ordem de grandes segmentos do genoma. Explicar a história evolutiva de um conjunto de espécies com rearranjos pode ser visto como um problema de otimização computacional, chamado de Problema de Rearranjo de Múltiplos Genomas. Este problema consiste em encontrar uma árvore que relaciona o conjunto de genomas recebido, minimizando a soma dos pesos das arestas, sendo o peso de uma aresta o número de rearranjos que explica a evolução entre os genomas dos vertesses incidentes. A qualidade da inferência e a complexidade do problema dependem do modelo de rearranjo utilizado, que define formalmente como os genomas podem ser modificados. Recentemente, um novo modelo de rearranjo foi proposto, o Single-Cut-or-Join (SCJ), que traz como grande vantagem a simplificação de muitos problemas, que sob outros modelos são NP-difíceis. Apesar da teoria do SCJ ser bem construída, havia dúvidas sobre sua relevância biológica. Neste trabalho contribuímos com o entendimento deste modelo, realizando um extenso estudo que aplica o SCJ sob diferentes condições evolutivas, com dados reais e simulados, analisando dois aspectos da reconstrução evolucionária: a estrutura da árvore e o genoma (ordem dos genes) das espécies ancestrais. Na primeira análise, descobrimos que o SCJ é capaz de recuperar entre 60% e 80% da estrutura da árvore. Em relação à segunda questão, dada a estrutura da árvore, a reconstrução dos genomas ancestrais varia conforme a distância da espécie ancestral para as espécies conhecidas. No caso de espécies ancestrais mais próximas às folhas, cerca de 85% da ordem dos genes foi coberta enquanto, em espécies mais distantes, aproximadamente 50% da ordem dos genes foi coberta, usando conjuntos de genomas de 64 espécies. Em relação ao tempo, os métodos, que implementamos em Java, podem encontrar a topologia de 64 genomas com 2000 genes cada em cerca de 10,7 minutos e reconstruir seus genomas ancestrais em 0,05 minutos, ambos em um computador desktop padrão / Abstract: Rearrangements are evolutionary events that modify in different ways the order of large segments in genomes. To explain the evolutionary history of a set of species with rearrangements can be seen as an computational optimization problem, called Multiple Genome Rearrangement Problem. This problem consists in finding a tree which relates the set of genomes received, minimizing the sum of edge weights, where the weight of an edge is the number of rearrangements that explains the evolution between the genomes of incident vertices. The quality of the inference and complexity of the problem depend on the rearrangement model used, which formally defines how the genomes can be modified. Recently, a new rearrangement model was proposed, Single-Cut-or-Join (SCJ), which brings a significant advantage in simplifying many problems that are NP-hard under other models. Although the SCJ theory is well constructed, there were doubts about its biological relevance. In this work we contribute to the understanding of this model, performing an extensive study that applies the SCJ under different evolutionary conditions, with real and simulated data, analyzing two aspects of evolutionary reconstruction: the tree structure and the genome (gene order) of the ancestral species. In the first analysis, we found out that SCJ can recover between 60% to 80% of the tree structure. Regarding the second question, given a tree structure, the reconstruction of ancestral genomes varies according to the distance from ancestral species to the known species. In the case of ancestral species close to the leaves, about 85% of the gene order can be recovered while, in more distant species, about 50% of gene order are recovered, using genome sets of 64 species. As far as time is concerned, the methods we implemented can find a topology for 64 genomes with 2000 genes each in about 10.7 minutes, and reconstruct the ancestral genomes in about 0.05 minutes, both on a typical desktop computer / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador : Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T00:48:43Z (GMT). No. of bitstreams: 1 Costa_AlyssonMachado_M.pdf: 694166 bytes, checksum: 446bf3769d5078fa5450d0342397fc40 (MD5) Previous issue date: 2002 / Mestrado

Orientador : Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T14:28:12Z (GMT). No. of bitstreams: 1 Carvalho_RodrigoMoreira_M.pdf: 6710938 bytes, checksum: 15412b36523f97788649863056960796 (MD5) Previous issue date: 2002 / Resumo: A área de otimização combinatória multiobjetivo tem despertado crescente interesse pela sua importância prática e pela necessidade de desenvolver métodos eficientes que forneçam uma boa aproximação das soluções ótimas de Pareto. Neste trabalho é abordado o problema de seqüenciamento de tarefas em uma máquina com tempos de processamento dependentes da seqüência, datas de entrega e duas medidas de desempenho: soma do atrasos das tarefas e tempo total para processar todas as tarefas, também chamado de makespan. A minimização do makespan é equivalente à minimização do comprimento da rota no problema do caixeiro viajante assimétrico. Diversas heurísticas construtivas para cada critério propostas na literatura foram adaptadas para gerar um conjunto inicial de soluções não dominadas. Este conjunto é utilizado como partida em um método de busca em vizinhança com múltiplos recomeços. Vários tipos de vizinhanças foram testados, bem como diferentes estratégias de implementação de uma busca local multiobjetivo. Uma versão do método é testada em problemas pequenos, onde as soluções ótimas de Pareto são obtidas por enumeração completa. Para problemas grandes testa-se o desempenho relativo de diversas versões do método, e compara-se a qualidade das soluções que minimizam cada objetivo individualmente com a qualidade das soluções geradas por algoritmos mono-objetivos propostos recentemente na literatura / Abstract: The area of multio~ve combinatorial optimization has attracted the attention of researchers due to its practical importance and the need to develop efficient methods that yield a good approximation of the Pareto optimal solutions. This work addresses the sequencing of jobs in a single machine with sequence dependent setup times, due dates and two performance measures: the sum of job tardiness and the total time to process all jobs, also known as makespan. The minimization of the makespan is equivalent to the minimization of the tour length for the asymmetric traveling salesman problem. Several constructive heuristics proposed for each criterion in the literature were adapted to generate an initial set of nondominated solutions. This set is used to start a neighborhood search method with multiple restarts. Various neighborhood types were tested, as well as different strategies of implementing a multiobjective local search. A version of the method is tested for small problems, where the optimal Pareto solutions are obtained by complete enumeration. For larger problems, the relative performance of versions of the method is evaluated, and the quality of the solutions that minimize each objective is compared with the solutions generated by single-objective algorithms recently proposed in the literature / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Christiano Lyra Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T21:35:03Z (GMT). No. of bitstreams: 1 Yoshimoto_Eduardo_M.pdf: 1325962 bytes, checksum: 7a3d6ef896a0e63627f46cd396e917bc (MD5) Previous issue date: 2003 / Resumo: Este trabalho apresenta uma nova metodologia para o Problema de Planejamento de Redes Secundárias de Distribuição de Energia Elétrica. A metodologia visa a minimização dos custos através de métodos heurísticos de otimização, tendo o compromisso de atendimento da demanda do consumidor final. A metodologia foi desenvolvida para um cenário onde se planeja a construção de um novo loteamento ("greenfield"). Divide-se a metodologia em três etapas, utilizando-se técnicas formais de otimização baseadas em heurísticas construtivas e de melhoria. Inicialmente, localiza-se os transformadores, utilizando-se o método das p-medíanas. Em seguida, através do algoritmo de obtenção de caminhos mínimos, é feita a ligação dos consumidores finais aos transformadores. Por fim, utilizando-se de um problema de Steiner, é feito o condutoramento da rede primária aos transformadores. Esta divisão é a fase construtiva do método GRASP. Na fase de melhoria é aplicada uma Busca em Vizinhança Variável (VNS). O trabalho propõe também uma nova metodologia para consideração adequada dos requisitos de potência e energia nas redes. Estudos de casos detalhados ilustram a aplicação das metodologias propostas. / Abstract: This work presents a new methodology for the planning problem of secundary networks in power distribution systems. The approach aims to minimize the compromise between facility costs and technical losses in secundary systems. The metodology was mainly developed for greenfild problems, where a new network must be built completely. It comprises three main phases, based on formal optimization techniques and heuristics. The first phase deals with transformers alocation, using a p-median optimization model. The second phase solves the secondary network routing problem. Finally, a Steiner tree problem defines the connections of transformers with the existing primary network. The three phases comprise the constructive part of a Greedy Randomized Adaptive Search Procedures (GRASP). Following, a Variable Neighborhood Search (VNS) process is applied to improve the solution. The work also presents a new approach to deal with loads, separeting power and energy demands. Case studies illustrate the possibilities of the approach. / Mestrado

Orientadores : Carlos Magnus Carlson Filho, Raul Vinhas Ribeiro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T22:22:33Z (GMT). No. of bitstreams: 1 Sousa_MarcosAntoniode_D.pdf: 2731661 bytes, checksum: feeceb1fd383e3af6f8ce129bce5b0c6 (MD5) Previous issue date: 2004 / Doutorado

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T23:44:20Z (GMT). No. of bitstreams: 1 Shiguemoto_AndreLuis_M.pdf: 3046317 bytes, checksum: c423cde2a2fa6c3581d15058afec5085 (MD5) Previous issue date: 2004 / Mestrado / Engenharia Eletrica / Mestre em Engenharia Elétrica

Orientadores: Ruben Augusto Romero Lazaro, Andre Luiz Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T00:23:55Z (GMT). No. of bitstreams: 1 Oliveira_SergioAzevedode_D.pdf: 11876459 bytes, checksum: 5fe45b6ab623e895fe15f36e44d5bd24 (MD5) Previous issue date: 2004 / Resumo: Neste trabalho foram desenvolvidas diversas metaheuristicas combinatorias para a resolução do problema do planejamento da expansão da transmissão dos sistemas de energia eletrica analisado do ponto de vista estatico e a longo prazo, dentre as quais uma versão paralela da metodologia ¿simulated annealing¿ e diversas versões paralelas de algoritmos geneticos; alem de um time assincrono cujos agentes são variantes destas metaheuristicas. Todas estas versões são inicializadas por um time assincrono de algoritmos heuristicos construtivos e executadas em um ambiente de processamento distribuido composto por uma rede heterogenea de estações SUN, sistema operacional SunOS, com biblioteca para processamento paralelo PVM. Foram feitos diversos testes para os sistemas: Garver (6 barras/15 ramos), Sul brasileiro (46 barras/79 ramos), Norte-Nordeste brasileiro (87 barras/179 ramos) e sistema colombiano (93 barras/155 ramos), e os resultados comprovam a eficacia das metodologias propostas quando comparados com os resultados das versões seriais de cada metaheuristica isoladamente, bem como mostram uma redução significativa nos tempos de processamento / Abstract: In this work, several combinatorial metaheuristics are developed for solving the transmission expansion planning problem of electric power systems that is analysed considering the static and long-term approach, e.g. a parallel version of the simulated annealing methodology and several parallel versions of a genetic algorithms, besides an asynchronous team which agents are variants of these metaheuristics. All of these versions are initialized by an asynchronous team of constructive heuristic algorithms, executed in a distributed processing environment, composed of a heterogeneous network of SUN workstations, SunOS, with PVM parallel processing library. Several tests are effectuated for the systems: Garver (6 busses/15 branches); brazilian South (46 busses/79 branches), brazilian North/Northeast (87 busses/179 branches) and the colombian system (93 busses/155 branches). The results show the efficiency of the proposed methodologies when compared to the serial versions of each metaheuristic isolatedely, as well as a significative reduction on the processing times / Doutorado / Engenharia Eletrica / Doutor em Engenharia Elétrica

Orientador: Christiano Lyra Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T13:52:34Z (GMT). No. of bitstreams: 1 Tao_WelfaneKemil_M.pdf: 5537070 bytes, checksum: daa47ae9abdc3c330e9d2f1c0deea02e (MD5) Previous issue date: 1999 / Resumo: Esse trabalho trata o problema da minimização das perdas em sistemas de distribuição de energia elétrica. Considerando a restrição da operação radial da rede de distribuição, o problema pode ser formulado como uma generalização da árvore recobridora de custo mínimo. A solução de mínimas perdas é obtida em duas etapas. A restrição de radialidade é relaxada na primeira etapa, obtendo-se uma solução otimista para o problema. Na segunda etapa, utiliza-se uma estratégia de busca para encontrar a solução ótima global factível do problema, guiada pelas informações da solução otimista. A solução otimista é obtida através de técnicas de otimização de fluxos não lineares em redes. A estratégia de busca usa procedimentos da área de inteligência artificial. Técnicas de processamento paralelo auxiliam a obtenção mais rápida da solução ótima / Abstract: This thesis addresses the problem of loss minimization for electric energy distribution system. As distribution networks operates radially, the problem can be formulated as a generalization of minimum spanning tree problem. The minimum loss solution is obtained in two steps. The constraint of radial operation is relaxes in the first step, leading to an optimistic solution. Information from optimistic solution is used to guide search strategies for obtain the optimal feasible solution. Non-linear network flow methods are adopted to find the optimistic solution. The search strategies is based on concepts from the field of artificial intelligence. Parallel processing speeds the search of optimal solution / Mestrado / Mestre em Engenharia Elétrica

Orientador: Christiano Lyra Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T19:24:38Z (GMT). No. of bitstreams: 1 Costa_MarcosFabioNobregada_M.pdf: 5953099 bytes, checksum: 8ffa825d7b121106adf6cb5400d1ac28 (MD5) Previous issue date: 1999 / Resumo: Este trabalho adota uma abordagem de computação evolutiva para encontrarmos a configuração de mínimas perdas de uma rede de distribuição de energia elétrica radial. O principal elemento da busca é um Algoritmo Genético, meta-heurística que imita os processos evolutivos naturais. A partir de população de indivíduos gerada aleatoriamente, a adequação média das gerações subseqüentes de indivíduos é melhorada através de mecanismos de Seleção, Cruzamento e Mutação. Uma importante característica dos Algoritmos Genéticos é a forte atração para ótimos locais com a perda da diversidade. Para escapar destas soluções, foram implementadas estratégia de diversificação inspiradas em Busca Tabu e Cruzamentos Baseados em Comportamento. A incorporação de busca local heurística explora conhecimento específico sobre o problema, sendo utilizada juntamente com procedimento de diversificação para preservação de níveis mínimos de diversidade. Resultados sobre redes reais de médio e grande porte são apresentados / Abstract: The present work adopts an evolutionary computation approach to reach the minimum loss configuration of a radial power distribution network. The main element of the search is a Genetic Algorithm, meta-heuristic that imitates the natural evolutive process. Starting with a random-generated population, the mean fitness of successive generations is increased through Selection, Crossover and Mutation mechanisms. One important feature of Genetic Algorithms is the strong attraction to local optimal solutions. To escape from these solutions, we implemented a diversification strategy inspired in Tabu Search and Behavior-Based Crossovers. The incorporation of heuristic local search, that explores specific knowledge of the problem domain, is added to the diversification procedure to preserve a minimum level of diversity. Results for real, medium, and large distribution networks are discussed. / Mestrado / Mestre em Engenharia Elétrica