* 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:
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; }
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); } }
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