Diversity measures¶

The pyvrp.diversity module contains operators that determine the relative difference between two Solution objects. This difference provides a measure of diversity: a Population of highly diverse solutions allows the genetic algorithm to perform better. At the same time, one also wants to balance diversity with quality: the solutions should also be good. That balance is maintained by computing a fitness score for each solution, which balances the diversity with the objective value.

broken_pairs_distance(first: Solution, second: Solution) → float¶

Computes the symmetric broken pairs distance (BPD) between the given two solutions. This function determines whether each location in the problem shares neighbours between the first and second solution. If not, the location is part of a ‘broken pair’: a link that is part of one solution, but not of the other.

Formally, given two solutions \(f\) and \(s\), let \(p_f(i)\) and \(p_s(i)\) be the preceding location of location \(i = 1, \ldots, n\) in \(f\) and \(s\), respectively. Here, \(n\) represents the number of locations (clients and depots). Similarly define \(s_f(i)\) and \(s_s(i)\) for the succeeding location. Then, we have

\[\text{BPD}(f, s) = \frac{ \sum_{i = 1}^n 1_{p_f(i) \ne p_s(i)} + 1_{s_f(i) \ne s_s(i)} }{2n}.\]

Note

Note that our definition is directed: a route [1, 2, 3, 4] is considered completely different from a route [4, 3, 2, 1].

Note

Depot locations do not add to the number of broken pairs, but are counted in the denominator. The maximum BPD between two solutions is thus always less than one.

Parameters:

first: Solution¶

First solution.

second: Solution¶

Second solution.

Returns:

A value in [0, 1) that indicates the percentage of broken links between the two solutions. A value near one suggests the solutions are maximally diverse, a value of zero indicates they are the same.

Return type:

float