CCT-UFCA/Ciência da Computação/Inteligência Artificial/Algoritmos Genéticos

Além da Busca Clássica

Por que ir além da busca clássica?

Até agora, estudamos algoritmos que procuram um objetivo e mostram o caminho (ex.: BFS, DFS, A*).

Mas em muitos problemas não precisamos do caminho, apenas da solução final.

Exemplos:

• Problema das 8 rainhas – queremos só a posição final correta das rainhas.
• Escalonamento de tarefas, projeto de circuitos, roteamento de veículos, gestão de carteiras financeiras – o que importa é a configuração final ótima, não o processo passo a passo.

Para isso, usamos buscas locais e algoritmos de otimização.

Busca Local e Otimização

• Considera um estado por vez (não guarda o caminho).
• Move-se apenas para estados vizinhos.
• Usa pouca memória.
• Funciona bem em espaços contínuos ou enormes.

Objetivo

• Encontrar um ótimo global (melhor solução possível).
• O desafio é não ficar preso em ótimos locais (soluções parciais que parecem boas, mas não são as melhores).

Subida da Encosta

• Sempre anda na direção que melhora a solução.
• Para quando não há vizinho melhor.
• Analogia: subir uma montanha no nevoeiro, só vendo os passos ao redor.

Problema: pode parar em:

• Mínimos/Máximos locais → soluções parciais.
• Platôs → áreas planas sem melhora.

Exemplo:

Analogia: Imagine que você está em uma montanha com nevoeiro. Você só consegue ver os arredores imediatos.

• Você dá passos sempre na direção que sobe.

• Para quando não há mais como subir.

Montanha
         /\      ← Ótimo global
        /  \      
       /    \
   /\_/      \     
  /            \
 ↑              \
 Você pode parar aqui (ótimo local)

Problema: pode parar em um pico pequeno achando que é o topo da montanha.

Têmpera Simulada

• Parecida com a subida da encosta, mas aceita vizinhos piores com certa probabilidade.
• Isso ajuda a escapar de mínimos locais.
• A probabilidade de aceitar algo pior diminui com o tempo (analogia com esfriar metal na forja).

Muito usada em otimização industrial (design de chips, logística, etc.).

Exemplo:

Analogia: Forjar um metal → quando está quente, as partículas vibram muito (podem sair de posições ruins), mas conforme esfria, elas se acomodam.

• No início, você aceita dar passos para baixo (descida) de vez em quando → ajuda a escapar de vales locais.

• Conforme o tempo passa (“temperatura cai”), você aceita cada vez menos quedas → converge para o topo certo.

Montanha com buracos
   /\          /\   
  /  \    /\  /  \   
 /    \__/  \/    \  
       ↑
 Aceita cair um pouco
 para depois subir mais

Diferença do Subida da Encosta: às vezes aceita piorar, mas com estratégia.

Busca de Feixe Local

• Mantém k estados simultaneamente.
• Em cada rodada:
  • Gera sucessores de todos.
  • Escolhe os k melhores para continuar.
• Variante: feixe estocástico, que escolhe sucessores com base em probabilidade → mantém diversidade na busca.

Útil para evitar ficar preso em uma única região ruim do espaço de busca.

Exemplo:

Analogia: Vários alpinistas começam a escalar montanhas diferentes.

• A cada rodada, só os que estão nas posições mais altas continuam.
• Variante estocástica: alguns azarões também podem ser escolhidos, para não deixar todos irem pelo mesmo lado.

Vários alpinistas
   /\      /\     /\
  /  \    /  \   /  \   
 ↑    ↑   ↑   ↑
 Cada um explora um caminho

Isso ajuda a explorar várias áreas ao mesmo tempo.

Algoritmos Genéticos (AG)

Inspirados na evolução natural.

• Mantêm uma população de estados (indivíduos).
• Cada indivíduo tem um valor de adaptação (fitness).
• Novas gerações são criadas por:
  • Seleção → escolhe os melhores para serem pais.
  • Crossover → combina pedaços de dois pais para gerar filhos.
  • Mutação → altera aleatoriamente alguns valores para manter diversidade.

Exemplo:

Analogia: Evolução natural.

• Cada solução é como um indivíduo (DNA = configuração).
• A cada geração:
  • Seleção → os mais fortes sobrevivem.
  • Crossover → dois indivíduos se combinam.
  • Mutação → mudanças aleatórias garantem diversidade.

Pais:   [101010] + [111000] 
Cruzam → [101000] (filho)  
Mutação → [101100] (filho mutante)

Com o tempo, a população melhora até surgir a solução ótima.

Comparação das Estratégias

Algoritmo	Vantagens	Limitações
Subida da Encosta	Simples, rápido	Pode ficar preso em mínimos locais
Têmpera Simulada	Escapa de mínimos locais	Mais lenta, depende do ajuste da “temperatura”
Feixe Local	Considera vários estados	Pode perder diversidade sem variante estocástica
Algoritmos Genéticos	Muito flexível, inspirado na natureza	Mais complexos, dependem de ajustes finos

Conclusão

• Esses algoritmos não buscam o caminho, mas sim a solução final ótima.
• São ideais para problemas de otimização complexa, comuns na vida real.

• Mostram como a IA pode aprender, explorar e combinar soluções de forma criativa.

Referências

1. RUSSELL, S. J.; NORVIG, P. Inteligência artificial. 3 ed. LTC, 2013. 1016 p.
2. COPPIN, B. Inteligência Artificial. 1a ed. LTC, 2010. 664 p.