Revisão I – AP1
Prof. Alexandre Monteiro
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Inteligência Artificial
O que é inteligência Artificial?
O que diferencia inteligência artificial de
inteligência natural?
3
Paradigmas da IA

Simbólico: metáfora lingüística/lógica
• Sistemas de produção

Conexionista: metáfora cérebro
• Redes neurais

Evolucionista: metáfora teoria da evolução natural
• Algoritmos genéticos

Probabilista: probabilidade
• Redes bayesianas

IA Distribuída: metáfora social
• Sistemas multiagentes
4
O que é um agente

Agente é qualquer entidade que:?
• percebe seu ambiente através de sensores (ex.
câmeras, microfone, teclado, finger...)
• age sobre ele através de atuadores (ex. vídeo, autofalante, impressora, braços, ftp, ...)
Mapeamento: seqüência de percepções => ação
ambiente

Agente
sensores
?
Raciocinador
atuadores
modelo do
ambiente
6
Propriedades de Ambientes de Tarefas

Classes de ambientes
• Físico: robôs
• Software: softbots
• Realidade virtual (simulação do ambiente físico): softbots e avatares

Propriedades de um ambiente
• Acessível (completamente observável) x inacessível (parcialmente observável
• Estático (não muda) x dinâmico (muda) – semidinâmico (ações)
• Determinista (conhece próximo estado) x estocástico (ñ-determinista)
• Discreto x contínuo
• Episódico (só depende das ações anteriores) x não-episódico (seqüêncial)
• tamanho: número de percepções, ações, objetivos,...
• Discreto (xadrez) x contínuo (dirigir táxi)
• Agente único x multiagente
7
Algoritmo Básico

Função agenteSimples (percept) retorna ação
memória := atualizaMemória (memória, percept)
ação := escolheMelhorAção(memória)
memória := atualizaMemória (memória, ação)
retorna ação

Arquiteturas
• Agente tabela
• Agente reativo simples
• Agente reativo baseado em modelos
• Agente baseado em objetivos
• Agente baseado em utilidade
• Agente com aprendizagem
autonomia
complexidade
Um problema de busca em IA pode ser
definido em termos de...
1. um estado inicial
- Em (Recife)
- Estar (pobre)
2. um ou mais estados finais => definição do objetivo
- Em (João Pessoa)
- Estar (rico)
3. Espaço de Estados:
- conjunto de todos os estados alcançáveis a partir do estado inicial por
qualquer seqüência de ações.
- pode ser representado como uma árvore onde os estados são nós e as
operações são arcos.
4. Solução:
- caminho (seqüência de ações ou operadores) que leva do estado inicial
a um estado final (objetivo), passando de um estado para outro
• Ex., dirigir de Recife a João Pessoa
- Espaço de estados: todas as cidades da região de Recife a João Pessoa
8
9
Métodos de Busca

Busca exaustiva (sem informação ou cega)
• Não sabe qual o melhor nó da fronteira a ser
expandido = menor custo de caminho desse nó até
um nó final (objetivo).

Busca heurística (com informação)
• Estima qual o melhor nó da fronteira a ser
expandido com base em
funções heurísticas => conhecimento
Busca Cega

Estratégias para determinar a ordem de ramificação dos nós:
1. Busca em largura/extensão
2. Busca de custo uniforme
3. Busca em profundidade
4. Busca com aprofundamento iterativo (retrocesso)

Direção da ramificação:
1. Do estado inicial para um estado final
2. De um estado final para o estado inicial
3. Busca bi-direcional
11
Busca pela Melhor Escolha (BME)
Best-First Search


Busca genérica onde o nó de menor custo “aparente” na fronteira
do espaço de estados é expandido primeiro
Duas abordagens básicas:
1. Busca Gulosa (Greedy search)
2. Algoritmo A* e suas variantes

Algoritmo:
Função-Insere - ordena nós com base na Função-Avaliação
função Busca-Melhor-Escolha (problema,Função-Avaliação)
retorna uma solução
Busca-Genérica (problema, Função-Insere)
Algoritmos de Melhorias Iterativas

Dois exemplos clássicos
•Subida da encosta (Hill-Climbing)
•Têmpera simulada (Simulated Annealing)
12
Algoritmo BT




Começando com uma solução inicial s0, a cada iteração,
Um subconjunto V da vizinhança N(s) da solução corrente s
é explorado
O membro s0 de V com melhor valor nesta região segundo a
função f(:) torna-se a nova solução corrente
mesmo que s0 seja pior que s.
Evitando Ciclos



existe uma lista tabu T, a qual é uma lista de
movimentos proibidos.
A lista tabu clássica contém os movimentos reversos
aos últimos |T| movimentos realizados
|T| funciona como uma fila de tamanho fixo,
• isto é, quando um novo movimento é adicionado à lista, o
mais antigo sai.

Assim, na exploração do subconjunto V da vizinhança
N(s) da solução corrente s, ficam excluídos da busca os
vizinhos s0 que são obtidos de s por movimentos m que
constam na lista tabu
Introdução

Principal motivação para o estudo da computação evolutiva
através de algoritmos genéticos é:
•Otimização de processos complexo e que
possuem um grande número de variáveis

O que é otimizar?
15
Algoritmos Genéticos

Funcionamento:
GERAÇÕES
População inicial
População final
Avaliação
População atual
Seleção
Reprodução
16
Reprodução

Permite obtenção de novos indivíduos

Utiliza operadores genéticos
•Transformam a população
- Crossover (cruzamento ou recombinação)
- Mutação
17
Crossover

Diversas variações
•Um ponto
- Mais comum
•Dois pontos
•Multi-pontos
•Uniforme
18