taralino

Algorithmus erproben

In der folgenden Anwendung wird das genetische Verfahren angewandt, um das Problem des Handlungsreisenden zu lösen. Verwendet werden 48 zufällige Orte sowie die folgenden Parameter des Verfahrens:

		100	Populationsgröße
		200	Elternpaare pro Generation

In der Anwendung dargestellt wird jeweils die beste Lösung der aktuellen Generation (also die bislang kürzeste gefundene Rundtour).

Anwendung

Überzeuge dich davon, wie gut das genetische Verfahren das Problem lösen kann.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>


var n = 48;
var glb_int_size_of_population_var = 100;
var glb_int_number_of_children_var = 200;

var X = [];
var T = [];
var step = 0;
var stepwise = 0;




function random_permutation(m) {
  var x = [];
  for (var k = 0; k < m; k++) x.push(k);
  for (var i = 0; i < m; i++) {
    var j = Math.floor(m*Math.random());
    var h = x[i];
    x[i] = x[j];
    x[j] = h;
  };
  return x;
};


function generate_children_permutation(y, z) {
  var m = y.length;

  // init
  var a = [];
  var b = [];
  for (var k = 0; k < m; k++) a.push(-1);
  for (var k = 0; k < m; k++) b.push(-1);
  var ap = [];
  var bp = [];
  for (var k = 0; k < m; k++) ap.push(-1);
  for (var k = 0; k < m; k++) bp.push(-1);

  // step 1: swap random segments
  var t = 2 + Math.floor((m-2)*Math.random());
  var i = Math.floor(m*Math.random());
  var j = Math.floor(m*Math.random());
  for (var k = 0; k < t; k++) {
    a[(i+k)%m] = z[(j+k)%m];
    b[(j+k)%m] = y[(i+k)%m];
    ap[z[(j+k)%m]] = (i+k)%m;
    bp[y[(i+k)%m]] = (j+k)%m;
  };

  // step 2: fill up valid positions
  for (var k = 0; k < m; k++) {
    if ((a[k] == -1) && (ap[y[k]] == -1)) {
      a[k] = y[k];
      ap[y[k]] = k;
    };
    if ((b[k] == -1) && (bp[z[k]] == -1)) {
      b[k] = z[k];
      bp[z[k]] = k;
    };
  };

  // step 3: finalize
  for (var k = 0; k < m; k++) {
    if (a[k] == -1) {
      var h = y[k];
      while (ap[h] != -1) { h = y[ap[h]] };
      a[k] = h;
      ap[h] = k;
    };
    if (b[k] == -1) {
      var h = z[k];
      while (bp[h] != -1) { h = z[bp[h]] };
      b[k] = h;
      bp[h] = k;
    };
  };

  // return children
  return [a, b];
};


function generation() {
  for (var k = 0; k < glb_int_number_of_children_var; k++) {
    var i = Math.floor(glb_int_size_of_population_var * Math.pow(Math.random(), 2));
    var j = Math.floor(glb_int_size_of_population_var * Math.pow(Math.random(), 2));
    var H = generate_children_permutation(X[i].x, X[j].x);
    X.push({x:H[0], v:f(H[0])});
    X.push({x:H[1], v:f(H[1])});
  };
  X.sort(function(a,b) { return a.v - b.v; });
  X.splice(glb_int_size_of_population_var);
  step++;
};


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


function f(x) {
  var h = 0;
  var n = x.length;
  for (var k = 0; k < n; k++) h += distance(T[x[k]], T[x[(k+1)%n]]);
  return h;
};


function init() {
  T = [];
  while (T.length < n) {
    var p = [random(0,100), random(0,100)];
    var h = 1e6;
    for (var i = 0; i < T.length; i++) h = Math.min(h, distance(p, T[i]));
    if (h > 10) T.push(p);
  };
  // initialize population
  step = 0;
  X = [];
  for (var k = 0; k < glb_int_size_of_population_var; k++) {
    var x = random_permutation(n);
    X.push({x:x, v:f(x)});
  };
  X.sort(function(a,b) { return a.v - b.v; });
};


function draw() {
  Canvas.clear();

  for (var i = 0; i < 1; i++) {
    var s = X[i].x;
    for (var k = 0; k < n; k++) Canvas.line(T[s[k]][0], T[s[k]][1], T[s[(k+1)%n]][0], T[s[(k+1)%n]][1], {stroke:"red"});
  };

  Canvas.text(25, -10, "Generation: " + step.toFixed(0));
  Canvas.text(75, -10, "Fitness: " + X[0].v.toFixed(2));

  for (var k = 0; k < T.length; k++) Canvas.circle(T[k][0], T[k][1], 1.8, {fill:"blue"});
};


function setup() {
  Canvas.init([-10,110], [-20,110], {background:"lightgrey", width:400});
  init();
  draw();
  Animation.init({fps:12, autoplay:"off"});
  Button.add("start", "Start");
  Button.add("stop", "Pause");
  Button.add("reset", "Neustart");
  Button.add("stepwise", "20 Schritte");
};


function on_click(id) {
  if (id == "start") Animation.start();
  if (id == "stop") Animation.stop();
  if (id == "stepwise") {
    Animation.start();
    stepwise = 20;
  };
  if (id == "reset") {
    Animation.stop();
    init();
    draw();
  };
};


function loop() {
  generation();
  draw();
  if (stepwise > 0) {
    stepwise--;
    if (stepwise == 0) Animation.stop();
  };
};



</script>
</body>
</html>

Vorschau Download Kopie speichern

Aufgabe

Protokolliere die jeweils beste Fitness während des Verfahrens (im Abstand von je 20 Generationen). Welche Beobachtungen kannst du machen?