On the landscape ruggedness of the quadratic assignment problem

On the landscape ruggedness of the quadratic assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20023710
Country: United States
Volume: 263
Issue: 1/2
Start Page Number: 159
End Page Number: 172
Publication Date: Jul 2001
Journal: Theoretical Computer Science
Authors: ,
Keywords: quadratic assignment
Abstract:

Local-search-based heuristics have been demonstrated to give very good results to approximately solve the quadratic assignment problem (QAP). In this paper, following the works of Weinberger and Stadler, we introduce a parameter, called the ruggedness coefficient, which measures the ruggedness of the QAP landscape which is the union of a cost function and a neighborhood. We give an exact expression, and a sharp lower bound for this parameter. We are able to derive from it that the landscape of the QAP is rather flat, and so it gives a theoretical justification of the effectiveness of local-search-based heuristics for this problem. Experimental results with simulated annealing are presented which confirm this conclusion and also the influence of the ruggedness coefficient on the quality of results obtained.

Reviews

Required fields are marked *. Your email address will not be published.