Module org.cicirello.jpt
Package org.cicirello.permutations.distance

Class DeviationDistanceNormalized

java.lang.Object
org.cicirello.permutations.distance.DeviationDistanceNormalized
All Implemented Interfaces:
NormalizedPermutationDistanceMeasurerDouble, PermutationDistanceMeasurerDouble
public final class DeviationDistanceNormalized extends Object implements NormalizedPermutationDistanceMeasurerDouble
Normalized Deviation distance is the sum of the positional deviation of the permutation elements divided by N-1 (where N is the length of the permutation). The positional deviation of an element is the difference in its location in the two permutations. Normalizing by dividing by N-1 causes each element's contribution to distance to be in the interval [0,1].

For example, consider p1 = [0, 1, 2, 3, 4, 5] and p2 = [1, 0, 5, 2, 4, 3]. Element 0 is displaced by 1 position. Likewise for elements 1 and 2. Element 3 is displaced by 2 positions. Element 4 is in the same position in both. Element 5 is displaced by 3 positions.

Sum the deviations: 1 + 1 + 1 + 2 + 0 + 3 = 8.

The length is 6. So, normalized deviation distance is 8 / (6-1) = 1.6.

Runtime: O(n), where n is the permutation length.

Normalized deviation distance was introduced in:
S. Ronald, "More distance functions for order-based encodings," in Proc. IEEE CEC. IEEE Press, 1998, pp. 558–563.

  • Constructor Details

    • DeviationDistanceNormalized

      public DeviationDistanceNormalized()
      Constructs the distance measurer as specified in the class documentation.

  • Method Details