A cutoff time strategy based....pdf (592.28 kB)
A cutoff time strategy based on the coupon collector's problem
journal contributionposted on 2020-06-22, 09:50 authored by Fernando G Lobo, Mosab Bazargani, Edmund K Burke
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.
We thank EU Cost Action CA15140 for funding the STSM of Mosab Bazargani to visit the University of Algarve in Nov-Dec/2017. The ideas contained in this paper got started during that visit. This work was also supported by Fundação para a Ciência e Tecnologia, I.P., Portugal (UID/AMB/04085/2019), and by EPSRC grant EP/J017515/1.
CitationEuropean Journal of Operational Research 286 (2020) 101-114
- VoR (Version of Record)