巡回セールスマンの問題を解決するために、シミュレーテッド アニーリング アルゴリズムのこのコードを使用しています。都市の数は比較的少なく、約 30 ～ 40 です。問題は、1000 回目の繰り返しで OutOfMemory エラー メッセージ (INSIDE THE FUNCTION "GO") が表示されることです。なぜこれが起こるのですか？この問題にどう取り組むか？
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;
}
}