Pesquisa por melhorias sucessivas

Também conhecida como pesquisa local.

• A partir de uma dada configuração inicial, fazem-se refinamentos sucessivos até obter uma configuração satisfatória.

• A solução inicial pode ser aleatória.

Técnicas mais comuns:

• Reparação heurística

  • É a versão mais básica deste tipo de pesquisa: reparações à solução inicial vão sendo aplicadas de acordo com uma heurística local.

  • No caso de problemas de satisfação de restrições, a heurística pode ser:

    • Fazer a reparação que, naquele momento, mais contribui para reduzir os conflitos entre variáveis, dadas as restrições.

• Montanhismo.

• Recozimento simulado.

• Algoritmos genéticos.

Montanhismo

A pesquisa é vista como um problema de optimizar uma função.

O espaço de soluções é visto como uma paisagem de vales (zonas de soluções menos satisfatórias) e colinas (zonas de soluções melhores).

Tem semelhanças com a pesquisa em profundidade e com a pesquisa gulosa, diferenciando-se pelo seguinte:

• Escolhe-se sempre o sucessor com melhor valor da função de avaliação.

• Não há retrocesso (backtracking).

• Quando o valor da função no nó actual é superior ao valor da função em qualquer dos seus sucessores, a pesquisa pára. (atingiu-se um máximo local)

Problemas:

• Máximos locais, planaltos, ravinas.

Variantes

Montanhismo estocástico

Escolhe aleatoriamente entre os sucessores que melhoram a função de avaliação.

Montanhismo de primeira escolha

Escolhe sucessores aleatoriamente até encontrar um com melhor função de avaliação que o estado actual.

Montanhismo com reinício aleatório

Executar o montanhismo várias vezes, partindo de estados iniciais aleatórios, e escolhe a melhor solução.

Recozimento simulado

Recozimento simulado (Simulated Annealing) é uma variante da pesquisa por montanhismo na qual podem ser aceites refinamentos que, localmente, piorem a solução.

• O nome inspira-se no processo industrial chamado recozimento.

  • Recozer = “deixar esfriar lentamente (um produto de cerâmica ou de vidro) num forno especial, logo após o seu fabrico”.

Começou a ser usado circa 1980 para resolver problemas de configuração de circuitos VLSI.

Particularidades:

• O sucessor é seleccionado aleatoriamente.

• Quando o valor da função no nó actual é superior ao valor da função no sucessor, o sucessor é aceite com uma probabilidade que diminui exponencialmente em função da perda na função de avaliação.

• Pesquisa termina quando um indicador designado “temperatura” chega a zero.

Algoritmo

Regime térmico

Pesquisa local alargada

Pesquisa local alargada

Semelhante ao montanhismo mas, em cada iteração, são mantidos k estados, e os melhores k sucessores são passados para a iteração seguinte.

Pesquisa alargada estocástica

Semelhante à pesquisa local alargada, mas os k sucessores são seleccionados aleatoriamente.

Algoritmos genéticos

Variante da pesquisa alargada estocástica em que os sucessores são gerados por combinação de dois estados, e não apenas por modificação de um único estado.

Algoritmos Genéticos