シミュレーテッドアニーリング

Question

HTMLとJavaScriptでシミュレーテッドアニーリングをコーディングする必要があります。私は配置のためにそれをコーディングしたいが、簡単にするために、すべてのセルが1つの行にあると仮定している。私は約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でクイック検索を実行すると、が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; 
     } 
    }; 
})();