RSS Feed
London and Ant Colony Algorithms
So, I’m no longer in London, but I still haven’t written something for a while. Time to rectify that! First, I’ll mention an interesting DDJ article concerning ACOs – Ant Colony Algorithms.
The main idea is to combine a greedy short-time search with an evenhanded one, and in combination these two will cancel out each others’ flaws. As an example, the article tests a simple algorithm on the Travelling Salesman Problem, and the results are pretty good: within 100 iterations, a close-to-optimal-as-far-as-we-know-it-solution is found! 100 iterations? Yes, the algorithm depends on using ant-like behaviour, and knowledge from the previous iteration is used in the next one. An ant selects a path based on distance and the amount of pheromones placed on the path by previous ants, and afterwards places an amount of pheromones inversely proportional to the distance of the traversed paths; the pheromones also evaporate with time. Apparently, all this creates a positive feedback loop without the risk of landing at a local maximum.
Somehow I get the feeling that I’ve heard of this algorithm before, but I really can’t put my finger on it. It might simply be the fact that it combines search strategies and machine learning ideas, all of which are commonplace and well-known. Or, it might be the fact that it’s derived from some routing algorithm I’ve read about. Or, it might be the fact that I’ve read about it in some AI book – the author of the article makes no claims to have been overly original. Either way, I get a sudden urge to see this in action – I want to implement a graphical representation of flock behaviour in combination with an ant colony algorithm that doesn’t work in iterations, but continuously instead!
…
Back to the topic of London. In my last update I had had a very haphazard view of the city: pubs, an office, the hotel bar, Trafalgar Square, and so on. I had been a busy little tourist, taking pictures of statues and architecture and arches and whatnot. This continued later that day, when we went to Westminster to watch Big Ben and the lovely lions in front of whatever-that-house-was, and strolled over to the Tower and the Tower Bridge. That’s when disaster struck: one single picture of the Tower caused my digital camera to cough and wheeze, complaining that the memory card was being naughty. All my photos were gone.
This is a serious shame, as London is one of the most beautiful cities I have seen. The streets tell tales of long ago; roads and streets twine in insane ways, showing that the city can’t really have been planned – it must have grown from the old London Town. Beside that, the city is riddled with architectural delights everywhere. I kid you not when I say that there’s something worth watching in every street of the inner city: a statue placed here; magnificent Neoclassicistic pillars there; wonderful churches all over the place. As I walked around, I recalled that Sir Christopher Wren was the architect of many dozens of London’s churches, but to my dismay I couldn’t tell for sure when I actually saw them. “Wren spires” was a term that flowed through my mind, but the only Wren church (well, cathedral) that I could recall with certainity was St Paul’s Cathedral – which certainly didn’t have a spire.
Anyway, after that final day of rest, things got a bit blurred. I was supposed to be in London for a few days, but it turned into 10 days or so. And these days were filled with work from morning to late evening, and then a frantic search for pubs. Thank you God for this liver of steel!
After my last blog entry I got recommended the Oxo Tower restaurant, but since things got so frantic we really didn’t have time to go looking for it. That’s a damn shame. Also, Dan Marshall of Gibbage fame and fortune kindly gave me a nice list of pubs that I ought to visit. (Which I of course forgot to reply to, lazy bastard that I am, so I’ll link to his site instead as a thank-you.) Again, since we were pretty swamped, we only ended up visiting a single one of those: The Pillars of Hercules on Greek Street. Very nice indeed! Still, I think our favourite pub was The Marlborough Head. It had a horror theme, and was located pretty close to our hotel.
Finally, I have to mention something awesome: London is a city of musicals, and I seriously would have killed myself if I hadn’t gone to a single one. I wanted to see Phantom of the Opera, but the tickets were rather pricey. Instead I found a great surprise: Avenue Q has a London show as well as a Broadway one! You know, the show where the Internet is for Porn song comes from. It may not be the highest form of culture, and the jokes may be a bit crude at times, but I seriously loved it. Make sure you watch it as well, given an opportunity!