模擬退火

Question

我想在HTML和JavaScript中編寫模擬退火。我想編碼它的位置，但爲簡單起見，我假設所有單元格都在一行中。我有大約30個電池。我在網上尋找一些材料，但我找不到代碼。

我的僞代碼如下：

Simulated_Annealing{ 
    S = initial solution 
    T = initial temperature (>0) 
    while(T > 0) { 
    S’ = pick a random neighbor to S 
    C = cost of S – cost of S’ 
    if(C > 0){ 
     S = S’ 
    } else { 
     r = random number in range [0…1] 
     m = 1/e| C/T | 
     if(r < m) { 
     S = S’ 
     } 
    } 
    T = reduced T; 
    } 
} 

任何幫助表示讚賞。

謝謝。

Answer 1

在GitHub上快速搜索找到https://github.com/ebobby/Jsqueens，它使用模擬退火來解決9皇后問題。這裏的相關代碼：

/** 
* @author Francisco Soto <ebobby@gmail.com> 
*/ 
var SimulatedAnnealing = (function() { 
    var coolingFactor   = 0.0, 
     stabilizingFactor  = 0.0, 
     freezingTemperature  = 0.0, 
     currentSystemEnergy  = 0.0, 
     currentSystemTemperature = 0.0, 
     currentStabilizer  = 0.0, 

     generateNewSolution  = null, 
     generateNeighbor   = null, 
     acceptNeighbor   = null; 

    function _init (options) { 
     coolingFactor   = options.coolingFactor; 
     stabilizingFactor  = options.stabilizingFactor; 
     freezingTemperature  = options.freezingTemperature; 
     generateNewSolution  = options.generateNewSolution; 
     generateNeighbor   = options.generateNeighbor; 
     acceptNeighbor   = options.acceptNeighbor; 

     currentSystemEnergy  = generateNewSolution(); 
     currentSystemTemperature = options.initialTemperature; 
     currentStabilizer  = options.initialStabilizer; 
    } 

    function _probabilityFunction (temperature, delta) { 
     if (delta < 0) { 
      return true; 
     } 

     var C = Math.exp(-delta/temperature); 
     var R = Math.random(); 

     if (R < C) { 
      return true; 
     } 

     return false; 
    } 

    function _doSimulationStep() { 
     if (currentSystemTemperature > freezingTemperature) { 
      for (var i = 0; i < currentStabilizer; i++) { 
       var newEnergy = generateNeighbor(), 
        energyDelta = newEnergy - currentSystemEnergy; 

       if (_probabilityFunction(currentSystemTemperature, energyDelta)) { 
        acceptNeighbor(); 
        currentSystemEnergy = newEnergy; 
       } 
      } 
      currentSystemTemperature = currentSystemTemperature - coolingFactor; 
      currentStabilizer = currentStabilizer * stabilizingFactor; 
      return false; 
     } 
     currentSystemTemperature = freezingTemperature; 
     return true; 
    } 

    return { 
     Initialize: function (options) { 
      _init(options); 
     }, 

     Step: function() { 
      return _doSimulationStep(); 
     }, 

     GetCurrentEnergy: function() { 
      return currentSystemEnergy; 
     }, 

     GetCurrentTemperature: function() { 
      return currentSystemTemperature; 
     } 
    }; 
})();