OutOfMemory issue with simulated annealing code

Question

I am using this code of the simulated annealing algorithm in order to solve the traveling salesmen problem. The number of cities is relatively small, i.e. around 30-40. The problem is that at the 1000th iteration I receive the OutOfMemory error message (INSIDE THE FUNCTION "GO"). Why does this happen? How to tackle this issue?

package tsptw.logic;

import java.util.ArrayList;
import java.util.Random;

import tsptw.logic.objects.Point;
import tsptw.logic.objects.Solution;

public class SimulatedAnnealing {

    private static final double COOLING_ALPHA = 0.95;
    private static Random rand = new Random();
    private static int i = 0;

    public static Solution solve(Point start, ArrayList<Point> points) {
        Solution sol = Solution.randomSolution(start, points);
        double t = initialTemperature(sol, 1000);
        int frozen = 0;
        System.out.println("-- Simulated annealing started with initial temperature " +
                t + " --");
        return go(sol, t, frozen);
    }

    private static Solution go(Solution solution, double t, int frozen) {
        if (frozen >= 3) {
            return solution;
        }
        i++;

        Solution bestSol = solution;
        System.out.println(i + ": " + solution.fitness() + " " + solution.time() + " "
                + solution.penalty() + " " + t);
        ArrayList<Solution> nHood = solution.nHood();

        int attempts = 0;
        int accepted = 0;

        while (!(attempts == 2 * nHood.size() || accepted == nHood.size())) {
            Solution sol = nHood.get(rand.nextInt(nHood.size()));
            attempts++;

            double deltaF = sol.fitness() - bestSol.fitness();
            if (deltaF < 0 || Math.exp(-deltaF / t) > Math.random()) {
                accepted++;
                bestSol = sol;
                nHood = sol.nHood();
            }
        }

        frozen = accepted == 0 ? frozen + 1 : 0;

        double newT = coolingSchedule(t);
        return go(bestSol, newT, frozen);
    }

    private static double initialTemperature(Solution solution, double t) {
        ArrayList<Solution> nHood = solution.nHood();
        int accepted = 0;
        int attempts = nHood.size();
        for (Solution sol : nHood) {
            double deltaF = sol.fitness() - solution.fitness();
            if (deltaF < 0 || Math.exp(-deltaF / t) > Math.random()) {
                accepted++;
            }
        }
        double r = ((double)accepted) / attempts;

        if (r >= 0.94 && r <= 0.96) {
            return t;
        }
        return initialTemperature(solution, r > 0.95 ? t/2 : 2*t);
    }

    private static double coolingSchedule(double t) {
        return COOLING_ALPHA * t;
    }
}

Answer 1

It's a common problem when you run complicated algorithm. Try to increase the heap memory size see this: Increasing Java heap size in Eclipse - using virtual memory

Answer 2

In Eclipse, go to the Run Configuration for your program:

Run > RunConfiguration... > Arguments > VM arguments: and then type the line:

-Xmx500m

This will configure the virtual machine to allow up to 500M of memory. Hopefully that will be enough

P.S. - with that number of cities, you shouldn't be experiencing this issue unless you are dealing with large amounts of data for each city.

Answer 3

Did you try to increase maximum heap size? Some enviroments set it quite limited by default (Matlab).

You can use parameter -Xmx4g to set limit to 4GB of heap memory.

Increase heap size in Java http://docs.oracle.com/cd/E13150_01/jrockit_jvm/jrockit/jrdocs/refman/optionX.html

Answer 4

It looks like the recursion is producing a large heap. If your code is correct and you want to keep the recursion you might try to clean up a little bit. My first candidate would be the nHood.clear(). Use a profiler to identify your memory eaters.

Increasing the VM's heap size should be the last resort. I would rather suggest to refactor the recursion into a loop.

Answer 5

Besides increasing the heap size of the JVM, one thing that would help (possibly quite a bit, when you're going into the function many times) is to move out the creation of the variables, such as nHood, sol and bestSol outside of the function itself. Creating new objects each time you go into the function takes more time and space than assigning new values to previously created objects. With recursive functions, often all the variables created in intermediate steps, before reaching the final function call, will be kept in memory, so even making the variables attempts and accepted class variables, and just re-setting their values at that place, instead of creating new ones, would help.

Answer 6

This looks bad:

ArrayList<Solution> nHood = solution.nHood();
// How many solutions do you have in memory?
// How much memory does 1 solution take?

Also look into just in time random selection when implementing simulated annealing. Especially when the number of moves per neighborhood blow up (as your number of cities increases), this prevents your memory from blowing up too.