3

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

どんな助けでも大歓迎です。

ありがとう。

4

1 に答える 1

15

GitHub でクイック検索を行うと、シミュレーテッド アニーリングを使用して 9 クイーンの問題を解決するhttps://github.com/ebobby/Jsqueensが見つかりました。関連するコードは次のとおりです。

/**
 * @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;
        }
    };
})();
于 2012-04-30T03:32:20.113 に答える