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:
- 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: