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 i1 i1 i i entrada: G2(x) n i * xi2 i1 restrições: saida: n i1 xi 0.75 n xi 7.5 * n, 0 xi 10,1 i n i1 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
Download
