{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tolerance\n",
    "\n",
    "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.\n",
    "\n",
    "The following explains how these parameters are designed to work together and provide early stopping functionality.\n",
    "\n",
    "### ftol\n",
    "`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 \n",
    "`ftol * (1 + abs(best_cost_yet_found))`\n",
    "\n",
    "\n",
    "### ftol_iter\n",
    "`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.\n",
    "\n",
    "**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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import modules\n",
    "import random\n",
    "import numpy as np\n",
    "\n",
    "# Import PySwarms\n",
    "from pyswarms.single import GlobalBestPSO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Knapsack problem\n",
    "\n",
    "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](https://en.wikipedia.org/wiki/Knapsack_problem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Algorithm paramters\n",
    "random.seed(0)\n",
    "\n",
    "# The weight capacity of the knapsack \n",
    "capacity = 50\n",
    "number_of_items = 10\n",
    "item_range = range(number_of_items)\n",
    "\n",
    "value = [random.randint(1,number_of_items) for i in item_range]\n",
    "weight = [random.randint(1,number_of_items) for i in item_range]\n",
    "\n",
    "# PSO paramters\n",
    "n_particles = 2\n",
    "n_processes = 2\n",
    "iterations = 1000\n",
    "options = {'c1': 2, 'c2': 2, 'w': 0.7}\n",
    "dim = number_of_items\n",
    "LB = [0] * dim\n",
    "UB = [1] * dim\n",
    "constraints = (np.array(LB), np.array(UB))\n",
    "kwargs  = {'value':value,\n",
    "           'weight': weight,\n",
    "           'capacity': capacity\n",
    "            }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Helper function\n",
    "def get_particle_obj(X, **kwargs):\n",
    "    \"\"\" Calculates the objective function value which is\n",
    "    total revenue minus penalty of capacity violations\"\"\"\n",
    "    # X is the decision variable. X is vector in the lenght of number of items \n",
    "    # $ value of items\n",
    "    value = kwargs['value']\n",
    "    # weight of items\n",
    "    weight = kwargs['weight']\n",
    "    # Total revenue \n",
    "    revenue = sum([value[i]*np.round(X[i]) for i in item_range])\n",
    "    # Total weight of selected items\n",
    "    used_capacity = sum([kwargs['weight'][i]*np.round(X[i]) for i in item_range])\n",
    "    # Total capacity violation with 100 as a penalty cofficient\n",
    "    capacity_violation = 100 * min(0,capacity - used_capacity)\n",
    "    # the objective function minimizes the negative revenue, which is the same\n",
    "    # as maximizing the positive revenue\n",
    "    return -1*(revenue + capacity_violation)\n",
    "\n",
    "# Objective function\n",
    "def objective_function(X, **kwargs):\n",
    "    n_particles_ = X.shape[0]\n",
    "    dist = [get_particle_obj(X[i], **kwargs) for i in range(n_particles_)]\n",
    "    return np.array(dist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Early stopping using `ftol`\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "2020-05-15 16:19:18,362 - pyswarms.single.global_best - INFO - Optimize for 1000 iters with {'c1': 2, 'c2': 2, 'w': 0.7}\n",
      "pyswarms.single.global_best:   0%|          |2/1000, best_cost=-37\n",
      "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\n",
      " 0.49067837 0.93297015 0.95457747 0.30363181]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The total knapsack revenue is: 37.0\n",
      "Indices of selected items:\t [0 4 5 7 8]\n"
     ]
    }
   ],
   "source": [
    "KP_optimizer = GlobalBestPSO(n_particles=n_particles,\n",
    "                                    dimensions=dim,\n",
    "                                    options=options,\n",
    "                                    bounds=constraints,\n",
    "                                    bh_strategy='periodic',\n",
    "                                    ftol = 1e-3,\n",
    "                                    velocity_clamp = (-0.5,0.5),\n",
    "                                    vh_strategy = 'invert')\n",
    "best_cost, best_pos = KP_optimizer.optimize(objective_function,\n",
    "                                        iters=iterations,\n",
    "                                        n_processes= n_processes,\n",
    "                                        **kwargs)\n",
    "print(\"\\nThe total knapsack revenue is: \"+str(-best_cost))\n",
    "print(\"Indices of selected items:\\t \" + str(np.argwhere(np.round(best_pos)).flatten()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Extending property using `ftol_iter`\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "2020-05-15 16:19:18,499 - pyswarms.single.global_best - INFO - Optimize for 1000 iters with {'c1': 2, 'c2': 2, 'w': 0.7}\n",
      "pyswarms.single.global_best:   5%|▌         |54/1000, best_cost=-58\n",
      "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\n",
      " 0.5263472  0.40653976 0.52041271 0.67038903]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "The total knapsack revenue is: 58.0\n",
      "Indices of selected items:\t [0 1 2 3 4 5 6 8 9]\n"
     ]
    }
   ],
   "source": [
    "KP_optimizer.ftol_iter = 20\n",
    "best_cost, best_pos = KP_optimizer.optimize(objective_function,\n",
    "                                        iters=iterations,\n",
    "                                        n_processes= n_processes,\n",
    "                                        **kwargs)\n",
    "print(\"\\nThe total knapsack revenue is: \"+str(-best_cost))\n",
    "print(\"Indices of selected items:\\t \" + str(np.argwhere(np.round(best_pos)).flatten()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pyswarms",
   "language": "python",
   "name": "pyswarms"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
