Recall: breadth-first search, step by step CS 561, Session 7 1 Implementation of search algorithms Function General-Search(problem, Queuing-Fn) returns a solution, or failure nodes make-queue(make-node(initial-state[problem])) loop do if nodes is empty then return failure node Remove-Front(nodes) if Goal-Test[problem] applied to State(node) succeeds then return node nodes Queuing-Fn(nodes, Expand(node, Operators[problem])) end Queuing-Fn(queue, elements) is a queuing function that inserts a set of elements into the queue and determines the order of node expansion. Varieties of the queuing function produce varieties of the search algorithm. CS 561, Session 7 2 Recall: breath-first search, step by step CS 561, Session 7 3 Breadth-first search Node queue: initialization # state depth path cost parent # 1 Arad 0 0 -- CS 561, Session 7 4 Breadth-first search Node queue: add successors to queue end; empty queue from top # state depth path cost parent # 1 2 3 4 Arad Zerind Sibiu Timisoara 0 1 1 1 0 1 1 1 -1 1 1 CS 561, Session 7 5 Breadth-first search Node queue: add successors to queue end; empty queue from top # state depth path cost parent # 1 2 3 4 5 6 Arad Zerind Sibiu Timisoara Arad Oradea 0 1 1 1 2 2 0 1 1 1 2 2 -1 1 1 2 2 (get smart: e.g., avoid repeated states like node #5) CS 561, Session 7 6 Depth-first search CS 561, Session 7 7 Depth-first search Node queue: initialization # state depth path cost parent # 1 Arad 0 0 -- CS 561, Session 7 8 Depth-first search Node queue: add successors to queue front; empty queue from top # state depth path cost parent # 2 3 4 1 Zerind Sibiu Timisoara Arad 1 1 1 0 1 1 1 0 1 1 1 -- CS 561, Session 7 9 Depth-first search Node queue: add successors to queue front; empty queue from top # state depth path cost parent # 5 6 2 3 4 1 Arad Oradea Zerind Sibiu Timisoara Arad 2 2 1 1 1 0 2 2 1 1 1 0 2 2 1 1 1 -- CS 561, Session 7 10 Last time: search strategies Uninformed: Use only information available in the problem formulation • • • • • Breadth-first Uniform-cost Depth-first Depth-limited Iterative deepening Informed: Use heuristics to guide the search • Best first: • Greedy search • A* search CS 561, Session 7 11 Last time: search strategies Uninformed: Use only information available in the problem formulation • • • • • Breadth-first Uniform-cost Depth-first Depth-limited Iterative deepening Informed: Use heuristics to guide the search • Best first: • Greedy search -- enfileira primeiro os nós que maximizam a “desejabilidade” heurística baseado no custo do nó corrente ao objetivo; • A* search – enfileira primeiro os nós que maximizam a soma dos custos do caminho até o nó mais o custo estimado do nó corrente ao objetivo; CS 561, Session 7 12 This time • Iterative improvement • Hill climbing • Simulated annealing CS 561, Session 7 13 Melhoria Iterativa • Em muitos problemas de otimização, o caminho é irrelevante; o estado objetivo por si só é a solução. • Então, o espaço de estados = espaço de configurações “completo”. Objetivo do algoritmo: - achar configuração ótima (ex: TSP), ou, - achar configuração que satisfaça restrições (ex: n-queens) • Em tais casos, pode-se usar algoritmos de melhoria iterativa: manter um estado “corrente” único, e tentar melhorá-lo. CS 561, Session 7 14 Exemplo de melhoria iterativa: ambiente do aspirador Ambiente simplificado: 2 localizações, cada uma pode ou não conter sujeira e pode ou não conter agente. Objetivo do agente: limpar a sujeira. Se o caminho não importa, não é necessário mante-lo (sabê-lo). CS 561, Session 7 15 Exemplo de melhoria iterativa: n-queens • objetivo: colocar n rainhas num tabuleiro nxn, sem que hajam duas rainhas na mesma linha, coluna ou diagonal. • Aqui, o estado objetivo é desconhecido inicialmente, mas é especificado por restrições que ele deve satisfazer. CS 561, Session 7 16 Hill climbing (ou descida/subida do gradiente) • Maximiza “valor” do estado corrente iterativamente, atualizando-o pelo sucessor que possui o maior valor, na medida do possível. CS 561, Session 7 17 Hill climbing • Nota: minimizar uma função “valorada” v(n) é equivalente a maximizar –v(n), então ambas noções podem ser usadas intercambeadas. • Noção de “extremização”: achar extremo (mínimo ou máximo) de uma função valorada. CS 561, Session 7 18 Hill climbing • Problema: dependendo do estado inicial, pode parar em extremo (mínimo ou máximo) local. CS 561, Session 7 19 Minimizando energia • Vamos mudar a formulação do problema um pouco, de maneira que se possa empregar um novo formalismo: - comparar o espaço de estados ao de um sistema físico sujeito a interações naturais, e - comparar a função valorada à energia potencial total (E) do sistema. • Em toda atualização, temos DE 0 • Então, a dinâmica do sistema tende a mover E de encontro ao mínimo. • Estes estados podem ser diferentes — se forem mínimos locais. Minimização global pode não ser garantida. Basin of Attraction for C A B D E CS 561, Session 7 C 20 Máquinas de Boltzmann Basin of Attraction for C h A B D E A Máquina de Boltzmann de Hinton, C Sejnowski, e Ackley (1984) usa Simulated Annealing para fugir de mínimos locais. Para motivar a solução, considere como alguém poderia fazer uma bola navegar ao longo de uma curva para “provavelmente finalizar” no local mais profundo. A idéia é “chacoalhar” a caixa próximo de h de modo que a bola pule, provavelmente, D para C, ou, dependendo da amplitude, de D para B. No final, em algum tempo a bola deverá terminar no vale C. CS 561, Session 7 21 Idéia básica do Simulated annealing • Do estado corrente tomar um estado sucessor de forma aleatórea; • Se este estado possuir valor melhor que o do estado corrente, então “aceite a transição”, ou seja, faça do estado sucessor o corrente; • Caso contrário, não desistir, aceite a transição com uma dada probabilidade (pequena na medida que o sucessor for ruim). • Algumas vezes, a função valor é não-otimizada com probabilidade diferente de zero. CS 561, Session 7 22 Analogia: Refrigerar lentamente um líquido • Quanto menor a taxa de variação de T no início, mais gradualmente o líquido se tornará gelo; • Se no início tiver mudanças bruscas em T, algumas regiões gelarão primeiro que outras CS 561, Session 7 23 Teoria estatística dos gazes, de Boltzmann • Na teoria estatística dos gases, o gás é descrito pela probabilidade de ele se encontar em estados diferentes e não por uma dinâmica determinística. • No século 19, o físico Ludwig Boltzmann desenvolveu uma teoria que incluiu uma distribuição probabilística da temperatura, isto é, regiões do gás pequenas, vizinhas, possuem a mesma energia cinética. • A idéia de Hinton, Sejnowski e Ackley’s é que esta distribuição pode ser tb usada para descrever interações neurais, onde temperatura a baixar T é atualizada por um pequeno sinal de ruído: o análogo neural do movimento aleatório termal de moléculas. Os resultados se aplicam a otimização usando redes neurais, mas a idéia é mais geral. CS 561, Session 7 24 Distribuição de Boltzmann • Em equilíbrio térmico a uma temperatura T, a distribuição de Boltzmann produz a probabilidade relativa de que o sistema ocupará o estado A versus o estado B como: P( A) E ( A) E ( B) exp(E ( B) / T ) exp P( B) T exp(E ( A) / T ) • onde E(A) e E(B) são as energias associadas com os estados A e B. CS 561, Session 7 25 Simulated annealing Kirkpatrick et al. 1983: • Simulated annealing é um método geral para produzir um provável escape de mínimos locais permitindo saltos com energias mais altas. • A analogia aqui é com o processo de recozimento usado por um artesão para forjar uma espada de uma liga. • Aquece o metal, a seguir refrigera-o lentamente enquanto martela a lâmina para obter a forma desejada. • Se refrigerar a lâmina muito rapidamente, o metal formará pedaços com composição diferente; • Se o metal for refrigerado lentamente enquanto dando forma, os metais constituintes formarão uma liga uniforme. CS 561, Session 7 26 Simulated annealing na prática - determina T inicial (temperatura) otimiza para o dado T abaixa T (see Geman & Geman, 1984) repete CS 561, Session 7 27 Simulated annealing na prática - determina T inicial (temperatura) otimiza para o dado T abaixa T (see Geman & Geman, 1984) repete • Geman & Geman (1984): se T é abaixado lentamente (com respeito ao número de iterações usadas para otimizar a uma dada temperatura T), garante-se que o simulated annealing acha o mínimo global. • Caveat: este algoritmo pode não ter fim. O decrescimento em T (Geman & Geman) é da ordem de 1/log do número de iterações, então, T poderá nunca ser zero). Isto pode levar a um tempo infinito para atingir o mínimo global. CS 561, Session 7 28 Algoritmo para o Simulated annealing • Idéia: Escapar extremo local permitindo “movimentos ruins”, mas gradualmente decrementando o seu tamanho e freqüência. Nota: objetivo aqui é maximizar E. - CS 561, Session 7 29 Algoritmo para o Simulated annealing • Idéia: Escapar extremo local permitindo “movimentos ruins”, mas gradualmente decrementando o seu tamanho e freqüência. < CS 561, Session 7 Algoritmo visando minimizar E. 30 Simulated annealing: casos limites • Distribuição de Boltzmann: aceita “movimento ruim” com DE<0 (objetivo é maximizar E) com probabilidade P(DE) = exp(DE/T) • P/ T grande : DE < 0 DE/T < 0 and very small exp(DE/T) close to 1 accept bad move with high probability • P/ T pequeno (0): DE < 0 DE/T < 0 and very large exp(DE/T) close to 0 accept bad move with low probability CS 561, Session 7 31 Simulated annealing: casos limites • Distribuição de Boltzmann: aceita “movimento ruim” com DE<0 (objetivo é maximizar E) com probabilidade P(DE) = exp(DE/T) • If T is large: • If T is near 0: DE < 0 DE/T < 0 and very small exp(DE/T) close to 1 accept bad move with high probability Random walk DE < 0 DE/T < 0 and very large exp(DE/T) close to 0 accept bad move with low probability CS 561, Session 7 Deterministic down-hill 32 Sumário • Best-first search = general search, onde os nós de custo mínimo (de acôrdo com alguma medida) são expandidos primeiro. • Greedy search = best-first com o custo estimado para alcançar o objetivo sendo uma medida heurística. - Geralmente mais rápido que uninformed search - não ótimo - não completo. • A* search = best-first com medida = custo efetivo até o nó (desde origem) + custo estimado até o objetivo. - combina vantagens das estratégias uniform-cost e greedy - completo, ótimo e otimamente eficiente - complexidade de memória ainda exponencial CS 561, Session 7 33 Sumário • Complexidade de tempo dos algoritmos heurísticos dependem da qualidade da função heurística. Boas heurísticas podem algumas vezes serem construídas examinando-se a definição do problema ou generalizando de experiências com a classe de problemas. • Algoritmos de melhoria iterativa mantém apenas um único estado em memória. • Podem parar em extremos locais; simulated annealing provê uma maneira de escapar de extremos locais, e é completo e ótimo, se for aplicado um resfriamento suficientemente lento. CS 561, Session 7 34