Statistical mechanics and optimization in complex scenarios

Abstract

Combinatorial optimization problems, such as the process of searching for extrema of a function over a discrete domain, are ubiquitous in science and engineering. Despite its ubiquity, some of these problems are notably difficult, requiring a computational cost which exponentially scales with the number of inputs. Among the vast collection of combinatorial optimization problems, the traveling salesman problem (TSP) has been of particular importance because of its huge number of applications. A common approach to such hard problems is the use of heuristics such as simulated annealing. Many versions of this heuristic are explored in the literature, but so far the effects of the statistical distribution of the coordinates of the cities on the performance of the heuristic has been neglected. We propose a simple way to explore this aspect by analyzing the performance of a standard version of simulated annealing (one using the geometrical cooling schedule) in correlated systems with a simple and useful method based on a linear combination of independent random variables. Our results suggest that performance depends on the shape of the statistical distribution of the coordinates but not necessarily on its variance corroborated by the cases of uniform and normal distributions. On the other hand, a study with different power laws (different decay exponents) for the coordinates always produces different performances. We show that the performance of the simulated annealing, even in its best version, is not improved when the distribution’s first moment diverges. Surprisingly, however, we still obtain improvements when the first moment exists but the second moment diverges. Finite size scaling, fits, and universal laws support all of our results. In addition our study shows when the cost must be scaled.

Problemas de otimização combinatorial, com problemas envolvendo encontrar pontos extremos de uma função sobre um domínio contínuo, são onipresentes em ciência e engenharia. Apesar de sua onipresença, alguns desses problemas são particularmente difíceis, exigindo um custo computacional que aumenta exponencialmente com o número de entradas. Dentre a vasta coleção de problemas de otimização combinatória, o problema do caixeiro viajante (TSP) tem sido de especial importância devido a seu grande número de aplicações. Uma abordagem comum para tais problemas é a utilização de heurísticas, como o recozimento simulado. Muitas versões dessa heurística são exploradas na literatura, mas até então o efeito da distribuição das coordenadas no desempenho da heurística tem sido preterido. Neste trabalho propomos uma maneira simples de explorar esse aspecto analisando o desempenho de uma versão padrão do recozimento simulado (utilizando o cronograma de resfriamento geométrico) em sistemas correlacionados com um método simples baseado em combinações lineares de variáveis aleatórias independentes. Nossos resultados sugerem que o desempenho depende fortemente do formato da distribuição e independe de sua variância, o que foi verificado utilizando distribuições uniformes e normais. Entretanto, um estudo considerando diferentes leis de potência (diferentes expoentes de decaimento) para as coordenadas resulta em desempenhos diferentes. Mostramos que mesmo para a melhor versão do recozimento simulado estudada, o recozimento simulado não é capaz de encontrar um ciclo satisfatório quando a distribuição de coordenadas não têm o primeiro momento definido. Porém, surpreendentemente, observamos melhoras mesmo quando a distribuição tem seu segundo momento não definido. Análises de tamanho finito, ajustes e leis universais corroboram nossos resultados. Ademais, nossa análise mostra quando o custo deve ser escalado.