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

Autori

  • Francisco Davi Gomes de Oliveira
  • Márcio Costa Santos
  • Pablo Luiz Braga Soares

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)”.

Downloads

I dati di download non sono ancora disponibili.

Pubblicato

2023-03-16

Come citare

Oliveira, F. D. G. de, Santos, M. C., & Soares, P. L. B. (2023). Parametrização de um Algoritmo Genético para o Problema do Corte Máximo. Anais Do Encontro De Computação Do Oeste Potiguar ECOP/UFERSA (ISSN 2526-7574), 1(6), 42–45. Recuperato da https://periodicos.ufersa.edu.br/ecop/article/view/11834