Parametrização de um Algoritmo Genético para o Problema do Corte Máximo

Abstract

Este trabalho tem como finalidade a busca por boas soluções para o problema do corte máximo (Max-Cut) em um grafo, através da utilização de uma metaheurística baseada em algoritmo genético que por sua vez é inspirada no princípio teórico da evolução natural proposto por Charles Darwin. A ideia principal consiste na busca por uma configuração de parâmetros de refinamento do algoritmo genético que venha a apresentar bons resultados nas instâncias da literatura. O algoritmo genético foi implementado em linguagem C sendo centralizado em fornecer a otimização ao problema do corte máximo para grafos. Após a implementação do algoritmo, foram testadas 36 configurações diferentes de parâmetros de ajuste do algoritmo. Foram obtidos bons resultados, com o prevalecimento da seguinte configuração: “Com ilha, Mutação em 1 gene, Crossover que prevalece a igualdade entre os genes, e busca local a partir de 5 gerações sem convergências do melhor resultado(CIM1I5)”.