Título: Algoritmo Genético para a Árvore Geradora Generalizada de Custo Mínimo.

Data: 26/07/2017 Horário: 09:00h Local: Sala de Seminários - Bloco 952 - Pici

Resumo:

Dado um grafo m-partido G = (V, E), onde V e E correspondem respectivamente ao seu conjunto de vértices e arestas, cujo conjunto de vértices é dividido em m clusters, o problema da árvore geradora generalizada de custo mínimo consiste em encontrar uma árvore de custo mínimo contendo m - 1 arestas e um vértice de cada cluster. Este problema encontra aplicações em redes de telecomunicações, smart-cities, entre outros. Propomos um Algoritmo Genético (AG) contendo múltiplas populações independentes e um operador de cruzamento diferente dos já empregados em outros AGs para o GMSTP. Além disso, threads são utilizadas para acelerar o processo de cálculo do custo das soluções geradas durante a execução do AG. Experimentos computacionais foram realizados para testar o seu desempenho, incluindo uma comparação com os resultados de uma formulação matemática da literatura. O AG proposto é capaz de encontrar soluções ótimas para várias instâncias e supera os melhores resultados heurísticos presentes na literatura em 12 instâncias.

Banca:

• Prof. Dr. Rafael Castro de Andrade (MDCC/UFC) - Orientador
• Prof. Dr.ª Andréa Cynthia Santos Duhamel (UTT) - Coorientadora
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC)
• Prof. Dr. Christophe Duhamel (UBP)