Source: methods/Annealing.js

import Result from '../_common/Result.js';
import BufferedReply from '../_common/BufferedReply';

/**
 * Class for solving problems using simulated annealing
 */
export class AnnealingSolver{
  constructor(workerInterface){
    this._workerInterface = workerInterface;

    // buffers messages to reduce communication overhead while sending computation progress every cycle
    this._bufferedReply = new BufferedReply(this._workerInterface, 'progressBuffered', 75);
  }

  /**
   * Main function method, solves the problem using simulated annealing
   * @param  {object} problem type of problem
   * @param  {object} params  problem parameters
   * @return {Result} final configuration, its fitness and number of iterations
   */
  solve(problem, params){
      var currentTemp = +params.start_temp;
      var currentConfiguration = problem.getConfiguration();
      var currentCost = problem.evaluateMaximizationCost(currentConfiguration);
      var currentNeighbour = currentConfiguration.getNeighbour();
      var counter = 0;

      this._workerInterface.reply('init', { numberOfIterations: Math.ceil((Math.log(+params.min_temp) - Math.log(+params.start_temp)) / Math.log(+params.cool_coef))});

      // main cycle depending on temperature
      while (currentTemp > +params.min_temp) {
          //inner cycle
          for(var i = 0; i < +params.innerCycle; i++){
              var neighbourCost = problem.evaluateMaximizationCost(currentNeighbour)
              //next is better
              if(currentCost < neighbourCost){
                  currentConfiguration = currentNeighbour;
                  currentCost = neighbourCost;
              }
              // next is worse
              else if(Math.random() < Math.exp((neighbourCost - currentCost) / currentTemp)){
                      currentConfiguration = currentNeighbour;
                      currentCost = neighbourCost;
              }
              currentNeighbour = currentConfiguration.getNeighbour();
              counter++;
          }
          currentTemp *= +params.cool_coef;
          this._bufferedReply.addMessageWithAutoFlush( problem.transformMaximizationToRealCost(currentCost) );
      }
      this._bufferedReply.flush();
      return new Result(problem.getResult(currentConfiguration), problem.transformMaximizationToRealCost(currentCost), counter);
  }
  /**
   * Function to compute starting temperature
   * @param  {object} problem type of problem
   * @param  {object} params  problem parameters
   * @return {int} calculated starting temperature
   */
  computeStartingTemp(problem){
      var currentConfiguration = problem.getConfiguration();
      var currentNeighbour = currentConfiguration.getNeighbour();
      var arrayOfEnergyStates = [];

      var wantedPropability = 0.5;
      var currentPropability = 0;

      var maxSum;
      var minSum;
      var newEnergyState;
      var size = currentConfiguration.getSize();
      var conf, neigh = 0;
      var max = 0;

      var temperature = 100;

      // filling array with random transitions, more precisly with energies of those transitions (max and min price function)
      while(200 !== arrayOfEnergyStates.length)
      {
          conf = problem.transformMaximizationToRealCost(problem.evaluateMaximizationCost(currentConfiguration));
          neigh = problem.transformMaximizationToRealCost(problem.evaluateMaximizationCost(currentNeighbour));
          if(Math.sign(conf) === Math.sign(neigh) && Math.sign(conf) === 1)
          {
            newEnergyState = {
                max: Math.max(conf, neigh),
                min: Math.min(conf, neigh)
            };
            if(newEnergyState.max > max) max = newEnergyState.max > max;
            arrayOfEnergyStates.push(newEnergyState);
          }


          currentConfiguration = currentNeighbour;
          currentNeighbour = currentConfiguration.getNeighbour();
      }

      temperature = max;
      //calculating temperature for which is the propability of accepting average worse state equals to wantedPropability
      while(Math.abs(wantedPropability - currentPropability) > 0.005)
      {
          maxSum = 0;
          minSum = 0;

          for(var i = 0; i < arrayOfEnergyStates.length; i++)
          {
              maxSum += Math.exp(-arrayOfEnergyStates[i].max / temperature);
              minSum += Math.exp(-arrayOfEnergyStates[i].min / temperature);
          }
          if(maxSum === 0 || minSum === 0) break;
          currentPropability = maxSum / minSum;
          if(currentPropability === 1) return 1;

          temperature = temperature * (-Math.log(currentPropability) / -Math.log(wantedPropability));
      }

      return Math.ceil(temperature);
  }
}