TSP / ant colony
A first try at optimizing Java code line by line. It came out of a project on metaheuristics with Dietmar Meiringer at the University of Basel.
This started as a final assignment for a course on metaheuristic algorithms at Uni Basel. My report was about how ants find their way with pheromones, and how you can use that to solve optimization problems.
Ants are tiny and simple, but a colony still finds good paths to food. At first they wander around and leave a scent trail. Other ants prefer paths that already have scent, and a path that leads to food gets stronger the more ants use it. The same idea works for the travelling salesman problem, where you want the shortest round trip through a set of cities. You send lots of virtual ants through the cities. Each one picks its next city depending on how much pheromone lies on the way and how close the city is. After every round, the shorter tours get more pheromone, and the old pheromone slowly evaporates.
To play with it, I built a Java program with a window where you can watch the ants work live and change how many ants there are, how many rounds they get, how much they care about pheromone versus distance, and how fast it evaporates. It runs on random cities or on a small New York example, where you can even block a road. There is also a browser demo, which is a smaller JavaScript version of the same idea, not the Java program itself. I wrote it step by step with help from Codex.
Then I tried it out, always comparing the same ants with and without pheromone. On my New York example with eight sights, the tour got only about 3% shorter (27.30 to 26.43), which is so little that it could just be luck. So I made up a bigger problem with 200 cities, and there the pheromone helped clearly: about 13% shorter (5022 to 4390). My takeaway is that ant colony optimization is no magic trick, but it looked more useful the bigger the problem got. These are single runs on problems I made up, so this is an experiment, not a benchmark.
After the report I went back to make the program faster. I profiled it with Java Flight Recorder and found that about 82% of the time goes into picking the next city, which every ant does at every step. Caching the distances and looking up pheromone by row helped. A run with 340 cities, 420 ants and 200 rounds now takes about 4.7 seconds on my Mac. Going much faster would need a different approach, so I left it there.