Prof. Aurora T. R. Pozo Departamento de Informática Universidade Federal do Paraná ...
44
Tópicos em Inteligência Artificial – opt. CI309A http://www.inf.ufpr.br/aurora/disciplinas/topicosia2/topicosia2.htm Prof. Aurora T. R. Pozo Departamento de Informática Universidade Federal do Paraná www.inf.ufpr.br/aurora [email protected]
Prof. Aurora T. R. Pozo Departamento de Informática Universidade Federal do Paraná [email protected]
Prof. Aurora T. R. Pozo Departamento de Informtica Universidade
Federal do Paran www.inf.ufpr.br/aurora [email protected]
Slide 2
OTIMIZAO OTIMIZAO uma rea ubqua. Ela est presente em processos
de tomada de deciso e na anlise de sistemas fsicos, de modo que ela
est presente em praticamente todas as reas do conhecimento, da
engenharia a cincia e da economia a cincias sociais. Otimizao uma
atividade inerente ao ser humano. Investidores, por exemplo, buscam
criar portflios que evitem riscos excessivos enquanto alcanam uma
alta taxa de retorno. Industriais, por sua vez, desejam maximizar a
ecincia de seus processos de produo. Alm disso, a natureza segue
princpios de otimizao. Sistemas fsicos tendem para um estado de
mnima energia. As molculas em um sistema qumico isolado, por
exemplo, reagem umas com as outras at que a energia potencial dos
seus eltrons seja minimizada. Raios de luz viajam entre dois pontos
no menor tempo possvel (principio de Fermat).
Slide 3
Agentes baseado em Objetivos Otimizaao ubiqua
Slide 4
Metaheursticas Otimizao Estocstica uma classe de algoritmos e
tcnicas que utilizam algum grau de aleatoriedade para encontrar um
timo (o mais perto do timo) para problemas difceis. Essentials of
Metaheuristics (Sean Luke)
Slide 5
Metaheursticas Iterativamente melhorar um conjunto de solues
Pouco conhecimento do problema Precisa poder distinguir boas solues
Geralmente encontra boas solues possivelmente no o timo Adaptveis :
parmetros ajustveis
Slide 6
Slide 7
Slide 8
Otimizao S Sujeito a restries
Slide 9
Otimizao Baseada em Gradiente Mtodo matemtico clssico
Slide 10
Slide 11
Conhecer a funo que se otimiza Conhecer suas derivadas
Slide 12
Metaheursticas Inteligncia e Resoluo de Problemas Mtodos de
BUSCA Enxergam o problema a ser resolvido como um conjunto de
informaes a partir das quais algo dever ser extrado ou inferido; O
processo de soluo corresponde a uma seqncia de aes que levam a um
desempenho desejado ou melhoram o desempenho relativo de solues
candidatas; Este processo de procura por um desempenho desejado
denominado busca.
Slide 13
Quando Utilizar estas tcnicas Quase que invariavelmente, as
tcnicas de inteligncia computacional (IC) so tcnicas alternativas;
Isso indica que existem outras maneiras para se resolver um mesmo
problema ou sintetizar um dado fenmeno; preciso avaliar com cuidado
se h ou no a necessidade de aplicao de tcnicas de IC a um dado
problema.
Slide 14
Metaheuristicas Algoritmos usados em problemas nos quais existe
pouca informao : no se conhece a forma de uma soluo tima, No se
sabe como encontrar ela Uma explorao completa e impossvel devido ao
tamanho do espao Porem se voc tem uma soluo candidata, ela pode ser
avaliada
Slide 15
A IC pode ser usada quando: O problema a ser resolvido complexo
(grande nmero de variveis, grande quantidade de possveis solues,
etc.); No possvel garantir que uma soluo encontrada tima, mas
possvel criar mtricas de comparao entre solues candidatas; O
problema a ser resolvido no pode ser (apropriadamente) modelado. Em
alguns casos, pode-se empregar exemplos para ensinar o sistema a
resolver o problema;
Slide 16
Informaes Qualidade de uma Soluo Porem no se conhece a
superfcie da funo Qualquer tipo de representao da soluo Espao real,
inteiro, um grafo 2 espaos soluo e funo.
Slide 17
Problema de Santa Fe
Slide 18
Como Enfrentar Ter uma ou mais solues candidatas iniciais.
Procedimento de Inicializao Avaliao de uma soluo candidata
Procedimento de Avaliao Realizar uma copia da soluo candidata
Construir uma soluo candidata levemente diferente da soluo original
(aleatoriamente) Procedimento de modificao Procedimento de seleo :
que soluo continua
Slide 19
Hill-Climbing
Slide 20
Similar a gradiente descendente sem derivadas Algoritmo
Hill-Climbing 1: S Soluo Inicial; Procedimento de Inicializao 2:
Repita 3: R Tweak(Copy(S)) ; Procedimento de Modificao 4: Se
Qualidade(R) > Qualidade(S) Ento 5: S R 6: Ate S seja a soluo
ideal ou limite de tempo 7: retorne S
Slide 21
Steepest Ascent Hill-Climbing Amostrar a vizinhana e ficar com
o melhor
Slide 22
Slide 23
Busca Local Partindo de uma soluo inicial, consiste em navegar
interativamente pelo espao de busca movendo-se, em cada passo, de
uma soluo para uma soluo vizinha (adjacente).
Slide 24
Busca Local
Slide 25
Noo de vizinhana Seja S o espao de busca do problema Seja s uma
soluo do problema DEFINIES A funo vizinhana uma funo N(s) que
mapeia cada soluo s S para um subconjunto N(s) S. Um elemento
qualquer de N(s) denominado de vizinho de s.
Slide 26
Movimento Todo vizinho s' N(s) alcanado pela soluo s atravs de
uma operao denominada de movimento. a b c e s movimento N(S) = {a,
b, c, e}
Slide 27
O Problema da mochila Dados um conjunto de n objetos e uma
mochila com: c j = benefcio do objeto j w j = peso do objeto j b =
capacidade da mochila Determinar quais objetos devem ser colocados
na mochila para maximizar o benefcio total de tal forma que o peso
da mochila no ultrapasse sua capacidade.
Slide 28
O problema da mochila zero-um Maximizar Sujeito a Uma soluo s
um vetor de uns e zeros. Se o objeto j est mochila ento s j = 1,
caso contrrio s j = 0. (do ingls, 0-1 knapsack problem)
Slide 29
Vizinhana no problema da mochila s = (0,1,0,1,0) (1,1,0,1,0)
(0,0,0,1,0) (0,1,1,1,0) (0,1,0,0,0) (0,1,0,1,1) O movimento
consiste em mudar a varivel s j de 1 para 0 ou vice-versa.
Slide 30
Uma instncia do Problema da Mochila
Slide 31
Funo de Avaliao
Slide 32
Iterao 1
Slide 33
Iterao 2
Slide 34
Iterao 3 Iterao 3, soluo corrente = 11010010 No possvel
melhorar mais a soluo
Dificuldade de Resoluo Para mostrar a dificuldade de soluo do
PCV, assuma que a distncia de uma cidade i outra j seja simtrica,
isto , que dij = dji. Assim, o nmero total de rotas possveis (n -
1)!/2. Para se ter uma idia da magnitude dos tempos envolvidos na
resoluo do PCV por enumerao completa de todas as possveis solues,
para n = 20, tem-se 6 x 10 16 rotas possveis. Assim, um computador
que avalia uma rota em cerca de 10 -8 segundos, gastaria cerca de
19 anos para encontrar a melhor rota! Mesmo considerando os rpidos
avanos tecnolgicos dos computadores, uma enumerao completa de todas
essas rotas inconcebvel para valores elevados de n. Nos problemas
da classe NP-difcil, no possvel garantir que a rota de custo mnimo
seja encontrada em tempo polinomial. Assim, no pior caso, todas as
possveis solues devem ser analisadas. possvel dar uma certa
inteligncia a um mtodo de enumerao
Slide 43
Heursticas Para solucionar problemas desse nvel de
complexidade. Definimos heurstica como sendo uma tcnica inspirada
em processos intuitivos que procura uma boa soluo a um custo
computacional aceitvel, sem garantir sua otimalidade, bem como
garantir quo prximo est da soluo tima.
Slide 44
Heursticas Entretanto, a maioria das heursticas desenvolvidas
muito especfica para um problema particular, no sendo eficientes
(ou mesmo aplicveis) na resoluo de uma classe mais ampla de
problemas. Somente a partir da dcada de 1980 intensificaram-se os
estudos no sentido de se desenvolver procedimentos heursticos com
uma certa estrutura terica e com carter mais geral, sem prejudicar
a principal caracterstica destes, que a flexibilidade.