Late Acceptance Hill Climbing (and diversified) are algorithms in this field that came out after this paper was originally written and I wonder how it compares (maybe the author is around and can comment?)