Particle Swarm Optimization with spanning tree representation for Ising spin glasses

Spin glasses are magnetic materials with strong disorder. Their unique properties assure them a central role in Statistical Physics, with applications that outreach many other important fields. Finding the ground state of an Ising spin glass is a highly multi-modal optimization problem, proved equivalent to the problem of finding the minimum weight cut in a graph. The states of a spin glass can be represented in terms of spins or bonds. Bond-based representations benefit from the symmetry properties of spin glasses, but require more memory due to the larger number of bonds. To tackle this issue, we introduced in our previous research a bond-based representation defined on spanning trees. A genetic algorithm (GA) using this representation (and special genetic operators) provided very good results for large problem instances (up to 125 spins). In this paper we continue this research. First, we describe how Particle Swarm Optimization (PSO) can be used to search ground states using the classical spin-based representation. Next, we present how the spanning tree representation can be used with PSO. Finally, we perform a comparative study of the performances of GAs and PSO with spin-based and bond-based representation on systems larger than before (up to 2500 spins).