  In this paper, we explore the theory and expand upon the practice of fitness
landscape analysis for optimization problems over the space of permutations.
Many of the computational and analytical tools for fitness landscape analysis,
such as fitness distance correlation, require identifying a distance metric for
measuring the similarity of different solutions to the problem. We begin with a
survey of the available distance metrics for permutations, and then use
principal component analysis to classify these metrics. The result of this
analysis aligns with existing classifications of permutation problem types
produced through less formal means, including the A-permutation, R-permutation,
and P-permutation types, which classifies problems by whether absolute position
of permutation elements, relative positions of elements, or general precedence
of pairs of elements, is the dominant influence over solution fitness.
Additionally, the formal analysis identifies subtypes within these problem
categories. We see that the classification can assist in identifying
appropriate metrics based on optimization problem feature for use in fitness
landscape analysis. Using optimization problems of each class, we also
demonstrate how the classification scheme can subsequently inform the choice of
mutation operator within an evolutionary algorithm. From this, we present a
classification of a variety of mutation operators as a counterpart to that of
the metrics. Our implementations of the permutation metrics, permutation
mutation operators, and associated evolutionary algorithm, are available in a
pair of open source Java libraries. All of the code necessary to recreate our
analysis and experimental results are also available as open source.
