Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/80112| Type: | TCC |
| Title: | Experimentação de parâmetros de um algoritmo genético para o problema do corte máximo |
| Authors: | Oliveira, Francisco Davi Gomes de |
| Advisor: | Soares, Pablo Luiz Braga |
| Keywords in Brazilian Portuguese : | problema do corte máximo;algoritmo genético;configuração de parâmetros |
| Keywords in English : | maximum cut problem;genetic algorithm;parameter configuration |
| Knowledge Areas - CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Issue Date: | 2025 |
| 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. |
| Abstract in Brazilian Portuguese: | 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 |
| Access Rights: | Acesso Aberto |
| Appears in Collections: | CIÊNCIA DA COMPUTAÇÃO - RUSSAS - Monografias |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2025_tcc_fdgoliveira.pdf | 467,31 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.