Ant Colony Optimization in D3.js

Crude implementation of ACO in D3js, based on the awesome work of Joel Wenzel et al.

<!DOCTYPE html>
<meta charset="utf-8">
<style>
  body { margin: 0 }
</style>
<body>
  <div id="map"></div>
  <script src="https://d3js.org/d3.v3.min.js" charset="utf-8"></script>
  <script>
  !function(context){

var points = 20
      , waves = 40
      , nodes = []
      , stage = {
            height: context.innerHeight
          , width: context.innerWidth
        };

var wave = function(nodes){
      var self = extend(this, { nodes: nodes });

var NUM_ANTS = 20
        , RHO = 0.1      // Decay rate of the pheromone trails
        , BETA = 3.0     // Importance of the durations
    	, ALPHA = 0.1    // Importance of the previous trails
    	, Q = 1.0;       // see wikipedia - updating pheromones

var result = initPheromones();
	    var _pher = result.pheromones;
	    var _nextPher = result.pherUpdates;

self.route = [];
      self.distance;
      self.routes;
      self.distances;

self.runOnce = function(){
    		var result = sendWave(NUM_ANTS,_pher,_nextPher);
    		self.routes = result.paths;
    		self.distances = result.distances;
    	}

function initPheromones(){
    		//init pheremons
        var pheromones = new Array(self.nodes.length);
    		var pherUpdates = new Array(self.nodes.length);

/*
    		Get the average distance between points - https://www.ugosweb.com/Download/JavaACSFramework.pdf

Note that for each point, the distance to itself is 0.  This means that
    		the total number of valid distances is numPoints*(numPoints-1) since the distance
    		to itself is not valid
    		*/
    		var dsum = 0;
        for (var i = 0; i < self.nodes.length; i++) {
          dsum += self.nodes[i].avg;
        }
    		//each point has n-1 edges
    		var totalEdges = (20*(20-1));
    		var avgDistance = dsum / totalEdges;
    		var initVal = Q / avgDistance;

for (var i = 0; i < 20; ++i) {
    		  pheromones[i] = new Array(20);
    		  pherUpdates[i] = new Array(20);

for (var j = 0; j < 20; ++j) {
    		    pheromones[i][j] = initVal;
    		    pherUpdates[i][j] = 0.0;
    		  }
    		}

return { pheromones:pheromones, pherUpdates:pherUpdates };
    	}

function sendWave(numAnts, pheromones, pherUpdates){
        var startPoint = null; //parseInt(Math.random()*self.nodes.length);

var paths = new Array(numAnts);
    		var distances = new Array(numAnts);

var changed = false;
    		for (var ant = 0; ant < numAnts; ++ant)
    		{
    			var result = findAntPath(pheromones, pherUpdates, startPoint);
    			paths[ant] = result.path;
    			distances[ant] = result.distance;

if(self.route.length ==0 || result.distance<self.distance){
    				self.distance = result.distance;
    				self.route = result.path;
    				changed = true;
    			}
    		}

//update the smell globally
    		for (var i = 0; i < self.nodes.length; ++i)
    		{
    			for (var j = 0; j < self.nodes.length; ++j)
    			{
    				pheromones[i][j] =
    				//decay old pheromone
    				pheromones[i][j] * (1.0 - RHO)
    				//add new pheromone
    				+ pherUpdates[i][j];

pherUpdates[i][j] = 0.0;
    			}
    		}

return {paths:paths, distances:distances, changed:changed};
    	}

function findAntPath(pheromones, pherUpdates, startPoint){

var currPath = new Array(self.nodes.length);
    		var probability = new Array(self.nodes.length);
    		var visited = new Array(self.nodes.length);

if(startPoint == null){
    			//start at a random location
    			startPoint = parseInt(Math.random()*self.nodes.length);
    		}

var curr = startPoint;
    		currPath[0] = curr;

//get path for the ant
    		//any has to visit each point so run this numPoints times
    		//minus one since we visit the first node already
    		for (var step = 1; step < self.nodes.length; step++){
    			visited[curr] = 1;

//probability for next visit
    			var probSum = 0.0;
    			for (var next = 0; next < self.nodes.length; next++){
    				if (visited[next] != 1){
    					//probability[next] = distanceAB^-beta * pheromoneAB^alpha
    					//see reference formula
    					probability[next] = Math.pow(pheromones[curr][next], ALPHA) * Math.pow(self.nodes[curr].distances[next], 0.0-BETA);
    					probSum += probability[next];
    				}
    				else {
    					probability[next] = 0;
    				}
    			}

//One method is to convert the probability array to actual probabilities by
    			//dividing by probSum.  Then create a random value between 0 and 1 and add up probabilities
    			//for each path to the next point until one finally surpasses the random value.
    			//This point would be chosen for the next path.  Google does the same thing but
    			//Just takes a percentage of probSum rather than convert everything to probabilities
    			//between 0 and 1
    			var nextCity = -1;
    			var nextThresh = Math.random()*probSum;
    			for(var i=0;i<self.nodes.length;i++){
    				nextThresh -= probability[i];
    				if (nextThresh<=0) {
    					nextCity = i;
    					break;
    				}
    			}

currPath[step] = nextCity;
    			curr = nextCity;
    		}

/* do k2 optimization
    		var opt2 = new Tsp.Sequential2OptRunner({startRoute:currPath, distances:_distances, isKnownStart:false});
    		while(opt2.runOnce()){}
    		currPath = opt2.route;*/

var currDist = function(route, from, to){
      		var cost = 0;
      		for(var i=from+1;i<=to;i++){
            cost += self.nodes[route[i-1]].distances[route[i]];
      		}
      		return cost;
      	}(currPath, 0, currPath.length-1);

//store pheromons so that they can be added to the previous
    		//values after all the ants have finished
    		for (var i = 0; i < self.nodes.length-1; i++)
    		{
    			pherUpdates[currPath[i]][currPath[i+1]] += Q/currDist;
    		}

return {distance:currDist, path:currPath};
    	}

return self;
    };

var node = function(config){
      extend(this, config);
      return this;
    };

node.prototype = {
      calibrate: function(){
        this.sum = 0;
        this.avg = 0;
        for (var i = 0; i < nodes.length; i++){
          this.distances[i] = distance(nodes[this.id], nodes[i]);
          this.sum += this.distances[i];
        }
        this.avg = this.sum / this.distances.length;
        return this;
      }
    };

function distance(a, b){
      return Math.sqrt(Math.pow(b.x - a.x, 2) + Math.pow(b.y - a.y, 2));
    }

// Generate random points
    for (var i = 0; i < points; i++){
      nodes.push(new node({
          id: i
        , x: Math.floor(Math.random() * (stage.width - 50)) + 25
        , y: Math.floor(Math.random() * (stage.height - 50)) + 25
        , distances: new Array(points)
        , sum: 0
        , avg: 0
      }));
    }

// Compose the landscape
    var svg = d3.select("#map").append("svg");

var dots = svg.append("svg:g")
      .attr("class", "nodes")
      .selectAll("g.point")
        .data(nodes);

dots
      .enter()
      .append("svg:g")
        .attr("class", "point")
        .attr("transform", function(d,i){ return "translate(" + d.x + ", " + d.y + ")"; })
        .call(draggable)
        .append("svg:circle")
          .attr("r", 10)
          .attr("stroke", "#fff")
          .attr("stroke-width", 3);

var paths = svg.selectAll("line.path");
    var edges = [];

function run(){
      // Calculate distance between all points
      for (var i = 0; i < nodes.length; i++){
        nodes[i].calibrate();
        waves = 40;
      }

var runner = new wave(nodes);
      var aco_timer = setInterval(function(){
        var result;
        waves--;
        result = runner.runOnce();
        if (!waves || waves < 0){
          waves = 40;
          clearInterval(aco_timer);
        }

edges = [];
        for (var i = 0; i < runner.route.length-1; i++){
          edges.push({
              source: nodes[runner.route[i]]['id']
            , target: nodes[runner.route[i+1]]['id']
            , x1: nodes[runner.route[i]]['x']
            , y1: nodes[runner.route[i]]['y']
            , x2: nodes[runner.route[i+1]]['x']
            , y2: nodes[runner.route[i+1]]['y']
          });
        }

paths = paths.data(edges);

paths
          .enter()
          .insert("line", "g.nodes")
            .attr("class", "path")

paths
            .attr("stroke", "#333")
            .attr("stroke-width", 10)
            .attr("stroke-opacity", .1)
            .attr("x1", function(d,i){ return d.x1 })
            .attr("y1", function(d,i){ return d.y1 })
            .attr("x2", function(d,i){ return d.x2 })
            .attr("y2", function(d,i){ return d.y2 });

paths
          .exit()
          .transition()
          .remove();

}, 50);
    };
    run();

}(this);
  </script>
</body>

Modified http://d3js.org/d3.v3.min.js to a secure url

https://d3js.org/d3.v3.min.js