Navegando por Palavras-chave "Meta-heurísticas"

Agora exibindo 1 - 2 de 2
  • Imagem de Miniatura
    Item
    Acesso aberto (Open Access)
    Uma nova heurística para o problema de minimização de trocas de ferramentas
    (Universidade Federal de São Carlos, 2012-01-01) Chaves, Antonio Augusto [UNIFESP]; Senne, Edson Luiz França; Yanasse, Horacio Hideki [UNIFESP]; Universidade Federal de São Paulo (UNIFESP); Universidade Estadual Paulista (UNESP); Instituto Nacional de Pesquisas Espaciais
    The minimization of tool switches problem (MTSP) seeks a sequence to process a set of jobs so that the number of tool switches required is minimized. This study presents a new heuristic for the MTSP. This heuristic has two phases: a constructive phase, based on a graph where the vertices correspond to tools and there is an arc k = (i, j) linking vertices i and j if and only if the tools i and j are required to execute some job; and an improvement phase, based on an Iterated Local Search. Computational results show that the proposed heuristic has a good performance on the instances tested contributing to a significant reduction in the number of nodes generated by an enumerative algorithm.
  • Imagem de Miniatura
    Item
    Acesso aberto (Open Access)
    Seleção supervisionada de meta-heurísticas para o problema bipartite graph drawing
    (Universidade Federal de São Paulo, 2021-08-16) Ferrari, Bruno José Dreux [UNIFESP]; Rosset, Mariá Cristina Vasconcelos Nascimento [UNIFESP]; http://lattes.cnpq.br/1010810293243435; http://lattes.cnpq.br/2523020753840807
    O processo de visualização da informação é um tópico relevante para o estudo em Ciência da Computação. Dados e informações, quando apresentados de maneira intuitiva, ajudam o usuário a entender relações relevantes e a extrair novas informações de dados abstratos de maneira eficiente. Neste universo de visualização da informação, os grafos são uma forma bem estabelecida e aceita para se representar diversas informações. São estruturas que modelam diversos problemas e são utilizadas em vários cenários, como representações de redes sociais, ligações entre páginas na web, planejamento de produção, dentre outras. Entretanto, como são estruturas que não possuem ordem, podem ser de difícil entendimento caso não estejam dispostos de maneira organizada. Portanto, para que as informações contidas possam ser visualizadas corretamente, é importante que suas representações sejam feitas utilizando algum critério estético. Por ser uma forma de abstração que por construção, representa objetos de natureza combinatória, o problema de encontrar uma representação que seja ótima em algum critério, se faz necessário, na maioria das vezes, a resolução de problemas da classe NP-Completo, sendo necessário a utilização de heurísticas para uma solução rápida do problema. Nesse contexto, existem diversas meta-heurísticas que resolvem esse problema, conhecido por graph drawing, cujas meta-heurísticas diferenciam-se em seu desempenho a depender das instâncias estudadas. Dessa forma, o presente trabalho apresenta um método de seleção de algoritmos para o problema de graph drawing, por uma estratégia de aprendizado supervisionado (meta-aprendizado) baseada em algoritmos de classificação. 1240 grafos e 16 classificadores foram considerados em testes computacionais, sendo que, em termos de acurácia, seleções não melhores que a incidência da melhor meta-heurística foram encontradas. Em outras palavras, o método selecionou, proporcionalmente, de forma correta, na proporção equivalente à do algoritmo com maior parcela de melhores resultados. Após a análise dos resultados, concluiu-se que fatores para tal acontecimento foram a homogeneidade tanto de soluções geradas, isto é, resultados em geral muito próximos, quanto de grafos considerados, isto é, instâncias com características similares.