Tpicos em Inteligncia Artificial opt. CI309A

Tpicos em Inteligncia Artificial opt. CI309Ahttp://www.inf.ufpr.br/aurora/disciplinas/topicosia2/topicosia2.htmProf. Aurora T. R. PozoDepartamento de InformticaUniversidade Federal do Paranwww.inf.ufpr.br/auroraaurora@inf.ufpr.brOTIMIZAOOTIMIZAO 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). Agentes baseado em ObjetivosOtimizaao ubiqua

MetaheursticasOtimizao 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)

MetaheursticasIterativamente melhorar um conjunto de solues Pouco conhecimento do problema Precisa poder distinguir boas soluesGeralmente encontra boas solues possivelmente no o timo Adaptveis : parmetros ajustveis

Otimizao

SSujeito a restriesOtimizao Baseada em GradienteMtodo matemtico clssico

Mtodo matemtico clssicoConhecer a funo que se otimizaConhecer suas derivadasMetaheursticasInteligncia e Resoluo de ProblemasMtodos de BUSCAEnxergam 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.

Quando Utilizar estas tcnicasQuase 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.

MetaheuristicasAlgoritmos usados em problemas nos quais existe pouca informao : no se conhece a forma de uma soluo tima , No se sabe como encontrar elaUma explorao completa e impossvel devido ao tamanho do espao Porem se voc tem uma soluo candidata , ela pode ser avaliada 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;

InformaesQualidade de uma SoluoPorem no se conhece a superfcie da funoQualquer tipo de representao da soluoEspao real, inteiro, um grafo2 espaos soluo e funo.

Problema de Santa FeComo EnfrentarTer uma ou mais solues candidatas iniciais. Procedimento de Inicializao Avaliao de uma soluo candidataProcedimento de AvaliaoRealizar uma copia da soluo candidataConstruir uma soluo candidata levemente diferente da soluo original (aleatoriamente)Procedimento de modificao Procedimento de seleo : que soluo continuaHill-Climbing

Hill-ClimbingSimilar a gradiente descendente sem derivadasAlgoritmo Hill-Climbing1: S Soluo Inicial; Procedimento de Inicializao2: Repita3: R Tweak(Copy(S)) ; Procedimento de Modificao4: Se Qualidade(R) > Qualidade(S) Ento 5: S R6: Ate S seja a soluo ideal ou limite de tempo 7: retorne SSteepest Ascent Hill-ClimbingAmostrar a vizinhana e ficar com o melhor

Busca LocalPartindo 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).Busca Local

Noo de vizinhanaSeja S o espao de busca do problemaSeja s uma soluo do problemaDEFINIESA 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.

MovimentoTodo vizinho s' N(s) alcanado pela soluo s atravs de uma operao denominada de movimento.abces movimentoN(S) = {a, b, c, e}O Problema da mochilaDados um conjunto de n objetos e uma mochila com:cj = benefcio do objeto jwj = peso do objeto jb = capacidade da mochilaDeterminar quais objetos devem ser colocados na mochila para maximizar o benefcio total de tal forma que o peso da mochila no ultrapasse sua capacidade.O problema da mochila zero-umMaximizarSujeito aUma soluo s um vetor de uns e zeros.Se o objeto j est mochila ento sj = 1, caso contrriosj = 0.(do ingls, 0-1 knapsack problem)Vizinhana no problema da mochilas = (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 sj de 1 para 0ou vice-versa.Uma instncia do Problema da Mochila

Funo de Avaliao

Iterao 1

Iterao 2

Iterao 3

Iterao 3, soluo corrente = 11010010 No possvelmelhorarmais a soluo

Inicializao

Tweak

Tweak

Tweak

Distncia Total =143256Cid.12345610214912205972315038644930265978202612662011PCV

Dificuldade de ResoluoPara 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 1016 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 enumeraoHeursticasPara solucionar problemas desse nvel de complexidade. Definimos heurstica como sendo uma tcnica inspirada em processos intuitivos que procura uma boa soluoa um custo computacional aceitvel, sem garantir sua otimalidade, bem como garantir quo prximo est da soluo tima.HeursticasEntretanto, 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.