巡回セールスマン問題(eil51)コード例

1_simple_hillclimb.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


float distance(int *point1, int *point2)
{
  int
    dx = point1[0] - point2[0],
    dy = point1[1] - point2[1];

  return sqrt(dx * dx + dy * dy);
}


float totalDistance(int **points, int length)
{
  int
    i;
  float
    total = 0.0;

  for (i = 1; i < length; i++) {
    total += distance(points[i], points[i - 1]);
  }

  total += distance(points[0], points[length - 1]);

  return total;
}


void swap(int **array, int index1, int index2)
{
  int
    *tmp;

  tmp = array[index1];
  array[index1] = array[index2];
  array[index2] = tmp;
}


void hillclimb(int **route, int numberOfCities, int maxIterations)
{
  int
    currentIterations,
    randomIndex1,
    randomIndex2;
  float
    currentTotalDistance,
    newTotalDistance;

  for (currentIterations = 0; currentIterations < maxIterations; currentIterations++) {
    randomIndex1 = rand() % numberOfCities;
    randomIndex2 = rand() % numberOfCities;

    currentTotalDistance = totalDistance(route, numberOfCities);

    swap(route, randomIndex1, randomIndex2);

    newTotalDistance = totalDistance(route, numberOfCities);

    if (newTotalDistance < currentTotalDistance) {
      // do nothing
    } else {
      swap(route, randomIndex1, randomIndex2);
    }
  }
}


int **buildRoute(int mapData[][2], int numberOfCities)
{
  int
    **route = calloc(numberOfCities, sizeof(&mapData[0][0])),
    i;

  for (i = 0; i < numberOfCities; i++) {
    route[i] = mapData[i];
  }
  return route;
}


void printJSONRoute(int **route, int numberOfCities)
{
  int
    i;

  printf("[\n");
  for (i = 0; i < numberOfCities - 1; i++) {
    printf("  [%d, %d],\n", route[i][0], route[i][1]);
  }
  printf("  [%d, %d]\n", route[i][0], route[i][1]);
  printf("]\n");
}


int main(void)
{
  int
    maxIterations = 10000,
    numberOfCities = 51,
    mapData[][2] = {{37,52},{49,49},{52,64},{20,26},{40,30},{21,47},{17,63},{31,62},{52,33},{51,21},{42,41},{31,32},{5,25},{12,42},{36,16},{52,41},{27,23},{17,33},{13,13},{57,58},{62,42},{42,57},{16,57},{8,52},{7,38},{27,68},{30,48},{43,67},{58,48},{58,27},{37,69},{38,46},{46,10},{61,33},{62,63},{63,69},{32,22},{45,35},{59,15},{5,6},{10,17},{21,10},{5,64},{30,15},{39,10},{32,39},{25,32},{25,55},{48,28},{56,37},{30,40}},
    **route = buildRoute(mapData, numberOfCities);

  srand((unsigned)time(NULL));

  printf("%f\n", totalDistance(route, numberOfCities));

  hillclimb(route, numberOfCities, maxIterations);

  printf("%f\n", totalDistance(route, numberOfCities));
  printJSONRoute(route, numberOfCities);

  return 0;
}

1_simple_hillclimb.js

// 2都市間の距離の計算
function distance(point1, point2) {
  var
    dx = point1[0] - point2[0],
    dy = point1[1] - point2[1];

  return Math.sqrt(dx * dx + dy * dy);
}


// 総移動距離の計算
function totalDistance(points) {
  var
    total = 0,
    length = points.length,
    i;

  // 今の都市と一つ前の都市の距離を総移動距離に加える
  for (i = 1; i < length; i++) {
    total += distance(points[i], points[i - 1]);
  }

  // 全ての都市をまわったあとに出発地点の都市に戻る必要がある
  total += distance(points[0], points[length - 1]);

  return total;
}


// 配列の2要素の交換
function swap(array, index1, index2) {
  var
    tmp;

  tmp = array[index1];
  array[index1] = array[index2];
  array[index2] = tmp;
}


// 山登り法による経路の最適化
//   route: 初期経路
//   maxIterations: 繰り返し回数
function hillclimb(route, maxIterations) {
  var

    // 都市数。乱数の値(0 <= random() < 1)を
    // 0 〜 都市数 までの整数に直すのに利用
    length = route.length,

    // 現在の繰り返し回数
    currentIterations,

    // 現在の経路設定での総移動距離
    currentTotalDistance,

    // 新しく生成した経路設定での総移動距離
    newTotalDistance,

    randomIndex1,
    randomIndex2;

  for (currentIterations = 0; currentIterations < maxIterations; currentIterations++) {
    randomIndex1 = Math.floor(Math.random() * length);
    randomIndex2 = Math.floor(Math.random() * length);

    currentTotalDistance = totalDistance(route);

    swap(route, randomIndex1, randomIndex2);

    newTotalDistance = totalDistance(route);

    // 新しく生成した経路設定での総距離について
    //   元の経路設定での総距離より小さければ
    //     それを採用
    //   元の経路設定での総距離より大きければ
    //     経路を元に戻す
    if (newTotalDistance < currentTotalDistance) {
      // do nothing
    } else {
      swap(route, randomIndex1, randomIndex2);
    }
  }
}


;(function main() {
  var
    route = [[37,52],[49,49],[52,64],[20,26],[40,30],[21,47],[17,63],[31,62],[52,33],[51,21],[42,41],[31,32],[5,25],[12,42],[36,16],[52,41],[27,23],[17,33],[13,13],[57,58],[62,42],[42,57],[16,57],[8,52],[7,38],[27,68],[30,48],[43,67],[58,48],[58,27],[37,69],[38,46],[46,10],[61,33],[62,63],[63,69],[32,22],[45,35],[59,15],[5,6],[10,17],[21,10],[5,64],[30,15],[39,10],[32,39],[25,32],[25,55],[48,28],[56,37],[30,40]];

  console.log(totalDistance(route));
  hillclimb(route, 10000);
  console.log(totalDistance(route));
  console.log(JSON.stringify(route));
})();

1_simple_hillclimb.rb

def distance(point1, point2)
  dx = point1[0] - point2[0]
  dy = point1[1] - point2[1]

  Math.sqrt(dx * dx + dy * dy)
end

def total_distance(points)
  total = 0

  1.upto(points.length - 1) { |i|
    total += distance(points[i], points[i - 1])
  }
  total += distance(points[0], points[-1])
end

def swap!(array, index1, index2)
  array[index1], array[index2] = array[index2], array[index1]
end

def hillclimb!(route, max_iterations=10000)
  numberOfCities = route.length
  1.upto(max_iterations) {
    random_index1 = rand numberOfCities
    random_index2 = rand numberOfCities

    current_total_distance = total_distance route
    swap! route, random_index1, random_index2
    new_total_distance = total_distance route

    if new_total_distance < current_total_distance
      # do nothing
    else
      swap! route, random_index1, random_index2
    end
  }
end

if __FILE__ == $0
  max_iterations = 10000
  route = [[37,52],[49,49],[52,64],[20,26],[40,30],[21,47],[17,63],[31,62],[52,33],[51,21],[42,41],[31,32],[5,25],[12,42],[36,16],[52,41],[27,23],[17,33],[13,13],[57,58],[62,42],[42,57],[16,57],[8,52],[7,38],[27,68],[30,48],[43,67],[58,48],[58,27],[37,69],[38,46],[46,10],[61,33],[62,63],[63,69],[32,22],[45,35],[59,15],[5,6],[10,17],[21,10],[5,64],[30,15],[39,10],[32,39],[25,32],[25,55],[48,28],[56,37],[30,40]]
  puts total_distance(route)
  hillclimb! route, max_iterations
  puts total_distance(route)
  p route
end

2_simple_sa.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


float distance(int *point1, int *point2)
{
  int
    dx = point1[0] - point2[0],
    dy = point1[1] - point2[1];

  return sqrt(dx * dx + dy * dy);
}


float totalDistance(int **points, int length)
{
  int
    i;
  float
    total = 0.0;

  for (i = 1; i < length; i++) {
    total += distance(points[i], points[i - 1]);
  }

  total += distance(points[0], points[length - 1]);

  return total;
}


void swap(int **array, int index1, int index2)
{
  int
    *tmp;

  tmp = array[index1];
  array[index1] = array[index2];
  array[index2] = tmp;
}


float frand()
{
  return (float)rand()/(float)RAND_MAX;
}


int shouldChange(float delta, float t)
{
  if (delta <= 0) return 1;
  if (frand() < exp(- delta / t)) return 1;
  return 0;
}


void sa(int **route,
        int numberOfCities,
        float initialT,
        float finalT,
        int n,
        float coolingRate)
{
  int
    currentIterations,
    randomIndex1,
    randomIndex2,
    i;
  float
    t,
    currentTotalDistance,
    newTotalDistance;

  currentTotalDistance = totalDistance(route, numberOfCities);

  for (t = initialT; t > finalT; t *= coolingRate) {
    for (i = 0; i < n; i++) {
      randomIndex1 = rand() % numberOfCities;
      randomIndex2 = rand() % numberOfCities;

      swap(route, randomIndex1, randomIndex2);

      newTotalDistance = totalDistance(route, numberOfCities);

      if (shouldChange(newTotalDistance - currentTotalDistance, t)) {
        currentTotalDistance = newTotalDistance;
      } else {
        swap(route, randomIndex1, randomIndex2);
      }
    }
  }

}


int **buildRoute(int mapData[][2], int numberOfCities)
{
  int
    **route = calloc(numberOfCities, sizeof(&mapData[0][0])),
    i;

  for (i = 0; i < numberOfCities; i++) {
    route[i] = mapData[i];
  }
  return route;
}


void printJSONRoute(int **route, int numberOfCities)
{
  int
    i;

  printf("[\n");
  for (i = 0; i < numberOfCities - 1; i++) {
    printf("  [%d, %d],\n", route[i][0], route[i][1]);
  }
  printf("  [%d, %d]\n", route[i][0], route[i][1]);
  printf("]\n");
}


int main(void)
{
  int
    n = 1000,
    numberOfCities = 51,
    mapData[][2] = {{37,52},{49,49},{52,64},{20,26},{40,30},{21,47},{17,63},{31,62},{52,33},{51,21},{42,41},{31,32},{5,25},{12,42},{36,16},{52,41},{27,23},{17,33},{13,13},{57,58},{62,42},{42,57},{16,57},{8,52},{7,38},{27,68},{30,48},{43,67},{58,48},{58,27},{37,69},{38,46},{46,10},{61,33},{62,63},{63,69},{32,22},{45,35},{59,15},{5,6},{10,17},{21,10},{5,64},{30,15},{39,10},{32,39},{25,32},{25,55},{48,28},{56,37},{30,40}},
    **route = buildRoute(mapData, numberOfCities);
  float
    initialT = 100.0,
    finalT = 0.8,
    coolingRate = 0.9;

  srand((unsigned)time(NULL));

  printf("%f\n", totalDistance(route, numberOfCities));

  sa(route, numberOfCities, initialT, finalT, n, coolingRate);

  printf("%f\n", totalDistance(route, numberOfCities));
  printJSONRoute(route, numberOfCities);

  return 0;
}

2_simple_sa.js

// 2都市間の距離の計算
function distance(point1, point2) {
  var
    dx = point1[0] - point2[0],
    dy = point1[1] - point2[1];

  return Math.sqrt(dx * dx + dy * dy);
}


// 総移動距離の計算
function totalDistance(points) {
  var
    total = 0,
    length = points.length,
    i;

  // 今の都市と一つ前の都市の距離を総移動距離に加える
  for (i = 1; i < length; i++) {
    total += distance(points[i], points[i - 1]);
  }

  // 全ての都市をまわったあとに出発地点の都市に戻る必要がある
  total += distance(points[0], points[length - 1]);

  return total;
}


// 配列の2要素の交換
function swap(array, index1, index2) {
  var
    tmp;

  tmp = array[index1];
  array[index1] = array[index2];
  array[index2] = tmp;
}


// 焼きなまし法(Simulated Annealing)による経路の最適化
//   route: 初期経路
//   params: パラメータ(後述)
function sa(route, params) {

  // 経路を新しいものに変えるべきかどうかを決める関数
  //   delta: 新しい経路の総距離 - 古い経路の総距離
  //   t: 温度
  function shouldChange(delta, t) {
    if (delta <= 0) return true;
    if (Math.random() < Math.exp(- delta / t)) return true;
    return false;
  }

  var
    length = route.length,

    // パラメータ(params)が設定されていなかった場合に用いる
    defaults,

    // 現在の温度
    t,

    // 繰り返しを打ち切る温度
    finalT,

    // アニーリング回数(各温度で何回試行するか)
    n,

    // 冷却率
    coolingRate,

    currentTotalDistance,
    newTotalDistance,
    randomIndex1,
    randomIndex2,
    i;

  params = params || {};

  defaults = {
    initialT: 100,
    finalT: 0.8,
    n: 1000,
    coolingRate: 0.9
  };

  // 各種設定
  // パラメータが未定義の場合はデフォルトの設定値を使用する
  t = params.initialT || defaults.initialT;
  finalT = params.finalT || defaults.finalT;
  n = params.n || defaults.n;
  coolingRate = params.coolingRate || defaults.coolingRate;

  currentTotalDistance = totalDistance(route);

  for (; t > finalT; t *= coolingRate) {
    for (i = 0; i < n; i++) {
      randomIndex1 = Math.floor(Math.random() * length);
      randomIndex2 = Math.floor(Math.random() * length);

      swap(route, randomIndex1, randomIndex2);

      newTotalDistance = totalDistance(route);

      // 新しい経路の総距離と現在の経路の総距離の差をもとに経路を変えるべきかを判定
      if (shouldChange(newTotalDistance - currentTotalDistance, t)) {
        currentTotalDistance = newTotalDistance;
      } else {
        swap(route, randomIndex1, randomIndex2);
      }
    }
  }

}


;(function main() {
  var
    route = [[37,52],[49,49],[52,64],[20,26],[40,30],[21,47],[17,63],[31,62],[52,33],[51,21],[42,41],[31,32],[5,25],[12,42],[36,16],[52,41],[27,23],[17,33],[13,13],[57,58],[62,42],[42,57],[16,57],[8,52],[7,38],[27,68],[30,48],[43,67],[58,48],[58,27],[37,69],[38,46],[46,10],[61,33],[62,63],[63,69],[32,22],[45,35],[59,15],[5,6],[10,17],[21,10],[5,64],[30,15],[39,10],[32,39],[25,32],[25,55],[48,28],[56,37],[30,40]];

  console.log(totalDistance(route));
  sa(route);
  console.log(totalDistance(route));
  console.log(JSON.stringify(route));
})();

2_simple_sa.rb

def distance(point1, point2)
  dx = point1[0] - point2[0]
  dy = point1[1] - point2[1]

  Math.sqrt(dx * dx + dy * dy)
end

def total_distance(points)
  total = 0

  1.upto(points.length - 1) { |i|
    total += distance(points[i], points[i - 1])
  }
  total += distance(points[0], points[-1])
end

def swap!(array, index1, index2)
  array[index1], array[index2] = array[index2], array[index1]
end

def sa!(route, options = {})
  def should_change?(delta, t)
    return true if delta <= 0
    return true if rand < Math.exp(- delta / t)
    false
  end

  numberOfCities = route.length
  defaults = {
    initial_t: 100.0,
    final_t: 0.8,
    n: 2000,
    cooling_rate: 0.9
  }
  options = defaults.merge options

  initial_t = options[:initial_t].to_f
  final_t = options[:final_t].to_f
  n = options[:n].to_i
  cooling_rate = options[:cooling_rate].to_f

  current_total_distance = total_distance route
  t = initial_t
  while t > final_t
    1.upto(n) {
      random_index1 = rand numberOfCities
      random_index2 = rand numberOfCities

      swap! route, random_index1, random_index2
      new_total_distance = total_distance route

      if should_change?(new_total_distance - current_total_distance, t)
        current_total_distance = new_total_distance;
      else
        swap! route, random_index1, random_index2
      end
    }
    t *= cooling_rate
  end
end

if __FILE__ == $0
  options = {
    initial_t: 100.0,
    final_t: 0.8,
    n: 1000,
    cooling_rate: 0.9
  }
  route = [[37,52],[49,49],[52,64],[20,26],[40,30],[21,47],[17,63],[31,62],[52,33],[51,21],[42,41],[31,32],[5,25],[12,42],[36,16],[52,41],[27,23],[17,33],[13,13],[57,58],[62,42],[42,57],[16,57],[8,52],[7,38],[27,68],[30,48],[43,67],[58,48],[58,27],[37,69],[38,46],[46,10],[61,33],[62,63],[63,69],[32,22],[45,35],[59,15],[5,6],[10,17],[21,10],[5,64],[30,15],[39,10],[32,39],[25,32],[25,55],[48,28],[56,37],[30,40]]
  puts total_distance(route)
  sa! route, options
  puts total_distance(route)
  p route
end

3_experimental_ga.js

// This script is experimental code yet.

function GeneticAlgorithm(options) {
  this.populations = options.initialPopulations.map(function(pop) {
    return new CachedModel(pop);
  });
  this.numberOfPopulations = options.initialPopulations.length;
  this.evaluation = options.evaluation;
  this.selection = options.selection;
  this.crossover = options.crossover;
  this.mutation = options.mutation;
}

GeneticAlgorithm.prototype.execute = function() {
  var
    length = this.populations.length,
    nextPopulations,
    i;

  nextPopulations = this.selection(
    this.populations,
    this.evaluation,
    700
  );

  nextPopulations = nextPopulations.concat(this.crossover(this.populations, 250));

  for (i = 950; i < 1000; i++) {
    randomIndex1 = Math.floor(Math.random() * length);
    nextPopulations[i] = new CachedModel(this.mutation(
      this.populations[randomIndex1].model
    ));
  }
  this.populations = nextPopulations;
};

function CachedModel(model) {
  this.cache = 0;
  this.model = model;
}


function roulette(populations, evaluation, numberOfSelections) {
  var
    length = populations.length,
    remainingtableLength = length,
    sum = 0,
    selectionProbabilities,
    remainingTable,
    selected,
    pop,
    i;

  for (i = length; i--;) {
    pop = populations[i];
    pop.cache = (pop.cache || evaluation(pop.model));
    sum += pop.cache;
  }

  selectionProbabilities = new Float64Array(length);
  for (i = length; i--;) {
    selectionProbabilities[i] = populations[i].cache / sum;
  }

  remainingTable = new Array(length);
  for (i = length; i--;) {
    remainingTable[i] = i;
  }

  selected = new Array(numberOfSelections);
  while (numberOfSelections) {
    for (i = remainingtableLength; i--;) {
      if (selectionProbabilities[remainingTable[i]] > Math.random()) {
        selected[--numberOfSelections] = populations[remainingTable[i]];
        remainingTable[i++] = remainingTable[--remainingtableLength];
        if (numberOfSelections === 0) {
          break;
        }
      }
    }
  }

  return selected;
}

function partialMapping(populations, numberOfMapped) {
  var
    length = populations.length,
    mapped = new Array(numberOfMapped),
    randomIndex1,
    randomIndex2,
    crossPoint,
    outerI,

    route1,
    route2,
    newRoute,
    newRouteLength,
    target,
    index,
    j;


  for (outerI = numberOfMapped; outerI--;) {
    randomIndex1 = Math.floor(Math.random() * length);
    randomIndex2 = Math.floor(Math.random() * length);
    crossPoint = Math.floor(Math.random() * 51);

    route1 = populations[randomIndex1].model;
    route2 = populations[randomIndex2].model;

    newRoute = new Array(51);
    for (i = crossPoint; i--;) {
      newRoute[i] = route1[i];
    }
    newRouteLength = crossPoint;

    for (i = crossPoint; i < 51; i++) {
      target = route2[i];
      for (j = newRouteLength; j--;) {
        if (target === newRoute[j]) {
          target = route2[j];
          j = newRouteLength;
          continue;
        }
      }
      newRoute[newRouteLength++] = target;
    }

    mapped[outerI] = new CachedModel(newRoute);
  }
  return mapped;
}

function mutation(route) {
  var
    length = route.length,
    randomIndex1 = Math.floor(Math.random() * length),
    randomIndex2 = Math.floor(Math.random() * length),
    newRoute = new Array(length),
    tmp;

  for (i = length; i--;) {
    newRoute[i] = route[i];
  }

  tmp = newRoute[randomIndex1];
  newRoute[randomIndex1] = newRoute[randomIndex2];
  newRoute[randomIndex2] = tmp;

  return newRoute;
}



;(function _main() {

  //+ Jonas Raoni Soares Silva
  //@ http://jsfromhell.com/array/shuffle [v1.0]
  shuffle = function(o){ //v1.0
    for(var j, x, i = o.length; i; j = Math.floor(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
  };

  makeRandomRoutes = function(data, number) {
    var
      routes = new Array(number),
      route,
      i;

    for (i = 0; i < number; i++) {
      route = new Array(data.length);
      for (j = 0; j < data.length; j++) {
        route[j] = j;
      }
      shuffle(route);
      routes[i] = route;
    }
    return routes;
  };

  function distance(point1, point2) {
    var
      dx = point1[0] - point2[0],
      dy = point1[1] - point2[1];

    return Math.sqrt(dx * dx + dy * dy);
  }

  function totalDistance(points) {
    var
      total = 0,
      length = points.length,
      i;

    for (i = 1; i < length; i++) {
      total += distance(mapData[points[i]], mapData[points[i - 1]]);
    }

    total += distance(mapData[points[0]], mapData[points[length - 1]]);
    // return total;
    return 1/total;
  }
evaluation=totalDistance;

  var
    mapData = [[37,52],[49,49],[52,64],[20,26],[40,30],[21,47],[17,63],[31,62],[52,33],[51,21],[42,41],[31,32],[5,25],[12,42],[36,16],[52,41],[27,23],[17,33],[13,13],[57,58],[62,42],[42,57],[16,57],[8,52],[7,38],[27,68],[30,48],[43,67],[58,48],[58,27],[37,69],[38,46],[46,10],[61,33],[62,63],[63,69],[32,22],[45,35],[59,15],[5,6],[10,17],[21,10],[5,64],[30,15],[39,10],[32,39],[25,32],[25,55],[48,28],[56,37],[30,40]];

  a = new GeneticAlgorithm({
    initialPopulations: makeRandomRoutes(mapData, 1000),
    evaluation: totalDistance,
    selection: roulette,
    crossover: partialMapping,
    mutation: mutation
  });

}).call(this);
for(count=100;count--;)a.execute();
// console.log(a.populations.map(function(pop){return evaluation(pop.model)}));
console.log(a.populations.map(function(pop){return 1/evaluation(pop.model)}));
// console.log(a.populations.reduce(function(min, pop){
//   var result = 1/evaluation(pop.model);
//   return  result < min ? result : min
// }, 10000));

3_experimental_ga.rb

# this code is probably wrong ;p
class GeneticAlgorithm
  attr_accessor \
    :populations,
    :evaluation,
    :settings

  def initialize(populations, evaluation, options={})
    @populations = populations
    @evaluation = evaluation

    number_of_populations = @populations.length
    default_settings = {
      number_of_selections: Integer(number_of_populations * 0.75),
      number_of_crossovers: Integer(number_of_populations * 0.20),
      number_of_mutations:  Integer(number_of_populations * 0.05),
    }

    @settings = default_settings.merge options
  end

  def execute()
    next_populations = []

    next_populations.concat select(
      @populations,
      @evaluation,
      @settings[:number_of_selections]
    )

    next_populations.concat cross(
      @populations,
      @settings[:number_of_crossovers]
    )

    next_populations.concat mutate(
      @populations,
      @settings[:number_of_mutations]
    )

    @populations = next_populations
  end

  private

    # roulette
    def select(populations, evaluation, number_of_selections)
      return [] if number_of_selections == 0

      eval_values = populations.map(&evaluation)
      sum = eval_values.inject(&:+)

      selection_probabilities = eval_values.map {|value| value / sum }

      remaining_list = populations.zip selection_probabilities
      selected_list = []
      loop {
        remaining_list.each_with_index {|(route, prob), index|
          if prob > rand
            remaining_list.delete_at index
            selected_list.push route
            number_of_selections -= 1

            if number_of_selections == 0
              return selected_list
            end
          end
        }
      }
    end

    # partial mapping
    def cross(populations, number_of_crossovers)
      [*1..number_of_crossovers].map { cross_one populations }
    end

    def cross_one(populations)
      route1, route2 = populations.sample 2
      cross_point = rand 51

      new_route = route1[0, cross_point]
      cross_point.upto(50) {|i|
        target_point = route2[i]
        while new_route.include? target_point
          conflicting_index = new_route.index target_point
          target_point = route2[conflicting_index]
        end
        new_route.push target_point
      }
      return new_route
    end

    # simple exchange
    def mutate(populations, number_of_mutations)
      [*1..number_of_mutations].map { mutate_one populations }
    end

    def mutate_one(populations)
      route = populations.sample.clone
      r1 = rand 51
      r2 = rand 51

      route[r1], route[r2] = route[r2], route[r1]
      return route
    end

end


def distance(point1, point2)
  dx = point1[0] - point2[0]
  dy = point1[1] - point2[1]

  Math.sqrt(dx * dx + dy * dy)
end

def total_distance(points)
  total = 0

  1.upto(points.length - 1) {|i|
    total += distance(points[i], points[i - 1])
  }
  total += distance(points[0], points[-1])
end

def make_random_routes(map_data, number)
  [*1..number].map { map_data.clone.shuffle }
end


if __FILE__ == $0
  map_data = [[37,52],[49,49],[52,64],[20,26],[40,30],[21,47],[17,63],[31,62],[52,33],[51,21],[42,41],[31,32],[5,25],[12,42],[36,16],[52,41],[27,23],[17,33],[13,13],[57,58],[62,42],[42,57],[16,57],[8,52],[7,38],[27,68],[30,48],[43,67],[58,48],[58,27],[37,69],[38,46],[46,10],[61,33],[62,63],[63,69],[32,22],[45,35],[59,15],[5,6],[10,17],[21,10],[5,64],[30,15],[39,10],[32,39],[25,32],[25,55],[48,28],[56,37],[30,40]]

  initial_populations = make_random_routes map_data, 100
  evaluation = -> route { 1 / (total_distance route) }

  ga = GeneticAlgorithm.new(initial_populations, evaluation,
    number_of_selections: 78,
    number_of_crossovers: 20,
    number_of_mutations:  2,
  )

  puts ga.populations.map {|route| total_distance route }
  puts "----- ----- ----- -----"

  100.times {
    100.times {
      ga.execute()
    }
    puts ga.populations.map {|route| total_distance route }
  }
end

gistはシンタックスハイライトが控えめなのでダウンロードして適当なテキストエディタで見たほうが見やすい

(JavaScript的)Cのコードを追加

Ruby

GA

正式版 https://github.com/i09158knct/2012KE/tree/master/ke25

Ruby版GA(雰囲気)

山登り法

1. C
2. JavaScript
3. Ruby

焼きなまし法

1. C
2. JavaScript
3. Ruby

遺伝的アルゴリズム(実験的)

1. JavaScript
2. Ruby

正式版

https://github.com/i09158knct/2012KE/tree/master/ke25