## Class DeviationDistanceNormalized2005

• java.lang.Object
• org.cicirello.permutations.distance.DeviationDistanceNormalized2005
• All Implemented Interfaces:
`NormalizedPermutationDistanceMeasurerDouble`, `PermutationDistanceMeasurerDouble`

```public final class DeviationDistanceNormalized2005
extends Object
implements NormalizedPermutationDistanceMeasurerDouble```
Normalized Deviation Distance:

The original version of Normalized Deviation distance (Ronald, 1998) 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].

Sevaux and Sorensen (2005) suggested a different normalizing factor that provides a distance in the interval [0,1]. Maximal distance occurs for an inverted permutation. The normalizing factor is (N2/2) when N is even and (N2-1)/2 when N is odd.

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, which is even, so we'll divide by 18. So, normalized deviation distance is 8 / 18 = 0.444...

If instead, p2 = [5, 4, 3, 2, 1, 0], then 0 and 5 are both displaced by 5 positions, 1 and 4 are displaced by 3 positions, and 2 and 3 are displaced by 1 position. Sum of deviations is then: 2 * 5 + 2 * 3 + 2 * 1 = 18. The length is still 6, so we again divide by 18, and distance is 1.

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

Original 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.

This version of normalized deviation distance was introduced in:
M. Sevaux and K Sorensen, "Permutation distance measures for memetic algorithms with population management," in Proc. of MIC2005, 2005.

• ### Constructor Summary

Constructors
Constructor Description
`DeviationDistanceNormalized2005()`
Constructs the distance measurer as specified in the class documentation.
• ### Method Summary

All Methods
Modifier and Type Method Description
`double` ```distancef​(Permutation p1, Permutation p2)```
Measures the distance between two permutations
`double` `maxf​(int length)`
Computes the maximum possible distance between permutations of a specified length.
`double` ```normalizedDistance​(Permutation p1, Permutation p2)```
Measures the distance between two permutations, normalized to the interval [0.0, 1.0].
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### DeviationDistanceNormalized2005

`public DeviationDistanceNormalized2005()`
Constructs the distance measurer as specified in the class documentation.
• ### Method Detail

• #### distancef

```public double distancef​(Permutation p1,
Permutation p2)```
Measures the distance between two permutations
Specified by:
`distancef` in interface `PermutationDistanceMeasurerDouble`
Parameters:
`p1` - first permutation
`p2` - second permutation
Returns:
distance between p1 and p2
Throws:
`IllegalArgumentException` - if p1.length() is not equal to p2.length().
• #### maxf

`public double maxf​(int length)`
Description copied from interface: `NormalizedPermutationDistanceMeasurerDouble`
Computes the maximum possible distance between permutations of a specified length.
Specified by:
`maxf` in interface `NormalizedPermutationDistanceMeasurerDouble`
Parameters:
`length` - Permutation length.
Returns:
the maximum distance between a pair of permutations of the specified length.
• #### normalizedDistance

```public double normalizedDistance​(Permutation p1,
Permutation p2)```

Measures the distance between two permutations, normalized to the interval [0.0, 1.0].

Specified by:
`normalizedDistance` in interface `NormalizedPermutationDistanceMeasurerDouble`
Parameters:
`p1` - first permutation
`p2` - second permutation
Returns:
distance between p1 and p2 normalized to the interval [0.0, 1.0]
Throws:
`IllegalArgumentException` - if p1.length() is not equal to p2.length().