research-article

Fitness landscape analysis and memetic algorithms for the quadratic assignment problem

Authors:

P. Merz,

B. FreislebenAuthors Info & Claims

IEEE Transactions on Evolutionary Computation, Volume 4, Issue 4

Pages 337 - 352

https://doi.org/10.1109/4235.887234

Published: 01 November 2000 Publication History

Abstract

In this paper, a fitness landscape analysis for several instances of the quadratic assignment problem (QAP) is performed, and the results are used to classify problem instances according to their hardness for local search heuristics and meta-heuristics based on local search. The local properties of the fitness landscape are studied by performing an autocorrelation analysis, while the global structure is investigated by employing a fitness distance correlation analysis. It is shown that epistasis, as expressed by the dominance of the flow and distance matrices of a QAP instance, the landscape ruggedness in terms of the correlation length of a landscape, and the correlation between fitness and distance of local optima in the landscape together are useful for predicting the performance of memetic algorithms-evolutionary algorithms incorporating local search (to a certain extent). Thus, based on these properties, a favorable choice of recombination and/or mutation operators can be found. Experiments comparing three different evolutionary operators for a memetic algorithm are presented.

Cited By

View all

Uher VKromer P(2023)Impact of Different Discrete Sampling Strategies on Fitness Landscape Analysis Based on HistogramsProceedings of the 13th International Conference on Advances in Information Technology10.1145/3628454.3631563(1-9)Online publication date: 6-Dec-2023
https://dl.acm.org/doi/10.1145/3628454.3631563
Zeng ZCai YChung KLin HWu J(2023)A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSPIET Computers & Digital Techniques10.1049/2023/99157692023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1049/2023/9915769
El Yafrani MScoczynski MWagner MNielsen P(2023)A regression analysis of the impact of routing and packing dependencies on the expected runtimeSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08402-727:17(12099-12115)Online publication date: 27-May-2023
https://dl.acm.org/doi/10.1007/s00500-023-08402-7
Show More Cited By

Fitness landscape analysis and memetic algorithms for the quadratic assignment problem
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis

Recommendations

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 ...
Advanced fitness landscape analysis and the performance of memetic algorithms
Special issue on magnetic algorithms

Memetic algorithms (MAs) have demonstrated very effective in combinatorial optimization. This paper offers explanations as to why this is so by investigating the performance of MAs in terms of efficiency and effectiveness. A special class of MAs is used ...
Bag of local landscape features for fitness landscape analysis

Evolutionary computation is a research field dealing with black-box and complex optimization problems whose fitness landscapes are usually unknown in advance. It is difficult to select an appropriate evolutionary algorithm and parameters for a given ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Evolutionary Computation

IEEE Transactions on Evolutionary Computation Volume 4, Issue 4

November 2000

95 pages

ISSN:1089-778X

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 November 2000

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

105
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Uher VKromer P(2023)Impact of Different Discrete Sampling Strategies on Fitness Landscape Analysis Based on HistogramsProceedings of the 13th International Conference on Advances in Information Technology10.1145/3628454.3631563(1-9)Online publication date: 6-Dec-2023
https://dl.acm.org/doi/10.1145/3628454.3631563
Zeng ZCai YChung KLin HWu J(2023)A Fast Fully Parallel Ant Colony Optimization Algorithm Based on CUDA for Solving TSPIET Computers & Digital Techniques10.1049/2023/99157692023Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1049/2023/9915769
El Yafrani MScoczynski MWagner MNielsen P(2023)A regression analysis of the impact of routing and packing dependencies on the expected runtimeSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08402-727:17(12099-12115)Online publication date: 27-May-2023
https://dl.acm.org/doi/10.1007/s00500-023-08402-7
Neri FTurner A(2023)A Fitness Landscape Analysis Approach for Reinforcement Learning in the Control of the Coupled Inverted Pendulum TaskApplications of Evolutionary Computation10.1007/978-3-031-30229-9_5(69-85)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30229-9_5
Chen TSchmerl BMaggio MCámara J(2022)Planning landscape analysis for self-adaptive systemsProceedings of the 17th Symposium on Software Engineering for Adaptive and Self-Managing Systems10.1145/3524844.3528060(84-90)Online publication date: 18-May-2022
https://dl.acm.org/doi/10.1145/3524844.3528060
Hassan APillay N(2022)Automated Design of Hybrid Metaheuristics: A Fitness Landscape Analysis2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870231(1-8)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1109/CEC55065.2022.9870231
Thomson SOchoa GVerel S(2022)The fractal geometry of fitness landscapes at the local optima levelNatural Computing: an international journal10.1007/s11047-020-09834-y21:2(317-333)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s11047-020-09834-y
Nourmohammadzadeh ASarhani MVoß S(2022)Fitness Landscape Ruggedness Impact on PSO in Dealing with Three Variants of the Travelling Salesman ProblemLearning and Intelligent Optimization10.1007/978-3-031-24866-5_31(429-444)Online publication date: 5-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-24866-5_31
Wang RZhang Z(2021)Set Theory-Based Operator Design in Evolutionary Algorithms for Solving Knapsack ProblemsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.308068325:6(1133-1147)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1109/TEVC.2021.3080683
Dennis COmbuki-Berman BEngelbrecht A(2021)Predicting Particle Swarm Optimization Control Parameters From Fitness Landscape Characteristics2021 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC45853.2021.9505006(2289-2298)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1109/CEC45853.2021.9505006
Show More Cited By

Abstract

Cited By

Recommendations

Memetic search for the quadratic assignment problem

Advanced fitness landscape analysis and the performance of memetic algorithms

Bag of local landscape features for fitness landscape analysis

Comments

Information

Published In

Publisher

Publication History

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