Busca local e otimização

Este texto é parte da disciplina de Fundamentos de Inteligência Artificial do Programa de Pós-Graduação em Computação da Universidade Federal de Pelotas e não foi feito para fazer muito sentido fora deste contexto.

Os algoritmos de busca exaustiva, como DFS, BFS e A*, procedem enumerando os estados possíveis de serem atingidos a partir do estado atual e seguindo-os em alguma ordem. Por exemplo, se estamos desenvolvendo um algoritmo para solucionar o quebra-cabeça deslizante de 8 peças, a partir de qualquer estado temos entre dois e quatro estados alcançáveis — i.e. cada nó na árvore tem no máximo quatro filhos.

Porém, e se tivermos um problema com uma grande quantidade de estados alcançáveis? De fato, e se forem infinitos? Neste caso é claro que os métodos exaustivos não são adequados. Um algoritmo de busca local opera iterativamente sobre uma solução, movendo-se de estado para estado e verificando se o estado atual satisfaz algum critério de parada.

Aqui é importante distinguir entre dois tipos de problemas de busca. No quebra-cabeça deslizante, ou mesmo o Xadrez, estamos interessados não apenas no estado final em si, mas principalmente no caminho para chegar até esta solução. Afinal, no quebra-cabeça deslizante nós já sabemos qual é o estado final: é parte das regras do jogo. A solução é na verdade um caminho do estado inicial até este estado final. Por outro lado, considere o chamado Problema das N Rainhas: dado um tabuleiro de xadrez com N colunas e N linhas, como colocar N rainhas no tabuleiro de forma que nenhuma esteja em linha de ataque com outra rainha? Lembrando, uma rainha pode se mover qualquer número de casas na horizontal, vertical ou diagonal.

Uma solução para o Problema das N Rainhas com N = 4

Neste caso, a solução é o estado final e não o caminho — uma vez que se saiba o estado final, não importa como se coloca as rainhas nos locais certos. Sudoku também tem esta característica. Ninguém pergunta a quem solucionou uma instância difícil “mas em que ordem você colocou os números?”.

Algoritmos de busca local são particularmente úteis em problemas onde desejamos encontrar um estado de interesse, mas não o caminho até este estado. Isso permite que muitos poucos estados fiquem na memória em qualquer momento (no limite, um único estado) — e vimos como memória é um problema para algoritmos como BFS ou A*. Para que funcionem, é necessário essencialmente dois componentes: (i) uma função que avalia cada estado e (ii) uma maneira de gerar um novo estado a partir do atual. Com estas partes, é uma questão de gerar novos estados procurando por aqueles que sejam melhores que o inicial.

Por este motivo, algoritmos de busca local são também chamados de algoritmos de otimização. Ainda que se possa diferenciar entre estes dois termos baseado em se existe um estado final a priori ou se apenas queremos o melhor estado possível, em geral tratamos ambos como uma grande categoria: busca heurística. O termo pode ser confuso, pois o A* utiliza heurísticas mas não é um algoritmo de otimização; mas o A* é uma busca com heurística — a heurística é usada para guiar a busca, que é ótima, enquanto em uma busca heurística é a busca como um todo que é heurística (i.e. aproximada, sem garantias de encontrar a melhor solução), ainda que muitas utilizem heurísticas como as do A* também.

Buscas heurísticas são amplamente utilizadas em IA. Notadamente são essenciais para treinar modelos de aprendizado de máquina, como redes neurais artificiais. Uma grande variedade de algoritmos de otimização foram propostos ao longo dos anos, nem todas são aplicáveis a todos problemas e variam enormemente em suas propriedades.

Uma busca local simples

Considere um estado inicial, digamos no Problema das N Rainhas abaixo, gerado talvez colocando uma rainha em cada coluna e escolhendo aleatoriamente a linha de cada uma.

Podemos verificar se este estado é uma solução ou não. Claramente não é. Então precisamos considerar outro estado. Mas qual? Até podemos repetir o processo — gerar uma nova solução aleatória, sem nenhuma relação com a atual, e torcer pelo melhor. Pode-se imaginar que a probabilidade de sucesso não é grande.

Uma alternativa é continuar a busca a partir do estado atual, como fazem os algoritmos de busca exaustivos. Chamamos de vizinhança de um estado todos os estados alcançáveis a partir deste estado — i.e. que podem ser gerados a partir do estado. Em uma busca exaustiva, a vizinhança é dada pelos movimentos possíveis, pois a sequência de movimentos (o caminho) é a solução e isto tipicamente limita o tamanho da vizinhança. Mas no problema das rainhas, nada impede de movermos qualquer rainha para qualquer posição arbitrária para gerar um novo estado — todos estados são alcançáveis a partir de qualquer estado.

Uma abordagem para definir uma vizinhança mais razoável é considerar todos estados que podem ser gerados modificando um estado de forma mínima, ou pelo menos bem definida. No caso das rainhas, podemos definir que um estado é vizinho de outro se ele é gerado movendo uma única rainha uma casa para cima ou para baixo (se for possível). Considere: com esta definição, quantos vizinhos o estado representado na figura acima tem?

Nosso algoritmo agora pode proceder gerando UM vizinho qualquer a partir do estado atual. Digamos que movemos uma rainha e ficamos com o estado abaixo.

Podemos agora verificar se este estado é uma solução. Se fosse, ótimo. Infelizmente, não é. E agora? Se seguirmos desta forma, gerando novos estados a partir do atual que não é uma solução, não estamos realmente melhor do que a busca aleatória — de fato, apenas geramos um caminho aleatório que não melhora nossas chances de encontrar uma solução.

Vamos adicionar uma heurística à busca. Relembrando, uma heurística é uma função que recebe como entrada um estado e retorna um valor que indica de forma aproximada o quão próximo o estado está de um estado final. Para este problema, podemos definir algo bem simples: contamos o número de rainhas sendo atacadas. Se temos zero, esta é a solução. Mas, mais importante, podemos comparar e ordenar diferentes estados usando esta heurística. Um estado com três rainhas sendo atacadas é pior do que um onde apenas uma está sob ataque.

Com esta heurística, podemos agora fazer algo diferente quando geramos um novo estado. Sabemos a avaliação do estado atual e podemos avaliar o novo estado. Se este é melhor que o estado atual, então podemos adotá-la e torná-la o novo estado atual. Se, por outro lado, é pior, então descartamos o estado gerado, mantendo o estado atual. Por fim, repetimos o processo, gerando um novo estado e assim por diante, até que a solução seja encontrada ou até que não haja mais vizinhos melhores que o estado atual.

Em resumo, este algoritmo inicia em um estado e gera um estado vizinho por vez, adotando-o apenas se este for melhor que o estado anterior. Novos estados sempre são gerados a partir do melhor estado conhecido até então e o algoritmo ou encontra a solução ou chega em um estado que não tem mais vizinhos melhores e, portanto, não tem mais para onde ir. Este algoritmo é chamado busca por subida de encosta ou hill climbing search e é o mais básico dos algoritmos de busca local.

Abaixo está uma possível sequência inicial de estados para o Problema das N Rainhas. Deve-se observar que este algoritmo é guloso, ele nunca retorna a pontos anteriores para considerar novos caminhos, ainda que possa passar pelo mesmo estado múltiplas vezes (já que não há memória dos estados visitados).

O estado inicial está na esquerda, com valor 4. No centro, acima, um vizinho com valor superior ao do estado inicial é gerado e descartado. No centro, abaixo, outro vizinho é gerado e torna-se o estado atual por ter um valor inferior. Na direita, o primeiro vizinho gerado do estado atual tem menor valor e é aceito. Nenhum outro vizinho tem custo menor que 2 existe e o algoritmo encerra. Peças em vermelho indicam a peça que se moveu.

Também pode-se observar na imagem acima que a solução não foi atingida, mas que não há nenhum movimento adicional possível no último estado já que não há vizinhos melhores segundo a função de avaliação. Também é o caso que o estado onde parou é melhor que o estado inicial. Estas duas observações sintetizam algoritmos de busca local: tipicamente conseguimos algo melhor do que o que começamos (mas não necessariamente), mas que não é garantidamente a melhor solução possível (ainda que possa ser). Duas grandes questões são se a melhora observada é suficiente e quanto tempo se leva para obter tal melhora.

Ao atingirmos a solução no exemplo acima, dizemos que chegamos em um ótimo local (ou mínimo local, neste caso específico onde procuramos por soluções com avaliações menores) da função de avaliação. Uma função de avaliação com apenas um ótimo local, que coincide com o ótimo global (a melhor solução possível), é o caso ideal para este algoritmo; iniciando em qualquer estado inicial, ele convergirá para o ótimo global (ou próximo do ótimo, dependendo de fatores como distância definida dos vizinhos).

Porém, raramente temos tal situação. A figura abaixo ilustra a topografia de uma função de avaliação contínua fictícia. O eixo X é o estado (representado por um valor real) e o eixo Y é a avaliação deste estado, também um valor real.

Topografia de uma função de avaliação fictícia simples, com algumas propriedades destacadas

Nesta figura, é possível observar os principais obstáculos para a busca por subida de encosta. Ainda que exista um ótimo global, nem sempre ele é alcançável. Ademais, o resultado é sensível ao estado inicial — se começarmos próximo da origem, o algoritmo convergirá para o ótimo global, mas iniciando na extrema direita em seguida a busca converge para um platô, encerrando a busca.

É claro que com a visão total da topografia da função de avaliação podemos pensar em meios de atingir o ótimo global, mas é importante considerar que em problemas reais não temos esta visão, tampouco sabemos o que é um valor razoável que possa ser obtido, quantos máximos locais existem etc. Algoritmos de busca local tipicamente andam no escuro, apenas observando o que está imediatamente na sua volta (os estados vizinhos).

Alternativas a busca por subida de encosta procuram melhorar dois aspectos deste algoritmo: (i) melhorar a velocidade de convergência e (ii) evitar a estagnação em ótimos locais. Por exemplo, a busca por subida mais íngreme de encosta (steepest ascent hill climbing) é uma variação onde todos vizinhos são avaliados e o estado atual torna-se o melhor entre estes. Em contraste, a versão original move-se em direção ao primeiro melhor estado que encontrar, mesmo que haja outros melhores. Isto pode melhorar a velocidade de convergência, mas ainda causa estagnação quando não há melhores vizinhos.

Explorar vs Aproveitar

Dizemos que a busca por subida de encosta aproveita maximamente o estado atual (uma propriedade as vezes chamada de exploitação, do inglês exploitation). Isso quer dizer que ela procura aproveitar ao máximo informações conhecidas — no caso, o estado atual — gerando novos estados que são mínimas variações deste. Associado a nunca permitir uma piora no estado atual, este comportamento ultimamente leva a estagnação em ótimos locais ou platôs.

O outro extremo é uma busca maximamente exploratória, onde qualquer informação contida no estado atual é completamente descartada. É o caso de uma busca aleatória, mencionada no início deste texto: estados aleatórios são gerados a cada passo e se torce que algum seja a solução. Sendo aleatórios, os estados gerados não tem nenhuma relação com o estado atual.

A dualidade exploração e aproveitamento é crucial em algoritmos de busca local. Pouca exploração leva a estagnação, enquanto muita exploração leva a ineficiência. Muitos algoritmos procuram balancear a busca entre estes dois extremos.

Um deles é a Têmpera Simulada (Simulated Annealing), nome importado da metalurgia. A ideia por trás é permitir, probabilisticamente, que um novo estado seja pior do que o atual, mas apenas no início da busca — isso permite que, se o algoritmo estagnar muito cedo, ele consiga sair do ótimo local e continuar a busca. Naturalmente, sempre guardamos o melhor estado visitado em algum lugar, caso aquele ótimo local fosse melhor que qualquer outro visitado posteriormente. O algoritmo inicia explorativo e passa a ser mais exploitativo ao longo do tempo. Isso é controlado por um parâmetro chamado Temperatura, que decresce ao longo da execução do algoritmo. Quando este é zero, o algoritmo se reduz a subida de encosta, garantido que irá parar em pelo menos um ótimo local.

Aqui é útil ler a entrada na Wikipedia sobre Simulated Annealing (curioso: não parece existir uma entrada para a técnica em português)

A presença de um parâmetro que controla exploração e exploitação é particularmente útil por permitir que o algoritmo seja melhor aproveitado em diferentes problemas. Se um problema é simples, talvez com apenas um único ou poucos ótimos locais, podemos manter a Temperatura inicial baixa. Por outro lado, problemas complexos exigirão Temperaturas altas. Infelizmente não costumamos saber muito sobre a topografia do problema e, com alguma frequência, este parâmetro é ajustado de forma ad hoc — se experimenta com diferentes valores, observando a convergência para um pequeno número de iterações.

Neste site é possível experimentar com a Têmpera Simulada em um problema clássico de otimização combinatória: o problema do caixeiro viajante. Em resumo, neste problema o objetivo é encontrar o menor caminho que passa por todas as "cidades" do problema uma única vez; portanto, é um problema de minimização. Ligue a opção "trace solution" e clique em "animate" para ver a evolução da solução. Observe como o custo da solução flutua inicialmente, mas eventualmente converge para um valor razoável a medida que a temperatura decresce.

Leitura opcional: artigo A survey of simulated annealing as a tool for single and multiobjective optimization

Muitos outros algoritmos tentam evitar estagnação em ótimos locais. Outro, bastante simples, é a subida de encosta com reinício aleatório. Como o nome indica, rodamos a subida de encosta múltiplas vezes, cada vez com um estado inicial escolhido aleatoriamente. Então, retornamos a melhor solução entre todas execuções. O reinício é responsável pela exploração, enquanto a subida de encosta é responsável pela exploitação. O número de rodadas aumenta a exploração. Apesar de simples, este algoritmo pode ser bastante efetivo.

Leitura recomendada: Comparison of simulated annealing and hill climbing in the course timetabling problem

Conclusão

Ainda temos muito a falar sobre algoritmos de otimização, mas aqui é importante considerarmos alguns tipos de problemas que podemos solucionar com estas técnicas de forma direta. Essencialmente, estes algoritmos aplicam-se a qualquer situação onde é necessário ajustar parâmetros de alguma função ou sistema e pode-se avaliar o resultado, mesmo sem saber exatamente como os parâmetros influenciam a avaliação.

Por exemplo, o desenho de um carro tem muitos parâmetros: formato do capô, largura do chassi, tamanho das rodas etc. Além da estética, desejamos que o carro tenha, digamos, um baixo coeficiente de atrito com o ar, de forma a ser econômico. Este coeficiente é relativamente simples de medir dado o desenho de um carro, talvez em um túnel de vento simulado. Podemos usar algoritmos de busca local para encontrar os parâmetros que levam a um baixo coeficiente de atrito.

Interessantemente, há toda uma área chamada Design Generativo que procura construir coisas físicas dadas especificações em alto nível — e.g. podemos simplesmente dizer que queremos uma ponte que suporte tantas toneladas, e o algoritmo encontra os parâmetros necessários. Já existem ferramentas comerciais que fazem isso.

Podemos ainda pensar em aplicar estes algoritmos para construir heurísticas para um jogador de Xadrez ou Go. Uma abordagem para isso é especificar a forma de uma heurística e deixar o algoritmo encontrar os parâmetros específicos — por exemplo, a heurística pode especificar variáveis para peças diferentes e a tarefa do algoritmo de busca é encontrar os valores para as variáveis . A avaliação pode ser feita fazendo o jogador com a heurística jogar contra outros jogadores estabelecidos, ou contra o próprio jogador com diferentes versões da heurística, e contar o número de jogos vitoriosos.

Que outras aplicações você consegue vislumbrar?