Halloween_challenge.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Halloween challenge\n",
    "---\n",
    "\n",
    "Find the best solution with the fewest calls to the fitness functions for:\n",
    "\n",
    "* `num_points = [100, 1_000, 5_000]`\n",
    "* `num_sets = num_points`\n",
    "* `density = [.3, .7]` "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "a17f43c0bcbc7886"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Code\n",
    "---"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b3cdb26faa1b6c23"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Imported Libraries"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "972ff20494f2620b"
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3ffe7245-e849-41d0-9698-5f0e0b83fee9",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-02T20:45:16.471320800Z",
     "start_time": "2023-11-02T20:45:16.344616Z"
    }
   },
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "from random import random, randint, shuffle, seed, choice\n",
    "import numpy as np\n",
    "from scipy import sparse\n",
    "from copy import copy"
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Problem instance\n",
    "\n",
    "This function, called ``make_set_covering_problem``, returns a sparse matrix of size ``num_sets`` (number of sets) * ``num_points`` (number of elements) with Boolean values (True or False) in which the rows represent sets, and the columns represent the elements covered by the sets. The density of the matrix is controlled by a parameter called ``density``. For each pair, if a random number generated with random() is less than the specified ``density``, sets the corresponding element to True in the set.\n",
    "\n",
    "The ``current_state`` is an array of boolean where true indicates if the state contains that particular set, false if it doesn't contain it. We have to initialize it to a random possible solution."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b577c9aa805678d8"
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "6f03bd67-78a0-4d72-95b7-77a918727b91",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-02T20:45:18.029543Z",
     "start_time": "2023-11-02T20:45:18.025407700Z"
    }
   },
   "outputs": [],
   "source": [
    "def make_set_covering_problem(num_points, num_sets, density):\n",
    "    \"\"\"Returns a sparse array where rows are sets and columns are the covered items\"\"\"\n",
    "    seed(num_points*2654435761+num_sets+density)\n",
    "    sets = sparse.lil_array((num_sets, num_points), dtype=bool)\n",
    "    for s, p in product(range(num_sets), range(num_points)):\n",
    "        if random() < density:\n",
    "            sets[s, p] = True\n",
    "    for p in range(num_points):\n",
    "        sets[randint(0, num_sets-1), p] = True\n",
    "    return sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "221ffdba-5d3d-48cc-bd08-45ccc9366ea6",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2023-11-02T20:47:27.321420500Z",
     "start_time": "2023-11-02T20:47:26.598840900Z"
    }
   },
   "outputs": [],
   "source": [
    "num_points = 1000\n",
    "num_sets = num_points\n",
    "density = .3\n",
    "matrix = make_set_covering_problem(num_points, num_sets, density)\n",
    "\n",
    "starting_state = [choice([True, False]) for _ in range(num_sets)]"
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Fitness function\n",
    "\n",
    "The ``fitness`` function return the number of covered elements and the negative cost that is the number of taken sets as negative. That's because we want to take the solution with the smallest number of taken sets."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "57a7450903603992"
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [],
   "source": [
    "def fitness(state):\n",
    "    global fitness_counter\n",
    "    fitness_counter+=1\n",
    "    cost = sum(state)\n",
    "    valid = len(list(set(np.concatenate(matrix.rows[state]))))\n",
    "    return valid, -cost"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-11-02T20:45:21.980714400Z",
     "start_time": "2023-11-02T20:45:21.978202700Z"
    }
   },
   "id": "cb7eb2fd918a8cd5"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Hill Climbing\n",
    "\n",
    "The ``tweak`` function swap one of the set randomly, if it was taken we change it into not taken and vice versa.\n",
    "\n",
    "Results:\n",
    "\n",
    "| num points | num sets | density | number of evaluation | best fitness |\n",
    "|------------|----------|---------|----------------------|--------------|\n",
    "| 100        |    100   | .3      | 200                  | (100, -14)   |\n",
    "| 100        | 100      | .7      | 200                  | (100, -21)   |\n",
    "| 1000       | 1000     | .3      | 2.000                | (1000, -183) |\n",
    "| 1000       | 1000     | .7      | 2.000                | (1000, -192) |\n",
    "| 5000       | 5000     | .3      | 10.000               | (5000, -929) |\n",
    "| 5000       | 5000     | .7      | 10.000               | (5000, -)    |"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "cd8f12c5485f6497"
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [],
   "source": [
    "def tweak(state):\n",
    "    new_state = copy(state)\n",
    "    index = randint(0, num_points - 1) # pick a random index\n",
    "    new_state[index] = not new_state[index] # swap\n",
    "    return new_state"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-11-02T20:45:23.979566900Z",
     "start_time": "2023-11-02T20:45:23.975910900Z"
    }
   },
   "id": "66ee5bf5cb6a8bdd"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "current_state = starting_state\n",
    "global fitness_counter\n",
    "fitness_counter=0\n",
    "for step in range(num_points):  \n",
    "    new_state = tweak(current_state)\n",
    "    if fitness(new_state) > fitness(current_state):\n",
    "        current_state = new_state\n",
    "print(fitness(current_state), fitness_counter)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "4daced38a33ca403"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Simulated Annealing\n",
    "This algorithm is a Hill Climbing but with probability $p≠0$ of accepting a worsening solution $s'$ where $f(s)>f(s)': p=e^- \\frac{f(s)-f(s')}{t}$ where $s$ is the current solution,  $s'$ is the tweaked one and $t$ is the temperature. The idea is that the further we go with the exploration, the more T decreases and with it also the probability of accepting worse solutions.\n",
    "\n",
    "Results:\n",
    "\n",
    "| num points | num sets | density | number of evaluation | best fitness  |\n",
    "|------------|----------|---------|----------------------|---------------|\n",
    "| 100        |    100   | .3      | 200                  | (100, -38)    |\n",
    "| 100        | 100      | .7      | 200                  | (100, -45)    |\n",
    "| 1000       | 1000     | .3      | 2.000                | (1000, -488)  |\n",
    "| 1000       | 1000     | .7      | 2.000                | (1000, -492)  |\n",
    "| 5000       | 5000     | .3      | 10.000               | (5000, -2461) |\n",
    "| 5000       | 5000     | .7      | 10.000               | (5000, -2511) |"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c2abe38bd12a65cc"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "current_state = starting_state\n",
    "global fitness_counter\n",
    "fitness_counter=0\n",
    "t = num_points\n",
    "for step in range(num_points):\n",
    "    new_state = tweak(current_state)\n",
    "    _, newCost = fitness(new_state)\n",
    "    _, oldCost = fitness(current_state)\n",
    "    if newCost <= oldCost and random() < np.exp(-((oldCost-newCost)/t)):\n",
    "        current_state = new_state\n",
    "    elif newCost > oldCost:\n",
    "        current_state = new_state\n",
    "    t=t-1    \n",
    "print((fitness(current_state), fitness_counter))"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "16b689596b2826ff"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Tabu Search\n",
    "This algorithm keeps track of the states we have visited and avoids going back to them.\n",
    "\n",
    "Results:\n",
    "\n",
    "| num points | num sets | density | number of evaluation | best fitness |\n",
    "|------------|----------|---------|----------------------|--------------|\n",
    "| 100        |    100   | .3      | 191                  | (100, -14)   |\n",
    "| 100        | 100      | .7      | 197                  | (100, -21)   |\n",
    "| 1000       | 1000     | .3      | 1.993                | (1000, -183) |\n",
    "| 1000       | 1000     | .7      | 1.991                | (1000, -190) |\n",
    "| 5000       | 5000     | .3      | 9.997                | (5000, -929) |\n",
    "| 5000       | 5000     | .7      | 9.991                | (5000, -941) |"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "4e1275ded613fa5c"
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1000, -183) 1993\n"
     ]
    }
   ],
   "source": [
    "current_state = starting_state\n",
    "already_visited = []\n",
    "global fitness_counter\n",
    "fitness_counter=0\n",
    "for step in range(num_points):\n",
    "    new_state = tweak(current_state)\n",
    "    if new_state not in already_visited:\n",
    "        already_visited.append(new_state)\n",
    "        if fitness(new_state) > fitness(current_state):\n",
    "            current_state = new_state\n",
    "print(fitness(current_state), fitness_counter)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-11-02T20:47:46.622887300Z",
     "start_time": "2023-11-02T20:47:31.982366600Z"
    }
   },
   "id": "eaf690c1bb51661e"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Iterated Local Search\n",
    "Is a version of Hill Climbing. The Hill Climbing algorithm is put into a loop and restarted in a new position which can be the global optimum or the last optimum.\n",
    "\n",
    "Results: \n",
    "\n",
    "| num points | num sets | density | number of evaluation | best fitness |\n",
    "|------------|----------|---------|----------------------|--------------|\n",
    "| 100        |    100   | .3      | 200                  | (100, -9)    |\n",
    "| 100        | 100      | .7      | 200                  | (100, -4)    |\n",
    "| 1000       | 1000     | .3      | 2.000                | (1000, -14)  |\n",
    "| 1000       | 1000     | .7      | 5.000                | (1000, -5)   |\n",
    "| 5000       | 5000     | .3      | 100.000              | (5000, -21)  |\n",
    "| 5000       | 5000     | .7      | 100.000              | (5000, -11)  |"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "9d160632b260f66"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "current_state = starting_state\n",
    "global fitness_counter\n",
    "fitness_counter=0\n",
    "N_Restart = 5\n",
    "solution = current_state\n",
    "for i in range (N_Restart):\n",
    "    for step in range(num_points):\n",
    "        new_state = tweak(solution)\n",
    "        if fitness(new_state) > fitness(solution):\n",
    "            solution = new_state\n",
    "print((fitness(solution), fitness_counter))"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "7a91f93ad908ab87"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}