Use este identificador para citar ou linkar para este item:
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(es): | Oliveira, Francisco Davi Gomes de |
| Orientador: | Soares, Pablo Luiz Braga |
| Palavras-chave em português: | problema do corte máximo;algoritmo genético;configuração de parâmetros |
| Palavras-chave em inglês: | maximum cut problem;genetic algorithm;parameter configuration |
| CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Data do documento: | 2025 |
| Citação: | 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. |
| Resumo: | 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 |
| Tipo de Acesso: | Acesso Aberto |
| Aparece nas coleções: | CIÊNCIA DA COMPUTAÇÃO - RUSSAS - Monografias |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 2025_tcc_fdgoliveira.pdf | 467,31 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.