Estratégia do aprimoramento adiado para buscas locais: usando características de ótimos locais como critério na seleção de soluções aprimorantes

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.