Simulated Annealing

* Simulated Annealing is a good algorithm to avoid local optimum and search for the global optimum.
* It can have many applications: For eg. TSP, AI, training neural nets etc.
* Simulated annealing mimics the annealing process to solve an optimization problem.
* It uses a temperature parameter that controls the search.
* The temperature parameter typically starts off high and is slowly "cooled" or lowered in every iteration.
* At each iteration a new point is generated (randomly for example) and its distance from the current point is proportional to the temperature. .
* If the new point has a better function value it replaces the current point and iteration counter is incremented. It is possible to accept and move forward with a worse point.
* The probability of doing so is directly dependent on the temperature. This unintuitive step sometime helps identify a new search region in hope of finding a better minimum.

Codes of the Java files included in the program are given below:

Constants.java

In [ ]:
package sa;

public class Constants {

	private Constants(){
		
	}
	
	public static final double MIN_COORDINATE = -2;
	public static final double MAX_COORDINATE = 2;
	public static final double MIN_TEMPERATURE = 1;
	public static final double START_TEMPERATURE = 100;
	public static final double COOLING_RATE = 0.02;
}

SimulatedAnnealing.java

In [ ]:
package sa;

import java.util.Random;

public class SimulatedAnnealing {

	private Random randomGenerator;
	private double currentCoordinateX;
	private double nextCoordinateX;
	private double bestCoordinateX;
	
	//Constructor
	public SimulatedAnnealing(){
		this.randomGenerator = new Random();
	}
	
	//Method to find the optimum
	public void findOptimum(){
		
		double temperature = Constants.START_TEMPERATURE;
		
		while( temperature > Constants.MIN_TEMPERATURE ){
			
			nextCoordinateX = getRandomX();
			
			double currentEnergy = getEnergy(currentCoordinateX); //Current energy
			double newEnergy = getEnergy(nextCoordinateX); //New energy
			
			
			if( acceptanceProbability(currentEnergy,newEnergy,temperature)> Math.random()){
			//if its a better move, acceptanceProbability= 1 which is always> Math.random() 
			//else its < Math.random()				
				currentCoordinateX = nextCoordinateX;
			}
			
			// update the bestCoordinateX
			if( f(currentCoordinateX) < f(bestCoordinateX)){ //to find global min
			//if( f(currentCoordinateX) > f(bestCoordinateX)){ //to find global max
				bestCoordinateX = currentCoordinateX;
			}
			
			// On every iteration we decrease temperature
			temperature *= 1 - Constants.COOLING_RATE;	
		}
		
		System.out.println("Global extreme is: x="+bestCoordinateX +
							"f(x) = " + f(bestCoordinateX));
		
	}

	private double getEnergy(double x) {
		return f(x);
	}

	//Generate random X within the range MIN_COORDINATE to MAX_COORDINATE
	private double getRandomX() {
		return randomGenerator.nextDouble()*(Constants.MAX_COORDINATE-Constants.MIN_COORDINATE)
					+ Constants.MIN_COORDINATE;
	}

	private double f(double x){
		return (x-0.3)*(x-0.3)*(x-0.3)-5*x+x*x-2;
	}
	
	public double acceptanceProbability(double energy, double newEnergy, double temperature){
		
		// If the new solution is better, accept it
		if (newEnergy < energy) {
			return 1.0;
		}
		
		// If the new solution is worse, calculate an acceptance probability
		// T is small: we accept worse solutions with lower probability!
		return Math.exp((energy - newEnergy) / temperature);
	}
}

Main.java

In [ ]:
package sa;

public class Main {

	public static void main(String[] args) {
		
		SimulatedAnnealing annealing = new SimulatedAnnealing();
		annealing.findOptimum();
		
	}
}

Output of the program is :

Global extreme is: x=1.2107010315381097f(x) = -5.832394255283017

You can download the complete source code here : Source Code