Java Simulated Annealing from Pseudocode

Question

I am currently working on a project (TSP) and am attempting to convert some simulated annealing pseudocode into Java. I have been successful in the past at converting pseudocode into Java code, however I am unable to convert this successfully.

The pseudocode is:

T0(T and a lowercase 0)    Starting temperature
Iter    Number of iterations
λ    The cooling rate

1.  Set T = T0 (T and a lowercase 0)
2.  Let x = a random solution
3.  For i = 0 to Iter-1
4.  Let f = fitness of x
5.  Make a small change to x to make x’
6.  Let f’ = fitness of new point
7.  If f’ is worse than f then
8.      Let p = PR(f’, f, Ti (T with a lowercase i))
9.      If p > UR(0,1) then
10.         Undo change (x and f)
11.     Else
12.         Let x = x’
13.     End if
14.     Let Ti(T with a lowercase i) + 1 = λTi(λ and T with a lowercase i)
15. End for
Output:  The solution x

If somebody could show me a basic mark-up of this in Java I would be extremely grateful - I just can't seem to figure it out!

I am working across multiple classes using a number of functions (which I will not list as it is irrelevant for what I am asking). I already have a smallChange() method and a fitness function - could there be a chance that I would need to create a number of different versions of said methods? For example, I have something like:

public static ArrayList<Integer> smallChange(ArrayList<Integer> solution){

//Code is here.

}

Could I possibly need another version of this method which accepts different parameters? Something along the lines of:

public static double smallChange(double d){

//Code is here.

}

All I require is a basic idea of how this would look when written in Java - I will be able to adapt it to my code once I know what it should look like in the correct syntax, but I cannot seem to get past this particular hurdle.

Ablepsia

Here, you can also take a look at my implementation (parts of it). It's kept very generic. https://mcmap.net/q/453295/-simulated-annealing-tsp – Chuckhole

Answer 1

The basic code should look like this:

public class YourClass {
  public static Solution doYourStuff(double startingTemperature, int numberOfIterations, double coolingRate) {
    double t = startingTemperature;
    Solution x = createRandomSolution();
    double ti = t;

    for (int i = 0; i < numberOfIterations; i ++) {
      double f = calculateFitness(x);
      Solution mutatedX = mutate(x);
      double newF = calculateFitness(mutatedX);
      if (newF < f) {
        double p = PR(); // no idea what you're talking about here
        if (p > UR(0, 1)) { // likewise
          // then do nothing
        } else {
          x = mutatedX;
        }
        ti = t * coolingRate;
      }
    }
    return x;
  }

  static class Solution {
    // no idea what's in here...
  }
}

Now as far as wanting different versions of smallChange() method - totally doable, but you have to read up on inheritance a little bit

Cupule

I have the feeling ti = t * coolingRate; should be ti = ti * coolingRate; – Toritorie

Answer 2

You can compare your answer to the code provided for the textbook
Artificial Intelligence a Modern Approach.

• SimulatedAnnealingSearch.java

Nelan

Answer 3

Also, a Java-based approach to teaching simulated annealing (with sample code) is here:

Neller, Todd. Teaching Stochastic Local Search, in I. Russell and Z. Markov, eds. Proceedings of the 18th International FLAIRS Conference (FLAIRS-2005), Clearwater Beach, Florida, May 15-17, 2005, AAAI Press, pp. 8-13.

Related resources, references, and demos are here: http://cs.gettysburg.edu/~tneller/resources/sls/index.html

Sunstroke

The paper is really worth to read it. It motivates and explains the functionality of Simulated Annealing perfectly using coding examples. The code which they provide can be easily adapted to any kind of optimization problem. – Ahner