Abstract
The simulated annealing algorithm (SAA) is a wellestablished 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.
Original language | English |
---|---|
Title of host publication | Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings |
Editors | Ana Maria A.C. Rocha, Shangguang Wang, David Taniar, Beniamino Murgante, Carmelo M. Torre, Elena Stankova, Bernady O. Apduhan, Sanjay Misra, Osvaldo Gervasi |
Publisher | Springer-Verlag GmbH and Co. KG |
Pages | 239-250 |
Number of pages | 12 |
ISBN (Print) | 9783319421070 |
DOIs | |
Publication status | Published - Jul 2016 |
Externally published | Yes |
Event | 16th International Conference on Computational Science and Its Applications, ICCSA 2016 - Beijing, China Duration: 4 Jul 2016 → 7 Jul 2016 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 9787 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 16th International Conference on Computational Science and Its Applications, ICCSA 2016 |
---|---|
Country/Territory | China |
City | Beijing |
Period | 4/07/16 → 7/07/16 |
Bibliographical note
Funding Information:The work described in this paper was partially supported by Macao Science and Technology Development Fund under Grant No. 096/2013/A3 and the NSFC-Guangdong Joint Fund under Grant No. U1401251 and Guangdong Science and Technology Program under Grant No.2015B090923004.
Publisher Copyright:
© Springer International Publishing Switzerland 2016.
Keywords
- MIC optimization
- Parallel computing
- Simulated annealing