taramath: Problem des Handlungsreisenden

Beschreibung

Gegeben seien feste Orte in der Ebene. Das Problem des Handlungsreisenden oder das Traveling Salesman Problem besteht darin, alle Orte genau einmal zu besuchen und anschließend wieder zum Ausgangspunkt zurückzukehren. Dabei soll die gesamte Route möglichst kurz sein.

Das Problem des Handlungsreisenden lässt sich als ganzzahliges Programm formulieren und (theoretisch) exakt lösen. Aufgrund der Komplexität ist dies praktisch jedoch in keiner vertretbaren Rechenzeit möglich. Wir bestimmen daher eine gute Lösung des Problems unter Verwendung eines genetischen Algorithmus (GA).

Beispiel

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

Tipp: Aktualisiere die Vorschau (mehrfach) und beobachte den Zielfunktionswert der bestimmten Lösung. Verändere dabei auch die Anzahl der Iterationen des genetischen Verfahrens.

<!DOCTYPE html>
<html>

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

<body>

<div id="plot"></div>
<textarea id="print" style="width:100%; height:56px;"></textarea>

<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], "#999999");
};
for (var k = 0; k < m; k++) {
  Svg.disc(P[k][0], P[k][1], 0.8, "#0000ff");
};
Svg.draw();


// Textausgabe

Print.init("print");
Print.object("Zielfunktionswert:");
Print.object(f(x));
Print.set_digits(0);
Print.object("Loesung:");
Print.object(x);


</script>

</body>
</html>

Vorschau aktualisieren