Simulated Annealing algorithm from "Programming Collective Intelligence" by Toby Segaran.

gistfile1.txt

public class SimulatedAnnealing
{
    public static final double DEFAULT_TEMPERATURE = 10000;
	
	public static final double DEFAULT_COOL_RATE = 0.95;
	
	static public double[] optimize(double[][] domain, SolutionCost costF, double stepSize)
	{
		return optimize(domain, costF, DEFAULT_TEMPERATURE, DEFAULT_COOL_RATE, stepSize);
	}
	
	
	// example cost function: return 10000 - sim_results.changeRatio;
	static public double[] optimize(double[][] domain, SolutionCost costF, double temperature, double coolRate, double stepSize)
	{
		double[] soln = new double[domain.length];
		double[] best;
		double[] current;
		double solnCost = Double.MAX_VALUE;
		double bestCost = Double.MAX_VALUE; // i added best soln, not in orig alg
		double currentCost;
		double p; // probability to take worse soln
		
		// init with some random values
		for (int i=0; i < domain.length; i++)
		{
			soln[i] = Math.random() * (domain[i][1]-domain[i][0]);
		}
		best = soln.clone();
		
		int idx;
		double dir;
		double v;
		int pass = 0;
		while (temperature > 0.1)
		{
			System.out.println("[" + (++pass) + "] " + temperature);
			// choose a param
			idx = (int) Math.round(Math.random() * (soln.length-1));
			
			// choose direction
			dir = stepSize * (Math.random() > 0.5 ? 1 : -1);
			
			// copy soln, change a value, ensure value is valid
			current = soln.clone();
			v = current[idx] + dir;
			v = Math.max(domain[idx][0], v);
			v = Math.min(domain[idx][1], v);
			current[idx] = v;
			currentCost = costF.getCost(current);
			
			// swith if cost is less 
			if (currentCost < solnCost) 
			{
				soln = current;
				solnCost = currentCost;
				System.out.println(" + cost: " + solnCost);
				System.out.println(" + soln: " + Formatter.toString(soln));
			} 
			else 
			{
				// annealing thing says take the lesser soln
				p = Math.pow(Math.E, (-currentCost-solnCost)/temperature);
				if (Math.random() < p) 
				{
					soln = current;
					solnCost = currentCost;
					System.out.println(" - cost: " + solnCost);
					System.out.println(" - soln: " + Formatter.toString(soln));
				}
			}
			if (solnCost < bestCost) 
			{
				best = soln.clone();
				bestCost = solnCost;
				System.out.println(" * cost: " + bestCost);
				System.out.println(" * soln: " + Formatter.toString(best));
			} 
			temperature *= coolRate;
		}
		return best;
	}
}