Junhao Zhou, Hong Xiao, Hao Wang, Hong-Ning Dai
In: Gervasi O. et al. (eds) Computational Science and Its Applications – ICCSA 2016. ICCSA 2016. Lecture Notes in Computer Science, vol 9787. Springer
Publication year: 2016

The simulated annealing algorithm (SAA) is a well-established approach to the approximate solution of combinatorial optimisation problems. SAA allows for occasional uphill moves in an attempt to reduce the probability of becoming stuck in a poor but locally optimal solution. Previous work showed that SAA can find better solutions, but it takes much longer time. In this paper, in order to harness the power of the very recent hybrid Many Integrated Core Architecture (MIC), we propose a new parallel simulated annealing algorithm customised for MIC. Our experiments with the Travelling Salesman Problem (TSP) show that our parallel SAA gains significant speedup.

Leave a Reply

Your email address will not be published. Required fields are marked *