Empirical analysis of local search algorithms
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: artificial intelligencefibhill climbingiajavalocal search algorithmssimulated annealing
2 Comments »
2 Comments on “Empirical analysis of local search algorithms”
Follow comments feed
The document is pretty awesome, although we didn’t have the time to check its correctness… I’m not responsible for it.
We want moar tech posts (Ruby, rails, git, …)
Our assignment talked about the Bicing bicycle rental service in Barcelona, and simulating user and transportation van movements.
We simulated the actual service with the 418 existing stations, 50 bicycles in each station, 30 vans for moving them around, and simulated different bicycle distributions and usages, like a rush hour scenario and an equilibrium scenario. We also had two ways of generating the initial solution, a random way, and an n*log(n) intelligent way.
After almost 8 hours of simulation, we get the results and they were clear as water, just by adding 15 vans to the Bicing service our heuristic improved in a 10%.
I guess by now you must be enjoying Clips and Protégé ^^