Hi all
I'm pretty new to heuristic things and I tried to implement both Hill Climbing and Simulated Annealing for this begginner-friendly and considered-as-a-tutorial problem for heuristic contests on AtCoder https://atcoder.jp/contests/intro-heuristics/tasks/intro_heuristics_a.
It looks like Hill Climbing and Simulated Annealing yield similar results ( SA: https://atcoder.jp/contests/intro-heuristics/submissions/64189473, HC: https://atcoder.jp/contests/intro-heuristics/submissions/64189544 ).
I'm trying to understand why, and the only reason I could come up with was that there are "loads of neighbours" for each state ((26-1)*365 neighbours per state) so it's basically impossible to get stuck in a local optimum? I guess it could be deeper than that — I'm sure there are actually local optima (it makes sense when you read the problem), so what am I missing? Why wouldn't SA yield to better results here? Maybe I just implemented it wrong? Maybe Hill Climbing would only be bad if the algorithms were allowed to run for 15 hours? I checked locally the initial temperature and temperature decay, there are some "bad transitions accepted" early on and then very few when we get close to 2 seconds. So I don't think the problem is that my temperature + temperature decay are set up such that I'm actually never accepting bad transitions and hence degenerating to HC.
Any help is appreciated, keep it beginner friendly please :). I should add I'm not really looking for micro optimisation tips (although they're welcome*), but rather trying to grasp a better understanding of when SA >>>>> HC.
*if you just say code everything in C it'll be ever so slightly faster than C# AOT and will yield better results for both HC and SA, it won't be really helpful, I know that.
Code everything in brainfuck it'll be ever so slightly faster than C# AOT and will yield better results for both HC and SA.
Have you read the editorial? (https://img.atcoder.jp/intro-heuristics/editorial.pdf)
(You can translate it using google translate. Google translate doesn't know about simulated annealing and usually translates it to "bake" or "cook" when translating from Japanese).
Your temperature is way too low, the editorial seems to suggest a starting temperature of 2000 and a final temperature of 600.
Instead of multiplying the current temperature by a constant every iteration, it is probably better to set the current temperature to
t_initial * pow(t_final / t_initial, elapsed() / time_limit).If you don't know what the initial and final temperatures should be, just set the initial temperature very high (say
1e6) and the final temperature very low (1e-6).Thanks for the answer. I had not read the editorial because it was in Japanese but I'll give it a read after passing it through some translation app, good call.
I made the changes you suggested and this literally gave me a 40% increase in score. https://atcoder.jp/contests/intro-heuristics/submissions/64191286 . Thank you very much, I did not expect the "hyperparmeters" to matter that much and as a matter of fact I take back my words, I was probably very much wrong when I said my SA was not degenerating to HC.