Simulated Annealing
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 interface 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
public class City {
private String name;
private Point point;
public City() {
}
public City(String name, int latitude, int longitude) {
this.name = name;
point = new Point((int) latitude, (int) longitude);
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Point getPoint() {
return point;
}
public void setPoint(Point point) {
this.point = point;
}
public double getDistace(City c) {
return point.distance(c.getPoint());
}
}
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.
public class State {
private List cityList;
private double cost;
public State(List cityList) {
setCityList(cityList);
}
public State(State state) {
setCityList(new ArrayList(state.getCityList()));
}
public State() {
setCityList(new ArrayList());
}
public List getCityList() {
return cityList;
}
public void setCityList(List cityList) {
this.cityList = cityList;
calculateCost();
}
public double getCost() {
return cost;
}
public double calculateCost() {
double sum = 0;
int numOfCities = cityList.size();
for (int i = 0; i < numOfCities; i++) {
sum += cityList.get(i).getDistace(cityList.get((i + 1) % numOfCities));
}
cost = sum;
return sum;
}
}
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.
public class TravelingSalesmanProblem implements SimulatedAnnealingProblem {
Random random = new Random();
State currentState;
State nextState;
final static int numOfCities = 30;
@Override
public void init() {
currentState = new State();
for (int i = 0; i < numOfCities; i++) {
City c = new City("c"+i+"", random.nextInt(750),random.nextInt(550));
currentState.getCityList().add(c);
}
currentState.calculateCost();
}
@Override
public double getCostForCurrentState() {
return currentState.getCost();
}
/**
* creates a new state and randomly swaps 2 cities in it
*/
@Override
public void createNextState() {
nextState = new State(currentState);
int i1 = random.nextInt(numOfCities);
int i2 = random.nextInt(numOfCities);
while (i1 == i2) {
i2 = random.nextInt(numOfCities);
}
// randomly swap 2 cities
City tmp = nextState.getCityList().get(i1);
nextState.getCityList().set(i1, nextState.getCityList().get(i2));
nextState.getCityList().set(i2, tmp);
nextState.calculateCost();
}
@Override
public double getCostForNextState() {
return nextState.getCost();
}
@Override
public void goToNextState() {
currentState = nextState;
nextState = null;
}
@Override
public boolean isTotalNumberOfStatesReached() {
return false; //To change body of implemented methods use File | Settings | File Templates.
}
@Override
public String getSolutionString() {
StringBuffer result = new StringBuffer();
for (City c : currentState.getCityList()) {
result.append(c.getName());
if (c != currentState.getCityList().get(numOfCities - 1)) {
result.append(" -> ");
}
}
return result.toString();
}
@Override
public State getCurrentState() {
return currentState;
}
}
and finally the main
public class Main {
public static void main(String[] args) {
TravelingSalesmanProblem tsp = new TravelingSalesmanProblem();
AnnealingScheduler as = new DefaultSAScheduler();
SimulatedAnnealingProblemSolver problemSolver = new SimulatedAnnealingProblemSolver(as, tsp);
problemSolver.solve();
System.out.println(tsp.getSolutionString());
System.out.println(tsp.getCostForCurrentState());
}
}
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