Artigos
Análise Comparativa de Estratégias de Controle Populacional em Algoritmos Genéticos Aplicados ao Problema das N-Rainhas
Artigo de TCC que compara substituição total, substituição parcial, elitismo e controle por idade, com o mesmo orçamento de avaliações da função de aptidão no problema das N-Rainhas.
Esta página apresenta o artigo de TCC de Vinícius Rubin e Igor Yepes, do Instituto Federal Farroupilha — Campus Frederico Westphalen. O texto científico completo está disponível em português.
Ler o artigo completo em PDF · Acessar o repositório e os fontes LaTeX
O problema e o objetivo
O problema das N-Rainhas consiste em posicionar N rainhas em um tabuleiro N × N sem que elas se ataquem. O trabalho investiga como diferentes políticas de preservação e substituição de indivíduos afetam a convergência, a qualidade das soluções e o custo computacional de algoritmos genéticos aplicados a esse problema.
A representação por permutação elimina conflitos em linhas e colunas. A função de aptidão avalia os conflitos diagonais, buscando uma configuração sem ataques.
Estratégias comparadas
| Estratégia | Política de controle populacional |
|---|---|
| Substituição total | Renovação de toda a população a cada geração. |
| Substituição parcial | Substituição de 25% da população. |
| Elitismo | Preservação dos 10% melhores indivíduos. |
| Controle por idade | Renovação por tempo de vida, inspirada no GAVaPS, com população variável. |
Protocolo experimental
Para comparar as políticas, o estudo mantém os operadores genéticos constantes e adota o mesmo orçamento de avaliações da função de aptidão:
- População inicial de 100 indivíduos.
- Seleção por torneio binário e cruzamento OX.
- Mutação por troca com taxa de 10%.
- 100 execuções independentes por configuração.
- Encerramento ao encontrar uma solução válida ou atingir 2 × P × N avaliações, em que P é o tamanho da população inicial e N é o número de rainhas.
A análise considera taxa de sucesso, qualidade das soluções, avaliações consumidas, gerações e tempo de execução. A ferramenta experimental é descrita no artigo como uma implementação em Python com NumPy, Numba e Matplotlib.
Principais resultados
Nas condições avaliadas, o controle por idade apresentou bom equilíbrio entre qualidade e eficiência em instâncias intermediárias. O elitismo se destacou em instâncias maiores, com maior custo de tempo. As estratégias de substituição total e parcial perderam desempenho conforme o tamanho do problema aumentou.
Esses resultados mostram a importância da política de renovação da população na dinâmica da busca evolutiva. Os gráficos e a discussão completa estão no PDF original.
Materiais disponíveis e limitações
O repositório reúne o PDF do artigo, os fontes LaTeX, a bibliografia em BibTeX e os gráficos. O código dos experimentos, as sementes e os dados brutos não estão incluídos; compilar o documento reconstrói o artigo, mas não reproduz os experimentos.
As conclusões se referem ao problema e aos parâmetros estudados. O trabalho aponta como limitações o uso de um único problema, os parâmetros fixos e a ausência de análises estatísticas formais aprofundadas.
Artigo original
Título: Análise Comparativa de Estratégias de Controle Populacional em Algoritmos Genéticos Aplicados ao Problema das N-Rainhas.
Autores: Vinícius Rubin e Igor Yepes.
Instituição: Instituto Federal Farroupilha — Campus Frederico Westphalen.
Consultar o PDF original e os materiais do trabalho no GitHub.
A data exibida nesta página corresponde à inclusão no site, em 14 de outubro de 2026.