[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink])

Random walks are random moves in the search space that disregard the change of the cost function value. The idea is that the search is retracted from hopeless situations (like local minima) from time to time. Unlike restarts, random walks remain within the area of the current state.

Random walks can be included by introducing a second improvement heuristic for each constraint that makes a random variation of a random variable. The following figure shows the results for different probabilities for the random variation heuristics to be chosen. It is obvious that the random walks generally cause a deterioration in the results. At no point is there a cross-over: the more random walks, the more inconsistency.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek