Feb 102013

Just a quick one (mostly to remind myself that I have a blog which needs updating!)

One of my courseworks at university was to implement ant colony optimization for the traveling salesman problem.

My solution was one of the more self contained and interesting pieces of my work at uni. So I put it up on GitHub.

I was amazed at how much faster this algorithm was compared to the earlier genetic algorithm based approaches I tried during the course. The only non vanilla part of the implementation is an approximation for the Math.pow function in java which sped up the whole program up by a decent amount.

// Approximate power function, Math.pow is quite slow and we don't need accuracy. // See: // http://martin.ankerl.com/2007/10/04/optimized-pow-approximation-for-java-and-c-c/ // Important facts: // - >25 times faster // - Extreme cases can lead to error of 25% - but usually less. // - Does not harm results -- not surprising for a stochastic algorithm. public static double pow(final double a, final double b) { final int x = (int) (Double.doubleToLongBits(a) >> 32); final int y = (int) (b * (x - 1072632447) + 1072632447); return Double.longBitsToDouble(((long) y) << 32); } |