qts-knapsack-problem.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "from pathlib import Path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Qitem:\n",
    "    \"\"\"Abstraction of the representation of a qbit as a \"quantum\"-item of the knapsack problem.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    value : int\n",
    "        Object value represented by the qbit.\n",
    "    weight : int\n",
    "        Object weight represented by the qbit.\n",
    "    alpha : float, optional\n",
    "        Alpha value of qbit representation (default is math.sqrt(1/2)).\n",
    "    beta : float, optional\n",
    "        Beta value of qbit representation (default is math.sqrt(1/2)).\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, value=None, weight=None, alpha=math.sqrt(1/2), beta=math.sqrt(1/2)):\n",
    "        self.alpha = alpha\n",
    "        self.beta = beta\n",
    "        self.value = value\n",
    "        self.weight = weight\n",
    "    \n",
    "    def measure(self):\n",
    "        \"\"\"Measures the qbit value from comparison with a random number between [0,1).\n",
    "        \n",
    "        Returns\n",
    "        -------\n",
    "        measure : int\n",
    "            0 or 1 depending on the qbit (alpha and beta) and the random number drawn.\n",
    "        \"\"\"\n",
    "        return 1 if np.random.random_sample() < self.beta**2 else 0\n",
    "    \n",
    "    def update(self, matrix):\n",
    "        \"\"\"Update qbit alpha and beta values by applying matrix.\n",
    "        \n",
    "        Attributes\n",
    "        ----------\n",
    "        matrix :\n",
    "            Two-dimensional matrix (qgate) to be applied to the qbit.\n",
    "        \"\"\"\n",
    "        self.alpha = matrix[0][0] * self.alpha + matrix[0][1] * self.beta\n",
    "        self.beta = matrix[1][0] * self.alpha + matrix[1][1] * self.beta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def matrix_move_gate(delta):\n",
    "    \"\"\"Generate a move-gate matrix to operate under a qitem with the given angle.\"\"\"\n",
    "    return [[math.cos(delta), -math.sin(delta)], [math.sin(delta), math.cos(delta)]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def measure_individuals(Q):\n",
    "    \"\"\"Measure each qbit of the qitem population and return the result (list of 0s and 1s).\"\"\"\n",
    "    return [q.measure() for q in Q]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fit_solution(Q, solution):\n",
    "    \"\"\"Evaluate value and weight of the given solution.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    Q : [Qitem]\n",
    "        Qitem population.\n",
    "    solution : [int]\n",
    "        Solution from a population measurement.\n",
    "        \n",
    "    Returns\n",
    "    -------\n",
    "    value : int\n",
    "        Total value of the evaluated solution.\n",
    "    weight : int\n",
    "        Total weight of the evaluated solution.\n",
    "    \"\"\"\n",
    "    value = 0\n",
    "    weight = 0\n",
    "\n",
    "    for i, measure in enumerate(solution):\n",
    "        value += measure*(Q[i].value)\n",
    "        weight += measure*(Q[i].weight)\n",
    "    \n",
    "    return value, weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def repair_solution(Q, solution, w_capacity, v_solution, w_solution):\n",
    "    \"\"\"Repairs the solution to make it a valid solution.\n",
    "    If the sum of the item weights exceeds the limit, \n",
    "    it removes items at random until the constraint is satisfied.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    Q : [Qitem]\n",
    "        Qitem population.\n",
    "    solution : [int]\n",
    "        Solution from a population measurement.\n",
    "    w_capacity : int\n",
    "        Knapsack weight limit capacity.\n",
    "    v_solution : int\n",
    "        Total value of solution to be repaired.\n",
    "    w_solution : int\n",
    "        Total weight of solution to be repaired.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    v_solution : int\n",
    "        Total value of the repaired solution.\n",
    "    w_solution : int\n",
    "        Total weight of the repaired solution.\n",
    "    \"\"\"\n",
    "    while w_solution > w_capacity:\n",
    "        index = np.random.randint(0, len(solution)-1)\n",
    "        if solution[index]:\n",
    "            solution[index] = 0\n",
    "            v_solution -= Q[index].value\n",
    "            w_solution -= Q[index].weight\n",
    "    \n",
    "    return v_solution, w_solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fit_and_repair(Q, solution, w_capacity):\n",
    "    \"\"\"Evaluates (value and weight) and repairs a solution.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    Q : [Qitem]\n",
    "        Qitem population.\n",
    "    solution : [int]\n",
    "        Solution from a population measurement.\n",
    "    w_capacity : int\n",
    "        Knapsack weight limit capacity.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    v_solution : int\n",
    "        Total value of the evaluated and repaired solution.\n",
    "    w_solution : int\n",
    "        Total weight of the evaluated and repaired solution.\n",
    "    \"\"\"\n",
    "    v_solution, w_solution = fit_solution(Q, solution)\n",
    "    if w_solution > w_capacity:\n",
    "        v_solution, w_solution = repair_solution(Q, solution, w_capacity, v_solution, w_solution)\n",
    "    return v_solution, w_solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_neighborhood(Q, population):\n",
    "    \"\"\"Measures qitem population to generate a population of neighboring solutions.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    Q : [Qitem]\n",
    "        Qitem population.\n",
    "    population : int\n",
    "        Number of neighboring populations to be generated.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    [solution : [int]]\n",
    "        List of neighboring solutions (list of different measurements of the population).\n",
    "    \"\"\"\n",
    "    return [[q.measure() for q in Q] for p in range(population)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fit_and_repair_neighborhood(Q, neighborhood, w_capacity):\n",
    "    \"\"\"Evaluates (value and weight) and repairs all neighboring solutions.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    Q : [Qitem]\n",
    "        Qitem population\n",
    "    neighborhood : [[int]]\n",
    "        List of neighboring solutions (list of different measurements).\n",
    "    w_capacity : int\n",
    "        Knapsack weight limit capacity\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    [[solution : [int], value : int, weight : int]]\n",
    "        List of repaired solution and corresponding evaluation (value and weight).\n",
    "    \"\"\"\n",
    "    solutions = []\n",
    "    for i, solution in enumerate(neighborhood):       \n",
    "        solutions.append([solution, *fit_and_repair(Q, solution, w_capacity)])\n",
    "    return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def update_state(Q, delta, T, tabu_itt, solution_current, solution_comparison, is_best):\n",
    "    \"\"\"Update each qbit of the population by applying the matrix \n",
    "    according to the current solution and the comparison solution.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    Q : [Qitem]\n",
    "        Qitem population\n",
    "    delta : float\n",
    "        Angle used to build the move-gate matrix and operate under solution states.\n",
    "    T : dict {int : int}\n",
    "        Tabu list (implemented as a dictionary)\n",
    "    tabu_itt : int\n",
    "        Number of iterations an item should be kept on the tabu list\n",
    "    solution_current : [int]\n",
    "        Current solution from a population measurement.\n",
    "    solution_comparison : [int]\n",
    "        Solution to be compared with the current.\n",
    "    is_best : bool\n",
    "        True if the comparison solution was the best found from neighbors (worst otherwise).\n",
    "    \"\"\"\n",
    "    for i, q in enumerate(Q):\n",
    "        if T.setdefault(i, 0) == 0:\n",
    "            continue\n",
    "        diff = solution_comparison[i] - solution_current[i]\n",
    "        if diff == 0:\n",
    "            continue\n",
    "        if not is_best: \n",
    "            diff *= -1\n",
    "        if Q[i].alpha * Q[i].beta < 0:\n",
    "            diff *= -1\n",
    "        \n",
    "        Q[i].update(matrix_move_gate(delta*diff))\n",
    "        T[i] = tabu_itt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def qts(itt, delta, population, tabu_itt, file):\n",
    "    \"\"\"Performs the quantum-inspired tabu search algorithm.\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    itt : int\n",
    "        Number of iterations for the algorithm to execute\n",
    "    delta : float\n",
    "        Angle used to build the move-gate matrix and operate under solution states.\n",
    "    population : int\n",
    "        Number of neighboring populations to be generated in each loop.\n",
    "    tabu_itt : int\n",
    "        Number of iterations an item should be kept on the tabu list\n",
    "    file: Path\n",
    "        Knapsack problem instance file\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    best_sol : [solution : [int], value : int, weight : int]\n",
    "        Best solution found for the knapsack problem\n",
    "    best_itt : int\n",
    "        Iteration where the best solution was found\n",
    "    \"\"\"\n",
    "    \n",
    "    Q = []\n",
    "    T = dict()\n",
    "    w_capacity = 0\n",
    "    n_items = 0\n",
    "    optimum = 0\n",
    "    solution_i = None\n",
    "    \n",
    "    best_sol = []\n",
    "    best_itt = -1\n",
    "\n",
    "    with open(file) as f:\n",
    "        n_items = int(f.readline().split()[1])\n",
    "        w_capacity = int(f.readline().split()[1])\n",
    "        optimum = int(f.readline().split()[1])\n",
    "        f.readline()\n",
    "        for line in f:\n",
    "            _, lineV, lineW, _ = list(map(int, line.split(',')))\n",
    "            Q.append(Qitem(lineV, lineW))\n",
    "    \n",
    "    solution_i = measure_individuals(Q)\n",
    "\n",
    "    value_i, weight_i = fit_and_repair(Q, solution_i, w_capacity)\n",
    "    \n",
    "    best_sol = [solution_i, value_i, weight_i]\n",
    "    \n",
    "    itt_count = 0\n",
    "    itt_not_change = 0\n",
    "    while itt_count < itt and itt_not_change < 200:\n",
    "        itt_count += 1\n",
    "        neighborhood_population = get_neighborhood(Q, population)\n",
    "        neighborhood = fit_and_repair_neighborhood(Q, neighborhood_population, w_capacity)\n",
    "        best_neighbor = max(neighborhood, key=lambda x: x[1])\n",
    "        worst_neighbor = min(neighborhood, key=lambda x: x[1])\n",
    "        \n",
    "        found_better_solution = (\n",
    "            best_neighbor[1] > best_sol[1] or \n",
    "            (best_neighbor[1] == best_sol[1] and best_neighbor[2] < best_sol[2])\n",
    "        )\n",
    "        \n",
    "        if found_better_solution:\n",
    "            best_sol = best_neighbor[:]\n",
    "            best_itt = itt_count\n",
    "            itt_not_change = 0\n",
    "        else:\n",
    "            itt_not_change +=1\n",
    "            \n",
    "        for key, value in list(T.items()):\n",
    "            T[key] -= 1\n",
    "            if T[key]==0:\n",
    "                del T[key]\n",
    "        \n",
    "        update_state(Q, delta, T, tabu_itt, solution_i, best_neighbor[0], True)\n",
    "        solution_i = measure_individuals(Q)\n",
    "        \n",
    "        update_state(Q, delta, T, tabu_itt, solution_i, worst_neighbor[0], False)\n",
    "        solution_i = measure_individuals(Q)\n",
    "\n",
    "    return best_sol, best_itt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best Solution: 3468 on itt: 11\n"
     ]
    }
   ],
   "source": [
    "knapsack_instance = Path('./data/knapPI_11_500_1000_1.csv')\n",
    "# knapsack_instance = Path('./data/knapPI_12_500_1000_1.csv')\n",
    "# knapsack_instance = Path('./data/knapPI_13_500_1000_1.csv')\n",
    "# knapsack_instance = Path('./data/knapPI_1_5000_1000000_1.csv')\n",
    "\n",
    "best_sol, best_itt = qts(1000, 0.01*math.pi, 10, 2, knapsack_instance)\n",
    "print('Best Solution:', best_sol[1], 'on itt:', best_itt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}