A Step Counting Hill Climbing Algorithm

This paper presents a new single-parameter local search heuristic named Step Counting Hill Climbing algorithm (SCHC). It is a very simple technique, where the current cost serves as an acceptance bound for a number of consequent steps. This number is a sole algorithmic parameter, which should be set up by the user. Furthermore, the counting of steps can be organized in different ways, so the proposed method supposes a high number of variants and modifications. In this paper, we investigate three basic versions of SCHC with the university exam timetabling problem. Our experiments demonstrate that the proposed technique has the properties quite similar to the Late Acceptance Hill Climbing method, i.e. the convergence time is proportional to the value of its parameter and a non-linear rescaling of a problem does not affect the search performance. However, our new method has two additional advantages: a more flexible acceptance condition and better (on average) overall performance. In this study we present the comparison of these two search techniques, and compare both of them with Simulated Annealing. The Step Counting Hill Climbing has shown the strongest performance over three competitor algorithms on the most of our benchmark problems.