1

我正在使用模拟退火算法的代码来解决旅行商问题。城市数量相对较少，即30-40 个左右。问题是在第 1000 次迭代时，我收到 OutOfMemory 错误消息（在函数“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;
    }
}
4

6 回答 6

1

这看起来很糟糕：

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

在实施模拟退火时还要考虑及时随机选择。尤其是当每个社区的移动次数激增时（随着您的城市数量增加），这也可以防止您的记忆也爆炸。

于 2014-01-07T15:47:39.423 回答
1

看起来递归正在产生一个大堆。如果您的代码是正确的并且您想保持递归，您可能会尝试清理一下。我的第一个候选人将是nHood.clear(). 使用分析器来识别你的记忆吞噬者。

增加虚拟机的堆大小应该是最后的手段。我宁愿建议将递归重构为循环。

于 2014-01-07T15:40:28.827 回答
1

除了增加 JVM 的堆大小之外，还有一件事会有所帮助（当您多次进入函数时，可能会有所帮助）是将变量的创建移出，例如nHood,sol和bestSol函数本身之外. 每次进入函数时创建新对象比为以前创建的对象分配新值需要更多的时间和空间。对于递归函数，通常在到达最终函数调用之前，在中间步骤中创建的所有变量都将保存在内存中，因此即使创建变量attempts和accepted类变量，只需在该位置重新设置它们的值，而不是创建新的那些，会有所帮助。

于 2014-01-07T15:40:33.573 回答
0

在 Eclipse 中，转到您的程序的运行配置：

运行 > RunConfiguration... > 参数 > VM 参数：然后键入以下行：

-Xmx500m

这会将虚拟机配置为允许最多 500M 的内存。希望这就足够了

PS - 对于这么多城市，除非您处理每个城市的大量数据，否则您不应该遇到这个问题。

于 2014-01-07T15:35:00.117 回答
0

您是否尝试增加最大堆大小？默认情况下，某些环境将其设置为非常有限（Matlab）。

您可以使用参数 -Xmx4g 将限制设置为 4GB 的堆内存。

增加 Java 中的堆大小 http://docs.oracle.com/cd/E13150_01/jrockit_jvm/jrockit/jrdocs/refman/optionX.html

于 2014-01-07T15:37:30.657 回答
0

当您运行复杂的算法时，这是一个常见问题。尝试增加堆内存大小，请参阅：Increasing Java heap size in Eclipse - using virtual memory

于 2014-01-07T15:33:44.430 回答