I really like peltorator's idea to encourage people to write blog posts about interesting ideas. I don't have new and rare stuff to share, instead, I just want to share some insights about how Simulated Annealing works.
Sorry for cross-posting, but the actual blog could be found here: https://bminaiev.github.io/simulated-annealing. It contains a lot of dynamic plots, which are hard to embed inside the CodeForces blog (and I really suggest checking the blog on the desktop, not the phone).
The blog was inspired by Psyho's Twitter thread. If you haven't seen it — check it out!
Also, I don't really have a lot of real experience with SA, so some facts or ideas in the blog could be wrong. Would be really interested to hear feedback from more experienced SA users :)
I think it's a little bit chaotic, but overall it feels like a good intro to understanding the temp scheduling.
Few comments:
It's worth noting that the temp schedule I've been using is very "safe" (as in, it's easy to get something that produces good results). But you can probably squeeze out slightly better results by trying different schedule shapes.
Optimal temp schedule for "probability of finding optimal answer" is not necessary the same as optimal temp schedule for expected score. I don't have too much experience with searching with the former, but my intuition would be that exponential temp schedule would be better for finding optimal answers while "less exponential" temp schedules would be better for optimizing expected score. At least with "uniform" TSP.
"We can use the fact that the function of the expected score depending on temp_start and temp_end is roughly independent by parameters, so you can first find an optimal temp_end, and then separately find an optimal temp_start.". This is definitely true, although I'd recommend finding temp_start first ;)
I think it's really cool that you have a graph of "acceptance rate" (not an official term). As for "I also think it should be possible to change the temperature automatically based on the acceptance rate, but I’ve never seen somebody doing this. Let me know if you tried it!" — I thought about it a bit at some point, but the reality is that you're switching one problem ("what's the optimal temp shape") for another ("what's the optimal acceptance rate shape"), while the second problem is not any easier. I rarely analyze acceptance rate in the contests, because it's usually just easier to make 10 runs with different temp schedules and take the one that performs the best.
I'm not sure if I'm in minority on this, but 3D graphs feel very unreadable for me. In your case heatmaps convey the same information but in much clearer way (as long as you get the colors right).
Thanks for the feedback!
I thought that the problem "what's the optimal temp shape" doesn't have the same solution for all tasks (at least because if you multiply all scores by constant, you also need to adjust the temperature the same way). But the problem "what's the optimal acceptance rate shape" potentially could have the same solution for all tasks. But maybe I am wrong.
Idea behind 3D graphs is that for each
(temp_start, temp_end)they show a distribution of results, while the heatmap only shows one value (average or probability of minimum in my case). I realize that reading 3D graphs is harder, and if you already know that the function is sane, and one number is enough to describe the function, heatmaps are easier.It might be the case that acceptance rate schedule might have slightly fewer dependencies, but I'd say it's a problem of the very similar complexity as the temperature schedule.
Number of allowed evals/transitions within the time limit, "smoothness" of transitions, distribution and shapes of local extrema, interaction between different transition types are still going to affect you in the same complex way. Overall, I'd advise people to stay away from this topic (unless you're looking for a long research project) and instead focus more exploring either code optimization or various tricks you can apply for problems where SA struggles.