Algoritmos e Estrutura de Dados · IF-MG · 2024 | Questão sqc-qg240149

Algoritmos Genéticos – Evitando Convergência Prematura

Gabarito: letra E. Aumentar a taxa de mutação é a ação mais direta para incrementar a diversidade populacional e evitar que o algoritmo genético convirja rapidamente para uma solução subótima. A mutação insere variação aleatória nos indivíduos, permitindo que o espaço de busca seja explorado além das regiões já dominadas pelos operadores de seleção e cruzamento.

Em algoritmos genéticos, a convergência prematura ocorre quando a perda de diversidade genética impede a fuga de ótimos locais. Nesse cenário, as soluções tornam-se muito semelhantes entre si, e o algoritmo estagna. A mutação é o principal mecanismo para reintroduzir material genético perdido e garantir a exploração contínua do espaço de soluções.

Convergência prematura

1Causa
- Perda de diversidade genética
- Soluções muito semelhantes
- Estagnação em ótimo local
2Solução principal
- Aumentar taxa de mutação
  - Insere variação aleatória
  - Reintroduz material genético perdido
  - Permite explorar novas regiões
3Outras ações (menos eficazes)
- Aumentar população
  - Custo computacional maior
  - Efeito indireto na diversidade
- Alterar alelos/indivíduo
  - Modifica espaço de busca
  - Não garante exploração
- Criar parâmetro heurístico
  - Vago e não padronizado
- Modificar codificação
  - Não resolve falta de variação

LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Aumentar o número de indivíduos (tamanho da população) pode, em tese, ampliar a diversidade inicial, mas não atua diretamente sobre o problema descrito. Populações maiores aumentam o custo computacional e, sem um mecanismo que force a variação, ainda podem convergir para a mesma região subótima. O efeito é indireto e menos eficaz que o aumento da mutação.

Alternativa B — ❌ Incorreta

O número de alelos por indivíduo está relacionado à codificação do indivíduo (quantos bits ou variáveis compõem cada cromossomo). Alterar esse número não tem impacto direto na diversidade da população; modifica o espaço de busca, mas não garante que o algoritmo explore melhor as regiões já mapeadas. A questão não indica que a codificação seja inadequada, apenas que o algoritmo converge para um mesmo ponto subótimo.

Alternativa C — ❌ Incorreta

Criar um novo parâmetro heurístico é uma ação vaga e não padronizada. Heurísticas podem guiar a busca, mas não são o recurso primário para evitar convergência prematura em algoritmos genéticos. A mutação é um operador consagrado e específico para esse fim.

Alternativa D — ❌ Incorreta

Modificar a codificação dos genes altera a representação dos indivíduos, mas não resolve o problema de diversidade. A codificação pode ser mais ou menos adequada ao problema, mas o sintoma (convergência prematura) indica falta de variação, não de representação. A mutação atua diretamente sobre a diversidade independentemente da codificação.

Alternativa E — ✅ Correta ⟵ GABARITO

O aumento da taxa de mutação é a técnica clássica para combater a convergência prematura. A mutação aplica pequenas alterações aleatórias aos genes, impedindo que a população se estabilize em torno de um único ótimo local. Com uma taxa mais elevada, cada geração terá indivíduos geneticamente mais diversos, aumentando a exploração do espaço de busca e a chance de encontrar soluções globais melhores.

PEGA ESSA DICA!

Em problemas de seleção de features, a convergência prematura é comum devido à alta correlação entre atributos. Lembre-se de que a taxa de mutação é o primeiro parâmetro a ajustar quando o algoritmo estagna. Uma regra prática é iniciar com taxa entre 0,01 e 0,1 e aumentá-la gradualmente até que a diversidade seja mantida ao longo das gerações.

Gabarito: letra E