Pesquisa em Contextos Competitivos e Otimização
1. Pesquisa em Contextos Competitivos
Os contextos competitivos envolvem jogos e cenários onde agentes enfrentam adversários ou lidam com incertezas no ambiente. Aqui, a pesquisa é categorizada em jogos determinísticos e estocásticos.
1.1 Jogos Determinísticos vs. Estocásticos
- Jogos Determinísticos:
- Não incluem elementos de aleatoriedade.
- Exemplo: Xadrez, damas.
- Jogos Estocásticos:
- Contêm incertezas devido a fatores aleatórios, como lançamentos de dados ou cartas.
- Exemplo: Gamão, póquer.
1.2 Jogos Estocásticos
- Informação Perfeita (Algoritmo Expectiminimax):
- Todos os jogadores conhecem completamente o estado do jogo.
- O algoritmo Expectiminimax combina decisões determinísticas e expectativas probabilísticas, avaliando nós "de sorte" para incluir fatores aleatórios.
- Exemplo: Gamão.
- Informação Imperfeita (Algoritmo Miniminimax e Teoria dos Jogos):
- Os jogadores têm conhecimento parcial do estado do jogo.
- Miniminimax: Adaptação do minimax que inclui incertezas.
- Teoria dos Jogos: Modelo matemático para interações estratégicas entre agentes racionais, utilizando conceitos como equilíbrios de Nash.
- Exemplo: Póquer.
2. Procura Local e Problemas de Otimização
A procura em IA pode ser vista como um processo de exploração em busca de soluções ótimas ou satisfatórias dentro de um espaço de estados.
2.1 Procura vs. Otimização
- Procura: Envolve encontrar uma solução que satisfaça os critérios definidos, independentemente de ser a melhor possível.
- Otimização: Visa encontrar a melhor solução dentro de um conjunto definido, minimizando ou maximizando uma função objetivo.
- Exemplo: Planeamento de rotas (procura vs. rota mais rápida ou económica).
2.2 Exploration vs. Exploitation
- Exploration: Explorar novas áreas do espaço de busca para evitar soluções locais.
- Exploitation: Focar-se em áreas promissoras para refinar a solução atual.
- Desafio: Encontrar o equilíbrio entre explorar e explorar para maximizar a eficácia da pesquisa.
2.3 Meta-heurísticas
- Estratégias gerais que orientam a pesquisa de soluções em problemas complexos, combinando exploração e exploração.
- Exemplos: Algoritmos genéticos, otimização por colónias de formigas.
2.4 Procura Local vs. Procura Global
- Procura Local:
- Inicia de uma solução e procura melhorar continuamente, explorando estados vizinhos.
- Risco: Ficar preso em ótimos locais.
- Procura Global:
- Explora o espaço completo, tentando encontrar o ótimo global, frequentemente mais dispendioso em termos computacionais.
2.5 Solução Única vs. Population-Based
- Solução Única: Trabalha com uma única solução que é refinada ao longo do tempo.
- Population-Based: Gera e mantém uma população de soluções, promovendo diversidade e permitindo cruzamento de ideias.
3. Algoritmos de Solução Única
Algoritmos baseados em procura local, eficientes para problemas de otimização complexos.
3.1 Procura Subida da Colina (Hill-Climbing Search)
- Descrição:
- Parte de uma solução inicial e move-se para estados vizinhos que melhoram a solução.
- Risco: Preso em máximos locais.
- Variações:
- Stochastic Hill-Climbing: Escolhe movimentos aleatórios entre vizinhos.
- First-Choice Hill-Climbing: Explora vizinhos até encontrar a primeira melhoria.
3.2 Arrefecimento Simulado (Simulated Annealing)
- Descrição:
- Inspira-se no processo de arrefecimento dos metais.
- Permite movimentos para estados piores ocasionalmente, diminuindo a probabilidade ao longo do tempo, evitando ótimos locais.
- Vantagem: Maior probabilidade de encontrar o ótimo global em comparação com a subida da colina simples.
3.3 Procura Tabu (Tabu Search)
- Descrição:
- Baseia-se na subida da colina, mas mantém uma lista tabu que evita revisitar estados recentes.
- Permite explorar além de ótimos locais, aliviando problemas de ciclos.
4. Procura em Contexto de Ações Não Determinísticas
Em ambientes onde as ações não têm resultados garantidos, a procura deve considerar múltiplos cenários e planeamento contingente.
- Abordagens:
- Planeamento Contingente: Explora caminhos alternativos com base em possíveis resultados.
- Estratégias Expectativas: Integra probabilidades nos cálculos, semelhante ao expectiminimax.
- Exemplo: Navegação de robôs em terrenos imprevisíveis ou planeamento em condições meteorológicas variáveis.
Considerações Finais
A escolha entre algoritmos e estratégias depende da natureza do problema e das características do ambiente.
- Problemas Determinísticos: Beneficiam de algoritmos focados, como subida da colina ou minimax.
- Ambientes Estocásticos: Exigem métodos mais flexíveis, como arrefecimento simulado ou estratégias baseadas em probabilidades.
- Ambientes Não Determinísticos: Exigem planeamento robusto e adaptável.