Multi-point search for combinatorial optimization problems

Abstract

Neste trabalho propomos e testamos maneiras de aplicar os princípios por traz do go with the winners, em problemas de otimização combinatória. Go with the winners foi proposto como um algorítimo para mover partículas em árvores abstratas, e é comprado com um algorítimo, simple restart, onde diversas partículas são soltas na raiz da árvore e deixadas à descender sem interagirem umas com as outras. O técnica go with the winners permite que as partículas utilizem informação das outras de forma a aumentar a chance delas chegarem em níveis mais baixos da árvore. Nós desenvolvemos um algorítimo que utiliza as idéias chave do go with the winners para três problemas distintos. Primeiramente desenvolvemos um problema artificial para testes preliminares do algorítimo para verificarmos como as previsões teóricas são traduzidas para um ponto intermediário entre um verdadeiro problema de otimização e o framework abstrato. Nós então implementamos e testamos o go with the winners no clássico problema de otimização do caixeiro viajante e por último no moderno machine reassignment. Para cada uma de nossas implementações nós fazemos uma bateria completa de testes e comparamos com a performance contra o simple restart e as meta-heurísticas comumente utilizadas GRASP e simulated annealing.

In this work we propose and test ways to apply the principles of go with the winners in combinatorial optimization problems. Go with the winners was proposed as an algorithm to move particles in abstract trees, and is compared with an algorithm, the simple restart, where several particles are released at the root of the tree and let to descend the tree without interacting with one another. The go with the winners approach lets particles use information from other particles in order to increase the chance that they will reach deeper levels of the tree. We develop an algorithm that use the core ideas of the go with the winners in three distinct problems. First we define an artificial optimization problem to test a preliminary algorithm and see how the theoretical predictions are translated in a mid point between an actual optimization problem and the abstract framework. We proceed, then, to implement and test the go with the winners in a classic optimization problem, the travelling salesperson problem, and finally in the modern problem machine reassignment. For each of our implementations we perform a comprehensive set of benchmark tests and compare the performance against the simple restart and the commonly used metaheuristics GRASP and simulated annealing.