# Tolerance

In this example we will have a look at the various early stopping features available. These features are based on “tolerance” values when finding an optimum solution for the objective function. The optimizers have two parameters namely `ftol` and `ftol_iter` that work together to provide this additional functionality.

The following explains how these parameters are designed to work together and provide early stopping functionality.

## ftol

`ftol` is defined as the relative error in the objective function that is acceptable for convergence. In simpler terms, `ftol` stops the optimizer if absolute difference between the `current_best_cost` and the `best_cost_yet_found` is less than the relative measure defined as `ftol * (1 + abs(best_cost_yet_found))`

## ftol_iter

`ftol_iter` helps to generatilze the `ftol` property and extends the feature over ‘n’ iterations. As a fixed tolerance might seem too restrictive, `ftol_iter` provides the optimizer some breathing space to improve the best cost. If there are no improvements detected over ftol_iter subsequent iterations, the optimizer stops.

Note: To maintain the initial functionality of `ftol` (stop immediately), default value of `ftol_iter = 1`. The default value of `ftol = -inf` to completey disable early stopping.

    [1]:

    # Import modules
    import random
    import numpy as np

    # Import PySwarms
    from pyswarms.single import GlobalBestPSO

### Knapsack problem

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively. Refernce

    [2]:

    # Algorithm paramters
    random.seed(0)

    # The weight capacity of the knapsack
    capacity = 50
    number_of_items = 10
    item_range = range(number_of_items)

    value = [random.randint(1,number_of_items) for i in item_range]
    weight = [random.randint(1,number_of_items) for i in item_range]

    # PSO paramters
    n_particles = 2
    n_processes = 2
    iterations = 1000
    options = {'c1': 2, 'c2': 2, 'w': 0.7}
    dim = number_of_items
    LB = [0] * dim
    UB = [1] * dim
    constraints = (np.array(LB), np.array(UB))
    kwargs  = {'value':value,
               'weight': weight,
               'capacity': capacity
                }

    [3]:

    # Helper function
    def get_particle_obj(X, **kwargs):
        """ Calculates the objective function value which is
        total revenue minus penalty of capacity violations"""
        # X is the decision variable. X is vector in the lenght of number of items
        # $ value of items
        value = kwargs['value']
        # weight of items
        weight = kwargs['weight']
        # Total revenue
        revenue = sum([value[i]*np.round(X[i]) for i in item_range])
        # Total weight of selected items
        used_capacity = sum([kwargs['weight'][i]*np.round(X[i]) for i in item_range])
        # Total capacity violation with 100 as a penalty cofficient
        capacity_violation = 100 * min(0,capacity - used_capacity)
        # the objective function minimizes the negative revenue, which is the same
        # as maximizing the positive revenue
        return -1*(revenue + capacity_violation)

    # Objective function
    def objective_function(X, **kwargs):
        n_particles_ = X.shape[0]
        dist = [get_particle_obj(X[i], **kwargs) for i in range(n_particles_)]
        return np.array(dist)

### Early stopping using `ftol`

Setting `ftol = 1e-3` means, if the best cost yet found does not improve by more than the tolerance, the optimizer will stop. In the case when the optimizer shows no improvement in two consecutive iterations (`best_cost_yet_found == current_best_cost`), the optimizer stops as the condition is met (`0 < ftol`). To help with this, the `ftol_iter` parameter is added, to extend the `ftol` property as explained later on.

    [4]:

    KP_optimizer = GlobalBestPSO(n_particles=n_particles,
                                        dimensions=dim,
                                        options=options,
                                        bounds=constraints,
                                        bh_strategy='periodic',
                                        ftol = 1e-3,
                                        velocity_clamp = (-0.5,0.5),
                                        vh_strategy = 'invert')
    best_cost, best_pos = KP_optimizer.optimize(objective_function,
                                            iters=iterations,
                                            n_processes= n_processes,
                                            **kwargs)
    print("\nThe total knapsack revenue is: "+str(-best_cost))
    print("Indices of selected items:\t " + str(np.argwhere(np.round(best_pos)).flatten()))

    2020-05-15 16:19:18,362 - pyswarms.single.global_best - INFO - Optimize for 1000 iters with {'c1': 2, 'c2': 2, 'w': 0.7}
    pyswarms.single.global_best:   0%|          |2/1000, best_cost=-37
    2020-05-15 16:19:18,387 - pyswarms.single.global_best - INFO - Optimization finished | best cost: -37.0, best pos: [0.95660081 0.18010925 0.4655673  0.44918644 0.83728236 0.60629341
     0.49067837 0.93297015 0.95457747 0.30363181]

    The total knapsack revenue is: 37.0
    Indices of selected items:       [0 4 5 7 8]

### Extending property using `ftol_iter`

To provide additional iterations for the optimizer to improve (find a better solution), the `ftol_iter = 20` states that the optimizer stop only is the `ftol` condition is not met for 20 consecutive iterations. If the algorithm finds a better solution in the next few iterations, the propoerty reset looking for the next 20 iterations with no acceptable improvements. This also means that the optimizer must run for a minimum of `ftol_iter` iterations before stopping; which in the following case is 20 iterations.

    [5]:

    KP_optimizer.ftol_iter = 20
    best_cost, best_pos = KP_optimizer.optimize(objective_function,
                                            iters=iterations,
                                            n_processes= n_processes,
                                            **kwargs)
    print("\nThe total knapsack revenue is: "+str(-best_cost))
    print("Indices of selected items:\t " + str(np.argwhere(np.round(best_pos)).flatten()))

    2020-05-15 16:19:18,499 - pyswarms.single.global_best - INFO - Optimize for 1000 iters with {'c1': 2, 'c2': 2, 'w': 0.7}
    pyswarms.single.global_best:   5%|▌         |54/1000, best_cost=-58
    2020-05-15 16:19:18,610 - pyswarms.single.global_best - INFO - Optimization finished | best cost: -58.0, best pos: [0.78167301 0.72297094 0.55090836 0.5990936  0.57963271 0.6234684
     0.5263472  0.40653976 0.52041271 0.67038903]

    The total knapsack revenue is: 58.0
    Indices of selected items:       [0 1 2 3 4 5 6 8 9]

    [ ]: