TY - JOUR

T1 - A cutoff time strategy based on the coupon collector’s problem

AU - Lobo, Fernando G.

AU - Bazargani, Mosab

AU - Burke, Edmund K.

PY - 2020/10/1

Y1 - 2020/10/1

N2 - Throughout the course of an optimization run, the probability of yielding further improvement becomes smaller as the search proceeds, and eventually the search stagnates. Under such a state, letting the algorithm continue to run is a waste of time as there is little hope that subsequent improvement can be made. The ability to detect the stagnation point is therefore of prime importance. If such a point can be detected reliably, then it is possible to make better use of the computing resources, perhaps restarting the algorithm at the stagnation point, either with the same or with a different parameter configuration. This paper proposes a cutoff time strategy. It presents a method that is able to reliably detect the stagnation point for one-point stochastic local search algorithms applied to combinatorial optimization problems. The strategy is derived from the coupon collector’s problem, and is scalable based on the employed perturbation operator and its induced neighbourhood size, as well as from feedback from the search. The suitability and scalability of the method is illustrated with the Late Acceptance Hill-Climbing algorithm on a comprehensive set of benchmark instances of three well-known combinatorial optimization problems: the Travelling Salesman Problem, the Quadratic Assignment Problem, and the Permutation Flowshop Scheduling Problem.

AB - Throughout the course of an optimization run, the probability of yielding further improvement becomes smaller as the search proceeds, and eventually the search stagnates. Under such a state, letting the algorithm continue to run is a waste of time as there is little hope that subsequent improvement can be made. The ability to detect the stagnation point is therefore of prime importance. If such a point can be detected reliably, then it is possible to make better use of the computing resources, perhaps restarting the algorithm at the stagnation point, either with the same or with a different parameter configuration. This paper proposes a cutoff time strategy. It presents a method that is able to reliably detect the stagnation point for one-point stochastic local search algorithms applied to combinatorial optimization problems. The strategy is derived from the coupon collector’s problem, and is scalable based on the employed perturbation operator and its induced neighbourhood size, as well as from feedback from the search. The suitability and scalability of the method is illustrated with the Late Acceptance Hill-Climbing algorithm on a comprehensive set of benchmark instances of three well-known combinatorial optimization problems: the Travelling Salesman Problem, the Quadratic Assignment Problem, and the Permutation Flowshop Scheduling Problem.

KW - Metaheuristcs

KW - Stochastic local search

KW - Late acceptance hill-climbing

KW - Cutoff time

KW - Coupon collector’s problem

U2 - 10.1016/j.ejor.2020.03.027

DO - 10.1016/j.ejor.2020.03.027

M3 - Article

VL - 286

SP - 101

EP - 114

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -