Estratégias de paralelização para um algoritmo GRASP multicritério

AUTOR(ES)

Vianna, Dalessandro Soares, Arroyo, José Elias Claudio, Vieira, Pedro Sampaio, Azeredo, Thiago Ribeiro de

FONTE

Production

DATA DE PUBLICAÇÃO

2007-04

RESUMO

Este artigo propõe diferentes estratégias de paralelização de um algoritmo GRASP (Greedy Randomized Adaptive Search Procedure) multicritério. O algoritmo paralelo proposto é aplicado ao problema da árvore geradora mínima multicritério, que é NP-difícil. Neste problema, um vetor de custos é definido para cada aresta do grafo e o objetivo é encontrar as árvores geradoras eficientes (soluções Pareto-ótimas). Cada processo encontra um subconjunto de soluções eficientes. Estes subconjuntos são reunidos usando diferentes estratégias para obter o conjunto final de soluções eficientes. O algoritmo proposto é testado em grafos completos com n = 20, 30 e 50 nós e r = 2 e 3 critérios. Os resultados computacionais mostram que a proposta de se paralelizar o algoritmo reduz o tempo de execução e os resultados obtidos pela versão seqüencial foram melhorados.

ASSUNTO(S)

algoritmo grasp paralelo otimização combinatória multicritério árvore geradora mínima

Documentos Relacionados

• Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético
• Paralelização do algoritmo de migração sísmica em plataformas heterogêneas
• Estratégias de paralelização para renderização de documentos XSL-FO com uso da ferramenta FOP
• Um modelo multicritério para produção de um jornal
• Um modelo multicritério para produção de um jornal