Parallel Genetic Algorithm Using PySpark for Knapsack Problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parallel Genetic Algorithm Using PySpark for Knapsack Problem    \n",
    "    Author: Furkan Cantürk\n",
    "    Date: 15.01.2021"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyspark import SparkContext, SparkConf, SQLContext\n",
    "from pyspark.sql import SparkSession, Row\n",
    "from pyspark.sql.functions import udf\n",
    "from pyspark.sql import functions as F\n",
    "import os\n",
    "from pyspark.sql.types import *\n",
    "from sklearn.preprocessing import MinMaxScaler\n",
    "import csv\n",
    "import pyspark\n",
    "import matplotlib.pyplot as plt\n",
    "import pickle\n",
    "import random\n",
    "import pandas as pd\n",
    "from time import time, sleep\n",
    "import numpy as np\n",
    "from copy import deepcopy\n",
    "np.random.seed(1)\n",
    "random.seed(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Knapsack Instance Generation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of items: 1000\n",
      "Total knapsack capacity: 303414\n",
      "10 505.69 1000\n",
      "0 253.558 930\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEWCAYAAACJ0YulAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAABWuklEQVR4nO29fZgc1XXn/z3TU5J6hK0ZxcJBA0LYwdKixZLQ2JCQFwu8KLF4USxAZk1CEufxk98mcSSTiUWsGGmDg3YVG5L1ZvfxOontgPGIF48FJCtsgxOvbMASMxNFNkoAgURDjGxpsJFaUk/P+f1RdXuqq++9dau6qqdn5nyeR49mquvlVtX0OfeeV2JmCIIgCAIAdEz2AARBEIT2QZSCIAiCUEOUgiAIglBDlIIgCIJQQ5SCIAiCUEOUgiAIglBDlILQNhDR/yaiP8noXIuI6A0iKgS/f5OIfjuLcwfn+wciuiWr8yW47h1E9EMi+vdWX1uYGYhSEFoCEb1IRGUi+gkRjRLRt4nod4io9jfIzL/DzH/qeK732vZh5sPMfBYzVzMY+1Yiuidy/l9h5i80e+6E4zgPwK0ALmLmn9Z8/h4iejn0e6aKUJgZiFIQWsk1zPwmAOcD2A7gYwD+OuuLEFFn1udsE84H8CNmfm2yByJMX0QpCC2HmV9n5l0ANgC4hYj+IwAQ0eeJ6I7g57cQ0SPBquIYEX2LiDqI6O8ALALwcGAe+iMiWkxETEQfIqLDAB4PbQsriLcT0dNE9DoRfZWI5gfXqpthB9teJKL3EtEvA/hjABuC640En9dm4cG4thDRS0T0GhF9kYjmBZ+pcdxCRIcD08/HTc+GiOYFxx8NzrclOP97AXwNwMJgHJ+3PWMi+iSAXwDwmWD/zwTblxLR14JnepCIbgwd83ki+qvANPYGEe0hop8moruJ6DgRPUtEK0P7f4yISsHq7yARXWkbkzA1EKUgTBrM/DSAl+ELryi3Bp8tAPBW+IKZmfnXAByGv+o4i5n/e+iYXwLwHwCsMVzy1wH8FoCFAMYA/KXDGP8vgD8DMBBcb7lmt98I/q0G8DYAZwH4TGSfnwewBMCVAD5BRP/BcMn/AWBecJ5fCsb8m8z8dQC/AuCVYBy/ETPujwP4FoDfC/b/PSKaC1+xfAnA2QBuAvBXRLQsdOiNALYAeAuA0wC+A+CZ4PcHAHwaAIhoCYDfA/CuYPW3BsCLtjEJUwNRCsJk8wqA+ZrtFQDnADifmSvM/C2OL9S1lZlPMHPZ8PnfMfO/MPMJAH8C4EbliG6SDwL4NDO/wMxvALgNwAciq5RtzFxm5hEAIwAalEswlg0AbmPmnzDziwA+BeDXMhgjAFwN4EVm/ltmHmPmZwA8COD60D5fYeZ9zHwKwFcAnGLmLwa+mQEAaqVQBTAbwEVE5DHzi8z8fEbjFCYRUQrCZNML4Jhm+w4AzwF4jIheIKLNDuc6kuDzlwB48GfAzbIwOF/43J3wVziKcLTQSfiriShvATBLc67eDMYI+D6JSwOT3CgRjcJXaGGn9Q9CP5c1v58FAMz8HICNALYCeI2IvkxECzMapzCJiFIQJg0iehd8gff/op8FM+VbmfltAK4B8NGQzdq0YohbSZwX+nkR/NXIDwGcANAVGlcBvtnK9byvwBe44XOPoV6guvDDYEzRc5USnkcRHfcRAP/IzN2hf2cx8/+X6uTMX2Lmnw/GywD+W8pxCm2EKAWh5RDRm4noagBfBnAPM+/X7HM1Ef0MERGAH8M3V6jw0h/At7kn5WYiuoiIugD8VwAPBGaRfwUwh4jWEpEH36Y+O3TcDwAsDofPRrgPwCYiuoCIzsKED2IsyeCCsewE8EkiehMRnQ/gowDusR9pJPqcHgHwDiL6NSLygn/vsvg3jBDREiK6gohmAzgFfxXRdPivMPmIUhBaycNE9BP4M9aPw3da/qZh3wsBfB3AG/CdnX/FzN8MPrsTwJbABPKHCa7/dwA+D9+UMwfARwA/GgrAfwHwOfiz8hPwndyK+4P/f0REz2jO+zfBuf8JwCH4QvL3E4wrzO8H138B/grqS8H50/AXAK4PIof+kpl/AuAqAB+Av7r5d/iz+9mWc5iYDT+s+IfBec6GHwwgTHFImuwIgiAIClkpCIIgCDVEKQiCIAg1RCkIgiAINUQpCIIgCDWmdOGwt7zlLbx48eLJHoYgCMKUYt++fT9k5gW6z6a0Uli8eDH27t072cMQBEGYUhDRS6bPxHwkCIIg1BClIAiCINQQpSAIgiDUEKUgCIIg1BClIAiCINSY0tFHgiAI043BoRJ27D6IV0bLWNhdRP+aJVi3stf582YRpSAIgtAmDA6VcNtD+1Gu+FXIS6Nl3PaQX1l+3cre2M+zQMxHgiAIbcKO3QdrAl9RrlSxY/dBp8+zQJSCIAhCm/DKqL69uNoe93kWiFIQBEFoExZ2F63b4z7PAlEKgiAIbUL/miUoeoW6bUWvgP41S5w+zwJxNAuCILQJyllsii6K+zwLpnQ7zr6+PpaCeIIgtDt5h5EmhYj2MXOf7jNZKQiCIORIK8JIs0SUgiAIQo7YwkhNSmEyVxaiFARBEFLgKriThpFO9spCoo8EQRASogR3abQMxoTgHhwqNeybNIy0FQlqNkQpCIIgJMRFcA8OlXD59sdR0qwIbGGkrUhQsyHmI0EQBA0285BO0AMTgjtqAgpDANav6jWaghZ2F7XnzzJBzYYoBUEQhAg2uz7gC3ZdML8S3LqVhIIBPPHsUeO1+9csaVAoWSeo2RClIAiCECHOPKRTCATUBHecqcf2eSsS1GyIUhAEQYiQxq7PmBDoJhOQYl7Rs15/3UqzeSlvxNEsCIIQwRYxZPqsN7RdV6MozIkzY9pIJYVyUl+w+VFcvv1x675ZI0pBEAQhgq3wnEtRunUre3Hn+y+uUxRhKlU2hpjqwl03DgxjxbbHWqIcxHwkCIIQwcWub/osGrVkwmSKMjmpR8uVliSxiVIQBEHQYLPrmz7TRS3FRSpFsfkt4spjZIEoBUEQhBhcS1pse/hAwyyf0RjCagsxjXNS553EJkpBEAQhRFQBrF66AA/uK8XWIhocKuH4yYr2nAzfEe0SYqrLUwiTdxKbKAVBEIQAnfnn3icPN5h/dGYcW22i3u4i9my+wmkM6pzbHj7QoGRakcQmSkEQBCFA5+Q1tSErjZZx+fbHa7N/m8knqSBXPovJKKEtSkEQBCEgib2eMFEDyeZQ7i56qQX5ZCSxiVIQBEEIiJvxh4kqAJNDeeu1y5yv3w5tO0UpCIIgBMQ5eeNg+CuD0bLvC5jj6fODdcIfQFu07cxVKRDRJgC/Df9Z7QfwmwC6AAwAWAzgRQA3MvPxYP/bAHwIQBXAR5h5d57jEwRBCBNOWnNdMYTp6fJwqjJe+/34yfqEs8GhErbuOlBTGsCE8J/jdSRu25kHuSkFIuoF8BEAFzFzmYh2AvgAgIsAfIOZtxPRZgCbAXyMiC4KPl8GYCGArxPRO5g5ncoWBEGAm0lG7VMaLaNAhCpz3Yw/SnfRw+mx8Yby1sywVlc1rULKlapxddKq5jqKvM1HnQCKRFSBv0J4BcBtAN4TfP4FAN8E8DEA1wH4MjOfBnCIiJ4D8G4A38l5jIIgTDPCQj5s59eZZLYM7q8LO62y/9NouYIOAOOoJ+wniCqbTQPD2vG8Mlq29liw0armOorclAIzl4jozwEcBlAG8BgzP0ZEb2XmV4N9XiWis4NDegE8GTrFy8G2OojowwA+DACLFi3Ka/iCIExRorkGuhyDW3eOYNPAMLq7PGPCGeArhO6ih7mzO7UrjeiKw2R2WhgkrtnQrT4IwOqlC6zHZU1uVVKJqAf+7P8C+OaguUR0s+0QzbaGCC9m/iwz9zFz34IFrX1YgiC0Py4z8iozGLAqBMXr5Qr2bL4Ch7avxZ7NV1jt+7YKqrYZv1p9rF/VWycIGcCD+0rTpnT2ewEcYuajzFwB8BCAnwPwAyI6BwCC/18L9n8ZwHmh48+Fb24SBEFwJmsbfBLzTbhkNsHPZL7z/Rdj3cpeY4+Fni6vts8Tzx41Zk+3ijx9CocBXEZEXfDNR1cC2AvgBIBbAGwP/v9qsP8uAF8iok/DX1lcCODpHMcnCMI0IOpInmdxECdFV1YiGkHU0+Xh9muW1ZmUojWRVObzvKKHOV4HRk9WtE7vNB3fsiZPn8JTRPQAgGcAjAEYAvBZAGcB2ElEH4KvOG4I9j8QRCh9L9j/dyXySBAEHTZHslcgeB2EyvjEnFvtoyKLXOjVCO3BoRL67x+pO/fxkxX0PzACoNHHEPVvjJYrKHoF3LVhhdYMZUqea6WzmdjxAbUjfX19vHfv3skehiAILSQqaHX0dHnomtXoHI47tkCET9243Og3uHz748b8BV3RO9P+pgJ5uvEVvULNvJQVRLSPmft0n0lGsyAIUwoXR/LoyQqGPnFVw3YlWDcaQkfHmY05DK8E7TFN6Ew8Sc1BLh3f8kaUgiAIUwoX+7rN3LJuZa81dDSMy6rEds005qDJKIIXJs/oI0EQhMyJs6+r6qWXb3/cGMppCx1VDA6VcOvOESeF4BVIWx7b5TrthigFQRCmFDpBS6H/o9nLOsVgCx0FJlYILk7pni4PO67X+yHirtOOiKNZEIQph66ekckklKTrmcLmUA6f12TvN1VBneyy2ApxNAuCMK3Q2d1tdYeS4nKMrVdztAR2/wMjAKMWyjpZZbFdEPORIAjTApOvIU2Mv+sxumxjXXRUpcp1uQ3q2Ft3jtTMWyrJ7YLNj1r9IXkjKwVBENqCuBLXcZ/rGuSkdeomabYTXVUkWZlUmXHbQ/ux96VjeHBfadIb7ACiFARBaDFpuo7pTDJRoZlljL/uXCdOj2nLZ0RXFUlaegL+iuG+p440OLUno8EOII5mQRBaiCljd47Xoa1YqpzESTODo9fMQlHoxu4VCHNndeL1csWo4NR+YZ+CKwTg0Pa1iccae16Lo1l8CoIgtAydvb1cqRpLWCtTTNpCcUqQl4JsZFuYahzR8NKeLg9gv55R+NwAGsJQd1y/HDtuWI4C6ToEwLi91Q12ADEfCYKQE7oWl0lRQjFtoTiTEgqbZZKsJMJRT5dvf7xBmalz2/ou6FZK61f11vkU1PbJSHKTlYIgCJkTnqEDSKUQvI6JLOG0mcFxK4xmVhJpVi+mZLa+8+djjjchjruL3qQluclKQRCEzEnSjzichRzmrDmdTTuR41YYLiuJtOc2oeu3EF09nB6LdoZuHaIUBEHIlMGhklP0DcEeqTMamGYGh0rY9vCBmqmmu+g5O4vjwlSbaWqTVQisTTGpz1uZBS1KQRCEzFCz3jjCUUOmyKKF3UW/qc0DI6hUJ9YSo+UK+u/XN7WJErfCaKapTVYhsCYFpExZrc5dEKUgCEJqok7ak2fGnMxGq5cuqP1sm3Hv2H2wTiEoKuPsHMNvK0Xd7Gw/izLXJsVUIEpt2moGcTQLgpAKnZPWFFoa5Ylnj9Z+tlUStZlxsuhbrAsznd3ZgU0Dw9ZSE1mWpOhfs8TPYwjhFczRWnn3a5aVgiAIqUjiTI4SFWymGbfN55BVDL+6tkvWNKAveNe0WScq/9lXUDolm3fugqwUBEFIRTMz1u4uz2k/3SwaqA9XzYo4h2/S/ZJcN5rpXBlnMGNSGvSIUhAEIRWmGWvR66iZYwyJunBNW1i3shc7rl/uZw8HdBc97LhB39SmGVwjkZqJWEpy3OvlyqQ06BHzkSAIqehfswT99480zHLHxrkWhXPB5ke1x76uKSxnolU9i10jkZqJWEp63cno1ywrBUEQjNgcqutW9uKsOY3zykqVa6YUk6DsIMLgUKlteggA7lnTWfddbrc+zrJSEAQhVTlrYCLBLIoyiZj6ElSZcev9I+hA+3Qjc807yLJEdx7naxYpnS0IMxxdmQVT6QnALfEsvM/gUAmbdg47+xF05bCzKn8t+EjpbEEQjOiiaWzyO+wYdTF9rFvZ66wQoucHsi1/LcQj5iNBmOEkjZoJ+wnyMH3MK9aHq8YVrRscKmHrrgO1rmg9XR5uv2ZZbisJXS2mrdfmd71WI0pBEGY4SdpH6hygLhEy3UVP28pSx4kzYxgcKtXOaRpbabTs10aKREAdP1lB/wNutZGS0mwtJt352s0sJuYjQZjh9K9ZAkM6QR3NxMlvvXYZvI5IKYcOQpfXKILC0UuAuStZgUib+KU7R1bE1WJKgs4stmlgGFsG4wsK5okoBUGY4axb2Wv1IWR1jR03LK9vUXnDcpQr+r4BYZOWqQZQlTn32khJzpn0eiZfzr1PHp5Uf4mYjwRhhjM4VLJGGynShIzq7O93bVhR54uISwTrNZi3eoN98qqNpDPtZFmLyaREGKjzl7TavCQrBUGY4ezYfdB5pVCuVHHrzpHaTNaWfKbs7+Gibsr+rvZbvXRBg+kq6rewRTj1r1nSYJYC/CqjLslfpvGbIp5WL12grcWEYJ8kCXg2JfJK4C+ZjKgryVMQhBlGdPbp6mQOY2s2r/wOphwGwJ/l6xLbCMAHL1uEO9ZdrB1zabSMAvllpXtDSXZJoo/C59LRHUQ/6Rzj6prh1Y/u2bj4XgaHStg0MKxVyLZVkC6PIym2PIVclQIRdQP4HID/CH9V9FsADgIYALAYwIsAbmTm48H+twH4EIAqgI8w827b+UUpCEIykiaq2VDCWYfJ5BO+pkkhmYSebuyuAth2jqTcHTJ/uSTv2dgyuB/3Pnm47vmrezIpDAJwaPvadINX57Aohbx9Cn8B4P8y8/VENAtAF4A/BvANZt5ORJsBbAbwMSK6CMAHACwDsBDA14noHcyc/u0JglBH0kQ1GyaFAPgzXJuy6SAyKg2TrX3rrgOJOpHp8heY0ZRCAFDnV0l6D9HxPfHsUTDQsPpZt7LXyd+SB7kpBSJ6M4BfBPAbAMDMZwCcIaLrALwn2O0LAL4J4GMArgPwZWY+DeAQET0H4N0AvpPXGAVhpmETVklXDLaVAmLOVWU2Xk8n9AaHSsY8B909mfIXsiDcO8F0Dwx/FaEEfNRkt3rpgjrTW5W55idRCq7ZVqFpydPR/DYARwH8LRENEdHniGgugLcy86sAEPx/drB/L4AjoeNfDrbVQUQfJqK9RLT36NGj0Y8FQbBgmmX2dhdx14YVNVt2HF4H4aZLz3Pat8fQUEcnTE1Cz5YDoLsnU/5CEkzjBnxFFOegV47hLYP7GxzG9z55OLZRj6lNKYBcK8vmqRQ6AVwC4H8x80oAJ+CbikzoXPoNz5yZP8vMfczct2DBAs0hgiCYsEXyrFvZiz2br3BTDAT0nT/fKjgBX5ANfeIqp7F1Fz2jf8C2wtEpkWZzFIpeAbdfs8z4LBZ2F52uUa5Ucd9TR5xNdro2pXs2X4FD29fWfBR5RyTlqRReBvAyMz8V/P4AfCXxAyI6BwCC/18L7R+eepwL4JUcxycIUx7XfgRqv00Dw5jd2YGeLs/YzctF2KmM4duvWdagZBRK2ag8iDjmzu40OoxNK5yeLs/Y29lET5dXm313F72aYlOZ073dRaxfNWHTN4XMutr2bSa2JOMGsm8FqiM3nwIz/zsRHSGiJcx8EMCVAL4X/LsFwPbg/68Gh+wC8CUi+jR8R/OFAJ7Oa3yCMNVJ22h+tFxB0SvUJZGFcQ1TfWW03JCEpnOYXr79cSdfhaplpBuTyb5++zXLtOcydYXzChRbLC/6vBgTvoPwfQFwimQy+V6i/ggXf0Ezjm1X8o4++n0A9waRRy8A+E34q5OdRPQhAIcB3AAAzHyAiHbCVxpjAH5XIo8EwUxc9dCk+ylMAjWKmtXGFcRLIrBMGdNx1Vh1mb87blieqnqqKUIrGmYaHVN3l4c3To3VPTevQOjsIJQr9c9S5Xk88exR52xlW+Z5lhFJuSoFZh4GoIuFvdKw/ycBfDLPMQnCdCGvRvPrVvZak7OAZFEwSRLkbMrKpHxMK6Y7338xhm9382eESfK8omMKK6euWQWcOFNtKKCXtrS3zbG9eml2/lUpcyEIU5S4/sdx+9lml6Y2m0Dyaqk657auNIUii8JyzdjZ0zwvhXIM37VhBU6e0Rs6flwes57D5CeyPZcnns0uElOUgiBMUXTCFvAdm+GIlDSN4W2hq3s2X5FolqsLrVQVU5Nc20TSlVAcaZ5XFNusPvp+wtjqHcXVSsoKUQqCMEVRwlbXbyA8UzbFu9sEexaCMTrWcGjlupW9mV3DtmJKE8uf5nlFiRPSppWMbdVj63sxZXwKgiAkJ0m55HUre7FpYFj7WVgwuXRHi54XyLbNZl7X0EUmAROhoGlKfid9XlFc/Cg6xWFb9axb2Yu9Lx3T1krKMstZlIIgtBGuYaZhTAKo2dljs4Ixj2vYFKba3qEJAS1Xqtg4MFybced9XyZFFUb3fuLe5R3rLkbf+fNzVdaiFAShjUgaPgr4kSdpZ49ZNnFJcq40143WMyqNlut6I6vjL9j8qPEcquXl3peONZTnzpJo/oZrToJLvaO8lbUoBUFoI5I6TQeHSnhwX6lO4BCA9aviBUeaVUmacwH1JqJoMTjX627ddaAhd6Iyzti660DdcfOKnrF4HjDR8rLv/PmZCledolN5Da5KsBVmuzhEKQhCG5HUFGRKtHIJUUyzKkl6rq27DuD02HidArjnycMNx7tc1yTow9sHh0o4ccYe8gnUt7wMk3blFKdgk8zuW2G2syHRR4LQRiSNyGkmHDPJsXFtN01O1dFyxbl/QRZhlTt2H2xIFnO9XjPtL1tRk6hVyEpBENoIXS2haHhpGNPKQoVj2ma7rquSONNQ+OdmiHOM93R52izrcKXWJIoler1mVk5Z5kpk6edJg6wUBKHNCMfwR8Mqo7NWWwJb3GzXdVViE5a6z8Ln0qRQGIlzjN9+zTJ4hfoTqgJ3CteIK919NiPYm8mCDtPMaiUrRCkIQk64lrXW4WqOCCdamTCZMVyTtGzC0iYw73z/xXCtGt1d1JfAjo53x/XL6zOjr19ed5xJSYYxOeKbEexZJeK1gxnKyXxERJcz8564bYIg+CSJxtGZB9IUZTM1kbedz8WpGWdm0n2m5vO9DklcRa+ArdfqS2AnHa9LzoLJEd9M+8usooZM76k0Wo41B2YFsYMqJ6JnmPmSuG2tpq+vj/fu3TuZQxAELSYB3V306qJxAF/wRGfopuOj5ZvDXLD5UWvfgmgvgDA2O3ZUwYXHDACbBoa111XXix7rdRDOmtOJ0ZOV3IWc6ZkQgEPb1zZsz8qen/Y8NsWu0P29JIWI9jGzroK1faVARD8L4OcALCCij4Y+ejMA+xpNEGYYYUFgEs66sEqdMzPNrDWutIJrEx6V4LVxYLgm2O98/8VGIbfRUmZjsuPuk4b4ZhEO2kz+h0smdNqwYVfizEezAJwV7Pem0PYfA7g+lxEJwhRkcKiE/gdGnMMhoyizwZbB/bjvqSOoMoMAzJ1VwMkzVSdhmlagmHIdgPreBNEVilKCJuYV/aggV0GbNsvZdkwzJqG0xEUxqTGbOtWpc9gmF1lWRY1iVQrM/I8A/pGIPs/ML+U2CkGY4mx7+ECsQih6BczxOrRhlQu7i9gyuL8usYsBnDhTxc2XLaoryWAShGkFSpy5IqpIBodKsU14AODEmbGacz1O2KeZXbscY1qpAL6pJksFpLD5g6JjNhXtU+c1mZOyrIoaxepTIKK7mXkjET0MTRc4Zr42t5E5ID4FoV1YbKm3Q0CdMDLZ52/dOaLt5VsgwvN3vg+A3b4fFVA2v0T/miW12aoLygavu76NPH0oaY4Bkj3DNMfYxgXYlXB07GnG6oLNpxAXkvrF4P8/B/ApzT9BmLGEQ06TMLtz4mvX0+XVvuA6hQCgbnuSkEVTmOTqpQtqsfCuqJmpLS9Bhy6jWTfeNDkCafMK0oR9ZvHc+9csiR1b9HMVNtzlTfzNnBqrYu9Lx6znaYY4n8IO+P2U38fMH8ttFIIwxUgyY1ZJSP0PjKBaZYyHPnvj1ESdnoImfFJtVyQNVQUaTSdJBXvYBp+VLTt6njTlv9OWDM9DAUVNS+tX9eKJZ482mJq27jpgLdanG/vel47hZGXir4YZNTNjHpVe41YK5xDRLwG4lohWEtEl4X+Zj0YQpghJBSsAVCIKAZio8gkAN116nva4y97WU1uRdBhShG3RNKpnMOCHj7qsEApE2oS2JLbsoleoK0FhG2+a5K+0CWNpktRsx+iykB/cV0L/miU4tH1tTREv3vyoVSF4HaQd+31PHdHub9reLHErhU8A2AzgXACfjnzGAMyGO0GYxthmldHa+XEoQXHHuotx6Ogb2PP8hGmgA8DTh47XSkbrVhJxgjCpH6DoFepmuuG6S6YIp+6ih6uXn9MwOwb0PpToeNOErqYNd7VFJJkig6LlvsPHxJmWnJ+9oSSIi1kxS+Kijx4A8AAR/Qkz/2kuIxCEKYjJdKEchS5JSFEGh0p4+sXjddvGAYyP601K48xOgjDJqkYnAHVRPUkFsWsvgaTO07TH6MYEwBgZ9OC+ktEkZGuHmuTZV6qszT9wMStmiVOZC2b+UyK6FsAvBpu+ycyP5DIiQZgCxMW/u+QMKJSJJUnZ53FmbUauDlc/QFih2eLskwriNII7bc5COFS2u+hh67XLnBTQ4FDJGP0F+Pf/xLNHtVFNNt9GUh+Mbv+bLj1P24PCZG5sFqeCeER0J4A/APC94N8fBNsEYUYSV0xO9/nNly2yVvlMEw2U1b4uzuSkfRbSkqZSqEoeDOdOjJYr6L9/JHZM6npx5hjT+1m9dIFxe9J8At3+d6y7GDdftqi2MigQNeSuZIlrP4W1AFYw8zgAENEXAAwBuC2XUQnCFMClOFv0c1PT9cGhkrMvImlGrrb+UIEwd1YnXi831h+Ki+oJ293DY26mnWeYNH0NTKusyrjeJBN3PR0mc42py90Tzx5NtGK0vdc71l2ca0/pMEma7HQDUB6wedkPRRCmBuFSFAUi3HTpec5fWJMi2bH7oJNCsBW106EEeLlSNZZUiBLniA1/Fh2zLvs5qRko6UolLgkvaW6ACdNKwjbeaNMkE0nfa564KoU/AzBERE/A95H/ImSVIMxAoqUoqsyxMeMugtHFdBSXqau7btRxqoR72qgenb8hirqXtIXhXPMPtgzux71PHo5VpnEmnLhCggpTz4q48aqJgK1ia5L3mjexPgUi6oAfBHEZgIeCfz/LzF/OeWyC0HYkjRl3tY/HRZK0umGLym84tH0t9my+oibEXWbV6l7SXt8l/2BwqOSkEEyx/3HXi6IywXX+E9d8iay6s+VN7EqBmceJ6PeYeSeAXS0YkyC0HWq2nzRm3LVips3JmaYPwuBQKXHDHRdcZtXqXtKWoXAJe3Uxt9mij+Kut3rpgrrw0zRhukB90T1broMLrerd7Go++hoR/SGAAQAn1EZmzq8AhyDkRNIvl0vyl2mmn6Ripg4CrApBZ57Z+9IxPLjPHHHTzMzUxXGqzCxpy1AA8U78OMVS9Aq4evk52LH7IDYNDMe+57jrJQ3T1b0bW65DHM30aEiKq1L4Lfg+pf8S2f62TEcjCDmT9MsVF7+uCMeMh5WOrh0k4AtGl6gXBozRM6ZViHKC62i2l0DUcRqNmIrL1ciql0HciqVcqdaZl5oVoklXPaZ3Y8p1iCNNRFZanPIUAFwE4H8CGAEwDOB/AHBrqioIbUQSO7dL/Ho0ZjzqQ7CVpXA144T3C+cFmISibbzrV/Vix+6DTeUVKH/Di9vX4q4NKxpyNQB/Zr1pYBhzvA50Fz0QfHPOHK8DmwaGrdd2yX1w8QOYIqPSkNQfYOu1HL4f1zyPtKa4NLiuFL4Av9vaXwa/3xRsuzHzEQlCjiT5csXN5HXRQKZjdGUpXPsZhPMDXGLeTWURuoterF08KXFmk+MnKyh6BXzwskXaa+996VidOWXxTxXx7eePxc7wXUM9o7gK0aiJMak/wLaSUfejfnZ5H82Y4pLiulJYwsy/zcxPBP8+DMBpDUhEBSIaIqJHgt/nE9HXiOjfgv97QvveRkTPEdFBIlqT/HYEwcc0A0sy44sTICdOjzXM7EzHqLIU4Ugel9mu8ikAbklWRa+Amy49TxsNQ4TU0UiumFZi9z552Lg9HJm1J6QQ4saoVix3b1hhqiXXgIsQNVU9Xb+q15jBHsX2btX9ZNWjIWtclcIQEV2mfiGiSwHscTz2DwB8P/T7ZgDfYOYLAXwj+B1EdBGAD8A3S/0ygL8iIvs3RhA02MJAk3y54gTIaLnSEF6aROmES2EAjUUyCcAHL1vkHA6qBNUd6y7WluAYNbTPzNIEYTqXyaDlWudTOeZ1in7dyl6n8xD8v4U4s1mcPyCq3KOEEwZt95O0N4atrEqWuJqPLgXw60SksnYWAfg+Ee0HwMz8Tt1BRHQu/BIZnwTw0WDzdQDeE/z8BQDfBPCxYPuXmfk0gENE9ByAdwP4TpIbEgTbDEyZe1yij1wibaLOvqTO1bD5JS4qymaSiCZA6aJpTKaWLE0QrolgSZlX9Kymll7DdZUpzaUcR1x2tIvydDXxqWee5H2kKSyYBlel8Mspz383gD8C8KbQtrcy86sAwMyvEtHZwfZeAE+G9ns52FYHEX0YwIcBYNGiRSmHJUxnTF9qtd31y+Vqtw4LizSlpaPK4K4NK4xKatPAsHZWrBMkzdrFk2Cqh5QFBBhNX7fuHMGmgWHMK3rwClRX/0j1Mta9v2iuSFxHNMBNebqa+JL0mmg1rqWzX0p6YiK6GsBrzLyPiN7jcoju0pqxfBbAZwGgr68vny4TwpTGVn8+aY5CXIkCoFFYJJnRJQmRXbeyF/fvPVzXhEcRrdRpi5N/ZOTVmgAsV6q1zm9JFFf4uenqISnF0NtdxMkzY3XVSxVzZxVwZmy81kBIhzKh3aspHQ1MRFqNlivwOgg9XR5GT9YX+bP1O3Cd2YdNT7a/mbjmS6ZEvLwT0pKQpCBeUi6H38bzfQDmAHgzEd0D4AdEdE6wSjgHwGvB/i8DCBcIPxfAKzmOT5im2LKO0yQADQ6VjPkGYUdwHDrB6prxrI45cXpMe+5opU7TeR8ZeRUnztSfQ5WYBsy5GrbnpruWUgh7Nl+hFbxFr4BfvaQXA9+tLw9S6CC8aXZj9dYnnj0aa5aqjDO6ZnVi6BNX1W23Re64VkgNm542DQxj48CwNtM8rvlSlFaZhJLg6mhODDPfxsznMvNi+A7kx5n5ZvilMm4JdrsFwFeDn3cB+AARzSaiCwBcCODpvMYnTF9MfYHTRN/YchWijmAbJue3zdSlO8Zk4gg3kLd1fRstV4wlprfuOqB15MZFycQ5TE1O0ieePdowluo4Y+7szlSRWqax2IIL0jjZo76JsNO6lVFCeZHnSsHEdgA7iehDAA4DuAEAmPkAEe2E38RnDMDvMnOyzuiCAMCUu2XabhMMtryDT9243HmWZxKsJgpEiVo5hhvIux4TZbRcqSmd8GogTui7xNDrZsQ2s06UqK/Gliked2yaXBET0UCDND6ldqMlSoGZvwk/ygjM/CMAVxr2+yT8SCVBqCPqDOzp8nD7NfpiZ6/HOAyj2ByItrwDoL7gWVpbs44qc6JjTpwew7aHD6RWCDqUwIsT+nH9F0wCMmlCVjRSK22UV5gkTXBMRN9TO5qEkpCb+UgQsmJwqIT++0fqTCfHT1bQ/4C+1WKSEMu4pb3pXCpE0rVlpOk8pkJ6vd3FRPcxWq5onbnN8spoGf1rlmjbiKrnZjIPAWh4RpsGhrFl0F+BNGNqWbeyF+tX9da1qFy/qrfmh3FtERrNFUlDB1HDtfJoU9oqJsN8JAiJ2LH7oDZCpVLVt1pcvXSBU619AmqCxIRpFmzzT7jOSIteAetX9VrDRJudxbrQXfRABK1SqSmm6MOM/K6bHesqizKAe548jL7z5zdlahkcKuHBfaWaCanKXKsMm7SUR81vcf+INRLKhBpDtEptKyqa5gFxTPXHdqavr4/37t072cMQcsKl1SIBOLR9bd0xSQSpSzcznQnElC8QHU/cecIRRqXRckPLTCB5fZ8wRa+AOV6HVuCH7z3aUU5x82WLjJE/cc/OFsbbXfQwfPtVhk/jMTnTTeHI0bHqorp0TvwurwM9c2db/RhpxzCZENE+Zu7TfSYrBaEtSZoZqkjinAXcbP1JsoOVKUE369VlL6ta/6YmLne+/2Ls2XyFNaIoTHfRw9zZnQ3NXuLs77bm82krdNqym+MSxeIwXdulj7IuxNZEuTKO7wWC/ILNjzqNLWkv53ZDlILQlrgI97BdW5H0i2ez29ucpCYHZdSUADSaDHRCSTdLD5ujXByiRa9g7TRmM9PYBH/aCp39a5ZgoyHCqFlMYzLN0sNjTRrVFXfNNGOIo1Vd1nSIo1loS+KE+9xZBey4vjEkNCsnc1xv5ahzVecwVtnCUYdjEqEUjvVfv6pXWzQPiC+QpiqK3rVhBQA09DSwFfJL6xBet7IXc2fpcwtMuSSumMZkqhAbHqvrxCF6XDRr3HSMyxgAszPata93XohSENoK9UWJ7b/bNUsrAFcvXdAgOIteAXdvWIG7NQ1hbLPquEQ3JWgPbV9bC1GNMlquOCes6QgL6yeePar19ypbddxMcnCohP4HRurGoyK4bIK/mQqdn/zVi7WRS7df03yPrjnehPjqLnrWCrHRrGMdPV2e9TiTia1AVHeMyxhsgt/0t3frzpGWRDOJ+UhoG5I4iXWzPRWREhac0Qgj1yV4Uju6q2mhXKkazQtRXGe4rjPfbQ8faMggrlQZ2x4+UCsNYTJZpI29N0UYAe45HlG2DO5viC47PTZed800EWWmvBdFXK+MMHFjsE064vwleUcziVIQ2oa0tl7b8Qx/hpfURpvUjp4kCarKjKJXiM1oDre2TJrFq8OUx6C255V0FT2vzqeycWAYW3cdsPpE1LG6cONypYqNA8PYsfugU5FDIHkobJbdz9L4cMLk1Z8ZEPOR0EaktfXGHR8224STqBYn7AFMMNuVdSYWk928p8vD7E7zV6/oFfCpG5cDqE/+MtVfcmkc007JUyblr2tapDvWtsZytb+HTX8upjcg27pGSX04OvKKZhKlILQNpi9Kd9Fu6407vkCkXUEAE7PUFdseqxMkOseuSryK7hs+Jixobr9mWcOX2ysQ3jhVHxPvFajW3D58f7a6SwC0jWN041IzcxPdxUbl1UxGbtyxNmEWV6DQRRBm3WJUYfOtJH1eSXw4pqz3PPozA2I+EtoIXSZyXJhlGJOt2MWko2apwIR54dF/flU7K9Xtq0NnptAlSVWqfmXQaDKXzYat6zRmMinYzHJeB2HrtcvqzGvdXR7eODVWy+4tjZbRf/8Itj18oKFXQRSX/hBx5hGb4Hf13bjOom2Jg7r705nYlANf+WuUA1/tryPOhNVMnadmEaUgtAUuTuI4TF8014zgaB8DWy0hkwA2CRnVTc2UAKUavoTHPq/oaZO8FnYXEzmdrVVgb5gwUymho7vvyjjXttscnXH9IYB4/4ttBuzqu3GZRUeFbdiRa+svoY5V74oIiFbHUA78uEmDy992qyuvilIQWkKco9fmJE6C6YuWNKrJxfwQ7cRlEzJKiJpmuroexF6B4HVQXT0eNUN07bdsaxDU213EupW92hpFcZiUoouyUsdse/hAgwLyCoQTp8esWeEAjKsawL1Lmm0FpfpLuKyGTIFkWRYobGXlVVEKQu64mBSaDbe0ERYkcT2ElVB1vW74XmxCRgnRJAX2KlVGT5eHrlmdWmUaZ1KwNQgK75v2GeuOc43QUUJOZ7bS9XQwlQsBzP2h40I341aPplIcSUupTDXE0SzkjksimC0aIwuUE/jF7Wtx14YVxkzbxT9VdEqeCxMXX64ojZaxY/dBrF/V2+CsHDXMKkdPVrRRMi4JZTZHdXjftM9Yd5zNgapzxoad812zOhuqlLo4jdU5eruL2lBV0/EmB24crkpU58CfCshKQcgdW6jo4s2PoqfLw9p3nmMtIZ0lKrLnxJnGcX37+WOJFILCNb68NFrGwHePNJTocDUHhYkzKdgc1eHjdKsXr0CYO8vvlTyv6OHEmbG6xDfTu7Elq+W9Wkx6fFwCYQdBa8Zyec/KgT8VkZWCkDtxM9HjJysY+O4RXLJoXtNNU1wxCYq0heSTxJcrJ2SYPHr7uq6+dKuOHdcvx/DtV+HQ9rUYvv0q7Lh+ed3n61f5ilX3TnQ5AK1YLSY9Pq6xzjhDW3tI966iYcU7bnBv1dpuyEpBaJqoE3n10gW1ksu6stA6KlXGnueP1X5P0jTFNVs5vJ9rbXxXwteMRh/piDoh84gwsbXJjBK36rCFSLqUXYibxQ8OlXDyzFjD50kUY5L7Vfub+mJECTvW84oGmszKqGFEKQhNEVcGujRaxoP7Sli/qtfYrMVEuVLFfU8daRCs0dBRFwEVrZdjyg5OoyZ6ujxjjaDFjjX4w+NVgkHNouMEg0mY5CW8XMJOo9gc0LaaV+GidzbCheRc8g0A/7nufemYU5c+oDGCKu17Me2bVNHmhSgFIRUuXdEU5UoVTzx7FHs2X5FISAL2hiWDQyXcunPEqjTUWOO++AUiXPa2nsQ+Ba9jouKnTgh0G3INADSETKYRDLZjgHxi25Pa7geHSjhxunEVoEJHde9Qcfyknyh4/97DePKF46gyo0CEmy49D3es82tD6RR+ODvYNCb1bOYVPfz4VKUh1yBK0n4I0fdiSwBMo2jzQpSCkJikLS+BCYHR0+VlEr/NgHXpH1ZWcfVyAF+QPHP4dfzc2+cbFUN30cNPTo+hGpYeQQCLSThfsmhenVksOsaw0E8jGEzHbN11AKfHxnNRFkkKw9n+Vmyrtuj9RE2LajXad/58Y4E803OLjsmlC1xS/47uvdgSAPMMyU6KOJqFxKSJ01ZtKrNsCR53KuUYdP1ilStVPPnCcfzc2+drezIQoV4hwPeF7Nh9EFt3HdAK5ydfOB57TWUmSiMYTJ+Nliva8Wx7+EDTDVySOMXzjOm/76kjVoVvejZJx5Skf0TctcOE332ckzyPYAsTslIQEpNm9qJmg8325k2CKjPgWi8H8MepWymUK1WjILGd28WZrZ6naZxEE74J5fdQ9vIk9wbos2yTmimULV75e8KRYqZ7y4Mqc2ydJB1JqvFGC941W3rdNBabk7zV/gZZKQiJsdlWu4seOhxygpKmDalwvyQoAegaKqrIcDHjRAeRsfsZUF9XJ5ytu2lgGIt/qqidtSdtd2kTlNFZ6pbB/XhwX6mm8FSkmG72mlclT8D3A5nOT4DR3GMbk669aZr2mK5/c+GxhMup93R51mq5eVWCBUQpCCkwmQ/u3rACc2d3xjrsgInZrorrjuPEmTF0p+jru2LbY9g0MIzZnR3o6ZqII7/5skWJFEWeVJlrMz+XkskKhp9sp8uQ1pXtLnoFY5atSVDqBOK9Tx52FlLamP4OamjRaRubKQDppkvPM/a9+OBli4yzaJvA1rU3TSOUo7kf3UVPe8/hlUB4FX2qMtFJrtX+BjEfCXVsGdxfZxYIR3kodAXN1CzH9Q9VffEUl29/3LrcrlQZpyrVxGGj6os2Wq6g6BVqjeuT2pWLXgGzOztyM38pIRMWRqaKqmFU0cDwswR8YT67s6N2jz1dXi1KKkksv6lQoQ7duzeFxerMTwDqwpkVG969CACsf5dJ2n2q/zcODDvdR1qhbKrRFB2TriBh2KSXZcc3F0QpCDW2DO6v+1KGozzCX8DBoRK27jpQJyBVj4Fuh+ginRByKYlcDs2eAH9GOMfraNhuPr6K2x76ZwCNTXfiIDCuXt5YisNE0StgjteRKNIqKmTS9g7QRfyomWfS3IUks1GTkNIJR535ydSNTim96OTEdv44G7wyy7gI26TRVkn7XMcpnaRJec0iSkEA4P8x62ZpgD9D6zt/fmyV0XKlitmdHdbGNqaEomg2sAsMYI5XQBIhb1IgcSuQk5Vx5yS83m59vR/AvuKICpn+NUvqmreYiB4XF9qapAyz0fmN+ueVREhte1gfqWV6h0nNJK6hva7C1nW/tA7hOKXT6n4K4lMQfCdn0FRER5UZmwaGa3+4NhH1ermCO99/MboMhuDVSxdYM0yjZpA4Rk/612u2IqVrqQOlOE2O3LA9OmpXVr2ZR8sVbchrVMisW9mLDe86z+q41x2XpQ3a5D/64GWLnFqkRolrXqQjqZnE9f5dKs0m2S+tQ9glxFdXTyovZKUgYMfugw0li6O42vE7iKxJZfc9dcRoBlDoWk2aWBg0ilm3shcrtj3WkpDX0mi55iy1VQ61tbhkNIaXRr/oyswSfjVeB+GsOZ3WtphZ2qBN4adRc+KO3QexaWA4dhZrE5A9XR5OVcabNpMkuX/XVZPLfkmUcdTMtH5VLx4ZebX29+ta3iMPRCnMMHQ2zyyjGOLi8qvMtTr6JnTL9Q4AOsPP6qULaj+/7qgQ0tY4ClMZZ3QXPcydrW+AEy29oJsdhyNddHHwpqzYrlmdGPrEVQ3nU2RpgzbZ//vOn5+o9pTC9remHOFJzSS6goytKsMexlUZ6Z7ZwNNH6uK0VXkPQGofCTli+gK7OIfjIDK3JYwS98eus6GePDOmHWO4XaeLY7boFWp+gbhzx/F6uYLh2xuFs0utJUUpqOGkey9pbexZ2qDj7PNJS3OY3lF3sb6ooCu6Zxf2/bSy4ujqpQsa3rtOGZmUfZRpV/uIiM4D8EUAPw1/kvdZZv4LIpoPYADAYgAvAriRmY8Hx9wG4EMAqgA+wsy78xrfTMT0BSZwQy/gJETNKHHoCtbZqnwC5vDMsIDRNotxMLfoonVUf+STlsgmkznGpdaSokBkfC+m0tu6mWfc8zMRV8kzziSS1H+he0cE4Orl5ziNJ4rp2enCdPNErajCb4sAbaZ3kpX5ZNQ+ynOlMAbgVmZ+hojeBGAfEX0NwG8A+AYzbyeizQA2A/gYEV0E4AMAlgFYCODrRPQOZp6+zVBbyOBQyTiLPlkZx+Vvn68t3Hb52+fjmcOvW6N7KlW29g7QoRqru/bVtUXBKHNU2hly9Dhl/7cpBJs5IskX2VaqwfQ8wyYz3Ux508Aw9r50LNZ342L6iTOJJPVf6MpVM+DcOyNKuxSSM+VzPDLyai1yT/1NJlmZ55kRbiI3bwYzv8rMzwQ//wTA9wH0ArgOwBeC3b4AYF3w83UAvszMp5n5EIDnALw7r/HNJNSX34apkueLPyrjkkXzYq9hag5vK7dgimbSRWyEBWEYhv+FVDb5TUFC0l0bViSK0ghHd+h6BQP+rN4l2ibJF7m3u2jc35TRHDaZmYTRvU8erpVhMBVTc4mWiYuMSVIcT43jHkNV0/ueOpI4eifv3t6u2AoT9t8/UpcR/sapsYbsZpMgNv3d50lLfApEtBjASgBPAXgrM78K+IqDiM4OdusF8GTosJeDbdFzfRjAhwFg0aJFOY56+tBMpcrSaDnVrKvodSRO3goTveZXnjHXmVGzY91qA0CDEzLO1mzrbXxo+9rYsbt29AoLT51j2OZTiOtnoZRl9NzhZ+M6y/YTBP3ju4setl67rMH+H7c6cym3buudYaLViV0mbP6s6ASjMs4oeh04+01zEvnMWkXuSoGIzgLwIICNzPxjMtdz0X3Q8FfCzJ8F8FkA6Ovra3XtsilB1C6bpIqmjjQP2Q8tdMs01hGe6W0Z3I8TZ+xKTTfz/PhX9uPkmWqdsoh2het/YARbdx3A6+UJn0OcSSTO7q1MJKZkQGCi7ET4uOg5TUJ/XtFz6mehureZZt8u9xm9zumxxnfq4r9wmZi4+lCi11bnbyZiKYvWp6ayGTrKlfG6a9p8ZtFmTHmTq1IgIg++QriXmR8KNv+AiM4JVgnnAHgt2P4ygPNCh58L4JU8xzcd0dmJswjBTEoz14vO9O576kiq88QpEsD3h6jYcDWLXr+q1xjS6BqCece6i+vizqOciihMk2DVzYKJ4LTyW9hdtK4G7tqwwjrLzrIbmMtqc3YnoTIOa+6HjiQZ2kD7tL4MP0fb5K3V48vNp0D+kuCvAXyfmT8d+mgXgFuCn28B8NXQ9g8Q0WwiugDAhQCezmt80xXXAmZJy1DruDnIas0CXcliRRIHdrOoyBVTBmuSrNWt1y6DZ0hHLleq2Dgw3NAwJWz/37H7oLYC6qiDSU4JU5vNPS5TN0snrouN/2RlHGDUVbNN2tzGhTxKUac5Nvwc40pt51kqO0qeK4XLAfwagP1ENBxs+2MA2wHsJKIPATgM4AYAYOYDRLQTwPfgRy79rkQeJcdmKopm0AJA//0jqUJRCX4rxL7z5zvV57ER12DdFtmUNOrJhVdGy6mLlzUQo32j/g9dzH1UMJrMSgUijDM3mENsqwHbLDvLzGiXgoeAW3Jes+QRsWQ71tSCNvwcXWp/tSqiKs/oo//HzMTM72TmFcG/v2fmHzHzlcx8YfD/sdAxn2TmtzPzEmb+h7zGNp2x1eDX1YpPa/VnTCShzZ2Vbm7hFQh3G6KEwjNmU8p/B/k19bPui8CAseVhkmiXHbsPOinLcqWKW3eOYOPAsNMMVtujoEB405zG9+Bat0dHksiiOMLjiCNv4ZdHxJItgmztO89pWDF6HaStdbVn8xXGZ9SqiCopiDfNiJs1h79wO3YfbOg5nAQlsOLKS6ivQ3fRqzMN7Lh+uVY4RRu76HwDXV4HPn3jCtyx7mKsX9Ub25AmKaXRMjYODGPlf32sTjkkEZRJ8xVMxBVy6+nyAPbDH3WdwdIWU2tGoZjOZxN6iryFn8s7TNoT2WT+qTJj4OkjjZMvy59rlso4DcQttNdmTV9fH+/du3eyh9ESTNES0e0nTo9Zi8KFm9tcsPnRph3QhPjyEtGGOtF+DNFIHFvDnXDfXHWutCYwV3TX1DV1cY0eSkr0+UUxPS/dc29V+WUbtvDU6LPOcwymZ6Ebn+rmphICTX8Dt+4ccTZn2t5r3u+KiPYxc5/2M1EK7U+0uJriwrPn4uXjp5xzEKJfuLhuZy4of4DNXkxALb7fJMS9AtVWDnHKKlyIDglqLjVD3BdYV17DK9jLZLjgIiRNzyv63HXvSBcamyVxk5nSaLnmF4rzLbUK0/eCgFrnPp2f5s73X+yUnxI+XzTvpVWK26YUpCBem2NrfvNvr52IPV5Xnjku8SnuXAq1pFV/tKZZUgcRLtj8aG0lo5vVV6oc235QMVquTKyGWjSnsZmCTAXObKsX9SxtjnJXIWkqmxA2w5jyBPKsxhkX+qnzI7mW4M4T07sOJwQmzf3QEX4/g0Oluva2wOSFyopPoc3Z9vCBpo7vLBBuvszP/N4U2MhV2r2OotfRkILvdRB6uryaEAMa7cvrVvbiUzcuN9pVla3bZtoKtx/MwnlMAObOysYJrRSbzr6cxjGqFLXumRW9gtEBH2VwqIQ3To01bPcKhNVLF9Ts4jZBlVe4Y5LQz6gfKeoXyZOo/6DbUprlldGyNZ/A1e4f9hGoe9cp9laGoipEKbQ5zZa0rlQZ9z55uPZlO36yYq3rM3/ubGx413k152J30QNoYhxV5oYVgkI5Jm31jmyoqB8ATZ0H8M0ih7avxSd/tbnzKMKKLSqs0jpGVehrM85cU4Okzg7Cg/tKtfceRxa+jzC2Aoy6ntK37hwxKpCkTt+k44wqI52SVSzsLhqDGgpEWLey19gF0FQ7Ky7bu9XF/cR81CbkaUt0EQrKhBGNjb98++MNs/twVquuwUk0WzcJ4azirlmdOH6yUmdzfvX1MuJ8yl6BcPs1y5zq7YRR9nVgwmncoTHvqBBSZebQNXVxIdyDN+27NgmMpCVGXKK3XP9G4wowRs0mtz2032hCi/aWiJpUmv3eGBsZeR0oV8a15lJTOQt1D1uvXab1OYR7PKjZ/7qVvbFCv9XF/WSl0AbYls4ZR1o6EV6y2hJ9dOO+98nDqYvvha+vVjdA/erEphCioa5JCwEqZRYO4Rw3CKvwyuHBfSVcsmheoixxAjIJMZzXZG9qRVzETBLzTtxzP3lmzFqpNUyByLqCiI5p08AwFidYUdiU6l0bVmhXcKaQ2t7uYk1JqX4YarsqnaJ7fjahPxnF/WSl0AZs3XVA+4efpMBW1pRGy7hg86PamTLgOzd1juWs/L6mctqm/s09XV5DFmzSZbeuro+L47BcqRpLj5tgZOM8NE0aOgixK6owttwBZd7RrZh0dZDinnvYuW3bN65SrK2ki6uT1pa1bVrBmSqzrl66oG57eDJj8q/YfIbRirStQlYKk8zgUCnXZvPKyZwGhn4G6RUIb5waa2lNIsAXBP1rljQ4wgHgjVNjDTPDNMvuqJBavXRBJnWiomRVM8pUBymJQrAlbqnAhCRlrW2OWoWa9HRY7PO2DGhbsb/wNeKctGkSxUx+oCeePWpc1ZjGevxkpcFv2F30cPeGFRi+/apJib4SpTCJqBlYXvR0ebhj3cVGx1cSiCbMM3MNTWhciGu8Y0PN3nRlNSrj7FQOwuUaCl2LxSxIYxIwOVvTKL6eLs/o2I6aZEyBCQrd9ZPMFUzNmT51o28CtAltF9OZSz/rNI5+XZa4zdSa5D3Nnd1p9NXk5XAPI+ajSSLOwZYFava89dpliZJqdDD7pSWSRql0Fz0Qoa5HclyvAR1hG7xpZaUrBxFt/WgjKqxN9u5mSpGrGXBWpZ5dEgejzlJbsloSP4xJucWVPdFhKuZn65fgEq7tIoybcfRHr2UyRbkWBAT0iqyV5b5FKbQIXXJK3qjZ857NV2Tin0iTnTt8e72dX82+k6Js8INDJaNQViGt4e5qHUTafVVEky2b1pbEZBpDnMKoMif+Etvi/VWWten9qnwI1+gcVz+MTbmlaexk62pnEtpxJcRb7aS1dYHTKTdTSRpTccWselvEIUqhBQwOlXDr/SNNFZ9Li/qSmxy0eaIzW8XNRMlQtqKDUHN8255itLuaaSU2zowXY1prmoRbb7e5fWJ3ENZqyu4m+H8PSb7ItmQpALVIK5f6R3G4CPS40hs64eh1EM6a02mcFKUxg9nGOhklM+K6wEWVmy5kOmlxxTxyGMSn0AK2PXxgUhQC4GfiDg6VnOzrWTtUr15+TsO2uGiTYqf+T3KczY7vNER9BzpbrbZEdQcZFQLgz15Vdrepv2zSDFVbspQiq8qaprLc3UX3xjc6O/2OG5Zj6BNX4e4NKzKrAGq6Z9ds8DxIUpE2iT8jj3LfJmSlkBPhpJrJLDlYZUb/AyPY8K7zMLuzwzpLL3QQquOc2Xgf3FdC3/nznUI8lTmiFWG4uhIDNluteo/zih5OWBQCUJ+QZrqXpLM7kyIMb4+bpbqS5Xl0x2R1/qzPNVm4+jNspqmsEaWQA0kzafOmUmUnx+5YZDWj7ONJY94VOpunyeH25mIn9r50LPd+0lGzQpytNvyl1WV3h4l+SU0mO93szpaZazpPNFxTZ564fPvjRoFpumZU2Iazb7MgK8du1udqN6LvJ5wRnacCFKWQEeEXaEr4yhOvAzhrjr5aZlrUHTRj+XKNCDp+suIcJQRMRKt0d3l445S+8moUr0A4cXoMmwaGsWP3QfSvWZLIVhs3w58dMX2tXrqg4Z50s7toaXSVmbtxYBi9hjIacbPEuBWQ7XOgsS3oZFTrzJJ26SXhiu796Fqz5oEohQyIfqlbrRAAoDKOpmoO5YWaFYfLdduih1zQNb1xaW5SqXJtpq8EnUvZ6fC2uJLeYcGqy3G4ZNG8htm6ThmGFcSD+0pYv6oXD+17uRYBdmqsir0vHUsUWhpeAcVVMG1VpEsakgr4VoZzZkUro42iiKO5SbYM7sc9CWa4edIu5qow/WuW1CVEAVmYhxjbHj5QcwwDMNYoslGuVMEMZ8eni7NefXFNUVbffv5YXdLRjt0HY59HuVKtUwiAH6F1z5OHsWVQX3gubgVk+rxkKQ3d6mqdOtKU2E5SwrtdaGW0URRRCk1ga4DT7nTkUbtBQ5rCdHGUK+M4frK+H7FLaQUdr5crDf2OZ3d2YNPAcEPWaDhaxIat5n40+sj1S27KEbnvqSPa7bZolcGhkrG8hI3wqq8VmbVRbCW2bYlskyFgm31GrYw2iiJKoQnaeaZho7vo4c1zsqmu6ULSL58SVyrkMq6ss5rxp9FzqnTGns1X4K4NK3CqMo7R8oTCiVbdVPvaFIOt5j5Q/zya/ZKbTGamcE1VtC2piVOtniarGU5cBYDjJyvGMbRawGbxjLIKMU6DKIUmaIfltAvh5h6q0FaaUgRpSfrlU1m4z9/5PrxoKV8d5vVyBR+MKf7nRZZHLmUtolU31Rfb9u771yyxCt3w82i2y5xJ+SQp2hZHOH4+L1NM3MzaZbUZHYM6p/JjhclTwGbxjJptvtQM4mh2ROfcSpPOPxlUmRu+FK5jJ/hZuuHaRQBincYAcPnb5wPQR+HEhZ5GZ9NxY13YXcQd6y7GIyOvasNGVSiqzUHpWnVz3UpzH+meLs+aYRzto6Cun7YEyk2Xnlf3u80Ja+uGZkJlpauILVt2terDnTSyx8UR7DIBC+8TDf4IlybJI9vZpe950knkZIXbilJwYHCohP77R2phj6XR8qT2OkhDeBkLxBdSCx93Kmg4Ev4DVWGNJmF24dlz8eKPyli8+dEGBUBAbVZv8smEZ9M6pRImPOu7evk52nOuXrqg7kumaxI/r+jFljEP95FuKOVQIDD75TjmFT14BUKlOjFqdd/RL7pSImmUQt/582s/u4SZmujp8nCqMt5QmuLEmbG6iC2bMo/+jcVFBCXpbufybsI+D1NEV9KyHy645iW1uoNaWkQpOLB114HUpaJbyawC4UzVPk412+1fswRzPHuGc/SYuLotikIH4d9eO1H7Xffl/MozJZw4Y67sGc44tpWvJgLWr5oQ9k88e1S7X3i7Tnj23z8Cl4BeVa45muCl8iWU4IoKMNXq0yQo05oiwwI4aZipQlVODd/PQkN9J1sxwOg1Tfcaff5xGdul0TK8AsHrIOP3MDwxsEV05WHydTFtTUYHtbSIUnAgzyY4WVLo6ACq8UI+2vcW8Ge5c2d1Gu+1NFquZcfOK3r48amKManNpc6TSSEA9RE6cV845vpyGi6RJqa+vC4QNZpo7tqwInamP3qygo2hpLmowExrigwLYFuYqY2wrTo8rgs2P6rd3+VJ2YRvmmi0StXvm3z2m+fU/gajJdldTE15zNZdFE2r/AFZIEpBQ/RLP1VQfWFdIksahGKVMXd2J+bO7jTawtX2VihJneIyoUwNgL2mffjcaTkeCPek44w6rPe+dKyuZEGcicyGEkppFEtvEH2lw8VkY8IWIpx2tn6yMo4/c/AFmJ5DVn2xo5gSIBW2Z9yOSPRRiMGhElZsewwbB4brwsmmEqovbBpUu8vo8XnXIzIRbn4eR5UZGweGcfQnp7RRRquXLqhFt0zmONX+9z55uO5v7MF9JfzM2XNTXV8pPNO7M2ETkoNDJZw4M5ZqPIC+PaqimYmWSwSP6Tno/DlZYJuDTSWzkUJWCvC/AFt3HZgyZqI40iaKdQeRM0C9bXkyFaNScq73dKbKKHT4pZ5fL1dqs/Bo7aDJHmdUjpQrVbxw9GTi64aFTtJ3xzA7g3fsPljnJE+KavCkO39ckEOPZebtsspoZfXUuB7rScxG7VKfacYrhXaraDqZnAqeQTQUTsV6TwYFIqxf1Yv7njrinHBVHfdNYarr2+XbH3d6v91FD3Nnd6YqahgOeY2L0jGO2/F6ttDKJO9Ol4DnElrpikmAq/HpJmLK6W2KanNdZbQinFPJDhNJzEbtVJ9pxiqFVrXHnIyOZ2kpB6UUWrFy6uny0DWrs+Y0NF2ryowH95USZ+CGBZLL7JLg+0rmzu7EXRtWYFOCkONwy8VoyKtOQZgUhskfFH5WSWeQ/WuWoP+BkYZZv9dBDWaNtBMk0/3YBLh6VrbZcR79A7Kcjdsc5knHOpkF8KLMSKXwwf/zHex5/lju11Ex0Rf9yT8k7m/c0+Vh7Tv1Mfd5smVwPwaePmKNxukORX6kMTCEm8fHzbYKRKlWcWGBZGvsoxL7oo5gVydrd9HD1msbQ011CiLsVNaVwl6/qle73RbKGocuOc405rQ1qjoLBHB9BJerUGxFMx5F1rNx22QjabTRZBbAizLjlMKWwf0tUQhhJ14a0+wbp8Zw7yQU24sz00STf1ZseyzxiiJcPnrbwwess600Qsor1M+CTV2rTGapcqWKOV5Hw/VVn2FdGGSUuBlp3/nztZ+btichugo2KYEoaQVQpcoNq5nVSxc0JAfGrQzU2Jv5PPocwvueOD2mnY2ryLWkz9nWwzurc3V3edZGSXnQdkqBiH4ZwF8AKAD4HDNvz/L89z7VGkGrnHiDQyWcHkve52CykuXizDRhwZE2QiVcPtpmvkvqSwD86q87rl/eYGcHoJ2tm849erJSyz9I+oXUzUg3Bk1zwgLaNENudjYcNReNlivovz9e8NlCOePewOjJCoY+cVVtDLoZ+d6XjtWthJI0/nH5PPocovuaqDKnWjFk2SLTlCH/xqmJBMJW+RnaSikQUQHA/wTwnwC8DOC7RLSLmb+X1TVa1f+GMDFTmU6EzTJpI1Rcm9c/8exRq0KIzuSjzXfC6BywtlWIqp6a5stnM8O4Cui0mN6JLRpIYVtRqZwKkwM++nehm5GbVmUujX9cPo8+hySrzDT2+yxNXLpznTg91rAKb4Wfoa2UAoB3A3iOmV8AACL6MoDrAGSmFFqFEnztWkm16HUASGavjzonm7k31wJntv7EcQXu0l6/WYdm3L25COg8rh03Lhchp3NGR5+X6TomBR/X+Mf187htcaQ5Jssop+i5TDk1ecuUdlMKvQDCXUNeBnBpeAci+jCADwPAokX2Usk6uryOxE7ftDQT51/0Cpjd2ZE6Ashmj/c6CHe+/50A4FzYT2eXjnPg2lAzS9uzUULJJISa+ULaxt5sSQKXd57XF9t2bZdwzrhn6qI4kv5dqHHFZaO7ZKvHjaGny8OPy2Oxq512IMn9Zkm7ZTTrEjDr3h4zf5aZ+5i5b8GCBYkv8Gfvf2fLuo6pL4zL5bwOQk+XV1c7feu1y1JlJ6vjw93EuosT595xw/Lal9/ULKa3u4gXt6+t/Ru+/aoGYWFqBHLTpedZx62Eev+aJfAK+qejnMXrVuZTV9409k/duDyXc0fJ64tteqa6ENS0rFvpNxo6tH0t9my+oqm/i/AqI66xTJLGM6Z9b79mGT514/JJa2CThMlqtNNuK4WXAYQLxJ8L4JUsL6AL0bPRQdAWflNp833nzzcm4SihtvelYw11bVQBOpV1azN9qFmZKgJ2/GRFG04Zva6LcGvGWWabNYajaLq7PDDDeK/RdxGtKJpHIlKeWa+25CwgWwFtunaa6KOsx5A0uirunSR5Zy77tkP2sI1WZmaHIW6V59UBIuoE8K8ArgRQAvBdAP+ZmbUNWPv6+njv3r2pr6eLHw8XKYs2lFGCWJdJmmUoXTP3kDaEsd2/IFOVtOGhgpAnRLSPmfu0n7WTUgAAInofgLvhh6T+DTN/0rRvs0pBEARhJmJTCu1mPgIz/z2Av5/scQiCIMxE2s3RLAiCIEwiohQEQRCEGqIUBEEQhBqiFARBEIQabRd9lAQiOgrgpQSHvAXAD3MaTjsj9z1zmIn3DMzM+27mns9nZm3275RWCkkhor2mMKzpjNz3zGEm3jMwM+87r3sW85EgCIJQQ5SCIAiCUGOmKYXPTvYAJgm575nDTLxnYGbedy73PKN8CoIgCIKdmbZSEARBECyIUhAEQRBqzBilQES/TEQHieg5Ito82ePJCiI6j4ieIKLvE9EBIvqDYPt8IvoaEf1b8H9P6JjbgudwkIjWTN7om4OICkQ0RESPBL/PhHvuJqIHiOjZ4J3/7Ay5703B3/e/ENF9RDRnOt43Ef0NEb1GRP8S2pb4PoloFRHtDz77SyJyby3GzNP+H/wy3M8DeBuAWQBGAFw02ePK6N7OAXBJ8POb4PejuAjAfwewOdi+GcB/C36+KLj/2QAuCJ5LYbLvI+W9fxTAlwA8Evw+E+75CwB+O/h5FoDu6X7f8Nv0HgJQDH7fCeA3puN9A/hFAJcA+JfQtsT3CeBpAD8Lvx/YPwD4FdcxzJSVwrsBPMfMLzDzGQBfBnDdJI8pE5j5VWZ+Jvj5JwC+D/9LdB18AYLg/3XBz9cB+DIzn2bmQwCeg/98phREdC6AtQA+F9o83e/5zfCFxl8DADOfYeZRTPP7DugEUAwacXXB78g47e6bmf8JwLHI5kT3SUTnAHgzM3+HfQ3xxdAxscwUpdAL4Ejo95eDbdMKIloMYCWApwC8lZlfBXzFAeDsYLfp8izuBvBHAMZD26b7Pb8NwFEAfxuYzT5HRHMxze+bmUsA/hzAYQCvAnidmR/DNL/vEEnvszf4ObrdiZmiFHT2tGkVi0tEZwF4EMBGZv6xbVfNtin1LIjoagCvMfM+10M026bUPQd0wjct/C9mXgngBHxzgolpcd+BDf06+CaShQDmEtHNtkM026bcfTtgus+m7n+mKIWXAZwX+v1c+MvPaQERefAVwr3M/FCw+QfBMhLB/68F26fDs7gcwLVE9CJ8U+AVRHQPpvc9A/59vMzMTwW/PwBfSUz3+34vgEPMfJSZKwAeAvBzmP73rUh6ny8HP0e3OzFTlMJ3AVxIRBcQ0SwAHwCwa5LHlAlBVMFfA/g+M3869NEuALcEP98C4Kuh7R8gotlEdAGAC+E7paYMzHwbM5/LzIvhv8vHmflmTON7BgBm/ncAR4hoSbDpSgDfwzS/b/hmo8uIqCv4e78Svu9sut+3ItF9BiamnxDRZcHz+vXQMfFMtre9hV7998GPzHkewMcnezwZ3tfPw18a/jOA4eDf+wD8FIBvAPi34P/5oWM+HjyHg0gQldCO/wC8BxPRR9P+ngGsALA3eN+DAHpmyH1vA/AsgH8B8HfwI26m3X0DuA++36QCf8b/oTT3CaAveFbPA/gMguoVLv+kzIUgCIJQY6aYjwRBEAQHRCkIgiAINUQpCIIgCDVEKQiCIAg1RCkIgiAINUQpCEKGBKUnLorZ5/NEdL1m+2Ii+s/5jU4Q4hGlIAgZwsy/zczfS3n4YgCiFIRJRZSCIGggoj8ioo8EP99FRI8HP19JRPcQ0VVE9B0ieoaI7g9qT4GIvklEfcHPHyKifw22/R8i+kzoEr9IRN8mohdCq4btAH6BiIaJaFMLb1cQaohSEAQ9/wTgF4Kf+wCcFdSY+nkA+wFsAfBeZr4EfobxR8MHE9FCAH8C4DIA/wnA0sj5zwnOdTV8ZQD4xe2+xcwrmPmuzO9IEBzonOwBCEKbsg/AKiJ6E4DTAJ6Brxx+AX7NmYsA7AkaWs0C8J3I8e8G8I/MfAwAiOh+AO8IfT7IzOMAvkdEb83zRgQhCaIUBEEDM1eCKqy/CeDb8GsNrQbwdvhdwL7GzDdZThHX/vB0gn0FoWWI+UgQzPwTgD8M/v8WgN+BX3DwSQCXE9HPAEBQvfMdkWOfBvBLRNQTdAtb73C9n8BvqSoIk4YoBUEw8y34tv/vMPMPAJyCb/M/Cr9H8H1E9M/wlUSdz4D9bmF/Br8L3tfhl7h+PeZ6/wxgjIhGxNEsTBZSJVUQcoKIzmLmN4KVwlcA/A0zf2WyxyUINmSlIAj5sZWIhuHXtT8Ev/+BILQ1slIQBEEQashKQRAEQaghSkEQBEGoIUpBEARBqCFKQRAEQaghSkEQBEGo8f8DoYFZxKhzSBQAAAAASUVORK5CYII=",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "n_items = 1000\n",
    "min_w = 10\n",
    "max_w = min_w * 100\n",
    "weight = np.random.randint(min_w, max_w+1, n_items).astype(int)\n",
    "profit = ((np.random.random(n_items)) * weight).astype(int) \n",
    "item_idx = np.arange(n_items)\n",
    "\n",
    "min_p = np.min(profit)\n",
    "max_p = np.max(profit)\n",
    "mean_p = np.mean(profit)\n",
    "mean_w = np.mean(weight)\n",
    "\n",
    "W = int(mean_w * n_items * 0.6)\n",
    "print(\"Number of items:\",n_items)\n",
    "print(\"Total knapsack capacity:\", W)\n",
    "print(min_w, mean_w, max_w)\n",
    "print(min_p, mean_p, max_p)\n",
    "plt.scatter(x=weight, y=profit)\n",
    "plt.xlabel(\"weight\")\n",
    "plt.ylabel(\"profit\")\n",
    "plt.title(\"Distribution of Items\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initial Population Generation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Population size: 10000\n",
      "Mean profit: 126847.301\n",
      "Max. profit: 145100\n"
     ]
    }
   ],
   "source": [
    "population_size = 10000\n",
    "n_generations = 1\n",
    "init_population = np.random.randint(0, 2, (int(population_size*1.5),n_items), dtype=bool)\n",
    "init_population = list(filter(lambda chromosome: np.sum(chromosome * weight) <= W, init_population))[:population_size]\n",
    "init_profits = np.sum(np.array(init_population) * profit, axis=1)\n",
    "init_mean_profit = np.mean(init_profits)\n",
    "init_max_profit = np.max(init_profits)\n",
    "print(\"Population size:\", len(init_population))\n",
    "print(\"Mean profit:\", init_mean_profit)\n",
    "print(\"Max. profit:\", init_max_profit)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Greedy Heuristic Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#selected items: 598 total weight: 303406 total profit: 212316\n"
     ]
    }
   ],
   "source": [
    "ratio = profit/weight\n",
    "sorted_item_idx = sorted(item_idx, key=lambda x: ratio[x], reverse=True)\n",
    "total_w = 0\n",
    "total_p = 0\n",
    "knapsack = []\n",
    "for i in sorted_item_idx:\n",
    "    if total_w + weight[i] <= W:\n",
    "        knapsack.append(i)\n",
    "        total_w += weight[i]\n",
    "        total_p += profit[i]\n",
    "print(\"#selected items:\",len(knapsack), \"total weight:\",total_w, \"total profit:\",total_p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "spark.stop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spark Session"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#parallel processors: 2\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "\n",
       "        <div>\n",
       "            <p><b>SparkContext</b></p>\n",
       "\n",
       "            <p><a href=\"http://DESKTOP-192JFUF:4040\">Spark UI</a></p>\n",
       "\n",
       "            <dl>\n",
       "              <dt>Version</dt>\n",
       "                <dd><code>v3.0.1</code></dd>\n",
       "              <dt>Master</dt>\n",
       "                <dd><code>local[2]</code></dd>\n",
       "              <dt>AppName</dt>\n",
       "                <dd><code>test</code></dd>\n",
       "            </dl>\n",
       "        </div>\n",
       "        "
      ],
      "text/plain": [
       "<SparkContext master=local[2] appName=test>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n_processors = 2\n",
    "spark = SparkSession.builder \\\n",
    "       .master(f\"local[{n_processors}]\") \\\n",
    "       .appName(\"test\") \\\n",
    "       .config(\"spark.driver.memory\", \"5g\")\\\n",
    "       .getOrCreate()\n",
    "sc = spark.sparkContext\n",
    "sql_context = SQLContext(sc)\n",
    "sql_context.setConf(\"spark.sql.execution.arrow.pyspark.enabled\", \"true\")\n",
    "print(\"#parallel processors:\", sc.defaultParallelism)\n",
    "sc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "spark.stop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('spark.app.name', 'test'),\n",
       " ('spark.driver.host', 'DESKTOP-192JFUF'),\n",
       " ('spark.driver.port', '51296'),\n",
       " ('spark.rdd.compress', 'True'),\n",
       " ('spark.serializer.objectStreamReset', '100'),\n",
       " ('spark.submit.pyFiles', ''),\n",
       " ('spark.executor.id', 'driver'),\n",
       " ('spark.submit.deployMode', 'client'),\n",
       " ('spark.driver.memory', '5g'),\n",
       " ('spark.ui.showConsoleProgress', 'true'),\n",
       " ('spark.master', 'local[1]'),\n",
       " ('spark.app.id', 'local-1610877049907')]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "spark.sparkContext._conf.getAll() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parallel GA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24.75 169187.7 174506\n"
     ]
    }
   ],
   "source": [
    "def produce_new_generation(i, sub_population):\n",
    "    global gn, migration_period\n",
    "    population_lst = list(sub_population) \n",
    "    pop_size = len(population_lst)\n",
    "    \n",
    "    if gn > migration_period and gn % migration_period == 0:\n",
    "        print(i, gn)\n",
    "        try:\n",
    "            best_individuals = [pickle.load(open(f\"best{part_id}.pkl\", \"rb\")) for part_id in range(n_partitions) if part_id != i]\n",
    "            population_lst.extend(best_individuals)\n",
    "        except:\n",
    "            print(\"Other executor is writing on the file right now\")\n",
    "            print(\"Waiting for 0.001 seconds\")\n",
    "            sleep(0.001)\n",
    "            best_individuals = [pickle.load(open(f\"best{part_id}.pkl\", \"rb\")) for part_id in range(n_partitions) if part_id != i]\n",
    "            population_lst.extend(best_individuals)\n",
    "\n",
    "        \n",
    "    mating_pool = []\n",
    "    for _i in range(pop_size):\n",
    "        parent_1, parent_2 = random.choices(population_lst, k=2)\n",
    "        selected_p = random.choices([parent_1, parent_2], k=1, weights=[parent_1['profit'], parent_2['profit']])[0]\n",
    "        mating_pool.append(selected_p)\n",
    "    \n",
    "    new_generation = []\n",
    "\n",
    "    iter_pool = iter(mating_pool)\n",
    "    p1 = next(iter_pool)\n",
    "    best_individual = p1\n",
    "    new_gen_profits = []\n",
    "   \n",
    "    while p1:\n",
    "        p2 = next(iter_pool, False)\n",
    "        if not p2:\n",
    "            break\n",
    "        c1, c2 = generate_children(i, p1, p2, n_trials=10)\n",
    "        i1, i2 = choose(p1, p2, c1, c2)\n",
    "\n",
    "        if i1.profit > best_individual.profit:\n",
    "            best_individual = i1\n",
    "        elif i2.profit > best_individual.profit:   \n",
    "            best_individual = i2\n",
    "        \n",
    "        if (W - i1.weight)/W > random.random():\n",
    "            i1 = mutation(i1)\n",
    "        elif (W - i2.weight)/W > random.random():\n",
    "            i2 = mutation(i2)\n",
    "            \n",
    "        new_generation.extend([i1, i2])\n",
    "        new_gen_profits.extend([i1.profit, i2.profit])\n",
    "        \n",
    "        p1 = next(iter_pool, False)\n",
    "    \n",
    "    with open(f\"best{i}.pkl\", \"wb\") as f:\n",
    "        pickle.dump(best_individual, f)\n",
    "        f.close()\n",
    "    if save_population:\n",
    "        with open(f\"sub_population_{i}.csv\", \"a\") as f:\n",
    "            wr = csv.writer(f, dialect='excel')\n",
    "            wr.writerow(new_gen_profits)\n",
    "\n",
    "    return new_generation\n",
    "\n",
    "def generate_children(i, parent_1, parent_2, n_trials):\n",
    "    for i in range(n_trials):\n",
    "        child_1, child_2 = crossover(i, parent_1, parent_2)\n",
    "        if child_1.weight <= W and child_2.weight <= W:\n",
    "            return child_1, child_2\n",
    "    return parent_1, parent_2\n",
    "\n",
    "def choose(parent_1, parent_2, child_1, child_2):\n",
    "    return sorted([parent_1, parent_2, child_1, child_2], key=lambda i: -i.profit)[:2]\n",
    "\n",
    "def crossover(i, parent_1, parent_2, n_splits=1):\n",
    "    split = next(splits[i%4]())\n",
    "    new_chrom_1 = np.hstack((parent_1.chromosome[:split], parent_2.chromosome[split:]))\n",
    "    new_chrom_2 = np.hstack((parent_2.chromosome[:split], parent_1.chromosome[split:]))    \n",
    "    child_1 = Row(chromosome=new_chrom_1, profit=int(np.sum(new_chrom_1 * profit)), weight=int(np.sum(new_chrom_1 * weight)))\n",
    "    child_2 = Row(chromosome=new_chrom_2, profit=int(np.sum(new_chrom_2 * profit)), weight=int(np.sum(new_chrom_2 * weight)))\n",
    "    return child_1, child_2\n",
    "\n",
    "def s0():\n",
    "    yield np.random.randint(0, n_items*0.25)\n",
    "def s1():\n",
    "    yield np.random.randint(n_items*0.25, n_items*0.5)\n",
    "def s2():\n",
    "    yield np.random.randint(n_items*0.5, n_items*0.75)\n",
    "def s3():\n",
    "    yield np.random.randint(n_items*0.75, n_items)\n",
    "    \n",
    "splits = {0: s0, 1:s1, 2:s2, 3:s3}\n",
    "\n",
    "def mutation(individual, n_trials=5):\n",
    "    n_genes_to_be_mutated = int((W - individual.weight) / mean_w)\n",
    "    for x in range(n_trials):\n",
    "        new_chro = individual.chromosome.copy()\n",
    "        selected_genes = random.choices((new_chro == False).nonzero()[0], k=n_genes_to_be_mutated)\n",
    "        new_chro[selected_genes] = True\n",
    "        new_w = int(np.sum(new_chro * weight))\n",
    "        if new_w <= W:\n",
    "            new_p = int(np.sum(new_chro * profit))\n",
    "            return Row(chromosome=new_chro, profit=new_p, weight=new_w)\n",
    "        else:\n",
    "            del new_chro\n",
    "    return individual\n",
    "\n",
    "def increment_generation_time(x):\n",
    "    global generation_no\n",
    "    generation_no.add(1/n_partitions)\n",
    "\n",
    "\n",
    "results = []\n",
    "periods = [2, 4, 8, 16, 32]\n",
    "n_generations = 64\n",
    "n_partitions = 4\n",
    "save_population = False\n",
    "for p in periods:      \n",
    "    st = time()\n",
    "\n",
    "    rdd_of_rows = sc.parallelize([Row(chromosome=chromosome, \n",
    "                                      profit=int(np.sum(chromosome * profit)), \n",
    "                                      weight=int(np.sum(chromosome * weight))) \n",
    "                                  for chromosome in init_population],\n",
    "                                 n_partitions)\n",
    "\n",
    "    migration_period = p\n",
    "    generation_no = sc.accumulator(1.0)\n",
    "    migrant_freq = 1/migration_period \n",
    "\n",
    "    for gen in range(1, n_generations+1):\n",
    "        gn = generation_no.value\n",
    "        rdd_of_rows = rdd_of_rows.mapPartitionsWithIndex(produce_new_generation)\n",
    "        if gen > n_generations:\n",
    "            if gen%migration_period == 0:\n",
    "                rdd_of_rows.foreachPartition(increment_generation_time)\n",
    "            else:\n",
    "                generation_no.add(1)\n",
    "\n",
    "\n",
    "    result = rdd_of_rows.filter(lambda individual: individual.profit >= init_mean_profit ).collect() \n",
    "    result_profits = [i.profit for i in result]\n",
    "    mean_profit, max_profit = round(np.mean(result_profits),1), np.max(result_profits)\n",
    "    best_sol = max(result, key=lambda individual: individual.profit)\n",
    "    total_time = round(time() - st,2)\n",
    "    results.append([n_generations, migrant_freq, total_time, mean_profit, max_profit])\n",
    "    print(total_time, mean_profit, max_profit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20.09 169219.5 174134\n"
     ]
    }
   ],
   "source": [
    "st = time()\n",
    "\n",
    "rdd_of_rows = sc.parallelize([Row(chromosome=chromosome, \n",
    "                                  profit=int(np.sum(chromosome * profit)), \n",
    "                                  weight=int(np.sum(chromosome * weight))) \n",
    "                              for chromosome in init_population],\n",
    "                             n_partitions)\n",
    "n_generations = 25\n",
    "migration_period = 100\n",
    "generation_no = sc.accumulator(1.0)\n",
    "migrant_freq = 1/migration_period \n",
    "\n",
    "for gen in range(1, n_generations+1):\n",
    "    gn = generation_no.value\n",
    "    rdd_of_rows = rdd_of_rows.mapPartitionsWithIndex(produce_new_generation)\n",
    "    #if gen > n_generations:\n",
    "    #    if gen%migration_period == 0:\n",
    "    #        rdd_of_rows.foreachPartition(increment_generation_time)\n",
    "    #    else:\n",
    "    #        generation_no.add(1)\n",
    "\n",
    "result = rdd_of_rows.filter(lambda individual: individual.profit >= init_mean_profit ).collect() \n",
    "result_profits = [i.profit for i in result]\n",
    "mean_profit, max_profit = round(np.mean(result_profits),1), np.max(result_profits)\n",
    "best_sol = max(result, key=lambda individual: individual.profit)\n",
    "total_time = round(time() - st,2)\n",
    "results.append([n_generations, migrant_freq, total_time, mean_profit, max_profit])\n",
    "print(total_time, mean_profit, max_profit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>n_generations</th>\n",
       "      <th>migration_freq</th>\n",
       "      <th>time</th>\n",
       "      <th>mean_profit</th>\n",
       "      <th>max_profit</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>64</td>\n",
       "      <td>0.50000</td>\n",
       "      <td>307.24</td>\n",
       "      <td>194112.0</td>\n",
       "      <td>194112</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>64</td>\n",
       "      <td>0.25000</td>\n",
       "      <td>156.97</td>\n",
       "      <td>191451.0</td>\n",
       "      <td>191451</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>64</td>\n",
       "      <td>0.12500</td>\n",
       "      <td>85.90</td>\n",
       "      <td>186227.0</td>\n",
       "      <td>186227</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>64</td>\n",
       "      <td>0.06250</td>\n",
       "      <td>52.23</td>\n",
       "      <td>185028.0</td>\n",
       "      <td>185028</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>64</td>\n",
       "      <td>0.03125</td>\n",
       "      <td>40.07</td>\n",
       "      <td>186481.7</td>\n",
       "      <td>188272</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   n_generations  migration_freq    time  mean_profit  max_profit\n",
       "0             64         0.50000  307.24     194112.0      194112\n",
       "1             64         0.25000  156.97     191451.0      191451\n",
       "2             64         0.12500   85.90     186227.0      186227\n",
       "3             64         0.06250   52.23     185028.0      185028\n",
       "4             64         0.03125   40.07     186481.7      188272"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pd.DataFrame(results, columns=[\"n_generations\", \"migration_freq\", \"time\", \"mean_profit\", \"max_profit\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sequential GA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "88.87 181714 182610\n"
     ]
    }
   ],
   "source": [
    "def produce_new_generation(population_lst):\n",
    "    mating_pool = []\n",
    "    pop_size = len(population_lst)\n",
    "    for _i in range(pop_size):\n",
    "        parent_1, parent_2 = random.choices(population_lst, k=2)\n",
    "        selected_p = random.choices([parent_1, parent_2], k=1, weights=[parent_1.profit, parent_2.profit])[0]\n",
    "        mating_pool.append(selected_p)\n",
    "    \n",
    "    new_generation = []\n",
    "\n",
    "    iter_pool = iter(mating_pool)\n",
    "    p1 = next(iter_pool)\n",
    "    best_individual = p1\n",
    "    new_gen_profits = []\n",
    "   \n",
    "    while p1:\n",
    "        p2 = next(iter_pool)\n",
    "        c1, c2 = generate_children(p1, p2, n_trials=10)\n",
    "        i1, i2 = choose(p1, p2, c1, c2)\n",
    "\n",
    "        if i1.profit > best_individual.profit:\n",
    "            best_individual = i1\n",
    "        elif i2.profit > best_individual.profit:   \n",
    "            best_individual = i2\n",
    "        \n",
    "        if True:\n",
    "            if (W - i1.weight)/W > random.random():\n",
    "                i1 = mutation(i1)\n",
    "            elif (W - i2.weight)/W > random.random():\n",
    "                i2 = mutation(i2)\n",
    "            \n",
    "        new_generation.extend([i1, i2])\n",
    "        new_gen_profits.extend([i1.profit, i2.profit])\n",
    "        \n",
    "        p1 = next(iter_pool, False)\n",
    "    \n",
    "    return new_generation\n",
    "\n",
    "def generate_children(parent_1, parent_2, n_trials):\n",
    "    for i in range(n_trials):\n",
    "        child_1, child_2 = crossover(parent_1, parent_2)\n",
    "        if child_1.weight <= W and child_2.weight <= W:\n",
    "            return child_1, child_2\n",
    "    return parent_1, parent_2\n",
    "\n",
    "def choose(parent_1, parent_2, child_1, child_2):\n",
    "    return sorted([parent_1, parent_2, child_1, child_2], key=lambda i: -i.profit)[:2]\n",
    "\n",
    "def crossover(parent_1, parent_2):\n",
    "    split = np.random.randint(np.ceil(n_items/4), np.ceil(n_items*0.75))\n",
    "    new_chrom_1 = np.hstack((parent_1.chromosome[:split], parent_2.chromosome[split:]))\n",
    "    new_chrom_2 = np.hstack((parent_2.chromosome[:split], parent_1.chromosome[split:]))    \n",
    "    child_1 = Row(chromosome=new_chrom_1, profit=int(np.sum(new_chrom_1 * profit)), weight=int(np.sum(new_chrom_1 * weight)))\n",
    "    child_2 = Row(chromosome=new_chrom_2, profit=int(np.sum(new_chrom_2 * profit)), weight=int(np.sum(new_chrom_2 * weight)))\n",
    "    return child_1, child_2\n",
    "\n",
    "def mutation(individual, n_trials=5):\n",
    "    n_genes_to_be_mutated = int((W - individual.weight) / mean_w)\n",
    "    for x in range(n_trials):\n",
    "        new_chro = individual.chromosome.copy()\n",
    "        selected_genes = random.choices((new_chro == False).nonzero()[0], k=n_genes_to_be_mutated)\n",
    "        new_chro[selected_genes] = True\n",
    "        new_w = int(np.sum(new_chro * weight))\n",
    "        if new_w <= W:\n",
    "            new_p = int(np.sum(new_chro * profit))\n",
    "            return Row(chromosome=new_chro, profit=new_p, weight=new_w)\n",
    "        else:\n",
    "            del new_chro\n",
    "    return individual\n",
    "\n",
    "st = time()\n",
    "\n",
    "population = [Row(chromosome=chromosome, \n",
    "                  profit=int(np.sum(chromosome * profit)), \n",
    "                  weight=int(np.sum(chromosome * weight))) \n",
    "              for chromosome in init_population]\n",
    "\n",
    "for i in range(n_generations):\n",
    "    population = produce_new_generation(population)\n",
    "\n",
    "result2 = list(filter(lambda individual: individual.profit >= init_mean_profit, population))\n",
    "result_profits2 = [i.profit for i in result2]\n",
    "mean_profit2, max_profit2 = round(np.mean(result_profits2)), np.max(result_profits2)\n",
    "best_sol = max(result2, key=lambda individual: individual.profit)\n",
    "print(round(time() - st,2), mean_profit2, max_profit2)"
   ]
  },
  {
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}