Algoritmos evolutivos para o problema de clusterização de grafos orientados: desenvolvimento e análise experimental

Abstract

Neste trabalho são apresentadas propostas para aperfeiçoamento de algoritmos genéticos (AGs). Para isto, um algoritmo genético tradicional (AGT), encontrado na literatura para a solução do problema de clusterização automática de vértices de um grafo orientado não ponderado, é utilizado como base para as adaptações propostas. As propostas de aperfeiçoamento do AGT correspondem à realização de alterações em alguns dos seus parâmetros e à inserção de novos procedimentos ao algoritmo. Para cada proposta são apresentados os resultados experimentais obtidos a partir da sua implementação e execução, utilizando grafos orientados, não ponderados, contendo diferentes quantidades de vértices e arcos. São realizados experimentos computacionais, utilizando as propostas de forma individual ou através de combinações entre elas. Os resultados mostram que os algoritmos aqui propostos melhoram consideravelmente o desempenho do AGT em relação à qualidade das soluções obtidas, exigindo, em média, tempos computacionais similares, ou menores, que os do algoritmo da literatura