Título: A Multi-Thread GRASP/VND For The Cluster Editing Problem
Autores: Bastos, L. de O.; Ochi, L. S.; Protti, F.
Resumo: O problema de Edição de Clusters é definido como se segue: dado como entrada um grafo não-direcionado e sem laços G = (V, E), pela adição e/ou remoção de arestas em G, este deve ser transformado num grafo de clusters, isto é , numa união de cliques disjuntas. Foi provado que o problema de Edição de Clusters é NP-Completo. Além disso, o problema modela várias aplicações práticas nas áreas de processamento de imagens, biologia computacional, entre outras. Este trabalho propõe um novo algoritmo GRASP/VND multi-thread para solucionar o problema heuristicamente, enquanto que uma formulação matemática é utilizada para solucionar o problema de forma exata. Além disso, um método para aplicação seletiva de busca local é utilizado para permitir a solução de instâncias muito grandes num tempo computacional razoável. Testes computacionais utilizando instancias da literatura mostraram que o algoritmo proposto encontra as soluções ótimas na grande maioria dos casos e, quando não o faz, obtém soluções muito próximas dos seus respectivos ótimos. Os tempos computacionais, por sua vez, se revelaram pequenos em comparação com os tempos de outros métodos da literatura.
Palavras-chave: Inteligência computacional; metaheuristicas; otimização combinatória; algoritmos paralelos; Edição de Clusters
Páginas: 8
Código DOI: 10.21528/CBIC2011-21.3
Artigo em pdf: st_21.3.pdf
Arquivo BibTex: st_21.3.bib