3 ms·
The article mentions the problem of "local minimums". The author suggests occasionally accepting worse solutions, in order to escape from such. "The hope here i
by gort 10y ago
The article mentions the problem of "local minimums". The author suggests occasionally accepting worse solutions, in order to escape from such. "The hope here is that by following this worse solution, we can eventually get to the global minimum." This is good but one may wish to take it further.
I once messed with something called "metropolis coupling", where you run multiple threads in parallel, with different thresholds for how often they accept worse solutions, i.e. one thread is "cold", one is slightly "hotter", and so on. If a hot thread's current solution is better than the solution of the neighbouring colder thread, the solutions are swapped. In this way the coldest thread (which is the one we're paying attention to) gets pulled out of the local minimum.
As I say, I messed with this once and it did seem to help. It seems to have been developed for inference in evolutionary phylogenetics, and is perhaps a bit obscure?
- tekromancr 10y agoThat's actually pretty brilliant. I haven't ever heard of metropolis coupling before, but I can see how it would break the algo out of a local minimum. Also, klaatu barada nikto.
- ChronosKey 10y agoHi, author here: Yep, this is the sort of thing we study in our cooperative and adaptive algorithms class. Similar techniques to what you suggest are shown here https://books.google.ca/books?id=G5ML5EYch94C&pg=PA88&lpg=PA88&dq=cooperative+SA+cosa&source=bl&ots=DjpEgTvDab&sig=LSBRppSNQqhr0qVjqRikt60b36c&hl=en&sa=X&ved=0ahUKEwi0hs39vP3NAhVrw4MKHbd0CEsQ6AEIHDAA#v=onepage&q=cooperative%20SA%20cosa&f=false https://books.google.ca/books?id=G5ML5EYch94C&pg=PA88&lpg=PA...
- klausnrooster 10y agoLooks neat but I gave up on it converging on my new laptop. I'm going to port it to rebol2. This bit confuses me: random.choice(range(0, i) + range(i+1, 4)) how is that different from random.choice(range(0, 4))? Obviously no Pythonista, but playing around in the REPL I see no diff.
- klausnrooster 10y agoDuh. Where is the button that reverses the passage of time?
- murbard2 10y agoThis has the advantage of working as a sampling strategy, not just an optimization strategy. It is useful when the mass of your distribution is concentrated in a region that may be hard to find with a random walk. https://en.wikipedia.org/wiki/Parallel_tempering https://en.wikipedia.org/wiki/Parallel_tempering Markov-chain Monte-Carlo sampling gives a theoretical underpinning which explains why simulated annealing works in optimization.