Last active
August 11, 2019 08:04
-
-
Save i09158knct/4239460 to your computer and use it in GitHub Desktop.
巡回セールスマン問題(eil51)コード例
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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)); | |
})(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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)); | |
})(); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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)); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
GA
Ruby版GA(雰囲気)
山登り法
焼きなまし法
遺伝的アルゴリズム(実験的)
正式版
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Ruby