Related Experiment Videos
Sample-sort simulated annealing
Dale R Thompson1, Griff L Bilbro
1Computer Science and Computer Engineering Department, University of Arkansas, Fayetteville, AR 72701, USA. d.r.thompson@ieee.org
Summary
A novel Sample-Sort algorithm extends simulated annealing (SA) across multiple samplers. This parallel approach maintains convergence properties and shows comparable performance to serial SA for global optimization problems.
Area of Science:
- Computer Science
- Artificial Intelligence
- Optimization Algorithms
Background:
- Simulated Annealing (SA) is a widely used probabilistic technique for approximating the global optimum of a given function.
- Serial SA algorithms can be computationally intensive, particularly for complex global optimization problems.
Purpose of the Study:
- To propose a parallelized version of the simulated annealing algorithm, named Sample-Sort.
- To evaluate the performance and convergence properties of Sample-Sort compared to traditional serial SA.
Main Methods:
- Sample-Sort replaces the sequential temperature schedule of SA with an array of samplers operating at static temperatures.
- A set of samplers, utilizing a biased generator, samples the same distribution as serial SA to preserve convergence.
- The algorithm was tested on a suite of global optimization problems.
Main Results:
- Sample-Sort demonstrated comparable performance to serial SA when sufficient iterations per sampler were utilized.
- The parallel nature of Sample-Sort offers potential computational advantages when the evaluation phase is dominant.
Conclusions:
- Sample-Sort provides a viable parallel processing approach for simulated annealing.
- This method can enhance computational efficiency for global optimization tasks, especially in evaluation-heavy scenarios.