Using Hysteresis for Optimization

We propose a new optimization method based on a demagnetization procedure well known in magnetism. We show how this procedure can be applied as a general tool to search for optimal solutions in any system where the configuration space is endowed with a suitable “distance.” We test the new algorithm on frustrated magnetic models and the traveling salesman problem. We find that the new method successfully competes with similar basic algorithms such as simulated annealing.

Figure 1

The total internal energy (without the Zeeman term) of a three-dimensional ($L=10$) Edwards-Anderson spin glass during ACD. The inset shows the corresponding magnetization curve.

Figure 2

Size dependence of the integrated energy distribution of states produced by ACD for the SK model. $E$ is the energy per spin measured from the ground state of each sample.

Figure 3

Probability density of finding a state of an SK model ($N=1000$, $H_{\mathrm{s}\mathrm{h}\mathrm{a}\mathrm{k}\mathrm{e}}=0.9$) with energy $E$ per spin above the ground state by ACD (symbols) and HO with 1, 10, and 100 shakeups (solid lines). Inset: Average energy per spin measured from the ground state vs running time for the SK model ($N=1000$).

Figure 4

Probability density of finding a state with energy $E$ per spin above the ground state for the three-dimensional ($L=10$) Edwards-Anderson model with HO with $n=1$, 10, and 100 consecutive shakeups (solid lines) and $H_{\mathrm{s}\mathrm{h}\mathrm{a}\mathrm{k}\mathrm{e}}=2.2$. Symbols: Best of $n=10$, and 100 single shakeups. Dashed lines: HO combined with renormalization group (RG) techniques. Inset: Typical energies as a function of running times for SA and HO with shakeups.

Figure 5

Distribution of length generated by HO for a two-dimensional TSP with $N=100$. For comparison, we also show the best of 24 quenches, taking the same time as ACD.