Optimization and benchmarking of the thermal cycling algorithm

Optimization plays a significant role in many areas of science and technology. Most of the industrial optimization problems have inordinately complex structures that render finding their global minima a daunting task. Therefore, designing heuristics that can efficiently solve such problems is of utmost importance. In this paper we benchmark and improve the thermal cycling algorithm [Phys. Rev. Lett. 79, 4297 (1997)] that is designed to overcome energy barriers in nonconvex optimization problems by temperature cycling of a pool of candidate solutions. We perform a comprehensive parameter tuning of the algorithm and demonstrate that it competes closely with other state-of-the-art algorithms such as parallel tempering with isoenergetic cluster moves, while overwhelmingly outperforming more simplistic heuristics such as simulated annealing.

Figure 1

The percentage of frozen spins in TCA for the system size $L=12$ versus inverse temperature $\beta$. The colors on the lines represent different pool sizes $N_p$. With only a few walkers, there is more chance of agreement between the spin values at a given site, hence the system collapses to a single walker early on during the annealing process, whereas with too many walkers, the freezing mechanism ceases to function.

Figure 2

Optimization of total sweeps for PT$+$ICM using various system sizes. The minimum TTS points correspond to the optimal sweep values.

Figure 3

(a) Parameter tuning of the thermal cycling algorithm using DCL problems of linear size $L=12$. The figure shows the number of cycles $N_c$ versus the number of annealing steps $N_T$, with the rest of the parameters fixed to the values listed in Table 1. The color map shows the TTS values. Two minima with similar depths are observed. The lowest minimum corresponds to the optimal parameters. (b) Optimization of the pool size $N_p$ of TCA for a various system sizes. Above the horizontal dashed line, none of the problems can be solved in 100 attempts. Across all problem sizes studied $N_p=16$ is sufficient.

Figure 4

Main panel: TTS of the thermal cycling algorithm versus the linear problem size $L$. Various quenching schemes consisting of SSGM, DSRM, and LKCM are displayed. The lines represent a linear fit in the logarithmic (base 10) scale to the five largest system sizes. We observe a sizable constant speedup with the LKCM although it diminishes at larger system sizes. Inset: Scaling exponent $b$ corresponding to the slope of the linear fits in the main panel. The height of the boxes represents the error bars. The best scaling is obtained when TCA is used in conjunction with DSRM. These moves are simple enough to cause minimal overhead, yet complex enough to considerably reduce the number of the metastable states.

Figure 5

Comparison between the scaling results of the studied algorithms using the DCL problems. (a) TTS versus the linear problem size $L$ for various algorithms. Note that TTS is given on a logarithmic (base 10) scale. (b) Scaling exponent $b$ in Eq. (5) for various algorithms. The height of the boxes represents the error bars. The TCA data points correspond to the best performing quenching scheme, i.e., DSRM, shown in Fig. 4. TCA scales better than SA and PT, and even comparable to SQA within the error bars. PT$+$ICM shows the best scaling. However, the latter is due to the great efficiency of the ICM updates in sampling the DCL phase space which is nonrepresentative for denser industrial problems. Unlike in TCA, the addition of DSRM quenches to SA (SA$+$DSRM) does not improve the performance.