Experimentação de parâmetros de um algoritmo genético para o problema do corte máximo

Oliveira, Francisco Davi Gomes de

Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.ufc.br/handle/riufc/80112

Registro completo de metadatos

Campo DC	Valor	Lengua/Idioma
dc.contributor.advisor	Soares, Pablo Luiz Braga	-
dc.contributor.author	Oliveira, Francisco Davi Gomes de	-
dc.date.accessioned	2025-03-20T20:25:37Z	-
dc.date.available	2025-03-20T20:25:37Z	-
dc.date.issued	2025	-
dc.identifier.citation	OLIVEIRA, Francisco Davi Gomes de. Experimentação de parâmetros de um algoritmo genético para o problema do corte máximo. 2025. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) - Campus de Russas, Universidade Federal do Ceará, Russas, 2025.	pt_BR
dc.identifier.uri	http://repositorio.ufc.br/handle/riufc/80112	-
dc.description.abstract	This work aims to search for good solutions to the problem of maximum cut (Max-Cut) in a graph, through the use of a metaheuristic based on a genetic algorithm which, in turn, is inspired by the theoretical principle of natural evolution proposed by Charles Darwin. The main idea consists of searching for a configuration of parameters for refining the genetic algorithm that will present good results in the literature. The genetic algorithm was implemented in Python language, focusing on providing optimization to the maximum cut problem for graphs. After implementing the algorithm, 54 different configurations of algorithm tuning parameters were tested. Good results were obtained, with the following configuration prevailing: “No island, Mutation in 1 gene, Crossover that prevails equality between genes and local search from 20 generations without convergence of the best result (SIM1PIBL20)”.	pt_BR
dc.language.iso	pt_BR	pt_BR
dc.rights	Acesso Aberto	pt_BR
dc.title	Experimentação de parâmetros de um algoritmo genético para o problema do corte máximo	pt_BR
dc.type	TCC	pt_BR
dc.description.abstract-ptbr	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 Python, sendo centralizado em fornecer a otimização ao problema do corte máximo para grafos. Após a implementação do algoritmo, foram testadas 54 configurações diferentes de parâmetros de ajuste do algoritmo. Foram obtidos bons resultados, com o prevalecimento da seguinte configuração: “Sem ilha, Mutação em 1 gene, Crossover que prevalece a igualdade entre os genes e busca local a partir de 20 gerações sem convergências do melhor resultado(SIM1PIBL20)”	pt_BR
dc.subject.ptbr	problema do corte máximo	pt_BR
dc.subject.ptbr	algoritmo genético	pt_BR
dc.subject.ptbr	configuração de parâmetros	pt_BR
dc.subject.en	maximum cut problem	pt_BR
dc.subject.en	genetic algorithm	pt_BR
dc.subject.en	parameter configuration	pt_BR
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO	pt_BR
Aparece en las colecciones:	CIÊNCIA DA COMPUTAÇÃO - RUSSAS - Monografias

Ficheros en este ítem:

Fichero	Descripción	Tamaño	Formato
2025_tcc_fdgoliveira.pdf		467,31 kB	Adobe PDF	Visualizar/Abrir

Mostrar el registro sencillo del ítem