For a prob­lem I’m work­ing on I got stuck onto the clas­si­cal sit­u­a­tion of local max­i­mum. After trying to work around the prob­lem in sev­eral more or less cre­ative ways, I thought of the sim­u­lated anneal­ing algo­rithm. Con­sid­er­ing it’s been a while since I last saw it I tried to search for it on the web and sur­pris­ingly there is not much stuff about it, and the few bits I found are often con­trad­dic­tory. After quite a lot of dig­ging I decided to write about it here. As a warn­ing I should prob­a­bly say that there will be dig­ging into some basic sta­tis­tic and com­plex­ity analy­sis, as well as a quick formal intro­duc­tion to the prob­lem of the knap­sack. You should be able to follow even if you don’t know noth­ing about those topics, but having some foun­da­tions in these areas would be of great help.
(Con­tinue reading…)