taramath: GeneticAlgorithm.permutation

Beispiel

Im folgenden Beispiel wird eine Lösung das Problem des Handlungsreisenden mit Orten unter Verwendung eines genetischen Algorithmus approximiert. Anschließend wird das Ergebnis graphisch dargestellt.

<!DOCTYPE html>
<html>

<head>
  <script src="taramath.js"></script>
</head>

<body>

<div id="plot"></div>

<script>

// Eingabedaten

var P = [
  [77.3,39.5], [32.3,25.1], [65.3,39.2], [14.0,33.4], [40.8,41.4],
  [86.1,69.6], [85.7,62.2], [82.7,37.7], [79.0,43.9], [21.1,45.5],
  [64.7,51.1], [69.9,53.7], [57.1,51.7], [56.1,45.4], [73.5,51.8],
  [71.1,31.7], [86.1,76.8], [84.6,60.9], [87.3,72.2], [69.0,60.6],
  [54.8,58.7], [71.0,36.1], [62.0,46.8], [26.3,53.1], [53.1,48.2],
  [16.8,35.1], [85.5,73.2], [85.4,64.8], [41.8,32.6], [83.5,70.1],
  [85.5,53.0], [42.5,58.0], [74.3,56.7], [56.1,37.0], [10.2,47.2],
  [82.5,62.8], [87.6,71.0], [83.9,47.4], [44.8,53.3], [72.7,46.4],
  [59.9,26.4], [29.2,40.7], [82.8,74.0], [85.1,57.4], [10.1,51.8],
  [78.1,54.9], [61.9,57.6], [40.2,44.4]
];

var m = P.length;


// Zielfunktion

function distance (A, B) {
  return Math.sqrt((A[0]-B[0])*(A[0]-B[0]) + (A[1]-B[1])*(A[1]-B[1]));
};

var A = LinearAlgebra.zero_matrix(m);
for (var i = 0; i < m; i++) for (var j = i+1; j < m; j++) {
  A[i][j] = distance(P[i], P[j]);
  A[j][i] = A[i][j];
};

function f (x) {
  var h = 0;
  var m = x.length;
  for (var k = 0; k < m; k++) h += A[x[k]][x[(k+1)%m]];
  return h;
};


// Genetischer Algorithmus

GeneticAlgorithm.set_number_of_iterations(100);
GeneticAlgorithm.set_size_of_population(50, 400);
GeneticAlgorithm.set_mutation_rate(0.02);
var x = GeneticAlgorithm.permutation(f, m);


// Darstellung

Svg.init("plot", 400, 280);
Svg.resize(0, 100, 15, 85);
Svg.clear("#f0f0f0");
for (var k = 0; k < m; k++) {
  Svg.line(P[x[k]][0], P[x[k]][1], P[x[(k+1)%m]][0], P[x[(k+1)%m]][1], "#a6a6a6");
};
for (var k = 0; k < m; k++) {
  Svg.disc(P[k][0], P[k][1], 0.8, "#0059c5");
};
Svg.draw();


</script>

</body>
</html>

Vorschau aktualisieren

f	Funktion
m	positive ganze Zahl (Länge der Permutation)

GeneticAlgorithm.permutation

zur Durchführung eines genetischen Algorithmus