Estratégia do aprimoramento adiado para buscas locais: usando características de ótimos locais como critério na seleção de soluções aprimorantes
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Primeiro orientador
Membros da banca
Thiago Ferreira de Noronha
Vinícius Fernandes dos Santos
Maurício Cardoso de Souza
Túlio Toffolo
Daniel Aloise
Vinícius Fernandes dos Santos
Maurício Cardoso de Souza
Túlio Toffolo
Daniel Aloise
Resumo
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.
Existem 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 esigualdades 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.
Abstract
Local search is a neighbourhood based heuristic method, that aims to find good solutions for combinatorial problems. A Local search starts with a viable solution and through operations attempts to improve the initial solution, generating new viable solutions. The new solutions are called the neighbourhood of the current solution. Among neighbouring solutions is selected a better solution than the current solution by some pre-established criteria. Then, the selected solution becomes the new current solution creating a new neighbourhood. This process repeats until no better solution can be obtained among neighbouring solutions. The final solution of a local search is a local optimum. The best possible solution of a problem is a global optimum. There are several strategies for implementing local searches; the best known are Best Improvement and First Improvement. The Best Improvement approach selects, at each iteration, the best solution generated by the neighbourhood function; if it is better than the current solution. The First Improvement approach selects the first genereted solution, better than the current solution. This thesis presents a new approach to Local Search named Dalayed Improvement. Such approach attempts to avoid low quality local optimum. It tries to select in each iteration a neighbour soluttion that, been better than the currente one, it has less attributes of a local optimum. This approach is based on cuts (inequalities), commonly used in Integer Programming models. This method was implemented and tested using the Travelling Salesman Problem (TSP) and Max-Cut Problem as case studies. For TSP we used 2-OPT local search as reference and for Max-Cut Problem we used 1-Flip local search as reference. The computational results, although slower, had better local optimum when compared to conventional strategies. The new strategy obtained better results compared to experiments with fixed computation time or with a fixed target value for the objective function.
Assunto
Computação – Teses, Otimização combinatória – Teses, Programação heurística – Teses, Problema do caixeiro viajante– Teses
Palavras-chave
otimização combinatória, busca local, heurísticas, PCV, 2-OPT