Assignment4_Bees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bees Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Students:\n",
    "\n",
    "Ana Carmen Estrada Real A01748866\n",
    "\n",
    "Jesús Leopoldo Llano García A01748867\n",
    "\n",
    "Cody Eduardo Evans Trajo A01207043"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"./bees.jpg\" width=\"400\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Questions\n",
    "\n",
    "a) Choose a solution method from the metaheuristics of Ant System, Bees Algorithm, and\n",
    "Particle Swarm Optimization.\n",
    "\n",
    "We chose the bees algorithm.\n",
    "\n",
    "b) Document your solution by specifying:\n",
    "i) How do you describe and codify the solutions and how will you represent them in Python for the chosen method?\n",
    "\n",
    "We represent the initial board (from 0's and 1's) to '#' and '-', then we generate the random bees (n) (every bee is a list of locations for the sensors)and evaluate the solutions. We define the selected bees (m), the elite bees (e), and how many neighbors each will have. \n",
    "The size of the neighborhood for those bees is defined as choosing only one sensor from the selected bee (or elite) with random and move just that sensor to a random place.\n",
    "We evaluate the new bees from each place, choose the best ones, assign them to a new list and generate the remaining scouts with random again.\n",
    "All of this inside of a for depending on the amount of generations we want.\n",
    "Finaly we select the best bee after all the iterations and print it.\n",
    "\n",
    "ii) How do you generate the initial solutions?\n",
    "\n",
    "With the function rand_bees, we generate lists of random locations. The only restriction for the locations is that the sensors should be inside the board, so it takes into account the size of every sensor.\n",
    "\n",
    "iii) How are the new solutions generated from the current solutions during the\n",
    "execution of the method?\n",
    "iv) How do you evaluate the solutions you want to optimize?\n",
    "\n",
    "We place the sensors in the board, with the function eval_mat and count the empty spaces, then add a minus sign and choose the max values. \n",
    "\n",
    "c) Modify the Python code provided to solve the problem. Document it internally with Python comments. Indicate how to run it.\n",
    "\n",
    "d) You must experiment with different values for the parameters required by the chosen metaheuristic, trying to find appropriate values to solve the problem. Summarize the results of the experiments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Importing the packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import random as r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining the functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "## A Function to copy the grid\n",
    "def copy(grid):\n",
    "    init_grid = []\n",
    "    for row in grid:\n",
    "        temp_row =[]\n",
    "        for elem in row:\n",
    "            temp_row.append(elem)\n",
    "        init_grid.append(temp_row)\n",
    "    return init_grid\n",
    "\n",
    "\n",
    "## A Function to evaluate the board with sensors, we count empty spaces and add a minus to maximize it\n",
    "def eval_num(grid):\n",
    "    X=0\n",
    "    for j in range (0, len(grid)):\n",
    "            for k in range (0, len(grid[j])):\n",
    "                if grid [j][k] == '-':\n",
    "                   X=X+1\n",
    "    return -X\n",
    "\n",
    "## For printing the grid\n",
    "def printmat(grid):\n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid)):\n",
    "            print(grid[i][j], end=\"  \")\n",
    "        print()\n",
    "\n",
    "## To get the initial grid from 0,1 to '#' and '-'\n",
    "def initial_grid(grid):\n",
    "    init_grid = copy(grid)\n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid)):\n",
    "            if grid[i][j] == 1:\n",
    "                init_grid[i][j] ='-' \n",
    "            else:\n",
    "                init_grid[i][j] ='#'\n",
    "    return init_grid\n",
    "\n",
    "## Turn the coordinates of the sensors to boards we can evaluate\n",
    "def eval_mat(grid, sensors_range, locations):\n",
    "    for i in range(0, len(sensors_range)):\n",
    "        sensor_size = sensors_range[i]\n",
    "        for j in range (0, len(grid)):\n",
    "            for k in range (0, len(grid[j])):\n",
    "                g = [j,k]\n",
    "                #print (g)\n",
    "                if np.all(np.asarray(locations[i]) == np.asarray(g)):\n",
    "                    rng = sensors_range [i] \n",
    "                    for n in range (0, rng):\n",
    "                        for m in range (0, rng):\n",
    "                            if grid [j+m][k] == '-':\n",
    "                                grid [j+m][k] = i+1\n",
    "                            if grid [j+m][k+n] == '-':\n",
    "                                grid [j+m][k+n] = i+1\n",
    "                            if grid [j][k+n] == '-':\n",
    "                                grid [j][k+n] = i+1\n",
    "    return grid\n",
    "\n",
    "## Generate random bees     \n",
    "def rand_bees(num):\n",
    "    r.seed()\n",
    "    init_bees = []\n",
    "\n",
    "    for i in range(num):\n",
    "        bees = []\n",
    "        for j in range(len(sensors_range)):\n",
    "            bees.append([r.randint(0, 5-sensors_range[j]), r.randint(0, 5-sensors_range[j])])\n",
    "        init_bees.append(bees)\n",
    "    #print(init_bees)\n",
    "    return init_bees\n",
    "\n",
    "## Evaluate the bees\n",
    "def eval_bees(grid, sensors, bees):   \n",
    "    ev_bees = []\n",
    "\n",
    "    for i in range(len(bees)):\n",
    "        sgrid = copy(init_grid)\n",
    "        #printmat(eval_mat(sgrid, sensors_range, init_bees[i]))\n",
    "        ev_bees.append(eval_num(eval_mat(sgrid, sensors_range, init_bees[i])))\n",
    "        #print()\n",
    "    #print(ev_bees)\n",
    "    return ev_bees\n",
    "\n",
    "## Choose m selected bees\n",
    "def selec_bees(num, ev_bees, current_bees):    \n",
    "    m=num\n",
    "    best_bees = []\n",
    "    best_sites = []\n",
    "    bees = ev_bees.copy()\n",
    "    old_bees = current_bees.copy()\n",
    "\n",
    "    for j in range(m):\n",
    "        best_sites.append(max(bees))\n",
    "        k = bees.index(max(bees))\n",
    "        best_bees.append(old_bees[k])\n",
    "        del bees[k]\n",
    "        del old_bees[k]\n",
    "    \n",
    "    #print(best_bees)\n",
    "    return best_sites, best_bees\n",
    "\n",
    "## Elite bees\n",
    "def elite_bees(num, ev_bees, current_bees):\n",
    "    e = num\n",
    "    best_bees_e = []\n",
    "    best_sites_e = []\n",
    "    bees_e = ev_bees.copy()\n",
    "    old_bees1 = current_bees.copy()\n",
    "\n",
    "    for j in range(e):\n",
    "        best_sites_e.append(max(bees_e))\n",
    "        k = bees_e.index(max(bees_e))\n",
    "        best_bees_e.append(old_bees1[k])\n",
    "        del bees_e[k]\n",
    "        del old_bees1[k]\n",
    "    \n",
    "    #print(best_bees_e, k, ev_bees, bees_e)\n",
    "    return best_bees_e\n",
    "\n",
    "## The good bees are the rest of the selected but not elite\n",
    "def good_bees(num, sites, select_bees):\n",
    "    sel=num\n",
    "    best_bees_se = []\n",
    "    best_sites_se = []\n",
    "    bees_se = sites.copy()\n",
    "    old_best = select_bees.copy()\n",
    "\n",
    "    for j in range(sel):\n",
    "        best_sites_se.append(min(bees_se))\n",
    "        k = bees_se.index(min(bees_se))\n",
    "        best_bees_se.append(old_best[k])\n",
    "        del bees_se[k]\n",
    "        del old_best[k]\n",
    "    \n",
    "    #print(best_bees_se)\n",
    "    return best_bees_se\n",
    "\n",
    "## Generate the neighbors of the elite bees\n",
    "def neig_elite(e, n2, elite_bees, sensors_range):\n",
    "    rand_bees_elite = []\n",
    "    for j in range(n2+1):\n",
    "        for i in range(e):\n",
    "            rand_bees_elite.append(elite_bees[i])\n",
    "    for i in range(2, len(rand_bees_elite)):\n",
    "        sens = r.randint(0, 3)\n",
    "        rand_bees_elite[i][sens]=[r.randint(0, 5-sensors_range[sens]), r.randint(0, 5 -sensors_range[sens])]\n",
    "\n",
    "    #print(rand_bees_elite)\n",
    "    return rand_bees_elite\n",
    "\n",
    "## Generate the neighbors of the good bees\n",
    "def neig_good(g, n1, other_bees, sensors_range):\n",
    "    rand_bees_sel = []\n",
    "    for j in range(n1+1):\n",
    "        for i in range(g):\n",
    "            rand_bees_sel.append(other_bees[i])\n",
    "\n",
    "    for i in range(2, len(rand_bees_sel)):\n",
    "        sens = r.randint(0, len(sensors_range)-1)\n",
    "        rand_bees_sel[i][sens]=[r.randint(0, 5-sensors_range[sens]), r.randint(0, 5-sensors_range[sens])]\n",
    "    #print(rand_bees_sel)    \n",
    "    return rand_bees_sel\n",
    "\n",
    "## New list of scouts\n",
    "def new_scouts(new_bees, elite_best, good_best):\n",
    "    new_bee=new_bees.copy()\n",
    "    for i in range(len(elite_best)):\n",
    "        new_bee.append(elite_best[i])\n",
    "    for j in range(len(good_best)):\n",
    "        new_bee.append(good_best[j])\n",
    "    #print(new_bee)\n",
    "    return new_bee\n",
    "\n",
    "## Get the final best bee\n",
    "\n",
    "def best_bee(grid, ev_bees, current_bees, sensors_range):    \n",
    "    ev = []\n",
    "    bee = []\n",
    "    ev.append(max(ev_bees))\n",
    "    k = ev.index(max(ev_bees))\n",
    "    bee.append(current_bees[k])\n",
    "    print('Final Best Score and Coordinates of the sensors')\n",
    "    print(ev, bee)\n",
    "    \n",
    "    locations = bee\n",
    "    for i in range(0, len(sensors_range)):\n",
    "        sensor_size = sensors_range[i]\n",
    "        for j in range (0, len(grid)):\n",
    "            for k in range (0, len(grid[j])):\n",
    "                g = [j,k]\n",
    "                if np.all(np.asarray(locations[0][i]) == np.asarray(g)):\n",
    "                    rng = sensors_range[i] \n",
    "                    for n in range (0, rng):\n",
    "                        for m in range (0, rng):\n",
    "                            if grid [j+m][k] == '-':\n",
    "                                grid [j+m][k] = i+1\n",
    "                            if grid [j+m][k+n] == '-':\n",
    "                                grid [j+m][k+n] = i+1\n",
    "                            if grid [j][k+n] == '-':\n",
    "                                grid [j][k+n] = i+1\n",
    "    \n",
    "    print('Final: Best State')\n",
    "    printmat(grid)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define the initial board and sensors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "sensors_range = [3,2,4,1]    \n",
    "grid = [[1,1,1,0,1,0], [1,0,0,1,1,1], [0,0,1,1,0,1], [1,1,1,1,1,1], [0,0,0,1,1,1], [1,1,1,1,0,0]] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Print our initial grid and the evaluation to maximize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial Grid:\n",
      "-  -  -  #  -  #  \n",
      "-  #  #  -  -  -  \n",
      "#  #  -  -  #  -  \n",
      "-  -  -  -  -  -  \n",
      "#  #  #  -  -  -  \n",
      "-  -  -  -  #  #  \n",
      "-24\n"
     ]
    }
   ],
   "source": [
    "print('Initial Grid:')  \n",
    "init_grid = initial_grid(grid)\n",
    "printmat(initial_grid(grid))\n",
    "print(eval_num(init_grid))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Choose\n",
    "### How many initial bees (n)\n",
    "### How many selected bees (m)\n",
    "### How many elite bees (e)\n",
    "### How many helper bees for the elite neighborhood (n2)\n",
    "### How many helper bees for the rest of the selected bees (n1)\n",
    "### How many generations (gen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 25\n",
    "m=10\n",
    "e=5\n",
    "g=m-e\n",
    "n2=4\n",
    "n1=2\n",
    "gen=150"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Now we run the program and it will return at the end the best bee of the last generation, the board with the sensors, the locations and the evaluation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Final Best Score and Coordinates of the sensors\n",
      "[-9] [[[1, 2], [3, 3], [0, 0], [4, 0]]]\n",
      "Final: Best State\n",
      "3  3  3  #  -  #  \n",
      "3  #  #  2  1  -  \n",
      "#  #  1  1  #  -  \n",
      "3  1  1  1  1  -  \n",
      "#  #  #  1  2  -  \n",
      "-  -  -  -  #  #  \n"
     ]
    }
   ],
   "source": [
    "init_bees = rand_bees(n)\n",
    "for i in range(gen):\n",
    "    ev = eval_bees(init_grid, sensors_range, init_bees)\n",
    "    sites, sel_bees = selec_bees(m, ev, init_bees)  \n",
    "    sitese, elit_bees = selec_bees(e, ev, init_bees)  \n",
    "    other_bees = good_bees(g, sites, sel_bees) \n",
    "    neig_elit = neig_elite(e, n2, elit_bees, sensors_range)\n",
    "    neigh_good = neig_good(g, n1, other_bees, sensors_range)\n",
    "    ev_e = eval_bees(init_grid, sensors_range, neig_elit)\n",
    "    ev_g = eval_bees(init_grid, sensors_range, neigh_good)\n",
    "    sitese, elit_best = selec_bees(e, ev_e, neig_elit) \n",
    "    sitese, good_best = selec_bees(g, ev_g, neigh_good)\n",
    "    new_bees = rand_bees(n-m)\n",
    "    new_scout = new_scouts(new_bees, elit_best, good_best)\n",
    "    init_bees=new_scout\n",
    "\n",
    "ev_s = eval_bees(init_grid, sensors_range, new_scout)\n",
    "best_bee(init_grid, ev_s, new_scout, sensors_range)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: We did not put a restriction for sensors being on top of each other, so there can be more than one in the same place, but we hope the algorithm finds out the best configuration."
   ]
  },
  {
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}