Research Article
Classification of Permutation Distance Metrics for Fitness Landscape Analysis
@INPROCEEDINGS{10.1007/978-3-030-24202-2_7, author={Vincent Cicirello}, title={Classification of Permutation Distance Metrics for Fitness Landscape Analysis}, proceedings={Bio-inspired Information and Communication Technologies. 11th EAI International Conference, BICT 2019, Pittsburgh, PA, USA, March 13--14, 2019, Proceedings}, proceedings_a={BICT}, year={2019}, month={7}, keywords={Fitness landscape analysis Permutation distance Permutation metric Combinatorial optimization Fitness distance correlation}, doi={10.1007/978-3-030-24202-2_7} }- Vincent Cicirello
Year: 2019
Classification of Permutation Distance Metrics for Fitness Landscape Analysis
BICT
Springer
DOI: 10.1007/978-3-030-24202-2_7
Abstract
Commonly used computational and analytical tools for fitness landscape analysis of optimization problems require identifying a distance metric that characterizes the similarity of different solutions to the problem. For example, fitness distance correlation is Pearson correlation between solution fitness and distance to the nearest optimal solution. In this paper, we survey the available distance metrics for permutations, and use principal component analysis to classify the metrics. The result is aligned with existing classifications of permutation problem types produced through less formal means, including the A-permutation, R-permutation, and P-permutation types, and has also identified subtypes. The classification can assist in identifying appropriate metrics based on optimization problem feature for use in fitness landscape analysis. Implementations of all of the permutation metrics, and the code for our analysis, are available as open source.