taramath: Das GeneticAlgorithm-Paket

Beschreibung

In praktischen Anwendungsfällen können Optimierungsprobleme häufig nicht exakt gelöst werden, da entweder kein geeignetes Verfahren bekannt ist oder aber die Laufzeit exponentiell mit der Anzahl der Eingabedaten wächst. Man ist daher darauf angewiesen, im Sinne der Optimierungsaufgabe möglichst gute Lösungen in einer vertretbaren Rechenzeit zu bestimmen. Derartige Verfahren werden als Heuristiken bezeichnet. Genetische Algorithmen liefern spezielle Heuristiken, die sich insbesondere auf kombinatorische bzw. ganzzahlige Optimierungsprobleme anwenden lassen.

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

Das GeneticAlgorithm-Paket

zur Anwendung genetischer Algorithmen