Skip to content

Instantly share code, notes, and snippets.

@dustinlarimer

dustinlarimer/README.md

Last active October 20, 2017 05:40
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dustinlarimer/6d58d11e127b9c9c5f21 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dustinlarimer/6d58d11e127b9c9c5f21 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Dustin Larimer revised this gist Jun 28, 2014. 1 changed file with 2 additions and 13 deletions.
    15 changes: 2 additions & 13 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -23,8 +23,8 @@
    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
    , ALPHA = 0.1 // Importance of the previous trails
    , Q = 1.0; // see wikipedia - updating pheromones

    var result = initPheromones();
    var _pher = result.pheromones;
    @@ -57,7 +57,6 @@
    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;
    @@ -73,9 +72,6 @@
    }
    }

    for (var i = 0; i < self.nodes.length; i++){
    //self.pheromones.push(new pheromone());
    }
    return { pheromones:pheromones, pherUpdates:pherUpdates };
    }

    @@ -287,18 +283,11 @@
    var paths = svg.selectAll("line.path");
    var edges = [];

    function dragmove(d) {
    var x = d3.event.x;
    var y = d3.event.y;
    d3.select(this).attr("transform", "translate(" + x + "," + y + ")");
    }

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

    var runner = new wave(nodes);
  2. Dustin Larimer created this gist Jun 28, 2014.
    1 change: 1 addition & 0 deletions README.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    Crude implementation of ACO in D3js, based on the awesome work of [Joel Wenzel et al](http://joel.inpointform.net/software-development/traveling-salesman-ant-colony-optimization-javascript-solution/).
    353 changes: 353 additions & 0 deletions index.html
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,353 @@
    <!DOCTYPE html>
    <meta charset="utf-8">
    <style>
    body { margin: 0 }
    </style>
    <body>
    <div id="map"></div>
    <script src="http://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 - http://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;
    }
    }

    for (var i = 0; i < self.nodes.length; i++){
    //self.pheromones.push(new pheromone());
    }
    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));
    }

    function extend(target){
    for (var i = 1; i < arguments.length; i++) {
    for (var prop in arguments[i]){
    target[prop] = arguments[i][prop];
    }
    }
    return target;
    }



    // 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 draggable = d3.behavior.drag()
    .on("dragstart", function(d){
    for (var i = 0; i < edges.length; i++){
    if (edges[i]['source'] == d.id || edges[i]['target'] == d.id) {
    paths.attr("stroke-opacity", 0);
    //paths[0][i].remove();
    }
    }
    })
    .on("drag", function(d, i){
    d.x = d3.event.x;
    d.y = d3.event.y;
    d3.select(this)
    .attr("transform", function(d,i){
    return "translate(" + d.x + ", " + d.y + ")";
    })
    })
    .on("dragend", function(){
    run();
    });

    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 dragmove(d) {
    var x = d3.event.x;
    var y = d3.event.y;
    d3.select(this).attr("transform", "translate(" + x + "," + y + ")");
    }

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

    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>