Indicação do livro ESTRATÉGIA DO APRIMORAMENTO ADIADO PARA BUSCAS LOCAIS.
comentada em 07/06/2023 00:30

Livro Livros Escritos pelos Assinantes

ESTRATÉGIA DO APRIMORAMENTO ADIADO PARA BUSCAS LOCAIS
ESTRATÉGIA DO APRIMORAMENTO ADIADO PARA BUSCAS LOCAIS: USANDO CARACTERÍSTICAS DE ÓTIMOS LOCAIS COMO CRITÉRIO NA SELEÇÃO DE SOLUÇÕES APRIMORANTES heberfa

Busca local é um método heurístico para encontrar boas soluções para problemas combinatórios, baseado em busca em vizinhança. A busca local necessariamente parte de uma solução inicial viável e, através de operações, tenta melhorá-la, gerando novas soluções viáveis, chamadas de soluções vizinhas. Selecionam-se dentre as soluções vizinhas, soluções melhores do que a solução corrente por algum critério preestabelecido. Esse processo é repetido até que não seja possível obter nenhuma solução aprimorante. A solução final de uma busca local é chamada de ótimo local, a melhor solução possível para um problema é chamada de ótimo global.

Exitem várias estratégias para implementar buscas locais, sendo as mais conhecidas as abordagens Melhor Aprimorante Best Improvement e Primeiro Aprimorante First Improvement. A abordagem Melhor Aprimorante seleciona a melhor solução gerada pela função de vizinhança a cada iteração, desde que seja melhor que a solução corrente. A abordagem Primeiro Aprimorante seleciona a primeira solução melhor do que a solução corrente (aprimorante) gerada pela função de vizinhança.

A tese propõe uma nova abordagem de Busca Local denominada Melhoria Adiada Delayed improvement. Tal abordagem tenta evitar ótimos locais de baixa qualidade. Para isso, seleciona a cada iteração um vizinho aprimorante com poucos atributos de um ótimo local usando desigualdades baseadas em cortes, que normalmente são usadas em modelos de Programação Linear Inteira. Este método foi implementado e testado usando o problema do Caixeiro Viajante e o problema do Corte Máximo como casos de uso. Para o problema do Caixeiro Viajante foi usada a busca local 2-OPT como referência e para o problema do Corte Máximo foi usada a busca local 1-Flip como referência. Os resultados computacionais, embora mais lentos, obtiveram ótimos locais melhores quando comparados com as estratégias convencionais. A nova estratégia obteve melhores resultados comparativamente em experimentos com tempo de computação fixo ou com valor alvo fixo da função objetivo.

Ver mais detalhes e avaliar