Estratégias de exploração de vizinhança com GPU para problemas de otimização

• Ano de defesa: 2018
• Autor(a) principal: Araújo, Rodolfo Pereira
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; BR; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Meta-heuristics; Local Search; Dataflow; Graphics Processing Unit; Variable Neighborhood Descent; Meta-heurística; Busca Local; Vari able Neighborhood Descent; Programação (Computadores); Processamento eletrônico de dados; Heurística; Otimização matemática; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/7658

Problemas de otimização são de grande importância para diversos setores da indústria, desde o planejamento de produção até escoamento e transporte de produtos. Diversos problemas de interesse se enquadram na classe NP-Difícil, sendo desconhecidos algoritmos para resolvê-los de forma exata em tempo polinomial. Assim, estratégias heurísticas com capacidade de escapar de ótimos locais de baixa qualidade (meta-heurísticas) são geralmente empregadas. A busca local é, em geral, a etapa mais custosa, em termos de tempo computacional, do processo de uma meta-heurística. Desta forma torna-se muito importante fazer bom uso dos recursos nela utilizados. Esta dissertação estuda o emprego de múltiplas estratégias de vizinhança utilizadas paralelamente para explorar um espaço de vizinhança maior e com melhor aproveitamento dos recursos computacionais. O processamento paralelo das estratégias de vizinhança é implementado em nível de grão fino, através de processamento em GPU, e grão grosso, por meio de processamento multi core e processamento em rede, sendo os dois níveis combinados num ambiente heterogêneo, para arquiteturas von Neumann e dataflow.