Asymptotical behaviour of several interacting annealing processes (Q1892261)

The author considers parallel generalized annealing processes, which interact by comparing sequentially their instantaneous values of the cost function, and take step by step the best result. This dynamic is compared to independent multiple search, and is shown to be always slower. Interestingly, this parallel algorithm can be asymptotically equivalent to a single annealing process. The mathematical approach considers large deviations estimates, and the (finite time) rate of convergence is measured with the notion of (combinatorial) critical exponent.