showcase.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# AI Project : Biscuit Factory optimization"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "a1d11ed2bab28219"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Imports and initialization"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "74613360c3a1d53c"
  },
  {
   "cell_type": "code",
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "rng = np.random.default_rng()"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:30:26.001476305Z",
     "start_time": "2023-12-27T19:30:25.966741375Z"
    }
   },
   "id": "9a37ee47992e9311",
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "\n",
    "You also need the ```python-constraint``` library in conda, the ```biscuit_clement``` and ```biscuit_racel``` files, as they contain different implementations of the Roll class.  \n",
    "We have two implementations of the Roll class because we originally had one, then Clement copied it worked on his copy and Racel modified things on the original one.  \n",
    "When we tried to merge all the algorithms we had in the end, Clement's algorithms wouldn't work with Racel 's Roll class and the inverse was also true.  \n",
    "So we decided to keep it that way, we lacked time to try to merge the two Roll classes. In the notebook, the proper Roll class is reimported before each algorithm."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "f8545d9307f978cf"
  },
  {
   "cell_type": "markdown",
   "source": [
    "First we did greedy search and backtracking csp algorithms."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b8c89f391dcd8d61"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Greedy search"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "af50e58cbd72a47b"
  },
  {
   "cell_type": "code",
   "outputs": [],
   "source": [
    "from biscuits_clement import biscuit_types, Roll, defects_list\n",
    "from constraint import Problem  # from the python-constraint librairy in conda\n",
    "\n",
    "\n",
    "# Global access within this module for defects_list\n",
    "def get_defects_between(start, end, defects_list):\n",
    "    return [defect for defect in defects_list if start <= defect['x'] < end]\n",
    "\n",
    "# Constraint to ensure no overlapping biscuits\n",
    "def no_overlap_constraint(*positions):\n",
    "    sizes = [b.size for b in biscuit_types]  # Access the global biscuit_types\n",
    "    for i, pos in enumerate(positions[:-1]):\n",
    "        if pos + sizes[i] > positions[i + 1]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "# Constraint to ensure defects are within tolerance\n",
    "def defects_within_tolerance(*positions):\n",
    "    for i, pos in enumerate(positions):\n",
    "        biscuit = biscuit_types[i]  # Access the global biscuit_types\n",
    "        defects_in_range = get_defects_between(pos, pos + biscuit.size, defects_list)\n",
    "        defect_counts = {defect_class: 0 for defect_class in biscuit.tolerance.keys()}\n",
    "        for defect in defects_in_range:\n",
    "            defect_class = defect['class']\n",
    "            defect_counts[defect_class] += 1\n",
    "        if not biscuit.is_valid(defect_counts):\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "# Function to calculate the total value of biscuits on the roll\n",
    "def calculate_total_value(*positions):\n",
    "    total_value = 0\n",
    "    for i, pos in enumerate(positions):\n",
    "        total_value += biscuit_types[i].value\n",
    "    return total_value\n",
    "\n",
    "# Create the problem instance\n",
    "problem = Problem()\n",
    "\n",
    "# Variables for the positions of each biscuit type on the roll\n",
    "roll_size = 500\n",
    "\n",
    "# Assuming that biscuit_types are sorted by value with the most valuable first\n",
    "biscuit_types.sort(key=lambda b: -b.value)\n",
    "for i, biscuit in enumerate(biscuit_types):\n",
    "    problem.addVariable(f\"Biscuit_{i}\", range(roll_size - biscuit.size + 1))\n",
    "\n",
    "# Add constraints to the problem\n",
    "problem.addConstraint(no_overlap_constraint, [f\"Biscuit_{i}\" for i in range(len(biscuit_types))])\n",
    "problem.addConstraint(defects_within_tolerance, [f\"Biscuit_{i}\" for i in range(len(biscuit_types))])\n",
    "\n",
    "# Heuristic approach\n",
    "def greedy_heuristic():\n",
    "    roll = Roll(roll_size=500)\n",
    "    positions_filled = [False] * 500  # A simple way to track filled positions\n",
    "\n",
    "    for biscuit in sorted(biscuit_types, key=lambda b: -b.value):  # Sort by value as a heuristic\n",
    "        for position in range(roll.roll_size - biscuit.size + 1):\n",
    "            if not any(positions_filled[position:position + biscuit.size]):  # Check if space is free\n",
    "                defects_in_range = get_defects_between(position, position + biscuit.size, defects_list)\n",
    "                defect_counts = {defect_class: 0 for defect_class in biscuit.tolerance.keys()}\n",
    "                for defect in defects_in_range:\n",
    "                    defect_class = defect['class']\n",
    "                    defect_counts[defect_class] += 1\n",
    "\n",
    "                if biscuit.is_valid(defect_counts):\n",
    "                    # Fill the positions and add the biscuit to the roll\n",
    "                    for i in range(position, position + biscuit.size):\n",
    "                        positions_filled[i] = True  # Mark positions as filled\n",
    "                    biscuit_dict = {'start': position, 'end': position + biscuit.size, 'biscuit': biscuit}\n",
    "                    roll.append_biscuits(biscuit_dict)\n",
    "\n",
    "    return roll\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:30:26.004193486Z",
     "start_time": "2023-12-27T19:30:26.001785681Z"
    }
   },
   "id": "261fe353ed53c63b",
   "execution_count": 2
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The total value of the best roll is: 621\n",
      "The biscuits counts of the best roll is: {8: 44, 5: 1, 4: 14, 2: 1}\n"
     ]
    }
   ],
   "source": [
    "# Run the heuristic and get the Roll object with the best arrangement\n",
    "best_roll = greedy_heuristic()\n",
    "\n",
    "# Now you can access the total value and other properties of the best_roll\n",
    "print(f\"The total value of the best roll is: {best_roll.total_value()}\")\n",
    "print(f\"The biscuits counts of the best roll is: {best_roll.biscuit_type_count()}\")\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:30:26.047793313Z",
     "start_time": "2023-12-27T19:30:26.047184364Z"
    }
   },
   "id": "af8b294fecdffaed",
   "execution_count": 3
  },
  {
   "cell_type": "markdown",
   "source": [
    "Majority of biscuits of size 8 and 4"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "167826c764659095"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Backtracking algorithm"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "360d9fcbe42a0277"
  },
  {
   "cell_type": "code",
   "outputs": [],
   "source": [
    "from biscuits_clement import biscuit_types, defects_list, Roll\n",
    "\n",
    "\n",
    "# Helper function to check if a biscuit can be placed considering defects and overlapping\n",
    "def is_valid_position(start, biscuit, roll, defects_list):\n",
    "    # Check for overlap\n",
    "    for other in roll._biscuits:\n",
    "        if start < other['end'] and other['start'] < start + biscuit.size:\n",
    "            return False  # Overlap detected\n",
    "\n",
    "    # Check defects within the biscuit's range\n",
    "    defects_in_range = [defect for defect in defects_list if start <= defect['x'] < start + biscuit.size]\n",
    "    defect_counts = {defect_class: 0 for defect_class in biscuit.tolerance.keys()}\n",
    "    for defect in defects_in_range:\n",
    "        defect_class = defect['class']\n",
    "        defect_counts[defect_class] += 1\n",
    "\n",
    "    return biscuit.is_valid(defect_counts)\n",
    "\n",
    "\n",
    "# Backtracking algorithm\n",
    "def place_biscuits(roll, biscuits, defects_list, position=0):\n",
    "    if position >= roll.roll_size:  # Reached the end of the roll\n",
    "        return roll.total_value(), roll._biscuits.copy()\n",
    "\n",
    "    max_value = 0\n",
    "    best_arrangement = None\n",
    "\n",
    "    for biscuit in biscuits:\n",
    "        if is_valid_position(position, biscuit, roll, defects_list):\n",
    "            # Create a new biscuit dict to represent the placed biscuit\n",
    "            biscuit_dict = {'start': position, 'end': position + biscuit.size, 'biscuit': biscuit}\n",
    "            # Place the biscuit\n",
    "            roll.append_biscuits(biscuit_dict)  # Now passing a dict object\n",
    "            # Recurse to the next position\n",
    "            value, arrangement = place_biscuits(roll, biscuits, defects_list, position + biscuit.size)\n",
    "\n",
    "    # Consider not placing a biscuit at this position\n",
    "    value, arrangement = place_biscuits(roll, biscuits, defects_list, position + 1)\n",
    "    if value > max_value:\n",
    "        max_value = value\n",
    "        best_arrangement = arrangement\n",
    "\n",
    "    return max_value, best_arrangement\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:30:26.048173807Z",
     "start_time": "2023-12-27T19:30:26.047363716Z"
    }
   },
   "id": "5e6f3d9a5333e81b",
   "execution_count": 4
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The total value of the best roll is: 643\n",
      "The biscuits counts of the best roll is: {8: 43, 5: 0, 4: 21, 2: 1}\n"
     ]
    }
   ],
   "source": [
    "# Instantiate a Roll object\n",
    "roll = Roll(roll_size=500)\n",
    "# Sort biscuits by value, descending (as a heuristic)\n",
    "sorted_biscuits = sorted(biscuit_types, key=lambda b: -b.value)\n",
    "\n",
    "# Find the best arrangement\n",
    "total_value, arrangement = place_biscuits(roll, sorted_biscuits, defects_list)\n",
    "\n",
    "# Create a new Roll object with the best arrangement\n",
    "best_roll = Roll(roll_size=500)\n",
    "best_roll._biscuits = arrangement  # Directly setting the best arrangement\n",
    "\n",
    "# Now you can access the total value and other properties of the best_roll\n",
    "print(f\"The total value of the best roll is: {best_roll.total_value()}\")\n",
    "print(f\"The biscuits counts of the best roll is: {best_roll.biscuit_type_count()}\")\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:30:26.208584003Z",
     "start_time": "2023-12-27T19:30:26.047454522Z"
    }
   },
   "id": "c097254d802f0cfb",
   "execution_count": 5
  },
  {
   "cell_type": "markdown",
   "source": [
    "Majority of biscuits of size 8 and 4 too"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c6447d2f0b17bd48"
  },
  {
   "cell_type": "markdown",
   "source": [
    "We notice same distributions of biscuit types for greedy search and backtracking algorithm. This is because of the similar functionnality of these two algorithms, as they try to arrange for the best arrangement."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "d6e0847d4c8fa06"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Bogo search"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "db88890b7bc78fa1"
  },
  {
   "cell_type": "code",
   "outputs": [],
   "source": [
    "from biscuits_racel import Roll\n",
    "\n",
    "\n",
    "# bogo optimizer (as in bogo sort : https://en.wikipedia.org/wiki/Bogosort) \n",
    "# is an optimizing algorithm that generates a random roll at each iteration and compares it to the best roll found.\n",
    "# It is different to most random optimizer like random search as it generates a new solution at each iteration, instead of modifying the current best roll.\n",
    "def bogo(max_iter):\n",
    "    # initialize the best roll\n",
    "    best_roll = None\n",
    "    best_score = float('-inf')    \n",
    "    # at each iteration we generate a random roll and \n",
    "    for _ in range(max_iter):\n",
    "        roll = Roll(500)\n",
    "        # randomly fill the roll, we enable biscuit constraint checking so that biscuits must be a biscuit value \n",
    "        roll.fill_roll_random(check_biscuit_valid=True)\n",
    "        v = roll.total_price()\n",
    "        if v > best_score:\n",
    "            best_roll = roll\n",
    "            best_score = v\n",
    "\n",
    "    return best_roll, best_score"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:30:26.216898129Z",
     "start_time": "2023-12-27T19:30:26.211335911Z"
    }
   },
   "id": "263ab968499713f",
   "execution_count": 6
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best price is : 659, best number of biscuits is :138\n",
      "Best food biscuit counts is : {8: 25, 5: 19, 4: 32, 2: 15}\n"
     ]
    }
   ],
   "source": [
    "best_r, best_s = bogo(500)\n",
    "print(f'Best price is : {best_s}, best number of biscuits is :{best_r.number_of_biscuits()}')\n",
    "print(f'Best food biscuit counts is : {best_r.biscuit_type_count()}')"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:30:33.037558495Z",
     "start_time": "2023-12-27T19:30:26.242712028Z"
    }
   },
   "id": "261997d362bc330",
   "execution_count": 7
  },
  {
   "cell_type": "markdown",
   "source": [
    "Majority of size 8 and 4 biscuits as well, but more biscuits of sizes 2 and 5"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "bcda152c51d8d241"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Artificial bee colony algorithm"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "f0cda7826d946c35"
  },
  {
   "cell_type": "code",
   "outputs": [],
   "source": [
    "from bees import Hive, Scout, Worker, Onlooker\n",
    "from bees import names, generate_new_food, evaluate_roll\n",
    "\n",
    "def bee_search(obj_func,\n",
    "               minimize=False,\n",
    "               n_bees=10,\n",
    "               n_workers=None,\n",
    "               n_scouts=1,\n",
    "               max_iter=1000,\n",
    "               limit=5):\n",
    "    # The minimize parameter indicates whether the objective function should be minimized,\n",
    "    # in which case it should maximize the opposite, or not.\n",
    "    if minimize:\n",
    "        def fitness(roll):\n",
    "            return -1 * obj_func(roll)\n",
    "    else:\n",
    "        def fitness(roll):\n",
    "            return obj_func(roll)\n",
    "\n",
    "    # initializing the number of worker bees, if None\n",
    "    if n_workers is None:\n",
    "        n_workers = n_bees // 2\n",
    "\n",
    "    # Each worker should be assigned a food source\n",
    "    # So the number of food source is equal to the number of workers\n",
    "    n_foods = n_workers\n",
    "\n",
    "    # initialize the hive\n",
    "    hive = Hive({\n",
    "        'scouts': [Scout(fitness, name=rng.choice(names)) for _ in range(0, n_scouts)],\n",
    "        'onlookers':\n",
    "            [Onlooker(fitness, name=rng.choice(names)) for _ in range(0, n_bees - n_workers)],\n",
    "        'workers': [Worker(fitness, name=rng.choice(names)) for _ in range(0, n_workers)]\n",
    "    })\n",
    "\n",
    "    # generate an array of random coordinates in the search space\n",
    "    # of shape [[...] * food_sources_initial]\n",
    "    initial_foods = generate_new_food(n_foods, food_quantity=limit)\n",
    "\n",
    "    # Send all workers at the initial food\n",
    "    for worker, food in zip(hive.get_workers(), initial_foods):\n",
    "        worker.go_to_food(food)\n",
    "        worker.dance()\n",
    "\n",
    "    # Get the initial best food\n",
    "    best_quality_food = max(hive.get_workers(), key=lambda worker_bee: worker_bee.food.quality).food\n",
    "\n",
    "    # Algorithm loop\n",
    "    for i in range(max_iter):\n",
    "        \"\"\"Workers phase\"\"\"\n",
    "\n",
    "        for worker in hive.get_workers():\n",
    "            # We first check if the source has been depleted by the onlookers\n",
    "            # Indeed we gave the ability for onlooker to bring food to the hive, \n",
    "            # so the food source gets depleted by both type of bees.\n",
    "            # Because of the loop, if we have a food source of quantity value 0,\n",
    "            # the worker bee has to leave and join the scouts to search for a new food source.\n",
    "            if worker.should_leave():\n",
    "                new_scout = worker.leave_food_point()\n",
    "                hive.get_scouts().append(new_scout)\n",
    "                hive.get_workers().remove(worker)\n",
    "                continue\n",
    "\n",
    "            worker.dance()  # Workers register their food source and give them a food source quality value\n",
    "\n",
    "            # Search for a better food source around the current food source\n",
    "            new_solution = worker.look_around()\n",
    "            # Evaluate food source\n",
    "            new_solution_evaluation = worker.calculate_nectar(new_solution)\n",
    "            # If food source is better, discard old food source and select new open\n",
    "            # Else bring food to the hive, or leave if no more food is available\n",
    "            if new_solution_evaluation > worker.food.quality:\n",
    "                worker.food = new_solution\n",
    "                worker.dance()\n",
    "                if new_solution_evaluation > best_quality_food.quality:\n",
    "                    best_quality_food = new_solution\n",
    "            else:\n",
    "                worker.bring_food()\n",
    "                if worker.should_leave():\n",
    "                    new_scout = worker.leave_food_point()\n",
    "                    hive.get_scouts().append(new_scout)\n",
    "                    hive.get_workers().remove(worker)\n",
    "\n",
    "        \"\"\"Onlookers phase\"\"\"\n",
    "        # Onlookers choose a food source, among the worker ones.\n",
    "        # This choice is made by probabilities, \n",
    "        # otherwise they'd just choose the best one and never explore around the other ones.\n",
    "\n",
    "        # Calculate the probability value of the sources\n",
    "        # with which they are preferred by the onlooker bees\n",
    "        # First they watch the bees dance\n",
    "        # choreography is of type (worker, worker.food, food.quality)\n",
    "        choreography = np.array([worker.dance() for worker in hive.get_workers()])\n",
    "        # print([c.quality for c in choreography[:, 0]])\n",
    "        choreography[:, 1] = np.array([dance if dance > float('-inf') else 0 for dance in choreography[:, 1]])\n",
    "        # convert -inf to 0\n",
    "        choreography[:, 1] = np.abs(np.nan_to_num(choreography[:, 1]))\n",
    "        # calculate the sum of all the qualities\n",
    "        sum_dances = np.sum(choreography[:, 1])\n",
    "        # for functions that are flat on most of their definition space, sum could be zero\n",
    "        # we have to check for that condition to prevent having nan values in the probabilities list\n",
    "        if sum_dances == 0.0:\n",
    "            probabilities = None\n",
    "        else:\n",
    "            # divide each value to get the probability for the onlooker to choose that food source\n",
    "            probabilities = np.divide(choreography[:, 1], sum_dances).astype('float64')\n",
    "            # In that case, every food source has the same probability of being chosen which is not optimal.\n",
    "            # We want to have most likeliness for the most promising source\n",
    "\n",
    "        for onlooker in hive.get_onlookers():\n",
    "            # Onlookers choose a food source, then dance.\n",
    "            onlooker.choose_preferred_source(choreography[:, 0], probabilities)\n",
    "            onlooker.dance()\n",
    "            # Onlookers search for a new food source\n",
    "            new_solution = onlooker.look_around()\n",
    "            # Evaluate food source\n",
    "            new_solution_evaluation = onlooker.calculate_nectar(new_solution)\n",
    "            # If food source is better, discard old food source and select new food source\n",
    "            if new_solution_evaluation > onlooker.food.quality:\n",
    "                onlooker.food = new_solution\n",
    "                onlooker.dance()\n",
    "                if new_solution_evaluation > best_quality_food.quality:\n",
    "                    best_quality_food = new_solution\n",
    "            # Else increase limit counter\n",
    "            else:\n",
    "                if onlooker.food.has_food():\n",
    "                    onlooker.bring_food()\n",
    "                # If the food is exhausted, leave the food source\n",
    "                if onlooker.should_leave():\n",
    "                    onlooker.leave_food_point()\n",
    "\n",
    "        \"\"\"Scouts phase\"\"\"\n",
    "        # Scouts search for a new food source around the search space. \n",
    "        for scout in hive.get_scouts():\n",
    "            # Find a new food source\n",
    "            scout.find_new_food(quantity=limit)\n",
    "            # Convert back to worker and go on that food source\n",
    "            new_worker = scout.convert_worker(fitness)\n",
    "            hive.get_scouts().remove(scout)\n",
    "            hive.get_workers().append(new_worker)\n",
    "\n",
    "    return best_quality_food"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:30:33.045730772Z",
     "start_time": "2023-12-27T19:30:33.034995680Z"
    }
   },
   "id": "4c54e87612f48610",
   "execution_count": 8
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best price is : 657, best number of biscuits is :144\n",
      "Best food biscuit counts is : {8: 33, 5: 8, 4: 29, 2: 23}\n"
     ]
    }
   ],
   "source": [
    "best_food = bee_search(evaluate_roll,\n",
    "                       minimize=False,\n",
    "                       n_bees=30,\n",
    "                       n_scouts=1,\n",
    "                       max_iter=500,\n",
    "                       limit=3)\n",
    "print(f'Best price is : {best_food.location.total_price()}, best number of biscuits is :{best_food.location.number_of_biscuits()}')\n",
    "print(f'Best food biscuit counts is : {best_food.location.biscuit_type_count()}')"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-12-27T19:31:57.931303680Z",
     "start_time": "2023-12-27T19:31:26.164008201Z"
    }
   },
   "id": "e0018ee0cae1bd5a",
   "execution_count": 10
  },
  {
   "cell_type": "markdown",
   "source": [
    "Biscuits are more uniformly distributed on the roll. Results are similar than Bogo optimizer but take longer to be executed."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "624288729a85fe23"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The two first algorithms tend to have more homogenous distributions of biscuits with a high percentage of biscuit of size 8 and 4.  \n",
    "The two last algorithms are more heterogenous and had a uniform repartition of biscuit types along the roll.\n",
    "However we can infer adding randomness allows for better results, despite longer time of execution."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "a5157e762cc71b3e"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}