article

On the landscape ruggedness of the quadratic assignment problem

Authors:

Eric Angela,

Vassilis ZissimopoulosbAuthors Info & Claims

Theoretical Computer Science, Volume 263, Issue 1-2

Pages 159 - 172

https://doi.org/10.1016/S0304-3975(00)00239-5

Published: 28 July 2001 Publication History

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 coeffcient, 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 toderive 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 con8rm this conclusion and also the influence of the ruggedness coe5cient on the quality of results obtained.

References

[1]

E. Angel, V. Zissimopoulos, Autocorrelation coe5cient for the graph bipartitioning problem, Theoret. Comput. Sci. 191 (1998) 229-243.

Digital Library

Google Scholar

[2]

E. Angel, V. Zissimopoulos, On the quality of local search for the quadratic assignment problem, Discrete Appl. Math. 82 (1998) 15-25.

Crossref

Google Scholar

[3]

G.F.M. Beenker, T.A.C.M. Claasen, P.W.C. Hermens, Binary sequences with a maximally 6at amplitude spectrum, Philips J. Res. 40 (1985) 289-304.

Google Scholar

[4]

D.T. Connolly, An improved annealing scheme for the qap, European J. Oper. Res. 46 (1990) 93-100.

Crossref

Google Scholar

[5]

M. Dorigo, V. Maniezzo, A. Colorni, Algodesk: an experimental comparison of eight evolutionary heuristics for the quadratic assignment problem, European J. Oper. Res 81 (1995) 188-204.

Crossref

Google Scholar

[6]

M.R. Garey, D.S. Johnson, Computers and Intractability - a Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco, CA, 1979.

Digital Library

Google Scholar

[7]

D.S. Johnson, Local optimization and the traveling salesman problem, ICALP 90 Automata, Languages and Programming, 1990, pp. 446-461.

Crossref

Google Scholar

[8]

D.S. Johnson, C.R. Aragon, L.A. McGeoch, C. Schevon, Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning, Oper. Res. 37 (6) (1989) 865-892.

Digital Library

Google Scholar

[9]

T.C. Koopmans, M. Beckmann, Assigment problems and the location of economic activities, Econometrica 25 (1957) 53-76.

Crossref

Google Scholar

[10]

Y. Li, P.M. Pardalos, Generating quadratic assignment test problems with known optimal permutations, Comput. Optim. Appl. 1 (1992) 163-184.

Crossref

Google Scholar

[11]

S. Sahni, T. Gonzalez, P-complete approximation problems, J. ACM 23 (1976) 555-565.

Digital Library

Google Scholar

[12]

P.F. Stadler, Landscapes and their correlation functions Tech. Rep. 95-07-067, Santa Fe institute, Santa Fe, NM, 1995.

Google Scholar

[13]

E.D. Taillard, Comparison of iterative searches for the quadratic assignment problem, Location Sci. 3 (1995) 87-105.

Crossref

Google Scholar

[14]

E.D. Weinberger, Correlated and uncorrelated 8tness landscapes and how to tell the di9erence, Biol. Cybernet. 63 (1990) 325-336.

Digital Library

Google Scholar

Cited By

View all

Moser IGheorghita MAleti A(2017)Identifying features of fitness landscapes and relating them to problem difficultyEvolutionary Computation10.1162/evco_a_0017725:3(407-437)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1162/evco_a_00177
Chicano FLuque GAlba EAlba E(2013)Problem understanding through landscape theoryProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482683(1055-1062)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2482683
Chicano FAlba E(2013)Elementary landscape decomposition of the 0-1 unconstrained quadratic optimizationJournal of Heuristics10.1007/s10732-011-9170-619:4(711-728)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1007/s10732-011-9170-6
Show More Cited By

Index Terms

On the landscape ruggedness of the quadratic assignment problem
1. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem

The quadratic assignment problem (QAP) is one of the well-known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP - M-SA-QAP. The novelty of the ...
Memetic search for the quadratic assignment problem

We present a memetic algorithm (called BMA) for the well-known QAP.BMA integrates BLS within the population-based evolutionary computing framework.BMA is able to attain the best-known results for 133 out of 135 QAP benchmark instances.We provide ...
A tabu search algorithm for the quadratic assignment problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 263, Issue 1-2

July 28 2001

369 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 28 July 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Moser IGheorghita MAleti A(2017)Identifying features of fitness landscapes and relating them to problem difficultyEvolutionary Computation10.1162/evco_a_0017725:3(407-437)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1162/evco_a_00177
Chicano FLuque GAlba EAlba E(2013)Problem understanding through landscape theoryProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482683(1055-1062)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2482683
Chicano FAlba E(2013)Elementary landscape decomposition of the 0-1 unconstrained quadratic optimizationJournal of Heuristics10.1007/s10732-011-9170-619:4(711-728)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1007/s10732-011-9170-6
Chicano FDaolio FOchoa GVérel STomassini MAlba E(2012)Local optima networks, landscape autocorrelation and heuristic search performanceProceedings of the 12th international conference on Parallel Problem Solving from Nature - Volume Part II10.1007/978-3-642-32964-7_34(337-347)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32964-7_34
Chicano FAlba E(2012)Exact computation of the fitness-distance correlation for pseudoboolean functions with one global optimumProceedings of the 12th European conference on Evolutionary Computation in Combinatorial Optimization10.1007/978-3-642-29124-1_10(111-123)Online publication date: 11-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-29124-1_10
Chicano FWhitley LAlba E(2011)A methodology to find the elementary landscape decomposition of combinatorial optimization problemsEvolutionary Computation10.1162/EVCO_a_0003919:4(597-637)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1162/EVCO_a_00039
Chicano FLuque GAlba EPelikan MBranke J(2010)Elementary landscape decomposition of the quadratic assignment problemProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830745(1425-1432)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830745
Tseng LLiang S(2006)A Hybrid Metaheuristic for the Quadratic Assignment ProblemComputational Optimization and Applications10.1007/s10589-005-3069-934:1(85-113)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1007/s10589-005-3069-9
Angel EZissimopoulos V(2002)On the Hardness of the Quadratic Assignment Problem with MetaheuristicsJournal of Heuristics10.1023/A:10154546122138:4(399-414)Online publication date: 1-Jul-2002
https://dl.acm.org/doi/10.1023/A%3A1015454612213

Abstract

References

Cited By

Index Terms

Recommendations

A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem

Memetic search for the quadratic assignment problem

A tabu search algorithm for the quadratic assignment problem

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations