Empirical analysis of local search algorithms

Posted on   April 18th, 2010

Last week in Artificial Intelligence (5th year’s subject in FIB, my university), we worked in a project analysing the empirical differences among some local search algorithms. We were given AIMA, an AI Java framework, and a problem to solve with those algorithms. The problem consisted basically of creating optimal K bus routes in a squared city (called SquareTown) for a randomly generated set of P bus stops. By optimal they meant minimal cover distance including all stops and minimal difference between the distances of every two consecutive stops. The algorithms to be used were Hill Climbing and Simulated Annealing. The full formulation of the problem can be found here (in Spanish).

Our findings were quite interesting, and I will sum them up in the following points:

  • The HC (Hill Climbing) algorithm is extremely fast (it gets to a solution almost instantly).
  • If HC starts from a smart initial solution it can get pretty good results (30-40% better than random initial solution).
  • SA (Simulated Annealing) is slower than the former (like 100x slower).
  • If well parametrized (by trial and error, of course), SA gets better results than HC (from 0.5x to 2.5x times better).
  • SA doesn’t care about the initial solution, even using a smart one we got results only 3-5% better.
  • Using a completely indeterministic (random) initial solution, it improves the performance of SA even better than using the smart initial solution, conversely to what happens with HC.
  • If we run HC consecutively with an indeterministic initial solution each time (indeed for a unique problem), we get even better results than SA in its best conditions. The number of iterations is chosen to be equivalent to the time taken by SA. In our case, we were getting the same results of SA with half its elapsed time. This approach is called RRHC (Random Restart Hill Climbing).
  • The bigger the problem gets (the space to search) the worse are the results for both approaches.

Our code (of Jordi and I) is now public in Github and can be used by anyone (read the REAME). The important files are SquareTown.java, where we implement the whole problem and Main.java, where we execute the experimentation (pay no attention to the code of the Main,  due to the last-minute policy of coding projects for university, it is quite filthy). The project’s final documentation can be found here (in Catalan).

Update: We got a 8/10 for the project.

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

Tags:

2 Comments »