OutOfMemory問題與模擬退火代碼

我使用this code的模擬退火算法來解決旅行商問題。城市數量相對較少，即30-40左右。問題是，在第1000次迭代中，我收到OutOfMemory錯誤消息（INSIDE THE FUNCTION「GO」）。爲什麼會發生？如何解決這個問題？OutOfMemory問題與模擬退火代碼

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; 
    } 
}

來源

2014-01-07 Klausos Klausos

JVM參數？你有堆轉儲和分析嗎？ – Markus

這是運行復雜算法時常見的問題。嘗試增加堆內存大小看到這一點：Increasing Java heap size in Eclipse - using virtual memory

來源

2014-01-07 15:33:44 Lucas

在Eclipse中，去運行配置爲你的程序：

運行> RunConfiguration ...>參數> VM參數：然後鍵入行：

-Xmx500m

這將配置虛擬機以允許高達500M的內存。希望這將是足夠的

P.S. - 有了這麼多城市，除非您處理每個城市的大量數據，否則您不應該遇到這個問題。

來源

2014-01-07 15:35:00 MaineCoder

也許發生這種情況是因爲我對不同的城市組多次執行算法。 –

您是否嘗試增加最大堆大小？一些環境默認情況下將其設置得非常有限（Matlab）。

您可以使用參數-Xmx4g將限制設置爲4GB的堆內存。

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

來源

2014-01-07 15:37:30 karna7

它看起來像遞歸產生一大堆。如果你的代碼是正確的，你想保持遞歸，你可以嘗試清理一下。我的第一個候選人將是nHood.clear()。使用分析器來識別你的記憶食器。

增加VM的堆大小應該是最後的手段。我寧願建議將遞歸重構爲循環。

來源

2014-01-07 15:40:28

除了增加JVM的堆大小之外，有一件事會幫助（可能相當多，當你進入函數多次時）是移除變量的創建，如nHood,sol和功能本身之外的bestSol。每次進入函數時創建新對象比向先前創建的對象分配新值需要更多的時間和空間。對於遞歸函數，在達到最終函數調用之前，通常在中間步驟創建的所有變量都將保存在內存中，因此即使將類變量attempts和accepted設爲變量，並且只是在該位置重新設置它們的值，而不是創造新的，會有所幫助。

來源

2014-01-07 15:40:33

情況不妙：

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

還應考慮just in time random selection實現模擬退火時。特別是當每個鄰里的移動次數爆炸時（隨着城市數量的增加），這可以防止你的記憶也被炸燬。

來源

2014-01-07 15:47:39

OutOfMemory問題與模擬退火代碼

回答

相關問題