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: pyvrp._pyvrp.Solution, second: pyvrp._pyvrp.Solution)

Computes the symmetric broken pairs distance (BPD) between the given two solutions. This function determines whether each client in the problem shares neighbours between the first and second solution. If not, the client 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 client (or depot) of client \(i = 1, \ldots, n\) in \(f\) and \(s\), respectively. Similarly define \(s_f(i)\) and \(s_s(i)\) for the succeeding client (or depot). 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].

Parameters:

first

First solution.

second

Second solution.

Returns:

float

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.