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 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 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.
In [1]:
# Import modules
import random
import numpy as np
# Import PySwarms
from pyswarms.single import GlobalBestPSO
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
In [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
}
In [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)
ftolSetting 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.
In [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()))
ftol_iterTo 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.
In [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()))
In [ ]: