Navegando por Assunto "Algoritmos"

Agora exibindo 1 - 4 de 4

Algoritmos Exatos e Heurísticos para os Problemas de Steiner e de Conexão de Terminais com Número Restrito de Roteadores e Elos
(2019-07-08) Libório, Felipe Tenório de Holanda Rocha; Pinheiro, Rian Gabriel Santos; http://lattes.cnpq.br/1447954471683870; http://lattes.cnpq.br/1881833645223497
Neste trabalho foram apresentadas soluções para o Problema de Conexão de Terminais com Número Restrito de Roteadores e Elos (TCP, do inglês Terminal Connection Problem). O TCP consiste em encontrar uma árvore que conecte um subconjunto de vértices de um dado grafo. Ele se diferencia do problema de Steiner pela introdução de uma restrição adicional ao número de vértices de Steiner que podem fazer parte de uma solução. O TCP pode ser aplicado nos mesmos tipos de problema em que se pode fazer uso do problema de Steiner, o que inclui: projetos de circuitos VLSI; roteamento multicast; modelar e resolver problemas de planejamento em telecomunicações; e distribuição de eletricidade. Como o TCP é uma generalização do problema de Steiner em grafos, também foram feitos testes em instâncias deste problema. Além disso, foram geradas diversas instâncias de diferentes níveis de dificuldade para o TCP, que trabalhos posteriores poderão utilizar para a comparação da performance de futuras soluções. Os resultados obtidos nas instâncias do Problema de Steiner foram comparados ao de outra solução da literatura e a meta-heurística utilizada na solução, a Large Neighborhood Search (LNS), se mostrou viável como uma forma simples e de baixo custo computacional, tanto em tempo de execução quanto em requisitos de memória, de se obter resultados satisfatórios para este problema. Conseguindo uma taxa de erro média abaixo de 2% nas instâncias avaliadas, a depender do tempo de execução dado ao algoritmo. Além disso, este é o primeiro trabalho a apresentar soluções para o TCP de que se tem conhecimento. Foi implementada, além da solução meta-heurística, uma solução exata com o uso do solver IBM Ilog CPLEX. Para as instâncias avaliadas cujos valores ótimos foram encontrados pela solução exata apresentada, a implementação da LNS obteve taxa de erro média de 0,66% ao mesmo tempo em que apresentou um tempo de execução 22 vezes menor que a solução exata e conseguiu obter o valor ótimo em 14 das 18 instâncias testadas. Os resultados obtidos na resolução das instâncias do TCP, juntamente às próprias instâncias geradas, formaram uma base para comparações de soluções futuras que possam vir a ser propostas para o problema.
Análise de performance de algoritmos estocásticos aplicados ao problema do caixeiro viajante
(2024-10-09) Lima, Lucas Gabriel Oliveira Sales; Monteiro, Cleviton Vinicius Fonsêca; http://lattes.cnpq.br/9362573782715504; http://lattes.cnpq.br/7636465842833021
Algoritmos de otimização são ferramentas cada vez mais relevantes nas empresas modernas por serem capazes de otimizar processos e recursos, garantindo resultados mais eficientes e com processamento em tempo hábil para tomada de decisão. A comparação destes algoritmos é o processo comum durante seus estudos de adoção. Entretanto, a utilização de metodologias complexas muitas vezes pode levar à escolha de um algoritmo impreciso, pois seu resultado pode não refletir a realidade de uma empresa que busca implementar aplicações com recursos limitados. Tendo em vista esta problemática, surge a necessidade de avaliar estes algoritmos sob uma nova ótica. O objetivo principal deste trabalho é propor uma reflexão acerca da forma que experimentos em algoritmos são conduzidos. O presente estudo realizou experimentos com algoritmos de otimização utilizando recursos computacionais semelhantes àqueles encontrados na maioria das empresas, comparando com um outro trabalho no qual foram utilizados otimizações e tunings nesses mesmos algoritmos. Para o experimento, foi utilizado o problema do caixeiro viajante, através de 15 benchmarking dividido em 3 categorias, de acordo com o tamanho de cada artigo. Ao final foram obtidas métricas estatísticas do desempenho de cada algoritmo que, comparadas com o artigo de referência, obtiveram tempos de execução menores, sem comprometer a precisão dos resultados. Algoritmos probabilísticos possuem grande importância financeira para empresas com necessidades de gerir recursos rapidamente, tais como aeroportos e estaleiros. Sendo assim, a escolha adequada de parâmetros fornece uma visão mais acurada da realidade.
M Harmony BR: o uso de formalismos para a composição algorítmica baseada em conhecimento
(2018-02-23) Silva, Vinícius Santana; Carvalho, Tiago Buarque Assunção de; Costa Junior, Jerônimo Barbosa da; http://lattes.cnpq.br/6050271311748487; http://lattes.cnpq.br/7150833804013500; http://lattes.cnpq.br/8393251786005816
Ao longo da história, diversos estudos buscaram introduzir o uso dos computadores em outras áreas do conhecimento, inclusive na música, várias pesquisas foram realizadas com a finalidade de mostrar a capacidade dos computadores em compor músicas. O presente trabalho teve como objetivo verificar a possibilidade da criação de um softwaresimples capaz de gerar harmonias de determinado estilo musical, por meio de gramáticas livres de contexto, baseadas no conhecimento obtido de composições musicais já existentes. O desenvolvimento da ferramenta teve como base a análise das características de dois estilos musicais distintos: Punk Rock e Sertanejo Universitário, por meio da coleta e análise de dados de 40 músicas. Posteriormente, a base de dados foi ampliada com a inclusão de 50 músicas do estilo Reggae e de 30 músicas do estilo Sertanejo Universitário, totalizando 120 músicas. Utilizando os dados extraídos da base de músicas foram geradas 3 gramáticas específicas para produção de harmonias de cada estilo analisado por meio de um algoritmo de composição. O estudo teve como resultado a produção de um aplicativo que compõe harmonias baseadas em conhecimento, que se mostrou útil no auxílio ao processo de composição musical.
Segmentação de banhistas utilizando algoritmos de agrupamento com seleção automática do número de grupos em regiões litorâneas
(2019) Moura, Allan Alves de; Macário Filho, Valmir; http://lattes.cnpq.br/4346898674852080; http://lattes.cnpq.br/3319938637009294
O crescente aumento de ataques de tubarões vem assustando a população das regiões litorâneas, impossibilitando a tomada de banho em certos locais. Em caso de ataque, muitas vezes uma ação para salvar a vítima é tomada somente após o ocorrido do incidente, em que um guarda-vidas tentará socorre-la. Para mitigar estes acontecimentos, foi pensado em uma ferramenta de auxílio aos guarda-vidas que permitissem aos mesmos agir antes que acidentes pudessem ocorrer, avisando o profissional caso algum banhista ultrapasse uma determinada zona de segurança. O primeiro passo para realização desta ferramenta é a segmentação das imagens de praia em busca de agrupar partes com características visualmente semelhantes afim de encontrar as pessoas dentro do mar. Para isso, o objetivo deste trabalho é estudar e encontrar um bom algoritmo de segmentação de imagens com seleção automática do número de grupos para evitar a necessidade do controle de parâmetros a fim de separar a foto em regiões ou segmentos. Este algoritmo será utilizado para a implementação da primeira etapa desta ferramenta de auxílio aos guarda-vidas em busca de regiões da imagem que representem banhistas. Técnicas de pré-processamento de imagens como a remoção da faixa de praia foram avaliadas, como também a avaliação de sistemas de cores diferentes na representação da imagem a fim de realizar a comparação entre todos esses fatores. A combinação dos algoritmos e sistemas de cores foram avaliados com e sem a remoção da faixa de praia. Os algoritmos analisados foram: Hierárquico aglomerativo, hierárquico divisivo, X-means, Auto group segmentation e segmentação automática de imagens coloridas. Todos eles foram aplicados pra três tipos diferentes de vetores de características, compostos por sistema de cor RGB(red, green e blue), LAB e a combinação de RGB + LAB. O resultado mais promissor, após avaliação visual das imagens, comportamento dos algoritmos e resultados do índice de Dunn, foi obtido utilizando o algoritmo de segmentação de imagens coloridas com vetor de características composto de RGB + LAB, totalizando para o índice de Dunn 1.5245 de média para todas as imagens, aplicando a remoção de praia depois da execução do algoritmo.