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 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

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

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

Aplicação do algoritmo de otimização por colônia de formigas sobre o problema do passeio do robô seletivo

This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented, GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results

Implementação de algoritmos genéticos paralelos em uma arquitetura MPSoC.

Essa dissertação apresenta a implementação de um algoritmo genético paralelo utilizando o modelo de granularidade grossa, também conhecido como modelo das ilhas, para sistemas embutidos multiprocessados. Os sistemas embutidos multiprocessados estão tornando-se cada vez mais complexos, pressionados pela demanda por maior poder computacional requerido pelas aplicações, principalmente de multimídia, Internet e comunicações sem fio, que são executadas nesses sistemas. Algumas das referidas aplicações estão começando a utilizar algoritmos genéticos, que podem ser beneficiados pelas vantagens proporcionadas pelo processamento paralelo disponível em sistemas embutidos multiprocessados. No algoritmo genético paralelo do modelo das ilhas, cada processador do sistema embutido é responsável pela evolução de uma população de forma independente dos demais. A fim de acelerar o processo evolutivo, o operador de migração é executado em intervalos definidos para realizar a migração dos melhores indivíduos entre as ilhas. Diferentes topologias lógicas, tais como anel, vizinhança e broadcast, são analisadas na fase de migração de indivíduos. Resultados experimentais são gerados para a otimização de três funções encontradas na literatura.

Algoritmos para geração de referências, inicialização e proteção de um condicionador unificado de qualidade de energia

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Investigação da transição isolante-metal do CDM via algoritmos computacionais e estudo de nano-dispositivos orgânicos

Apresentamos neste trabalho um estudo teórico sobre polímeros orgânicos conjugados. É conhecido que estes sistemas, em geral semicondutores ou isolantes, sob dopagem química podem vir a adquirir propriedades elétricas de material condutor. E ainda, sob ação de campo elétrico, pequenos oligômeros podem apresentar comportamento equivalente ao de dispositivos usuais, mas com inúmeras vantagens como, por exemplo, tamanho extremamente reduzido (alguns nanômetros). Dessa forma no primeiro capítulo faremos uma breve introdução sobre polímeros orgânicos conjugados mostrando alguns resultados experimentais obtidos para o polímero 4-dicianometileno-4,4-ciclopenta [2,1-b: 3,4b’] ditiofeno – CDM, que é o objeto central de estudo desta dissertação. O capítulo 2 trata dos métodos quânticos utilizados. Citaremos a Teoria de Hartre-Fock (HF) e suas derivações semi-empíricas. A técnica de Interação de configuração (CI) e a Teoria do Funcional da Densidade (DFT) também serão tratadas neste capítulo. O capítulo 3 é dedicado a descrever as características de alguns dispositivos usuais como diodos e transistores. Aqui o fundamental é entender a composição, o funcionamento e principalmente, como se comportam suas curvas características corrente versus voltagem (IxV). Citaremos ainda alguns dispositivos eletrônicos extremamente pequenos. No capítulo 4 começa nossos resultados e discussões referentes a análise da transição isolante-metal em CDM sob ação de dopagem. Primeiramente a nível semiempírico, obtivemos a caracterização ótica de oligômeros de CDM neutro e na presença de defeitos conformacionais do tipo bipólarons negativo e positivo. Partindo de geometrias otimizadas via métodos AM1 e PM3 obtivemos o espectro de absorção para sistemas com e sem carga. A nível Hartree-Fock calculamos a Estrutura de Bandas e a Densidade de Estados (DOS) para o PCDM no estado neutro e dopado. O cálculo da DOS e da Dispersão foram realizados através de programas computacionais desenvolvidos aqui no Grupo de Física de Materiais da Amazônia (GFMA). Apresentamos ainda neste capítulo o espectro de absorção teórico para oligômeros de CDM com diversas configurações com geometrias totalmente otimizadas pelo DFT. No capítulo 5 temos os resultados relativos à análise de nanodispositivos baseados em tetrâmeros de CDM com e sem carga. As curvas do deslocamento de carga versus voltagem apresentam características de curvas de dispositivos usuais. Analisamos também o espectro de absorção teórico dos nanodispositivos para valores de tensão nula e em pontos de saturação de corrente nas regiões direta e reversa.

Modelo mecânico para estruturas lineares em concreto armado - uma abordagem acoplada entre a mecânica do dano e algoritmos de otimização

Modelos escritos através dos conceitos da Mecânica do Dano no Contínuo representam atualmente uma alternativa consistente para a simulação numérica do comportamento de estruturas constituídas por materiais quase frágeis, onde a perda de rigidez em função da fissuração crescente é o fator preponderante da resposta não-linear de seus elementos estruturais. No entanto, modelos de dano apresentam forte dependência de parâmetros internos usados para descrever os critérios e evolução das variáveis de dano, que devem ser calibrados adequadamente para uma resposta mecânica coerente da estrutura. Neste contexto, o artigo mostra um estudo sobre a calibração de parâmetros do modelo de dano de Mazars e sua aplicação na análise numérica de vigas e pórticos planos em concreto armado. O Método dos Mínimos Quadrados é adotado para resolver o problema, em conjunto com a técnica de Gauss-Newton. Em virtude da ausência de resultados experimentais para diversas classes de resistência do concreto, como referência para o processo de calibração, são adotados alguns modelos constitutivos teóricos tanto à tração quanto à compressão. Esse processo de calibração de parâmetros é incorporado a um modelo mecânico em elementos finitos para análise de barras em concreto armado, com a consideração conjunta dos mecanismos complementares de resistência ao cisalhamento, como efeito de pino, armadura transversal e engrenamento de agregados. Uma lei constitutiva exponencial para o decaimento da resistência à tração do concreto é proposta com o objetivo de simular o comportamento do tipo tension softening do material. Testes de simulação envolvendo o modelo proposto foram realizados, comparando-se com resultados experimentais e numéricos mostrando a boa precisão e capacidade de obtenção de cargas últimas em estruturas de barras em concreto armado.

Imputação de dados em experimentos multiambientais: novos algoritmos utilizando a decomposição por valores singulares

As análises biplot que utilizam os modelos de efeitos principais aditivos com inter- ação multiplicativa (AMMI) requerem matrizes de dados completas, mas, frequentemente os ensaios multiambientais apresentam dados faltantes. Nesta tese são propostas novas metodologias de imputação simples e múltipla que podem ser usadas para analisar da- dos desbalanceados em experimentos com interação genótipo por ambiente (G×E). A primeira, é uma nova extensão do método de validação cruzada por autovetor (Bro et al, 2008). A segunda, corresponde a um novo algoritmo não-paramétrico obtido por meio de modificações no método de imputação simples desenvolvido por Yan (2013). Também é incluído um estudo que considera sistemas de imputação recentemente relatados na literatura e os compara com o procedimento clássico recomendado para imputação em ensaios (G×E), ou seja, a combinação do algoritmo de Esperança-Maximização com os modelos AMMI ou EM-AMMI. Por último, são fornecidas generalizações da imputação simples descrita por Arciniegas-Alarcón et al. (2010) que mistura regressão com aproximação de posto inferior de uma matriz. Todas as metodologias têm como base a decomposição por valores singulares (DVS), portanto, são livres de pressuposições distribucionais ou estruturais. Para determinar o desempenho dos novos esquemas de imputação foram realizadas simulações baseadas em conjuntos de dados reais de diferentes espécies, com valores re- tirados aleatoriamente em diferentes porcentagens e a qualidade das imputações avaliada com distintas estatísticas. Concluiu-se que a DVS constitui uma ferramenta útil e flexível na construção de técnicas eficientes que contornem o problema de perda de informação em matrizes experimentais.

Algoritmos de otimização e o problema inverso aplicados à identificação de danos estruturais com o uso do MEF

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Civil e Ambiental, 2015.

Avances en algoritmos de estimación de distribuciones. Alternativas en el aprendizaje y representación de problemas

131 p.: graf.

Algoritmos meméticos en problemas de investigación operativa

En este artículo se plantea la resolución de un problema de Investigación Operativa utilizando PHPSimplex (herramienta online de resolución de problemas de optimización utilizando el método Simplex), Solver de Microsoft Excel y un prototipo híbrido que combina las teorías de los Algoritmos Genéticos con una técnica heurística de búsqueda local. La hibridación de estas dos técnicas es conocida como Algoritmo Memético. Este prototipo será capaz de resolver problemas de Optimización con función de maximización o minimización conocida, superando las restricciones que se planteen. Los tres métodos conseguirán buenos resultados ante problemas sencillos de Investigación Operativa, sin embargo, se propone otro problema en el cual el Algoritmo Memético y la herramienta Solver de Microsoft Excel, alcanzarán la solución óptima. La resolución del problema utilizando PHPSimplex resultará inviable. El objetivo, además de resolver el problema propuesto, es comparar cómo se comportan los tres métodos anteriormente citados ante el problema y cómo afrontan las dificultades que éste presenta. Además, este artículo pretende dar a conocer diferentes técnicas de apoyo a la toma de decisiones, con la intención de que se utilicen cada vez más en el entorno empresarial sustentando, de esta manera, las decisiones mediante la matemática o la Inteligencia Artificial y no basándose únicamente en la experiencia.

Implementación de algoritmos de Inteligencia Swarm con fines didácticos

Con este proyecto hemos querido proporcionar un conjunto de recursos útiles para la impartición de un curso de Swarm Intelligence enfocado a la Particle Swarm Optimization (PSO). Estos recursos constan de una aplicación en NetLogo para poder experimentar, ejecutar y visualizar los diferentes modelos de la PSO, un review de la Swarm Intelligence profundizando en la PSO y una ontología de PSO que incluye los recursos bibliográficos necesarios para la investigación y la escritura de artículos.