Pesquisa local (otimização) - Local search (optimization)

Na ciência da computação , a busca local é um método heurístico para resolver problemas de otimização computacionalmente difíceis . A pesquisa local pode ser usada em problemas que podem ser formulados como encontrar uma solução que maximize um critério entre várias soluções candidatas . Os algoritmos de busca local movem-se de solução em solução no espaço de soluções candidatas (o espaço de busca ) aplicando mudanças locais, até que uma solução considerada ótima seja encontrada ou um limite de tempo decorrido.

Os algoritmos de busca local são amplamente aplicados a vários problemas computacionais difíceis, incluindo problemas de ciência da computação (particularmente inteligência artificial ), matemática , pesquisa operacional , engenharia e bioinformática . Exemplos de algoritmos de busca local são WalkSAT , o algoritmo 2-opt para o problema do caixeiro viajante e o algoritmo Metropolis – Hastings .

Exemplos

Alguns problemas em que a pesquisa local foi aplicada são:

  1. O problema da cobertura de vértices , em que a solução é uma cobertura de vértices de um grafo , e o objetivo é encontrar uma solução com um número mínimo de nós
  2. O problema do caixeiro viajante , em que a solução é um ciclo contendo todos os nós do gráfico e o objetivo é minimizar a duração total do ciclo
  3. O problema de satisfatibilidade booleana , em que uma solução candidata é uma atribuição de verdade e o objetivo é maximizar o número de cláusulas satisfeitas pela atribuição; neste caso, a solução final é útil apenas se satisfizer todas as cláusulas
  4. O problema de agendamento de enfermagem em que uma solução é a atribuição de enfermeiros a turnos que satisfaça todas as restrições estabelecidas
  5. O problema de agrupamento k-medóide e outros problemas de localização de instalações relacionados para os quais a pesquisa local oferece as melhores taxas de aproximação conhecidas a partir de uma perspectiva de pior caso
  6. O problema de Redes Neurais de Hopfield para o qual encontrar configurações estáveis ​​na rede de Hopfield .

Descrição

A maioria dos problemas pode ser formulada em termos de espaço de busca e alvo de várias maneiras diferentes. Por exemplo, para o problema do caixeiro viajante, uma solução pode ser um ciclo e o critério para maximizar é uma combinação do número de nós e da duração do ciclo. Mas uma solução também pode ser um caminho, e ser um ciclo faz parte do objetivo.

Um algoritmo de busca local começa a partir de uma solução candidata e então se move iterativamente para uma solução vizinha . Isso só é possível se uma relação de vizinhança for definida no espaço de busca. Como exemplo, a vizinhança de uma cobertura de vértice é outra cobertura de vértice diferindo apenas por um nó. Para satisfatibilidade booleana, os vizinhos de uma atribuição de verdade são geralmente as atribuições de verdade apenas diferindo dela pela avaliação de uma variável. O mesmo problema pode ter várias vizinhanças diferentes definidas nele; a otimização local com vizinhanças que envolvem a alteração de até k componentes da solução é freqüentemente chamada de k-opt .

Normalmente, cada solução candidata tem mais de uma solução vizinha; a escolha de para qual mover é feita usando apenas informações sobre as soluções na vizinhança da atual, daí o nome busca local . Quando a escolha da solução vizinha é feita tomando-se aquela que maximiza localmente o critério, a metaheurística toma o nome de hill climbing . Quando nenhuma configuração de melhoria está presente na vizinhança, a pesquisa local é travada em um ponto local ideal . Este problema local-ótimo pode ser curado usando reinicializações (busca local repetida com diferentes condições iniciais), ou esquemas mais complexos baseados em iterações, como busca local iterada , na memória, como otimização de busca reativa, em modificações estocásticas sem memória, como recozimento simulado .

O encerramento da pesquisa local pode ser baseado em um limite de tempo. Outra escolha comum é encerrar quando a melhor solução encontrada pelo algoritmo não tiver sido aprimorada em um determinado número de etapas. A pesquisa local é um algoritmo a qualquer momento : pode retornar uma solução válida mesmo se for interrompida a qualquer momento antes de terminar. Os algoritmos de busca local são tipicamente algoritmos de aproximação ou incompletos , pois a busca pode parar mesmo que a melhor solução encontrada pelo algoritmo não seja a ideal. Isso pode acontecer mesmo que o término seja devido à impossibilidade de melhorar a solução, pois a solução ótima pode estar longe da vizinhança das soluções cruzadas pelos algoritmos.

Para problemas específicos, é possível conceber bairros muito grandes, possivelmente de tamanho exponencial. Se a melhor solução dentro da vizinhança puder ser encontrada com eficiência, tais algoritmos são chamados de algoritmos de busca na vizinhança em grande escala .

Veja também

A pesquisa local é um subcampo de:

Os campos da pesquisa local incluem:

Espaços de busca com valor real

Existem vários métodos para realizar a pesquisa local de espaços de pesquisa com valor real :

Referências

Bibliografia