Simulated Annealing

19
Oct/110

Definition:Simulated Annealing (SA) is a random search technique which exploits an analogy between the way in which metal cools and freezes into a minimum energy crystalline (Busetti, F.)
I am too lazy to get into details but you can check presentations if you want to have more information!
Simulated annealing presentation in pdf format
Simulated annealing presentation in pptx (office 2010) format

Download Simulated Annealing Java Library including source codes

I also created a java library which you can use as you want. Library compounds of two interfaces and one concrete class.

Interfaces;
AnnealingScheduler provides information about the cooling schedule and termination conditions depending on the temperature
SimulatedAnnealingProblem represents the actual problem interface. You can easily integrate your problem using  SimulatedAnnealingProblem interface

Classes;
SimulatedAnnealingProblemSolver is class which solves a given  SimulatedAnnealingProblem using a given  AnnealingScheduler.

Here is an example:
Lets try to solve Travelling Salesman Problem using our library

After downloading the simulated annealing library first lets create POJOS which will be used in problem class

  1.  
  2. public class City {
  3.  
  4.         private String name;
  5.         private Point point;
  6.  
  7.         public City() {
  8.         }
  9.  
  10.         public City(String name, int latitude, int longitude) {
  11.             this.name = name;
  12.             point = new Point((int) latitude, (int) longitude);
  13.         }
  14.  
  15.         public String getName() {
  16.             return name;
  17.         }
  18.  
  19.         public void setName(String name) {
  20.             this.name = name;
  21.         }
  22.  
  23.         public Point getPoint() {
  24.             return point;
  25.         }
  26.  
  27.         public void setPoint(Point point) {
  28.             this.point = point;
  29.         }
  30.  
  31.         public double getDistace(City c) {
  32.             return point.distance(c.getPoint());
  33.         }
  34.  
  35. }
  36.  

Now lets create the State class. Our library is not dependent to any state classes however as the Simulated Annealing is Markov Chain type of method, having the state class makes more sense. State has two elements; cost and cityList. cost is the sum of the distances starting from the first city towards the last city in the cityList. cityList is in order as the cost depends on it.

  1.  
  2. public class State {
  3.     private List<City> cityList;
  4.     private double cost;
  5.  
  6.     public State(List<City> cityList) {
  7.         setCityList(cityList);
  8.     }
  9.  
  10.     public State(State state) {
  11.         setCityList(new ArrayList<City>(state.getCityList()));
  12.     }
  13.  
  14.     public State() {
  15.         setCityList(new ArrayList<City>());
  16.     }
  17.  
  18.     public List<City> getCityList() {
  19.         return cityList;
  20.     }
  21.  
  22.     public void setCityList(List<City> cityList) {
  23.         this.cityList = cityList;
  24.         calculateCost();
  25.     }
  26.  
  27.     public double getCost() {
  28.         return cost;
  29.     }
  30.  
  31.     public double calculateCost() {
  32.         double sum = 0;
  33.         int numOfCities = cityList.size();
  34.         for (int i = 0; i < numOfCities; i++) {
  35.             sum += cityList.get(i).getDistace(cityList.get((i + 1) % numOfCities));
  36.         }
  37.         cost = sum;
  38.         return sum;
  39.     }
  40. }
  41.  

Here is the class impelements SimulatedAnnealingProblem from our library. There are two important functions createNextState and goToNextState. in create next state, it creates a new state from the current state but swaps two cities locations.

  1.  
  2. public class TravelingSalesmanProblem implements SimulatedAnnealingProblem {
  3.  
  4.     Random random = new Random();
  5.     State currentState;
  6.     State nextState;
  7.  
  8.     final static int numOfCities = 30;
  9.  
  10.     @Override
  11.     public void init() {
  12.         currentState = new State();
  13.  
  14.         for (int i = 0; i < numOfCities; i++) {
  15.             City c = new City("c"+i+"", random.nextInt(750),random.nextInt(550));
  16.             currentState.getCityList().add(c);
  17.         }
  18.         currentState.calculateCost();
  19.     }
  20.  
  21.  
  22.     @Override
  23.     public double getCostForCurrentState() {
  24.         return currentState.getCost();
  25.     }
  26.  
  27.     /**
  28.      * creates a new state and randomly swaps 2 cities in it
  29.      */
  30.     @Override
  31.     public void createNextState() {
  32.         nextState = new State(currentState);
  33.         int i1 = random.nextInt(numOfCities);
  34.         int i2 = random.nextInt(numOfCities);
  35.         while (i1 == i2) {
  36.             i2 = random.nextInt(numOfCities);
  37.         }
  38.  
  39.         // randomly swap 2 cities
  40.         City tmp = nextState.getCityList().get(i1);
  41.         nextState.getCityList().set(i1, nextState.getCityList().get(i2));
  42.         nextState.getCityList().set(i2, tmp);
  43.         nextState.calculateCost();
  44.     }
  45.  
  46.     @Override
  47.     public double getCostForNextState() {
  48.         return nextState.getCost();
  49.     }
  50.  
  51.     @Override
  52.     public void goToNextState() {
  53.         currentState = nextState;
  54.         nextState = null;
  55.     }
  56.  
  57.     @Override
  58.     public boolean isTotalNumberOfStatesReached() {
  59.         return false;  //To change body of implemented methods use File | Settings | File Templates.
  60.     }
  61.  
  62.     @Override
  63.     public String getSolutionString() {
  64.         StringBuffer result = new StringBuffer();
  65.         for (City c : currentState.getCityList()) {
  66.             result.append(c.getName());
  67.             if (c != currentState.getCityList().get(numOfCities – 1)) {
  68.                 result.append(" -> ");
  69.             }
  70.         }
  71.         return result.toString();
  72.     }
  73.  
  74.  
  75.     @Override
  76.     public State getCurrentState() {
  77.         return currentState;
  78.     }
  79. }
  80.  

and finally the main

  1.  
  2. public class Main {
  3.    
  4.  
  5.     public static void main(String[] args) {
  6.  
  7.         TravelingSalesmanProblem tsp = new TravelingSalesmanProblem();
  8.         AnnealingScheduler as = new DefaultSAScheduler();
  9.  
  10.         SimulatedAnnealingProblemSolver problemSolver = new SimulatedAnnealingProblemSolver(as, tsp);
  11.         problemSolver.solve();
  12.  
  13.         System.out.println(tsp.getSolutionString());
  14.         System.out.println(tsp.getCostForCurrentState());
  15.     }
  16. }
  17.  

For fine tuning you can use setters in AnnealingScheduler class.

Outcome should be something like :
c13 -> c6 -> c11 -> c4 -> c9 -> c17 -> c16 -> c22 -> c15 -> c1 -> c8 -> c10 -> c20 -> c0 -> c28 -> c12 -> c27 -> c24 -> c5 -> c2 -> c14 -> c7 -> c3 -> c21 -> c18 -> c25 -> c29 -> c19 -> c23 -> c26
3164.855706704416

Download Simulated Annealing Java Library including source codes

Tagged as: , ,
No Comments

Pages

Categories

My Own Sites

Other sites you may interested

Calendar

February 2012
M T W T F S S
« Nov    
 12345
6789101112
13141516171819
20212223242526
272829  

Most Popular Tags

action game AI artificial intelligence Artificial intelligence in real-time strategy games BVH tree c++ cell processor cmath computer graphics cuda decision making direct input direct sound directX Distributed Neural Networks fast math fast sine function fast sin function fast sinus function fuzzy logic game game programming google Group Work interview KD tree long term decision making in strategy games master thesis MSc Dissertation MSc Project neural networks NVidia Ogre3D optimisation particle system play station 3 pooling ps3 python questions raytracing ray tracing ray tracing on cell real time ray tracing RTS Games shooting game short term decision making in strategy games Smart Attack University of Abertay Dundee using xml in games