«« Voltar
Paralelização de Metaheurísticas para Problemas de Otimização Combinatória
Protocolo do SIGProj:   188788.847.480.29102014
De:31/10/2014  à  30/10/2016
 
Coordenador-Extensionista
  Bianca de Almeida Dantas
Instituição
  UFMS - Universidade Federal de Mato Grosso do Sul
Unidade Geral
  FACOM - Faculdade de Computação
Unidade de Origem
  GAB/FACOM - Gabinete do Diretor
Resumo da Ação de Extensão
  Um dos mais conhecidos problemas de otimização combinatória com uma grande variedade de aplicações é o problema da mochila multidimensional e suas variantes. A variante binária, a mais conhecida, pode ser definida como um problema de programação inteira com uma única restrição no qual, a princípio, qualquer outro problema desse tipo pode ser transformado. Dessa forma, uma solução eficiente para o problema é de interesse para toda a área da programação inteira. O problema da mochila binária é caracterizado por duas entradas: um conjunto de itens (com seus respectivos valores e pesos) e a capacidade da mochila; há duas possibilidades para cada item: ele pertence ou não à solução. Apesar de sua simplicidade, esse problema é NP-completo, ou seja, não se conhece um algoritmo polinomial para sua solução exata. Com o aumento do número de restrições impostas ao problema da mochila, temos o problema da mochila multidimensional e a aplicação das técnicas de solução tradicional torna-se custosa, o que inviabiliza sua utilização. Essa situação leva à busca por soluções alternativas, ainda que aproximadas, para o problema como, por exemplo, as metaheurísticas e as técnicas de paralelização que são o foco do estudo de nosso trabalho. Após verificada a viabilidade da aplicação das metaheurísticas ao problema da mochila, pretende-se avaliar a sua aplicabilidade a outros problemas de otimização combinatória, tais como o QAP e o caixeiro viajante.
Palavras-chave
   Algoritmos paralelos, metaheurísticas, problema da mochila multidimensional
Público-Alvo
  
Situação
  Atividade COM RELATORIO FINAL
Contato
  
«« Voltar