Function test_ils_acceptance_behaviour

tests/test_IteratedLocalSearch.py:130–183

Tests ILS acceptance behaviour over a fixed trajectory.

(ok_small)

def test_ils_acceptance_behaviour(ok_small):
    """
    Tests ILS acceptance behaviour over a fixed trajectory.
    """
    sols = [
        Solution(ok_small, [[1, 3], [2, 4]]),  # 22065 (infeas)
        Solution(ok_small, [[1, 2], [3, 4]]),  # 9725
        Solution(ok_small, [[1, 2], [4, 3]]),  # 9868
        Solution(ok_small, [[1, 4], [2, 3]]),  # 9240
        Solution(ok_small, [[1, 2], [3, 4]]),  # 9725
    ]

    ils = IteratedLocalSearch(
        ok_small,
        PenaltyManager(initial_penalties=([20], 6, 6)),
        RandomNumberGenerator(42),
        lambda *_, **kws: sols.pop(0),  # returns from sols one at a time
        sols[0],
        IteratedLocalSearchParams(history_length=2, exhaustive_on_best=False),
    )

    res = ils.run(stop=MaxIterations(len(sols)))
    data = res.stats.data

    # First solution is also the initial solution, so nothing should have
    # changed.
    assert_equal(data[0].current_cost, 22_065)
    assert_equal(data[0].candidate_cost, 22_065)
    assert_equal(data[0].best_cost, 22_065)

    # The second iteration has a solution that is *much* better. This new
    # solution should become both the current and best.
    assert_equal(data[1].current_cost, 9_725)
    assert_equal(data[1].candidate_cost, 9_725)
    assert_equal(data[1].best_cost, 9_725)

    # We now get a candidate solution that is a little worse than the previous
    # iteration, but better than the solution from two iterations ago. It is
    # thus accepted.
    assert_equal(data[2].current_cost, 9_868)
    assert_equal(data[2].candidate_cost, 9_868)
    assert_equal(data[2].best_cost, 9_725)

    # We now find a new best solution that should also be accepted.
    assert_equal(data[3].current_cost, 9_240)
    assert_equal(data[3].candidate_cost, 9_240)
    assert_equal(data[3].best_cost, 9_240)

    # In the last iteration we again find a solution we found earlier. This
    # solution improves over the solution from two iterations ago, and should
    # thus be accepted.
    assert_equal(data[4].current_cost, 9_725)
    assert_equal(data[4].candidate_cost, 9_725)
    assert_equal(data[4].best_cost, 9_240)


def test_restart(ok_small):