Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo

The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature

Algoritomos transgenéticos aplicados ao problema da árvore geradora biobjetivo

The Multiobjective Spanning Tree is a NP-hard Combinatorial Optimization problem whose application arises in several areas, especially networks design. In this work, we propose a solution to the biobjective version of the problem through a Transgenetic Algorithm named ATIS-NP. The Computational Transgenetic is a metaheuristic technique from Evolutionary Computation whose inspiration relies in the conception of cooperation (and not competition) as the factor of main influence to evolution. The algorithm outlined is the evolution of a work that has already yielded two other transgenetic algorithms. In this sense, the algorithms previously developed are also presented. This research also comprises an experimental analysis with the aim of obtaining information related to the performance of ATIS-NP when compared to other approaches. Thus, ATIS-NP is compared to the algorithms previously implemented and to other transgenetic already presented for the problem under consideration. The computational experiments also address the comparison to two recent approaches from literature that present good results, a GRASP and a genetic algorithms. The efficiency of the method described is evaluated with basis in metrics of solution quality and computational time spent. Considering the problem is within the context of Multiobjective Optimization, quality indicators are adopted to infer the criteria of solution quality. Statistical tests evaluate the significance of results obtained from computational experiments

O problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Uma abordagem por nuvem de partículas para problemas de otimização combinatória

Combinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm optimization (metaheuristic) applied to combinatorial optimization problems: the Traveling Salesman Problem and the Multicriteria Degree Constrained Minimum Spanning Tree Problem. The first problem optimizes only one objective, while the other problem deals with many objectives. In order to evaluate the performance of the algorithms proposed, they are compared, in terms of the quality of the solutions found, to other approaches

Modelagem da disponibilidade de uma unidade geradora da UHE-Tucuruí

Com o advindo do marco regulatório do Setor Elétrico Brasileiro, a partir de 2004, os agentes que atuam neste mercado têm experimentado um acirramento nas disputas por novos negócios, evidenciando um aumento de competitividade. A Disponibilidade dos Ativos Físicos e os Custos com Manutenção se apresentam como os pontos chave para a competitividade dos agentes. O presente trabalho tem por objetivo apresentar uma metodologia de Análise de Disponibilidade de Sistemas Reparáveis, durante as etapas de projeto ou de operação do sistema, contemplando a mensuração dos Custos com Manutenção versus o Desembolso com Aquisição para um nível esperado de desempenho. A metodologia para a Análise de Disponibilidade sugerida se utiliza da construção do Diagrama de Blocos do Sistema com respectivas descrições funcionais, exportação das informações para o formato de Árvore de Sucesso, composta de portas lógicas dos tipos "E" e "OU" as quais caracterizam um subsistema integrante do sistema principal. O analista pode reavaliar a topologia do sistema, agregando ou retirando redundâncias com a finalidade de ajustar o desempenho do projeto aos requisitos de Disponibilidade, Custo de Aquisição e Custos de Manutenção. Como resultados do trabalho foram identificadas lacunas normativas que definem a forma de controle do desempenho dos ativos, estabelecida uma sistemática de integração entre técnicas de modelagem de confiabilidade e disponibilidade, estabelecidos e incorporados indicadores de desempenho de Manutenção Programada em um agente do mercado, foram modelados e discutidos diferentes cenários para um Sistema de Circulação de Óleo de Mancal e foi aplicado o modelo a toda uma Unidade Geradora Hidráulica por meio da implementação computacional do modelo aos componentes críticos dos principais sistemas.

Caracterização da matéria orgânica potencialmente geradora de petróleo e seu posicionamento bioestratigráfico, com base em palinologia e palinofácies da Formação Pojuca - Bacia do Recôncavo

O presente estudo baseou-se na análise do conteúdo orgânico de 173 amostras da Formação Pojuca, provenientes dos furos de sondagem 9-FBA-65-BA e 9-FBA-79-BA perfurados na Bacia do Recôncavo. Neste trabalho procedeu-se a um estudo integrando, resultados palinológicos, palinofaciológicos e de geoquímica orgânica com base nos dados de teores de Carbono Orgânico Total (COT) e de pirólise Rock-Eval. A associação palinoflorística identificada indica um paleoambiente dominantemente continental, composto por um sistema fluvial deltaico-lacustre, sob um clima quente e árido. Tal associação enquadra-se àquelas observadas nas bacias do Nordeste brasileiro e insere-se nas características das associações pertencentes à Província Microflorística Dicheiropollis (ex WASA). Foram identificadas 55 espécies de palinomorfos, incluindo grãos de pólen e esporos. A identificação das espécies, Dicheiropollis etruscus e Vitreisporites pallidus permitiu posicionar o intervalo analisado na Biozona Vitreisporites pallidus, considerada como de idade Aratu. Por meio de observação em microscopia óptica com luz branca transmitida e luz ultravioleta; e le-BA, caracterizando um conteúdo orgânico na janela de geração de hidrocarbonetos. Com base nos resultados de pirólise Rock-Eval, verificou-se que a Formação Pojuca, na área, é constituída vando-se em conta os tipos e o grau de preservação da matéria orgânica, foi possível individualizar três palinofácies distintas. As análises quantitativas do conteúdo orgânico mostram uma mistura de material orgânico de origem alóctone, representado por grãos de pólen, esporos e fitoclastos e autóctone dominada por material orgânico amorfo. As mais altas fluorescências são observadas nas Palinofácies 1 e 2, indicando um ambiente mais reduto r à época de sedimentação, destes estratos. Os dados de ICE apresentam valores de maturação de 5 para os sedimentos atravessados pelo poço 9-FBA-65-BA e 6,5-7 para o poço 9-FBA-79 na sua quase totalidade por matéria orgânica do tipo II, rica em hidrogênio e pobre em oxigênio, correspondendo ao um tipo de matéria orgânica propícia à geração de hidrocarbonetos líquidos e gasosos. Os níveis 3 e 4, localizados nas Palinofácies 1 e 2 do poço 9-FBA-79-BA apresentam valores de COT superiores a 1,5%, e considerando os dados de pirólise Rock-Eval, nota-se que estes intervalos são os que oferecem um maior potencial gerador, já que os valores de S2 excedem a 5,0 mg HC/g de rocha, além de valores de IH superiores a 200 e atingindo 600.

Algaroba (Prosopis juliflora): árvore de uso múltiplo para a região semiárida brasileira.

2009

Proposição de um método para melhoria do manuseio pós-colheita de pimentão baseado no Mapeamento de Processos e Falhas e na Árvore da Realidade Atual.

Introdução; Objetivo e escopo do projeto; Diagnóstico obtido; Confronto falha x ação de melhoria; Plano de melhoria - propostas preliminares; Ações futuras; Conclusões; Referências bibliográficas.

Levantamento de solos do entorno da Central Geradora Termelétrica Fortaleza (CGTF), Município de Caucaia - CE

2007

Mecanismo para edição de árvore hiperbólica através da Web.

2005

Estudo de caso ? Construção da Árvore de Conhecimento da Banana a partir dos Sistemas de Produção.

O presente estudo foi gerado a partir da análise dos Sistemas de Produção (SPs) on line do produto banana disponíveis no portal Embrapa.

Considerações Sobre o Bioetanol Lignocelulósico para Subsidiar a Elaboração de Conteúdo da Árvore do Conhecimento Agroenergia.

De acordo com a previsão da Agência Internacional de Energia (AIE) até o ano de 2030, os biocombustíveis representarão cerca de 7% do combustível utilizado no transporte, sendo a União Européia, os Estados Unidos e o Brasil os principais produtores e consumidores. Esse crescimento no mercado internacional é esperado devido ao aumento do preço do petróleo e, também porque os países desenvolvidos que assinaram o Protocolo de Kyoto se comprometeram a reduzir suas emissões de gases poluentes (BRASIL, 2005). Os constantes conflitos envolvendo os países do Oriente Médio, que estão nas regiões das reservas de petróleo, causam instabilidade ao suprimento e oscilações nos preços dos combustíveis fósseis, forçando vários países a buscarem alternativas que possibilitem reduzir a dependência em relação às importações desse produto. Todos esses fatores, cuja importância varia de país para país, vêm criando oportunidades para a viabilização econômica de novas fontes de energia de biomassa. O uso do etanol, biodiesel, carvão vegetal, biogás e energia obtida a partir de resíduos do agronegócio desperta interesse crescente em muitos países, não restando dúvidas de que ocupará posição de destaque na economia mundial no futuro próximo. O bioetanol pode ser obtido de diferentes matérias-primas, cada qual com um custo de produção e um valor de venda.

Manual de árvore hiperbólica.

2009