A New Metric to Measure Distances Between Solutions to the Quadratic Assignment Problem

Solutions to the Quadratic Assignment Problem (QAP) can be compared with each other in several ways. In this work a new distance metric for measuring the distance respectively similarity between two solutions will be introduced. Such a metric is useful in measuring the performance of heuristic optimization algorithms and generally in the analysis of the QAP's fitness landscape. The new metric is described, compared to the most commonly used metric and evaluated on a number of problem instances. The correlation between the fitness distance and the solution distance can be improved in several problem instances providing a different and more interesting picture on algorithm performance.