Genetic_Algorithm_Python_Example/Knapsack_problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Knapsack Problem solved using genetic algorithms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports \n",
    "import numpy as np\n",
    "import random\n",
    "\n",
    "from datetime import datetime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Parameters\n",
    "n_objects = 20\n",
    "max_weight = 3\n",
    "\n",
    "n_population = 100\n",
    "\n",
    "mutation_rate = 0.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Water': [0.8, 74],\n",
       " 'Food': [0.2, 26],\n",
       " 'Pants': [0.7, 74],\n",
       " 'Socks': [0.6, 53],\n",
       " 'Boots': [0.1, 4],\n",
       " 'Shirts': [0.6, 5],\n",
       " 'Coat': [0.9, 87],\n",
       " 'Blanket': [0.9, 20],\n",
       " 'Laptop': [0.4, 68],\n",
       " 'TV': [0.9, 92],\n",
       " 'Cellphone': [0.1, 82],\n",
       " 'Book': [0.6, 20],\n",
       " 'Gloves': [0.5, 2],\n",
       " 'Towel': [0.4, 95],\n",
       " 'Sunscream': [0.4, 66],\n",
       " 'Glasses': [0.5, 74],\n",
       " 'Fork': [0.7, 73],\n",
       " 'Knife': [0.5, 21],\n",
       " 'Matches': [0.5, 64],\n",
       " 'Chair': [0.3, 98]}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Generating a list of coordenades representing each city\n",
    "weight_value = [[x,y] for x,y in zip(np.random.randint(0,10,n_objects)/10,np.random.randint(0,100,n_objects))]\n",
    "object_list = np.array(['Water', 'Food', 'Pants', 'Socks', 'Boots', 'Shirts', 'Coat', 'Blanket', 'Laptop', 'TV', 'Cellphone', 'Book', 'Gloves', 'Towel', 'Sunscream', 'Glasses', 'Fork', 'Knife', 'Matches', 'Chair'])\n",
    "objects_dict = { x:y for x,y in zip(object_list,weight_value)}\n",
    "\n",
    "def get_current_weight_value(objects_list, objects_dict):\n",
    "    weight = 0\n",
    "    value = 0\n",
    "    for o in objects_list:\n",
    "        o = objects_dict[o]\n",
    "        weight += o[0]\n",
    "        value += o[1]\n",
    "    return weight, value\n",
    "        \n",
    "\n",
    "def fit_in_knapsack(objects_list, max_weight, objects_dict):\n",
    "    r = []\n",
    "    for o in objects_list:\n",
    "        r.append(o)\n",
    "        weight, value = get_current_weight_value(r, objects_dict)\n",
    "        if weight > max_weight:\n",
    "            r.pop()\n",
    "            return r\n",
    "    return r\n",
    "    \n",
    "objects_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Create the first population set\n",
    "We randomly shuffle the cities N times where N=population_size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "<ipython-input-4-c2eed31ea718>:20: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray\n",
      "  return np.array(population_set)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([list(['Chair', 'Fork', 'Shirts', 'Boots', 'Cellphone', 'Food', 'Laptop', 'Sunscream']),\n",
       "       list(['Boots', 'Socks', 'Food', 'Shirts', 'Sunscream', 'Water', 'Chair']),\n",
       "       list(['Book', 'Socks', 'Coat', 'Matches', 'Laptop']),\n",
       "       list(['Shirts', 'Pants', 'Blanket', 'Boots', 'Food']),\n",
       "       list(['Sunscream', 'Towel', 'Coat', 'Cellphone', 'TV']),\n",
       "       list(['Coat', 'Food', 'Blanket', 'TV', 'Cellphone']),\n",
       "       list(['Chair', 'Socks', 'Laptop', 'TV', 'Gloves']),\n",
       "       list(['Matches', 'Blanket', 'Towel', 'TV']),\n",
       "       list(['Shirts', 'Chair', 'Boots', 'Laptop', 'Book', 'Matches']),\n",
       "       list(['Socks', 'Glasses', 'Matches', 'Coat', 'Sunscream']),\n",
       "       list(['Towel', 'Chair', 'Socks', 'Blanket', 'Gloves']),\n",
       "       list(['Gloves', 'TV', 'Knife', 'Sunscream']),\n",
       "       list(['Boots', 'Sunscream', 'Coat', 'Towel', 'TV']),\n",
       "       list(['Boots', 'Cellphone', 'Chair', 'Towel', 'TV', 'Gloves', 'Book']),\n",
       "       list(['Coat', 'Glasses', 'Laptop', 'Cellphone', 'Boots', 'Socks']),\n",
       "       list(['Pants', 'TV', 'Cellphone', 'Matches', 'Towel']),\n",
       "       list(['Glasses', 'Boots', 'Book', 'Towel', 'Chair', 'Cellphone', 'Sunscream', 'Gloves']),\n",
       "       list(['Chair', 'Matches', 'Glasses', 'Knife', 'Book']),\n",
       "       list(['Fork', 'Shirts', 'Blanket', 'Cellphone', 'Book']),\n",
       "       list(['Book', 'Water', 'Matches', 'Knife', 'Boots', 'Laptop']),\n",
       "       list(['Knife', 'Laptop', 'Blanket', 'Socks', 'Shirts']),\n",
       "       list(['Pants', 'Boots', 'TV', 'Sunscream', 'Socks']),\n",
       "       list(['Shirts', 'Chair', 'Matches', 'Sunscream', 'Knife']),\n",
       "       list(['Cellphone', 'Fork', 'TV', 'Gloves', 'Matches']),\n",
       "       list(['Towel', 'Knife', 'Blanket', 'TV']),\n",
       "       list(['Knife', 'TV', 'Fork', 'Blanket']),\n",
       "       list(['Boots', 'Food', 'Matches', 'Gloves', 'Shirts', 'Towel']),\n",
       "       list(['Book', 'Socks', 'Boots', 'Fork', 'Gloves']),\n",
       "       list(['TV', 'Laptop', 'Cellphone', 'Gloves', 'Chair', 'Socks']),\n",
       "       list(['Water', 'Food', 'Book', 'Socks', 'Gloves']),\n",
       "       list(['Gloves', 'Coat', 'TV', 'Book']),\n",
       "       list(['Matches', 'Socks', 'Glasses', 'Book', 'Knife', 'Boots']),\n",
       "       list(['Laptop', 'Cellphone', 'Coat', 'Towel', 'Shirts', 'Boots']),\n",
       "       list(['Pants', 'Food', 'Book', 'Coat', 'Shirts']),\n",
       "       list(['Book', 'Chair', 'Knife', 'Water', 'Gloves', 'Cellphone']),\n",
       "       list(['Shirts', 'Water', 'Knife', 'Matches', 'Gloves']),\n",
       "       list(['Chair', 'Book', 'Coat', 'Fork', 'Cellphone']),\n",
       "       list(['Shirts', 'Cellphone', 'Sunscream', 'Book', 'Fork', 'Towel']),\n",
       "       list(['Socks', 'Gloves', 'Knife', 'TV']),\n",
       "       list(['TV', 'Book', 'Cellphone', 'Glasses', 'Coat']),\n",
       "       list(['Knife', 'Gloves', 'Socks', 'Laptop', 'Cellphone', 'Water']),\n",
       "       list(['TV', 'Cellphone', 'Pants', 'Matches', 'Boots', 'Book']),\n",
       "       list(['Towel', 'Pants', 'Coat', 'Boots', 'Glasses', 'Sunscream']),\n",
       "       list(['Gloves', 'Pants', 'Sunscream', 'Matches', 'Glasses']),\n",
       "       list(['Boots', 'Chair', 'Coat', 'Water', 'Glasses']),\n",
       "       list(['Food', 'Glasses', 'Pants', 'Fork', 'Gloves', 'Laptop']),\n",
       "       list(['Laptop', 'Knife', 'Book', 'Fork']),\n",
       "       list(['Gloves', 'Food', 'Boots', 'TV', 'Pants', 'Shirts']),\n",
       "       list(['Blanket', 'Glasses', 'Shirts', 'TV']),\n",
       "       list(['Coat', 'Boots', 'Pants', 'Water', 'Knife']),\n",
       "       list(['Knife', 'Coat', 'Water', 'Towel']),\n",
       "       list(['Socks', 'Shirts', 'Knife', 'Boots', 'TV']),\n",
       "       list(['Food', 'Book', 'Blanket', 'Socks', 'Sunscream']),\n",
       "       list(['Towel', 'Blanket', 'Socks', 'Cellphone', 'Fork', 'Chair']),\n",
       "       list(['Glasses', 'Book', 'Boots', 'Water', 'TV', 'Cellphone']),\n",
       "       list(['Towel', 'Pants', 'Food', 'Shirts', 'Sunscream', 'Fork']),\n",
       "       list(['Knife', 'Socks', 'Blanket', 'Food']),\n",
       "       list(['Blanket', 'Pants', 'TV', 'Towel']),\n",
       "       list(['Shirts', 'Matches', 'Boots', 'Food', 'TV', 'Chair']),\n",
       "       list(['Matches', 'Cellphone', 'Coat', 'Water', 'Pants']),\n",
       "       list(['Boots', 'Matches', 'Cellphone', 'Blanket', 'Towel', 'TV']),\n",
       "       list(['Matches', 'Fork', 'Food', 'Gloves', 'Boots', 'TV']),\n",
       "       list(['Matches', 'Coat', 'Water', 'Boots', 'Gloves']),\n",
       "       list(['Cellphone', 'Water', 'Fork', 'Pants', 'Gloves']),\n",
       "       list(['Cellphone', 'Chair', 'Glasses', 'TV', 'Boots', 'Shirts', 'Laptop']),\n",
       "       list(['Water', 'Towel', 'Food', 'Cellphone', 'Laptop', 'Book']),\n",
       "       list(['Fork', 'Pants', 'TV', 'Gloves']),\n",
       "       list(['Coat', 'Matches', 'Glasses', 'Fork', 'Chair']),\n",
       "       list(['Socks', 'Coat', 'Laptop', 'Towel', 'Shirts']),\n",
       "       list(['Cellphone', 'Boots', 'Fork', 'Sunscream', 'Knife', 'Pants', 'Matches']),\n",
       "       list(['Laptop', 'Gloves', 'Water', 'Sunscream', 'Blanket']),\n",
       "       list(['TV', 'Cellphone', 'Sunscream', 'Coat', 'Knife']),\n",
       "       list(['Food', 'Shirts', 'Fork', 'Sunscream', 'Book', 'Knife']),\n",
       "       list(['Coat', 'Book', 'Glasses', 'Blanket']),\n",
       "       list(['Boots', 'Book', 'Pants', 'Sunscream', 'Socks', 'Chair']),\n",
       "       list(['Towel', 'Food', 'Coat', 'Water', 'Boots', 'Sunscream']),\n",
       "       list(['Food', 'Cellphone', 'Socks', 'Towel', 'Chair', 'Matches', 'Blanket']),\n",
       "       list(['Pants', 'Glasses', 'Cellphone', 'Boots', 'Sunscream', 'TV']),\n",
       "       list(['Knife', 'TV', 'Sunscream', 'Book', 'Chair']),\n",
       "       list(['Glasses', 'Fork', 'Socks', 'Boots', 'Water']),\n",
       "       list(['Glasses', 'Pants', 'Socks', 'Blanket']),\n",
       "       list(['Book', 'Knife', 'Cellphone', 'Water', 'Gloves']),\n",
       "       list(['Glasses', 'Book', 'Boots', 'Coat', 'Gloves']),\n",
       "       list(['Knife', 'Towel', 'Laptop', 'Glasses', 'Chair', 'Water']),\n",
       "       list(['Matches', 'Laptop', 'Cellphone', 'Sunscream', 'Towel', 'Fork']),\n",
       "       list(['Chair', 'Socks', 'Book', 'Sunscream', 'Fork']),\n",
       "       list(['Matches', 'Laptop', 'Coat', 'Towel']),\n",
       "       list(['Pants', 'Knife', 'Socks', 'Gloves', 'Matches']),\n",
       "       list(['Cellphone', 'Fork', 'Shirts', 'Blanket', 'Pants']),\n",
       "       list(['Blanket', 'TV', 'Water']),\n",
       "       list(['Knife', 'Boots', 'Fork', 'TV', 'Food', 'Cellphone']),\n",
       "       list(['Towel', 'Pants', 'TV', 'Glasses']),\n",
       "       list(['Laptop', 'Coat', 'Boots', 'Book', 'Glasses']),\n",
       "       list(['Laptop', 'TV', 'Chair', 'Shirts', 'Gloves']),\n",
       "       list(['Boots', 'TV', 'Pants', 'Fork', 'Gloves']),\n",
       "       list(['Sunscream', 'Fork', 'Socks', 'Matches']),\n",
       "       list(['Pants', 'TV', 'Matches', 'Fork', 'Cellphone']),\n",
       "       list(['Socks', 'Blanket', 'Boots', 'Cellphone', 'Food', 'Gloves', 'Knife']),\n",
       "       list(['Chair', 'Cellphone', 'Food', 'Glasses', 'Shirts', 'Coat', 'Boots']),\n",
       "       list(['Laptop', 'Towel', 'Boots', 'Cellphone', 'Socks', 'Food', 'Gloves', 'Matches'])],\n",
       "      dtype=object)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# First step: Create the first population set\n",
    "def fit_in_knapsack(objects_list, max_weight, objects_dict):\n",
    "    r = []\n",
    "    for o in objects_list:\n",
    "        r.append(o)\n",
    "        weight, value = get_current_weight_value(r, objects_dict)\n",
    "        if weight > max_weight:\n",
    "            r.pop()\n",
    "            return r\n",
    "    return r\n",
    "\n",
    "def genesis(object_list, n_population, max_weight, objects_dict):\n",
    "\n",
    "    population_set = []\n",
    "    for i in range(n_population):\n",
    "        #Randomly generating a new solution\n",
    "        sol_i = object_list[np.random.choice(list(range(n_objects)), n_objects, replace=False)]\n",
    "        sol_i = fit_in_knapsack(sol_i, max_weight, objects_dict)\n",
    "        population_set.append(sol_i)\n",
    "    return np.array(population_set)\n",
    "\n",
    "population_set = genesis(object_list, n_population, max_weight, objects_dict)\n",
    "population_set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Evaluate solutions fitness\n",
    "The solutions are defined so that the first element on the list is the first city to visit, then the second, etc. and the last city is linked to the first.\n",
    "The fitness function needs to compute the distance between subsequent cities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([422., 326., 292., 129., 422., 307., 313., 271., 259., 344., 268.,\n",
       "       181., 344., 393., 368., 407., 441., 277., 200., 251., 167., 289.,\n",
       "       254., 313., 228., 206., 196., 152., 395., 175., 201., 236., 341.,\n",
       "       212., 297., 166., 360., 341., 168., 355., 300., 336., 400., 280.,\n",
       "       337., 317., 182., 203., 191., 260., 277., 175., 185., 421., 346.,\n",
       "       339., 120., 281., 289., 381., 357., 261., 231., 305., 423., 365.,\n",
       "       241., 396., 308., 384., 230., 348., 211., 201., 315., 352., 438.,\n",
       "       392., 297., 278., 221., 199., 187., 430., 448., 310., 314., 214.,\n",
       "       254., 186., 298., 335., 253., 265., 245., 256., 385., 208., 376.,\n",
       "       394.])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def get_all_fitnes(population_set, objects_dict):\n",
    "    fitnes_list = np.zeros(n_population)\n",
    "\n",
    "    #Looping over all solutions computing the fitness for each solution\n",
    "    for i in  range(n_population):\n",
    "        _, fitnes_list[i] = get_current_weight_value(population_set[i], objects_dict)\n",
    "\n",
    "    return fitnes_list\n",
    "\n",
    "fitnes_list = get_all_fitnes(population_set,objects_dict)\n",
    "fitnes_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Progenitors selection\n",
    "I will select a new set of progenitors using the Roulette Wheel Selection. Generates a list of progenitor pairs where N= len(population_set) but at each position there are two solutions to merge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Shirts', 'Cellphone', 'Sunscream', 'Book', 'Fork', 'Towel']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def progenitor_selection(population_set,fitnes_list):\n",
    "    total_fit = fitnes_list.sum()\n",
    "    prob_list = fitnes_list/total_fit\n",
    "    \n",
    "    #Notice there is the chance that a progenitor. mates with oneself\n",
    "    progenitor_list_a = np.random.choice(list(range(len(population_set))), len(population_set),p=prob_list, replace=True)\n",
    "    progenitor_list_b = np.random.choice(list(range(len(population_set))), len(population_set),p=prob_list, replace=True)\n",
    "    \n",
    "    progenitor_list_a = population_set[progenitor_list_a]\n",
    "    progenitor_list_b = population_set[progenitor_list_b]\n",
    "    \n",
    "    \n",
    "    return np.array([progenitor_list_a,progenitor_list_b])\n",
    "\n",
    "\n",
    "progenitor_list = progenitor_selection(population_set,fitnes_list)\n",
    "progenitor_list[0][2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Mating\n",
    "For each pair of  parents we'll generate an offspring pair. Since we cannot repeat cities what we'll do is copy a random chunk from one progenitor and fill the blanks with the other progenitor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Shirts', 'Matches', 'Cellphone', 'Boots', 'Coat', 'Food']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mate_progenitors(prog_a, prog_b, max_weight, objects_dict):\n",
    "    offspring = []\n",
    "\n",
    "    for i in zip(prog_a, prog_b):\n",
    "        offspring.extend(i)\n",
    "        offspring = list(dict.fromkeys(offspring)) #Removing duplicates\n",
    "        offspring = fit_in_knapsack(offspring, max_weight, objects_dict)\n",
    "\n",
    "    return offspring\n",
    "            \n",
    "    \n",
    "    \n",
    "def mate_population(progenitor_list, max_weight, objects_dict):\n",
    "    new_population_set = []\n",
    "    for i in range(progenitor_list.shape[1]):\n",
    "        prog_a, prog_b = progenitor_list[0][i], progenitor_list[1][i]\n",
    "        offspring = mate_progenitors(prog_a, prog_b, max_weight, objects_dict)\n",
    "        new_population_set.append(offspring)\n",
    "        \n",
    "    return new_population_set\n",
    "\n",
    "new_population_set = mate_population(progenitor_list, max_weight, objects_dict)\n",
    "new_population_set[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5. Mutation\n",
    "Now for each element of the new population we add a random chance of swapping"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Shirts', 'Matches', 'Matches', 'Cellphone', 'Boots', 'Coat', 'Food']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def mutate_offspring(offspring, max_weight, object_list, objects_dict):\n",
    "    for mutation_number in range(int(len(offspring)*mutation_rate)):\n",
    "    \n",
    "        a = np.random.randint(0,len(object_list))\n",
    "        b = np.random.randint(0,len(offspring))\n",
    "        \n",
    "        offspring.insert(b, object_list[a])\n",
    "        \n",
    "    offspring = fit_in_knapsack(offspring, max_weight, objects_dict)\n",
    "\n",
    "    return offspring\n",
    "    \n",
    "    \n",
    "def mutate_population(new_population_set, max_weight, object_list, objects_dict):\n",
    "    mutated_pop = []\n",
    "    for offspring in new_population_set:\n",
    "        mutated_pop.append(mutate_offspring(offspring, max_weight, object_list, objects_dict))\n",
    "    return mutated_pop\n",
    "\n",
    "mutated_pop = mutate_population(new_population_set, max_weight,object_list, objects_dict)\n",
    "mutated_pop[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6. Stopping\n",
    "To select the stopping criteria we'll need to create a loop to stop first. Then I'll set it to loop at 1000 iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "<ipython-input-9-ecc831523e1e>:10: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray\n",
      "  best_solution[2] = np.array(mutated_pop)[fitnes_list.max() == fitnes_list]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 120.0 289.98 31/01/21 17:50\n",
      "100 45.0 297.33 31/01/21 17:50\n",
      "200 149.0 304.4 31/01/21 17:50\n",
      "300 129.0 299.13 31/01/21 17:50\n",
      "400 138.0 317.4 31/01/21 17:50\n",
      "500 120.0 302.45 31/01/21 17:50\n",
      "600 104.0 301.38 31/01/21 17:50\n",
      "700 127.0 289.58 31/01/21 17:50\n",
      "800 103.0 305.04 31/01/21 17:50\n",
      "900 128.0 286.38 31/01/21 17:50\n",
      "1000 109.0 297.71 31/01/21 17:50\n",
      "1100 116.0 299.9 31/01/21 17:50\n",
      "1200 96.0 274.86 31/01/21 17:50\n",
      "1300 149.0 304.01 31/01/21 17:50\n",
      "1400 45.0 301.04 31/01/21 17:50\n",
      "1500 104.0 299.22 31/01/21 17:50\n",
      "1600 118.0 292.28 31/01/21 17:50\n",
      "1700 107.0 308.96 31/01/21 17:50\n",
      "1800 95.0 295.73 31/01/21 17:50\n",
      "1900 80.0 287.92 31/01/21 17:50\n",
      "2000 128.0 295.17 31/01/21 17:50\n",
      "2100 117.0 291.29 31/01/21 17:50\n",
      "2200 124.0 285.52 31/01/21 17:50\n",
      "2300 112.0 301.12 31/01/21 17:50\n",
      "2400 114.0 280.87 31/01/21 17:50\n",
      "2500 89.0 298.91 31/01/21 17:50\n",
      "2600 168.0 305.25 31/01/21 17:50\n",
      "2700 149.0 320.69 31/01/21 17:50\n",
      "2800 120.0 284.59 31/01/21 17:50\n",
      "2900 118.0 297.26 31/01/21 17:50\n",
      "3000 98.0 304.4 31/01/21 17:50\n",
      "3100 131.0 305.03 31/01/21 17:50\n",
      "3200 150.0 300.95 31/01/21 17:50\n",
      "3300 65.0 296.41 31/01/21 17:51\n",
      "3400 102.0 304.86 31/01/21 17:51\n",
      "3500 130.0 293.65 31/01/21 17:51\n",
      "3600 106.0 297.67 31/01/21 17:51\n",
      "3700 142.0 304.47 31/01/21 17:51\n",
      "3800 98.0 292.23 31/01/21 17:51\n",
      "3900 134.0 302.91 31/01/21 17:51\n",
      "4000 148.0 296.8 31/01/21 17:51\n",
      "4100 132.0 297.04 31/01/21 17:51\n",
      "4200 103.0 289.02 31/01/21 17:51\n",
      "4300 104.0 283.13 31/01/21 17:51\n",
      "4400 93.0 289.79 31/01/21 17:51\n",
      "4500 129.0 296.62 31/01/21 17:51\n",
      "4600 102.0 303.6 31/01/21 17:51\n",
      "4700 150.0 299.08 31/01/21 17:51\n",
      "4800 107.0 292.24 31/01/21 17:51\n",
      "4900 147.0 296.91 31/01/21 17:51\n",
      "5000 83.0 290.47 31/01/21 17:51\n",
      "5100 98.0 292.51 31/01/21 17:51\n",
      "5200 98.0 293.97 31/01/21 17:51\n",
      "5300 147.0 294.39 31/01/21 17:51\n",
      "5400 114.0 289.81 31/01/21 17:51\n",
      "5500 117.0 336.15 31/01/21 17:51\n",
      "5600 117.0 318.57 31/01/21 17:51\n",
      "5700 95.0 294.5 31/01/21 17:51\n",
      "5800 113.0 291.76 31/01/21 17:51\n",
      "5900 130.0 294.77 31/01/21 17:51\n",
      "6000 116.0 312.56 31/01/21 17:51\n",
      "6100 102.0 300.14 31/01/21 17:51\n",
      "6200 99.0 290.65 31/01/21 17:51\n",
      "6300 72.0 287.0 31/01/21 17:51\n",
      "6400 122.0 293.79 31/01/21 17:51\n",
      "6500 91.0 287.22 31/01/21 17:51\n",
      "6600 95.0 295.4 31/01/21 17:51\n",
      "6700 104.0 297.06 31/01/21 17:51\n",
      "6800 133.0 299.42 31/01/21 17:51\n",
      "6900 119.0 295.15 31/01/21 17:51\n",
      "7000 128.0 296.79 31/01/21 17:51\n",
      "7100 125.0 302.79 31/01/21 17:51\n",
      "7200 100.0 301.51 31/01/21 17:51\n",
      "7300 85.0 296.04 31/01/21 17:51\n",
      "7400 144.0 292.58 31/01/21 17:51\n",
      "7500 146.0 297.05 31/01/21 17:51\n",
      "7600 123.0 291.77 31/01/21 17:51\n",
      "7700 163.0 304.69 31/01/21 17:51\n",
      "7800 112.0 287.57 31/01/21 17:51\n",
      "7900 96.0 299.77 31/01/21 17:51\n",
      "8000 119.0 280.19 31/01/21 17:51\n",
      "8100 152.0 287.89 31/01/21 17:51\n",
      "8200 86.0 311.6 31/01/21 17:51\n",
      "8300 98.0 284.22 31/01/21 17:51\n",
      "8400 86.0 309.03 31/01/21 17:51\n",
      "8500 141.0 306.25 31/01/21 17:51\n",
      "8600 82.0 291.64 31/01/21 17:51\n",
      "8700 117.0 294.77 31/01/21 17:51\n",
      "8800 120.0 319.43 31/01/21 17:51\n",
      "8900 117.0 299.55 31/01/21 17:51\n",
      "9000 149.0 291.36 31/01/21 17:51\n",
      "9100 123.0 305.85 31/01/21 17:51\n",
      "9200 127.0 307.98 31/01/21 17:51\n",
      "9300 109.0 305.85 31/01/21 17:51\n",
      "9400 140.0 303.75 31/01/21 17:51\n",
      "9500 99.0 295.08 31/01/21 17:51\n",
      "9600 96.0 276.41 31/01/21 17:51\n",
      "9700 130.0 306.99 31/01/21 17:51\n",
      "9800 134.0 295.29 31/01/21 17:51\n",
      "9900 95.0 299.2 31/01/21 17:51\n"
     ]
    }
   ],
   "source": [
    "best_solution = [-1,-np.inf,np.array([])]\n",
    "for i in range(10000):\n",
    "    if i%100==0: print(i, fitnes_list.min(), fitnes_list.mean(), datetime.now().strftime(\"%d/%m/%y %H:%M\"))\n",
    "    fitnes_list = get_all_fitnes(mutated_pop,objects_dict)\n",
    "    \n",
    "    #Saving the best solution\n",
    "    if fitnes_list.max() > best_solution[1]:\n",
    "        best_solution[0] = i\n",
    "        best_solution[1] = fitnes_list.max()\n",
    "        best_solution[2] = np.array(mutated_pop)[fitnes_list.max() == fitnes_list]\n",
    "    \n",
    "    progenitor_list = progenitor_selection(population_set,fitnes_list)\n",
    "    new_population_set = mate_population(progenitor_list, max_weight, objects_dict)\n",
    "    \n",
    "    mutated_pop = mutate_population(new_population_set, max_weight,object_list, objects_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2.9000000000000004, 715)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_current_weight_value(best_solution[2][0], objects_dict)"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}