Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/80112| Tipo: | TCC |
| Título : | Experimentação de parâmetros de um algoritmo genético para o problema do corte máximo |
| Autor : | Oliveira, Francisco Davi Gomes de |
| Tutor: | Soares, Pablo Luiz Braga |
| Palabras clave en portugués brasileño: | problema do corte máximo;algoritmo genético;configuração de parâmetros |
| Palabras clave en inglés: | maximum cut problem;genetic algorithm;parameter configuration |
| Áreas de Conocimiento - CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Fecha de publicación : | 2025 |
| Citación : | 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. |
| Resumen en portugués brasileño: | 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)” |
| 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)”. |
| URI : | http://repositorio.ufc.br/handle/riufc/80112 |
| Derechos de acceso: | Acesso Aberto |
| 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 |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.