• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 4
  • 1
  • Tagged with
  • 5
  • 5
  • 5
  • 5
  • 4
  • 3
  • 3
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

A data structure for spanning tree optimization problems / Uma estrutura de dados para problemas de otimização de árvores geradoras

Barbosa, Marco Aurélio Lopes 17 June 2019 (has links)
Spanning tree optimization problems are related to many practical applications. Several of these problems are NP-Hard, which limits the utility of exact methods and can require alternative approaches, like metaheuristics. A common issue for many metaheuristics is the data structure used to represent and manipulate the solutions. A data structure with efficient operations can expand the usefulness of a method by allowing larger instances to be solved in a reasonable amount of time. We propose the 2LETT data structure and uses it to represent spanning trees in two metaheuristics: mutation-based evolutionary algorithms and local search algorithms. The main operation of 2LETT is the exchange of one edge in the represented tree by another one, and it has O(√n) time, where n is the number of vertices in the tree. We conducent qualitative and quantitative evaluations for 2LETT and other structures in the literature. For the main operation of edge exchange in evolutionary algorithms, the computational experiments show that 2LETT has the best performance for trees with more than 10,000 vertices. For local search algorithms, 2LETT is the best option to deal with large trees with large diameters. / Os problemas de otimização de árvores geradoras estão relacionados a muitas aplicações práticas. Vários desses problemas são NP-difícies, o que limita a utilidade de métodos exatos e pode exigir abordagens alternativas, como metaheurísticas. Um questão relevante para muitas metaheurísticas é a estrutura de dados usada para representar e manipular as soluções. Uma estrutura de dados com operações eficientes pode aumentar a utilidade de um método, permitindo que instâncias maiores sejam resolvidas em um período de tempo razoável. Propomos a estrutura de dados 2LETT e a usamos para representar árvores geradoras em duas metaheurísticas: algoritmos evolutivos baseados em mutações e algoritmos de busca local. A operação principal da 2LETT é a troca de uma aresta na árvore representada por outra aresta. Esta operação tem tempo de O(√n), onde n é o número de vértices na árvore. Conduzimos avaliações qualitativas e quantitativas para 2LETT e outras estruturas na literatura. Para a principal operação de troca de arestas em algoritmos evolutivos, os experimentos computacionais mostram que a 2LETT possui o melhor desempenho para árvores com mais de 10.000 vértices. Para algoritmos de busca local, o 2LETT é a melhor opção para lidar com árvores grandes com grandes diâmetros.
2

"Investigação de estratégias para a geração de máquinas de vetores de suporte multiclasses" / Investigation of strategies for the generation of multiclass support vector machines

Lorena, Ana Carolina 16 February 2006 (has links)
Diversos problemas envolvem a classificação de dados em categorias, também denominadas classes. A partir de um conjunto de dados cujas classes são conhecidas, algoritmos de Aprendizado de Máquina (AM) podem ser utilizados na indução de um classificador capaz de predizer a classe de novos dados do mesmo domínio, realizando assim a discriminação desejada. Dentre as diversas técnicas de AM utilizadas em problemas de classificação, as Máquinas de Vetores de Suporte (Support Vector Machines - SVMs) se destacam por sua boa capacidade de generalização. Elas são originalmente concebidas para a solução de problemas com apenas duas classes, também denominados binários. Entretanto, diversos problemas requerem a discriminação dos dados em mais que duas categorias ou classes. Nesta Tese são investigadas e propostas estratégias para a generalização das SVMs para problemas com mais que duas classes, intitulados multiclasses. O foco deste trabalho é em estratégias que decompõem o problema multiclasses original em múltiplos subproblemas binários, cujas saídas são então combinadas na obtenção da classificação final. As estratégias propostas visam investigar a adaptação das decomposições a cada aplicação considerada, a partir de informações do desempenho obtido em sua solução ou extraídas de seus dados. Os algoritmos implementados foram avaliados em conjuntos de dados gerais e em aplicações reais da área de Bioinformática. Os resultados obtidos abrem várias possibilidades de pesquisas futuras. Entre os benefícios verificados tem-se a obtenção de decomposições mais simples, que requerem menos classificadores binários na solução multiclasses. / Several problems involve the classification of data into categories, also called classes. Given a dataset containing data whose classes are known, Machine Learning (ML) algorithms can be employed for the induction of a classifier able to predict the class of new data from the same domain, thus performing the desired discrimination. Among the several ML techniques applied to classification problems, the Support Vector Machines (SVMs) are known by their high generalization ability. They are originally conceived for the solution of problems with only two classes, also named binary problems. However, several problems require the discrimination of examples into more than two categories or classes. This thesis investigates and proposes strategies for the generalization of SVMs to problems with more than two classes, known as multiclass problems. The focus of this work is on strategies that decompose the original multiclass problem into multiple binary subtasks, whose outputs are then combined to obtain the final classification. The proposed strategies aim to investigate the adaptation of the decompositions for each multiclass application considered, using information of the performance obtained for its solution or extracted from its examples. The implemented algorithms were evaluated on general datasets and on real applications from the Bioinformatics domain. The results obtained open possibilities of many future work. Among the benefits observed is the obtainment of simpler decompositions, which require less binary classifiers in the multiclass solution.
3

Representação Nó-profundidade em FPGA para algoritmos evolutivos aplicados ao projeto de redes de larga-escala / Node-depth representation in FPGA for evolutionary algorithms applied to network design problems of large-scale

Gois, Marcilyanne Moreira 26 October 2011 (has links)
Diversos problemas do mundo real estão relacionados ao projeto de redes, tais como projeto de circuitos de energia elétrica, roteamento de veículos, planejamento de redes de telecomunicações e reconstrução filogenética. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (correspondendo às variáveis de entrada), dificultando a obtenção de soluções em tempo real. O Projeto de uma Rede é um problema combinatório, em que se busca encontrar a rede mais adequada segundo um critério como, por exemplo, menor custo, menor caminho e tempo de percurso. A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de Algoritmos Evolutivos para Problemas de Projetos de Redes pode ser aumentado significativamente por meio de representações mais apropriadas. Este trabalho investiga a paralelização da Representação Nó-Profundidade (RNP) em hardware, com o objetivo de encontrar melhores soluções para Problemas de Projetos de Redes. Para implementar a arquitetura de hardware, denominada de HP-RNP (Hardware Parallelized RNP), foi utilizada a tecnologia de FPGA para explorar o alto grau de paralelismo que essa plataforma pode proporcionar. Os resultados experimentais mostraram que o HP-RNP é capaz de gerar e avaliar novas redes em tempo médio limitado por uma constante (O(1)) / Many problems related to network design can be found in real world applications, such as design of electric circuits, vehicle routing, telecommunication network planning and phylogeny reconstruction. In general, these problems can be modelled using graphs that handle thousands or millions of nodes (input variables), making it hard to obtain solutions in real-time. The Network Design is the combinatorial problem of finding the most suitable network subject to a evaluation criterion as, for example, lower cost, minimal path and time to traverse the network. The solution of those problems is in general computationally complex. Metaheuristics as Evolutionary Algorithms have been widely investigated for such problems. Several researches have shown that the performance of Evolutionary Algorithms for the Network Design Problems can be significantly increased through more appropriated dynamic data structures (encodings). This work investigates the parallelization of Node-Depth Encoding (NDE) in hardware in order to find better solutions for Network Design Problems. To implement the proposed hardware architecture, called HP-NDE (Hardware Parallellized NDE), the FPGA technology was used to explore the high degree of parallelism that such platform can provide. The experimental results have shown that the HP-NDE can generate and evaluate new networks in average time constrained by a constant (O(1))
4

"Investigação de estratégias para a geração de máquinas de vetores de suporte multiclasses" / Investigation of strategies for the generation of multiclass support vector machines

Ana Carolina Lorena 16 February 2006 (has links)
Diversos problemas envolvem a classificação de dados em categorias, também denominadas classes. A partir de um conjunto de dados cujas classes são conhecidas, algoritmos de Aprendizado de Máquina (AM) podem ser utilizados na indução de um classificador capaz de predizer a classe de novos dados do mesmo domínio, realizando assim a discriminação desejada. Dentre as diversas técnicas de AM utilizadas em problemas de classificação, as Máquinas de Vetores de Suporte (Support Vector Machines - SVMs) se destacam por sua boa capacidade de generalização. Elas são originalmente concebidas para a solução de problemas com apenas duas classes, também denominados binários. Entretanto, diversos problemas requerem a discriminação dos dados em mais que duas categorias ou classes. Nesta Tese são investigadas e propostas estratégias para a generalização das SVMs para problemas com mais que duas classes, intitulados multiclasses. O foco deste trabalho é em estratégias que decompõem o problema multiclasses original em múltiplos subproblemas binários, cujas saídas são então combinadas na obtenção da classificação final. As estratégias propostas visam investigar a adaptação das decomposições a cada aplicação considerada, a partir de informações do desempenho obtido em sua solução ou extraídas de seus dados. Os algoritmos implementados foram avaliados em conjuntos de dados gerais e em aplicações reais da área de Bioinformática. Os resultados obtidos abrem várias possibilidades de pesquisas futuras. Entre os benefícios verificados tem-se a obtenção de decomposições mais simples, que requerem menos classificadores binários na solução multiclasses. / Several problems involve the classification of data into categories, also called classes. Given a dataset containing data whose classes are known, Machine Learning (ML) algorithms can be employed for the induction of a classifier able to predict the class of new data from the same domain, thus performing the desired discrimination. Among the several ML techniques applied to classification problems, the Support Vector Machines (SVMs) are known by their high generalization ability. They are originally conceived for the solution of problems with only two classes, also named binary problems. However, several problems require the discrimination of examples into more than two categories or classes. This thesis investigates and proposes strategies for the generalization of SVMs to problems with more than two classes, known as multiclass problems. The focus of this work is on strategies that decompose the original multiclass problem into multiple binary subtasks, whose outputs are then combined to obtain the final classification. The proposed strategies aim to investigate the adaptation of the decompositions for each multiclass application considered, using information of the performance obtained for its solution or extracted from its examples. The implemented algorithms were evaluated on general datasets and on real applications from the Bioinformatics domain. The results obtained open possibilities of many future work. Among the benefits observed is the obtainment of simpler decompositions, which require less binary classifiers in the multiclass solution.
5

Representação Nó-profundidade em FPGA para algoritmos evolutivos aplicados ao projeto de redes de larga-escala / Node-depth representation in FPGA for evolutionary algorithms applied to network design problems of large-scale

Marcilyanne Moreira Gois 26 October 2011 (has links)
Diversos problemas do mundo real estão relacionados ao projeto de redes, tais como projeto de circuitos de energia elétrica, roteamento de veículos, planejamento de redes de telecomunicações e reconstrução filogenética. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (correspondendo às variáveis de entrada), dificultando a obtenção de soluções em tempo real. O Projeto de uma Rede é um problema combinatório, em que se busca encontrar a rede mais adequada segundo um critério como, por exemplo, menor custo, menor caminho e tempo de percurso. A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de Algoritmos Evolutivos para Problemas de Projetos de Redes pode ser aumentado significativamente por meio de representações mais apropriadas. Este trabalho investiga a paralelização da Representação Nó-Profundidade (RNP) em hardware, com o objetivo de encontrar melhores soluções para Problemas de Projetos de Redes. Para implementar a arquitetura de hardware, denominada de HP-RNP (Hardware Parallelized RNP), foi utilizada a tecnologia de FPGA para explorar o alto grau de paralelismo que essa plataforma pode proporcionar. Os resultados experimentais mostraram que o HP-RNP é capaz de gerar e avaliar novas redes em tempo médio limitado por uma constante (O(1)) / Many problems related to network design can be found in real world applications, such as design of electric circuits, vehicle routing, telecommunication network planning and phylogeny reconstruction. In general, these problems can be modelled using graphs that handle thousands or millions of nodes (input variables), making it hard to obtain solutions in real-time. The Network Design is the combinatorial problem of finding the most suitable network subject to a evaluation criterion as, for example, lower cost, minimal path and time to traverse the network. The solution of those problems is in general computationally complex. Metaheuristics as Evolutionary Algorithms have been widely investigated for such problems. Several researches have shown that the performance of Evolutionary Algorithms for the Network Design Problems can be significantly increased through more appropriated dynamic data structures (encodings). This work investigates the parallelization of Node-Depth Encoding (NDE) in hardware in order to find better solutions for Network Design Problems. To implement the proposed hardware architecture, called HP-NDE (Hardware Parallellized NDE), the FPGA technology was used to explore the high degree of parallelism that such platform can provide. The experimental results have shown that the HP-NDE can generate and evaluate new networks in average time constrained by a constant (O(1))

Page generated in 0.0449 seconds