Multi-point search for combinatorial optimization problems
Tadeu Knewitz Zubaran · Lume (Universidade Federal do Rio Grande do Sul) · 2013
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.