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 method in which the current cost serves as an acceptance bound for a number of consecutive steps. This is the only parameter in the method that should be set up b...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
Springer
2016
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/32920/ |
| _version_ | 1848794519350280192 |
|---|---|
| author | Bykov, Yuri Petrovic, Sanja |
| author_facet | Bykov, Yuri Petrovic, Sanja |
| author_sort | Bykov, Yuri |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | This paper presents a new single-parameter local search heuristic named Step Counting Hill Climbing algorithm (SCHC). It is a very simple method in which the current cost serves as an acceptance bound for a number of consecutive steps. This is the only parameter in the method that should be set up by the user. Furthermore, the counting of steps can be organized in different ways; therefore the proposed method can generate a large number of variants and also extensions. In this paper, we investigate the behaviour of the three basic variants of SCHC on the university exam timetabling problem. Our experiments demonstrate that the proposed method shares the main properties with the Late Acceptance Hill Climbing method, namely its convergence time is proportional to the value of its parameter and a non-linear rescaling of a problem does not affect its search performance. However, our new method has two additional advantages: a more flexible acceptance condition and better overall performance. In this study we compare the new method with Late Acceptance Hill Climbing, Simulated Annealing and Great Deluge Algorithm. The Step Counting Hill Climbing has shown the strongest performance on the most of our benchmark problems used. |
| first_indexed | 2025-11-14T19:17:29Z |
| format | Article |
| id | nottingham-32920 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:17:29Z |
| publishDate | 2016 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-329202020-05-04T20:01:39Z https://eprints.nottingham.ac.uk/32920/ A step counting hill climbing algorithm Bykov, Yuri Petrovic, Sanja This paper presents a new single-parameter local search heuristic named Step Counting Hill Climbing algorithm (SCHC). It is a very simple method in which the current cost serves as an acceptance bound for a number of consecutive steps. This is the only parameter in the method that should be set up by the user. Furthermore, the counting of steps can be organized in different ways; therefore the proposed method can generate a large number of variants and also extensions. In this paper, we investigate the behaviour of the three basic variants of SCHC on the university exam timetabling problem. Our experiments demonstrate that the proposed method shares the main properties with the Late Acceptance Hill Climbing method, namely its convergence time is proportional to the value of its parameter and a non-linear rescaling of a problem does not affect its search performance. However, our new method has two additional advantages: a more flexible acceptance condition and better overall performance. In this study we compare the new method with Late Acceptance Hill Climbing, Simulated Annealing and Great Deluge Algorithm. The Step Counting Hill Climbing has shown the strongest performance on the most of our benchmark problems used. Springer 2016-08 Article PeerReviewed Bykov, Yuri and Petrovic, Sanja (2016) A step counting hill climbing algorithm. Journal of Scheduling, 19 (4). pp. 479-492. ISSN 1099-1425 Optimisation Metaheuristics Simulated Annealing Late Acceptance Hill Climbing Step Counting Hill Climbing Exam Timetabling http://link.springer.com/article/10.1007%2Fs10951-016-0469-x doi:10.1007/s10951-016-0469-x doi:10.1007/s10951-016-0469-x |
| spellingShingle | Optimisation Metaheuristics Simulated Annealing Late Acceptance Hill Climbing Step Counting Hill Climbing Exam Timetabling Bykov, Yuri Petrovic, Sanja A step counting hill climbing algorithm |
| title | A step counting hill climbing algorithm |
| title_full | A step counting hill climbing algorithm |
| title_fullStr | A step counting hill climbing algorithm |
| title_full_unstemmed | A step counting hill climbing algorithm |
| title_short | A step counting hill climbing algorithm |
| title_sort | step counting hill climbing algorithm |
| topic | Optimisation Metaheuristics Simulated Annealing Late Acceptance Hill Climbing Step Counting Hill Climbing Exam Timetabling |
| url | https://eprints.nottingham.ac.uk/32920/ https://eprints.nottingham.ac.uk/32920/ https://eprints.nottingham.ac.uk/32920/ |