Derivative free optimization by using simulated annealing method

Annealing is the physical process of heating up a solid until it melts, followed by cooling it down until it crystallizes into a state with a perfect lattice. During this process, the free energy of solid is minimized. Practice shows that the cooling must be done carefully in order not to get trapped in a locally optimal lattice structure with crystal imperfections. In combinatorial optimization, we can define a similar process. This process can be formulated as the problem of finding (among a potentially very large number of solutions) a solution with minimal cost. Now, by establishing a correspondence between the cost function and the free energy, and between the solutions and physical states, we can introduce a solution method in the field of combinatorial optimization based on a simulation of the physical annealing process. The resulting method is called Simulated Annealing (SA).