Repository: PyVRP/PyVRP
Pull request #183 (2023-03-10 15:37:49)

Generalise binary tournament
This PR follows from #181. It:

- [x] Generalises binary tournament to k-ary tournament.
- [x] Adds and passes relevant tests.
- [x] Has well-formatted code and documentation.

<details>

**Notes**:

- It is essential that you add a test when making code changes.
  This keeps the code coverage level up, and helps ensure the changes work as intended.
- When fixing a bug, you must add a test that would produce the bug in the master branch, and then show that it is fixed with the new code. 
- New code additions must be well formatted. Changes should pass the pre-commit workflow, which you can set up locally using [pre-commit](https://pre-commit.com/#intro). 
- Docstring additions must render correctly, including escapes and LaTeX.

</details>



Patch:
diff --git a/pyvrp/Population.py b/pyvrp/Population.py
index 33ee816..18e4444 100644
--- a/pyvrp/Population.py
+++ b/pyvrp/Population.py
@@ -114,14 +114,23 @@ class Population:
         else:
             self._infeas.add(individual, cost_evaluator)
 
+    def clear(self):
+        """
+        Clears the population by removing all individuals currently in the
+        population.
+        """
+        self._feas = SubPopulation(self._op, self._params)
+        self._infeas = SubPopulation(self._op, self._params)
+
     def select(
         self,
         rng: XorShift128,
         cost_evaluator: CostEvaluator,
+        k: int = 2,
     ) -> Tuple[Individual, Individual]:
         """
-        Selects two (if possible non-identical) parents by binary tournament,
-        subject to a diversity restriction.
+        Selects two (if possible non-identical) parents by tournament, subject
+        to a diversity restriction.
 
         Parameters
         ----------
@@ -129,6 +138,9 @@ class Population:
             Random number generator.
         cost_evaluator
             Cost evaluator to use when computing the fitness.
+        k
+            The number of individuals to draw for the tournament. Defaults to
+            two, which results in a binary tournament.
 
         Returns
         -------
@@ -136,8 +148,9 @@ class Population:
             A pair of individuals (parents).
         """
         self._update_fitness(cost_evaluator)
-        first = self._get_binary_tournament(rng)
-        second = self._get_binary_tournament(rng)
+
+        first = self._get_tournament(rng, k)
+        second = self._get_tournament(rng, k)
 
         diversity = self._op(first, second)
         lb = self._params.lb_diversity
@@ -146,26 +159,17 @@ class Population:
         tries = 1
         while not (lb <= diversity <= ub) and tries <= 10:
             tries += 1
-            second = self._get_binary_tournament(rng)
+            second = self._get_tournament(rng, k)
             diversity = self._op(first, second)
 
         return first, second
 
-    def clear(self):
-        """
-        Clears the population by removing all individuals currently in the
-        population.
-        """
-        self._feas = SubPopulation(self._op, self._params)
-        self._infeas = SubPopulation(self._op, self._params)
-
-    def get_binary_tournament(
-        self,
-        rng: XorShift128,
-        cost_evaluator: CostEvaluator,
+    def get_tournament(
+        self, rng: XorShift128, cost_evaluator: CostEvaluator, k: int = 2
     ) -> Individual:
         """
-        Selects an individual from this population by binary tournament.
+        Selects an individual from this population by k-ary tournament, based
+        on the (internal) fitness values of the selected individuals.
 
         Parameters
         ----------
@@ -173,6 +177,9 @@ class Population:
             Random number generator.
         cost_evaluator
             Cost evaluator to use when computing the fitness.
+        k
+            The number of individuals to draw for the tournament. Defaults to
+            two, which results in a binary tournament.
 
         Returns
         -------
@@ -180,26 +187,11 @@ class Population:
             The selected individual.
         """
         self._update_fitness(cost_evaluator)
-        return self._get_binary_tournament(rng)
+        return self._get_tournament(rng, k)
 
-    def _get_binary_tournament(self, rng: XorShift128) -> Individual:
-        """
-        Selects an individual from this population by binary tournament.
-
-        Parameters
-        ----------
-        rng
-            Random number generator.
-
-        Returns
-        -------
-        Individual
-            The selected individual.
-
-        .. warning::
-            This function assumes self._update_fitness() has been called before
-            using this function unless nothing has changed.
-        """
+    def _get_tournament(self, rng: XorShift128, k: int) -> Individual:
+        if k <= 0:
+            raise ValueError(f"Expected k > 0; got k = {k}.")
 
         def select():
             num_feas = len(self._feas)
@@ -210,10 +202,6 @@ class Population:
 
             return self._infeas[idx - num_feas]
 
-        item1 = select()
-        item2 = select()
-
-        if item1.fitness < item2.fitness:
-            return item1.individual
-
-        return item2.individual
+        items = [select() for _ in range(k)]
+        fittest = min(items, key=lambda item: item.fitness)
+        return fittest.individual


Test patch:
diff --git a/pyvrp/tests/test_Population.py b/pyvrp/tests/test_Population.py
index 8be3432..2bdf04a 100644
--- a/pyvrp/tests/test_Population.py
+++ b/pyvrp/tests/test_Population.py
@@ -241,7 +241,8 @@ def test_elite_individuals_are_not_purged(nb_elite: int):
         assert_(id(elite_individual) in new_individuals)
 
 
-def test_binary_tournament_ranks_by_fitness():
+@mark.parametrize("k", [2, 3])
+def test_tournament_ranks_by_fitness(k: int):
     data = read("data/RC208.txt", "solomon", "dimacs")
     cost_evaluator = CostEvaluator(20, 6)
     rng = XorShift128(seed=42)
@@ -255,26 +256,48 @@ def test_binary_tournament_ranks_by_fitness():
 
     # Since this test requires the fitness values of the individuals, we have
     # to access the underlying infeasible subpopulation directly.
-    # We must also explicitly trigger to update the fitness first.
-    pop._infeas.update_fitness(cost_evaluator)
-    infeas = [item for item in pop._infeas]
-    infeas = sorted(infeas, key=lambda item: item.fitness)
-    infeas = {item.individual: idx for idx, item in enumerate(infeas)}
-    infeas_count = np.zeros(len(infeas))
+    infeas_pop = pop._infeas
+    infeas_pop.update_fitness(cost_evaluator)
+
+    items = [item for item in pop._infeas]
+    by_fitness = sorted(items, key=lambda item: item.fitness)
+    indiv2idx = {item.individual: idx for idx, item in enumerate(by_fitness)}
+    infeas_count = np.zeros(len(infeas_pop))
 
     for _ in range(10_000):
-        indiv = pop.get_binary_tournament(rng, cost_evaluator)
-        infeas_count[infeas[indiv]] += 1
+        indiv = pop.get_tournament(rng, cost_evaluator, k=k)
+        infeas_count[indiv2idx[indiv]] += 1
+
+    # Now we compare the observed ranking from the tournament selection with
+    # what we expect from the actual fitness ranking. We compute the percentage
+    # of times we're incorrect, and test that that number is not too high.
+    actual_rank = 1 + np.argsort(-infeas_count)  # higher is better
+    expected_rank = 1 + np.arange(len(infeas_pop))
+    pct_off = np.abs((actual_rank - expected_rank) / len(infeas_pop)).mean()
+    assert_(pct_off < 0.05)
 
-    # Now we compare the observed ranking from the binary tournament selection
-    # against what we would expect from the actual fitness ranking. We compute
-    # the percentage of times we're incorrect, and test that that number is not
-    # too high.
-    actual_rank = np.argsort(-infeas_count)  # higher is better
-    expected_rank = np.arange(len(infeas))
-    pct_off = np.abs((actual_rank - expected_rank) / len(infeas)).mean()
+    # Previous test compared just rank. Now we compare expected frequency. An
+    # item at rank i wins only when the other k - 1 items have a rank lower
+    # than i. That happens with probability roughly proportional to
+    #   (1 - i / #pop) ** (k - 1)
+    actual_freq = infeas_count / infeas_count.sum()
+    expected_freq = (1 - expected_rank / len(infeas_pop)) ** (k - 1)
+    expected_freq /= expected_freq.sum()
+    assert_allclose(actual_freq, expected_freq, atol=0.01)  # 1% tolerance
 
-    assert_(pct_off < 0.05)
+
+@mark.parametrize("k", [-100, -1, 0])  # k must be strictly positive
+def test_tournament_raises_for_invalid_k(k: int):
+    data = read("data/RC208.txt", "solomon", "dimacs")
+    cost_evaluator = CostEvaluator(20, 6)
+    rng = XorShift128(seed=42)
+    pop = Population(bpd)
+
+    for individual in make_random_solutions(5, data, rng):
+        pop.add(individual, cost_evaluator)
+
+    with assert_raises(ValueError):
+        pop.get_tournament(rng, cost_evaluator, k=k)
 
 
 def test_purge_removes_duplicates():