A Three-tier Parallel Simulated Annealing algorithm and its application

The paper presents a novel Three-tier Parallel Simulated Annealing algorithm with Memory function (TPSAM) based on multi-core computer with Threading Building Blocks (TBB). The purpose of a new memory function is not to trap into a local optimization. TPSAM is decomposed into three-tier: data decomposition parallelism, task processing parallelism and data composition parallelism and it can improve the convergence rate. TBB offers a rich and complete approach to express parallelism in a C++ program. Sequential Simulated Annealing algorithm with Memory function (SSAM) and TPSAM are implemented based on TBB with C++ for room allocation problem. Experiments show that a better global optimal solution can be reached and the quality of solution is better and the running efficiency is also sooner than before with the TPSAM.