Parallel Simulated Annealing Using an Adaptive Resampling Interval

Area of Science:

• Computational Science
• Optimization Algorithms
• Parallel Computing

Background:

• The method by Chu et al. (1999) faced scalability limitations in parallel simulated annealing.
• Adaptive cooling based on variance hindered performance in previous parallel approaches.
• High-dimensional optimization problems require efficient parallel algorithms.

Purpose of the Study:

• To develop a parallel simulated annealing algorithm that overcomes scalability barriers.
• To improve parallel efficiency in terms of both iteration and time for complex functions.
• To introduce an adaptive resampling strategy for enhanced performance.

Main Methods:

• A parallel simulated annealing algorithm was designed, abandoning adaptive cooling based on variance.
• Periodic resampling of states across processors was implemented.
• An adaptive method for tuning the resampling interval based on adoption rate was developed.

Main Results:

• The algorithm achieved 90% parallel efficiency in iteration and 40% in time on a 5000-dimension Rastrigin function using up to 192 processors.
• Abandoning adaptive cooling led to substantial gains in parallel efficiency.
• The adaptive resampling method yielded nearly identical parallel efficiency with higher success rates compared to fixed intervals.

Conclusions:

• The proposed parallel simulated annealing algorithm offers superior scalability and efficiency for high-dimensional optimization.
• The adaptive resampling strategy effectively optimizes performance across different processor configurations.
• This work presents a significant advancement in parallel optimization techniques.