Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Resolução de Problemas
Agente
Problema
Solução
Ambiente
Problema --> Modelo --> Solução
Problema --> Modeloap --> Soluçãoex(Modeloap)
Problema --> Modeloex --> Soluçãoap(Modeloex)
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Procura num Espaço de Soluções Candidatas
N - Rainhas
Estados S
- soluções candidatas
- completas ou não
Função de Avaliação F: S -> R
- número de ataques
Operadores O: S -> S
- move_rainha
- coloca_rainha
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Espaço de Estados
- conjunto de soluções candidatas
- viáveis, não viáveis
move_rainha
Procurar uma solução navegando no espaço
das soluões candidatas.
- partindo de uma solução
- partindo de várias
Problemas Complexos
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
SAT (Boolean SATisfiability Problem)
Tarefa: em que condições uma expressão
booleana contendo variáveis tem o valor
de verdade TRUE.
entrada: F(x)  (x17  x 37  x 73)  ... (x 2  x 97 )
saida: (xi )  TRUE,FALSE : F (x)  TRUE
Dimensão do Espaço de Procura
S  2 n  2100  10 30
Função de Avaliação
complicado quando a maior parte das vezes
uma solução candidata dá o valor False
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
TSP (Traveling Salesman Problem)
Tarefa: um vendedor tem quer percorrer um
conjunto de cidades, uma e uma vez só, regressando
à cidade de partida, minimizando a distância
percorrida
entrada: ci - cidades,
dist(ci,cj) distância entre cidades
saida: uma sequência de cidades, que responda
ao objectivo de minimização
(uma permutação)
Dimensão do Espaço de Procura
S
n!
(n 1)!

2* n
2
Função de Avaliação
f (s)   dist(ci ,c j )
Restrições: visitar uma só vez as cidades
- soluções inviáveis --> operadores especiais
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
NLP (Non Linear Programming)
Tarefa: Dada uma função encontrar o seu
mínimo (global).
n
4 (x )  2 n cos 2 (x )
cos
i1
i1
i
i
entrada: G2(x) 
n
i * xi2
i1
restrições:
saida:
n
i1 xi  0.75
n
 xi  7.5 * n, 0  xi  10,1  i  n
i1
x : y, y  x  G2(x)  G 2(y)
Dimensão do Espaço de Procura
n dimensões, precisão com 6 casas decimais
S  10 7n
Função de Avaliação
G2(x)
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
O que torna um problema complexo?
tarefa
- dimensão do espaço de procrura
- função de avaliação
- restrições
ambiente
- ruido
- dinâmico
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Métodos Globais vs. Locais
(exploration vs. exploitation)
Procura na vizinhança (local)
N
x
S
Definição da vizinhança N (métricas)
 (xi  y i ) 2
euclidiana
dist(x, y) 
hamming
dist(x, y)   xi  yi
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Trepa Colinas (Hill Climbing)
uma solução, heurístico, melhoria progressiva, local
programa trepa_colinas;
t <-- 0;
inicializa o melhor (best)
repete
local <-- FALSE
seleciona aleatóriamente um estado vc
avalia vc
repete
seleciona todos os (novos) estados na vizinhança de vc
seleciona o melhor de entre os vizinhos, vn
se vn é melhor do que vc
então vc <-- vn
senão local <-- TRUE fim se
até local ser TRUE
t <-- t+1
se vc é melhor do que best
então best <-- vc fim se
até t ser igual a MAX
fim programa
o problema dos máximos locais!
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
A*
uma solução, heurístico, o melhor primeiro, Global
programa A* (v)
visitar v
para cada w disponível fazer
avaliar w
fim fazer
q <-- o melhor estado disponível
A*(q)
fim programa
Estados disponíveis: cuja existência é conhecida
mas ainda não testados
Avaliar
Ei
f(w)=g(w)+h(w)
h - heurística
admissível
©2001, Ernesto Costa
Ef
g(w)= custo até w
w
h(w)= custo estimado
até Ef
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Recristalização Simulada (Simulated Annealing)
uma solução, heurístico, melhoria progressiva, local
Pode, probabilisticamente, ser escolhido um vizinho
de valor inferior. A probabilidade é controlada por
um parâmetro T (temperatura)
programa recristalização_simulada
t <-- 0
inicializa T
seleciona aleatóriamente um estado vc
avalia vc
repete
repete
seleciona um novo estado vn ,
na vizinhança de vc
se vn é melhor do que vc
então vc <-- vn
senão
se random[0,1) < e eval(vn)- eval(vc)/T
então vc <-- vn fim se
fim se
até condição de fim
T <-- g(T,t)
t <-- t+1
até critério de paragem
fim programa
©2001, Ernesto Costa
fuga aos máximos
locais
combina exploration
(no início), com
exploitation (no fim)
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Procura Tabu (Tabu Search)
uma solução, heurístico, melhoria progressiva, local
usa uma memória (de curto termo) para forçar o
algoritmo a explorar novas áreas. Pode selecionar
um estado de valor inferior ao corrente!
programa procura_tabu;
tentativas <-- 0;
repete
gera um estado vc
contador <-- 0
repete
seleciona todos os (novos) estados na vizinhança de vc
seleciona o melhor admissível de entre os vizinhos, vn
actualiza a memória tabu
se vn é o melhor nesta tentativa
então actualiza vc
fim se
contador <-- contador +1
até contador igual a número de OPERAÇÕES
tentativas <-- tentativas+1
se vc é o melhor de todas as tentativas
então actualiza o melhor global fim se
até tentativas ser igual a um valor MÁXIMO
fim programa
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Algoritmos Genéticos
procura adaptativa global relativamente a
uma função objectivo, de inspiração
biológica
A metáfora Biológica
• Evolução via Selecção Natural (Darwin)
- sobrevivem os mais aptos (fittest )
• Operadores Genéticos (Mendel)
- recombinação (crossover )
- mutação (mutation )
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Conceitos
• população
• indivíduo
• cromossoma
• gene
• alelo
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Funcionamento
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
programa GA(fa,pr,pm,cp)
% fa, função de adaptabilidade
% pr, probabilidade de recombinação
% pm, probabilidade de mutação, pm
% cp, critério de paragem
1. Definir aleatoriamente e avaliar a população
inicial, p0
2. Enquanto
não existir um indivíduo em pi que satisfaz cp
• Selecciona indivíduos de pi de acordo
com fa
• Recombina os indivíduos de acordo
com pr
• Muta os indivíduos de acordo com pm
• Define e avalia nova população p i+1
3. Devolve o melhor individuo da população final
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Recombinação (crossingover)
• um ponto
11101001000
11101010101
00001010101
00001001000
• dois pontos
11101001000
11001011000
00001010101
00101000101
• uniforme
11101001000
10001000100
00001010101
01101011001
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Mutação
• mutação aleatória
- mudança de um gene num cromossoma
• mutação por troca
- dois genes do mesmo cromossoma trocam os
respectivos valores
©2001, Ernesto Costa
Elementos de Inteligência Artificial
RESOLUÇÃO DE PROBLEMAS E PROCURA
Selecção
• proporcional à adaptabilidade (roleta)
fa(hi)
prob(hi)  p
 fa( j)
j 1
- problema da convergência prematura
• por número de ordem (rank)
- reduz a convergência prematura
- importância dos menos aptos
• elistista
- um número fixo dos melhores passa sempre
- limita o “poder destruidor” dos ops. genéticos
©2001, Ernesto Costa