Difference between revisions of "Distributed Simulated Annealing"

From SCECpedia
Jump to navigationJump to search
Line 1: Line 1:
 +
== Serial SA Algorithm ==
 +
* s = s0; e = E(s)
 +
* sbest = s; ebest = e
 +
* k = 0
 +
* while k < max_iterations:
 +
** snew = neighbour(s)
 +
** enew = E(snew)
 +
** if P(e, enew, temperature) > random(); then
 +
*** s = snew; e = enew
 +
** if enew < ebest
 +
*** sbest = snew; ebest = enew
 +
** k++'
 +
 +
== Parallel SA Algorithm ==
 +
* s = s0; e = E(s)
 +
* sbest = s; ebest = e
 +
* k = 0
 +
* while k < max_iterations
 +
** on n processors, do nSubIterations iterations of serial SA
 +
** find processor with best overall (lowest energy) solution, sbest
 +
** redistribute sbest, ebest to all processors
 +
** k += nSubIterations
 +
 
== Performance Graphs ==
 
== Performance Graphs ==
 
{| border="1"
 
{| border="1"

Revision as of 22:23, 6 September 2011

Serial SA Algorithm

  • s = s0; e = E(s)
  • sbest = s; ebest = e
  • k = 0
  • while k < max_iterations:
    • snew = neighbour(s)
    • enew = E(snew)
    • if P(e, enew, temperature) > random(); then
      • s = snew; e = enew
    • if enew < ebest
      • sbest = snew; ebest = enew
    • k++'

Parallel SA Algorithm

  • s = s0; e = E(s)
  • sbest = s; ebest = e
  • k = 0
  • while k < max_iterations
    • on n processors, do nSubIterations iterations of serial SA
    • find processor with best overall (lowest energy) solution, sbest
    • redistribute sbest, ebest to all processors
    • k += nSubIterations

Performance Graphs

Dataset ncal_constrained ncal_unconstrained state_constrained state_unconstrained
Energy vs Time ncal_constrained_e_vs_t.small.png ncal_unconstrained_e_vs_t.small.png state_constrained_e_vs_t.small.png state_unconstrained_e_vs_t.small.png
Avg Energy vs Time ncal_constrained_avg_e_vs_t.small.png ncal_unconstrained_avg_e_vs_t.small.png state_constrained_avg_e_vs_t.small.png state_unconstrained_avg_e_vs_t.small.png
Serial Time vs Parallel Time ncal_constrained_st_vs_pt.small.png ncal_unconstrained_st_vs_pt.small.png state_constrained_st_vs_pt.small.png state_unconstrained_st_vs_pt.small.png
Time Speedup vs Time ncal_constrained_spd_vs_t.small.png ncal_unconstrained_spd_vs_t.small.png state_constrained_spd_vs_t.small.png state_unconstrained_spd_vs_t.small.png
Std. Dev. vs Time ncal_constrained_std_dev_vs_t.small.png ncal_unconstrained_std_dev_vs_t.small.png state_constrained_std_dev_vs_t.small.png state_unconstrained_std_dev_vs_t.small.png
Improvement vs Energy ncal_constrained_imp_vs_t.small.png ncal_unconstrained_imp_vs_t.small.png state_constrained_imp_vs_t.small.png state_unconstrained_imp_vs_t.small.png
Retrieved from "https://strike.scec.org/scecwiki/index.php?title=Distributed_Simulated_Annealing&oldid=3398"