Frequency Fitness Assignment: Optimization without Bias for Good Solution outperforms Randomized Local Search on the Quadratic Assignment Problem

Chen, Jiayang; Wu, Zhize; Thomson, Sarah L.; Weise, Thomas

Abstract

The Quadratic Assignment Problem (QAP) is one of the classical N P-hard tasks from operations research with a history of more than 65 years. It is often approached with heuristic algorithms and over the years, a multitude of such methods has been applied. All of them have in common that they tend to prefer better solutions over worse ones. We approach the QAP with Frequency Fitness Assignment (FFA), an algorithm module that can be plugged into arbitrary iterative heuristics and that removes this bias. One would expect that a heuristic that does not care whether a new solution is better or worse compared to the current one should not perform very well. We plug FFA into a simple randomized local search (RLS) and yield the FRLS, which surprisingly outperforms RLS on the vast majority of the instances of the well-known QAPLIB benchmark set.

Citation

Chen, J., Wu, Z., Thomson, S. L., & Weise, T. (2024, November). Frequency Fitness Assignment: Optimization without Bias for Good Solution outperforms Randomized Local Search on the Quadratic Assignment Problem. Paper presented at ECTA 2024: 16th International Conference on Evolutionary Computation Theory and Applications, Porto, Portugal

• Presentation Conference Type: Conference Paper (unpublished)
• Conference Name: ECTA 2024: 16th International Conference on Evolutionary Computation Theory and Applications
• Start Date: Nov 20, 2024
• Acceptance Date: Jul 31, 2024
• Deposit Date: Aug 26, 2024
• Peer Reviewed: Peer Reviewed
• Keywords: Quadratic Assignment Problem; Frequency Fitness Assignment; Randomized Local Search