Nonlinear threshold accepting meta-heuristic for combinatorial optimisation problems
by Nabil Nahas; Mustapha Nourelfath
International Journal of Metaheuristics (IJMHEUR), Vol. 3, No. 4, 2014

Abstract: Local search algorithms are a wide class of improvement algorithms that start from a given solution and try to find a better solution in a defined neighbourhood of the current solution. Stochastic hill climbing algorithms, such as threshold accepting algorithms and simulated annealing are optimisation techniques which belong to the family of local search algorithms. The main difference between the existing algorithms resides in the mechanism of accepting or rejecting the candidate solution from the neighbourhood. In this paper, we test a simple but effective modification of the conventional threshold accepting algorithm. In the proposed variant, the acceptance rule is nonlinear. This acceptance rule is inspired from the RC-filter which is a low-pass filter used in electronics to reduce the amplitude of signals with higher frequencies. We apply the newly developed meta-heuristic to difficult instances of four combinatorial optimisation problems, namely quadratic assignment problem, dynamic discrete facility layout problems, flow-shop scheduling and berth allocation. The results presented show that this algorithm performs well for several test problems. Therefore, it can be used as a specialised heuristic for these problems.

Online publication date: Sat, 25-Apr-2015

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Metaheuristics (IJMHEUR):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com