{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The sGA best solution is: ((4, 5), [0, 0, 0, 0, 0])\n", "The cGA best solution is: ((5, 4), [1, 1, 1, 1, 1])\n" ] }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXsAAAEJCAYAAAB11IfBAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nO3deXQUVf428Kc7nc4GWTpNwARQwICAggtIlFUSHEUYHHWCoh4TYF5CRI4LIziOys9BzRBRRJIJx2E/DG5zCAYdODSLjDAiOzHsCohGEpIO2beuuu8fIa0thHRCd3VS9/n8Ezvd1fd+qePD5d6qWwYhhAAREema0dcdICIi72PYExFJgGFPRCQBhj0RkQQY9kREEmDYExFJwOTrDlxNfn5+q46zWq0oKirycG/aNhlrBuSsW8aaATnrbmnN0dHRTb7HkT0RkQQY9kREEmDYExFJgGFPRCQBhj0RkQQ0uxrniy++wJYtWyCEQHx8PB544AGtmiYikp4mI/sffvgBW7ZswZtvvon09HTs378f58+f16JpIiKCRiP7n376CTfeeCMCAgIAAH379sXu3bsxYcIEj7elfvgB7Od/hFJf7/L7w+YuyAvo7PH22gqj0Q+qqvi6G5qTsW4ZawZ0XndoBAz9bwMABJmMeKh/pMeb0CTsu3Xrhg8//BDl5eUwm804cOAAevXqddnnbDYbbDYbACAtLQ1Wq7XFbZUHBcFhMMDf39/l96vCBuF7fwsM3L6fiNoaAeDbYgCAJdgf/29kHwCAyWRqVQ5eiUGrh5ds3boVmzZtQmBgILp27Qp/f38kJSVd9RhP3kE7Y8P36BYWgNnDY1r1nW2djHcXAnLWLWPNgJx1e/IOWs0WaEePHo3Ro0cDAP71r38hMtLz/0y5GkUFjAZNmyQiajM0u/SytLQUAFBUVIRvvvkGw4YN06ppAIAqBPwMTHsikpNmI/sFCxagvLwcJpMJU6ZMQUhIiFZNAwAUVcCPdxUQkaQ0C/vXX39dq6auSBWAkSN7IpKUNGNdhdM4RCQxicIenMYhImlJE3+qypE9EclLmrBXhIAfr70kIknJE/a8zp6IJCZP2HOBlogkJkXYCyGgcoGWiCQmRfypl3b/4cieiGQlRdgrl/Z6M3LSnogkJUfYqw0//Zj1RCQpOcL+0siel14SkaykCHv10qQ95+yJSFZShL1yaYGWA3sikpUkYc9pHCKSmxxh75zG8XFHiIh8RIqwd15nz5E9EUlKirBvHNnz4SVEJCs5wt45svdtP4iIfEWK+FN46SURSU6OsBcMeyKSmxRhr3Iah4gkJ0X8cYGWiGQnR9g7b6rycUeIiHxEivj7ZddLjuyJSE4mrRrasGEDtm7dCoPBgG7duiE1NRVms1mTtlVul0BEktNkZG+32/Gf//wHaWlpWLBgAVRVxa5du7RoGsAvI3tmPRHJSrNpHFVVUVdXB0VRUFdXh4iICK2a5qWXRCQ9TaZxLBYLxo8fj+nTp8NsNmPgwIEYOHDgZZ+z2Wyw2WwAgLS0NFit1la1ZzKZXI4NKWn4abVEwGoNadV3tnW/rVkWMtYtY82AnHV7smZNwr6iogJ79uxBRkYGgoOD8c4772DHjh0YMWKEy+cSEhKQkJDgfF1UVNSq9qxWq8uxJaVlAICy0osoQnWrvrOt+23NspCxbhlrBuSsu6U1R0dHN/meJtM4ubm5iIqKQmhoKEwmE4YMGYITJ05o0TQALtASEWkS9larFSdPnkRtbS2EEMjNzUVMTIwWTQP49U1VmjVJRNSmaDKNExsbi7i4OMyePRt+fn644YYbXKZrvE3hfvZEJDnNrrNPTExEYmKiVs254K6XRCQ7Ke6gdW6ExqwnIklJEfaN19kbOY1DRJKSI+w5jUNEkpMj7LmfPRFJTor4UzmyJyLJSRH2zjl7Zj0RSUqOsFcbgt7AkT0RSUqOsBeCUzhEJDUpwl4VXJwlIrlJEYGKypE9EclNjrAXgjdUEZHU5Ah7lVslEJHc5Ah7LtASkeSkCHtVCC7QEpHUpIjAhuvsObInInnJEfZC8MElRCQ1OcJe5VYJRCQ3KcJe5QItEUlOnrCXolIioiuTIgK5QEtEspMj7DmNQ0SSkyTsuREaEclNighUuREaEUlOirDnRmhEJDuTFo3k5+fj3Xffdb4uLCxEYmIiHnjgAS2a50ZoRCQ9TcI+Ojoa6enpAABVVTFt2jTceeedWjQNgHfQEhFpPo2Tm5uLLl26oFOnTpq1qXJkT0SS02Rk/2s7d+7E0KFDr/iezWaDzWYDAKSlpcFqtbaqDZPJ5Hqs8SyCAgNb/X3twWU1S0LGumWsGZCzbk/WrGnYOxwO7Nu3D5MmTbri+wkJCUhISHC+LioqalU7VqvV5dg6hwOO+rpWf1978NuaZSFj3TLWDMhZd0trjo6ObvI9TadxDhw4gB49eiA8PFzLZrlAS0TS0zTsrzaF401coCUi2WkW9jU1NTh8+DCGDBmiVZNOvKmKiGSn2Zx9YGAgli1bplVzLhTB/eyJSG7S3EHLaRwikpkcYc8FWiKSnBRhr3JkT0SSkyLsFVXw4SVEJDXdh70QgvvZE5H0dB+Bqmj4yUsviUhmEoR9Q9oz7IlIZroPe+XSyN6o+0qJiJqm+whUVI7siYj0H/aNc/a6r5SIqGmtjsC6ujrU19d7si9eoXJkT0TkftivWrUKp06dAgDs378fycnJSE5Oxt69e73WOU9QGhdoeVMVEUnM7bD/6quv0K1bNwDAp59+imeeeQYvvvgi1q5d67XOeYKiNvxk1hORzNze9bK2thYBAQEoLy9HQUEB4uLiALT+aVJaUXjpJRGR+2EfHR2N//73vzh//jwGDBgAACgrK4PZbPZa5zyB0zhERC2YxpkyZQo2bdqEvLw8TJw4EQBw6NAhZ/C3VeqlaRzueklEMnN7ZH/jjTdi3rx5Lr8bPnw4hg8f7vFOeVLjyN7IkT0RScztsP/2228RFRWFqKgolJSUYM2aNTAajZg0aZLmDxBvCYUjeyIi96dxli5dCuOlPQdWrVoFRVFgMBiwZMkSr3XOE7hAS0TUgpG93W6H1WqFoig4dOgQMjMzYTKZMG3aNG/275o5b6riNA4RScztsA8KCsLFixdx7tw5dO3aFYGBgXA4HHA4HN7s3zVzboTGrCciibkd9vfddx9eeuklOBwOJCUlAQCOHTuGmJgYb/XNI3jpJRFRC8L+wQcfxJ133gmj0YguXboAACwWC1JSUrzWOU/grpdERC3cCK3xSpxdu3YBaAj7qKgor3TMU1TueklE5P7I/ocffsDf//53+Pv7o7i4GHfffTeOHDmCL7/8Es8991yzx1dWViIrKwvnzp2DwWDA9OnT0bt372vqvDs4siciakHYf/DBB5g4cSJGjBiB5ORkAEC/fv3cvvRy+fLluPXWW/HCCy/A4XCgtra2dT1uIedNVcx6IpKY25MbP/7442V3ywYGBqKurq7ZY6uqqnD06FGMHj0aAGAymRASEtLCrraO86Yqpj0RScztkX2nTp3w/fffo1evXs7fnTp1yrlYezWFhYUIDQ1FZmYmzp49i549eyIpKQmBgYEun7PZbLDZbACAtLQ0WK1Wd7vnwmQyOY8NLmpIe6vFAmtEUKu+rz34dc0ykbFuGWsG5KzbkzW7HfYTJ05EWloaxowZA4fDgXXr1mHz5s1u3VSlKApOnz6NyZMnIzY2FsuXL0d2djYeffRRl88lJCQgISHB+bq12ydbrVbnsaVl5QCAstISFCmVrfq+9uDXNctExrplrBmQs+6W1hwdHd3ke25P49xxxx34y1/+grKyMvTr1w8XLlzArFmzMHDgwGaPjYyMRGRkJGJjYwEAcXFxOH36tLtNX5PGBVojF2iJSGJuj+wBoEePHpg6dWqLGwkPD0dkZCTy8/MRHR2N3NxcdO3atcXf0xq8qYqIqAVh73A4sH37dpw5cwY1NTUu782YMaPZ4ydPnoxFixbB4XAgKioKqampLe9tK3DXSyKiFoT94sWLcfbsWdxxxx0ICwtrcUM33HAD0tLSWnzctVK56yURkfthf+jQISxevFizSyY95ZeHl/i4I0REPuR2BFqtVtTX13uzL17xyzQOR/ZEJC+3R/YjRoxAeno67r///sueTHXzzTd7vGOe8ssdtAx7IpKX22G/ceNGAMDatWtdfm8wGLB48WLP9sqDnA8c5zQOEUnM7bDPyMjwZj+8RhECBnBkT0Ryc3u8O3/+/Cv+/u233/ZYZ7xBFRzVExG5HYN5eXkt+n1boaiCo3oikl6z0zgfffQRgIabqhr/u1FBQQE6derknZ55iCIEr8QhIuk1G/bFxcUAAFVVnf/dyGq1IjEx0Ts98xCF0zhERM2HfeO2Br1793bZkbK9UFWO7ImIrhr2hYWFzmfM3nLLLSgoKLji5zp37uz5nnmIIgSM3ASNiCR31bCfNWsWFi1ahPDwcMycObPJz/12Lr8tUVRugkZEdNWwX7VqFZ566imsXLnSGejp6en485//rEnnPEERgtsbE5H0ml26FJe2G2h05MgRr3XGG1SO7ImImg97Qztf3FQEr7MnImr2ahxFUfDtt986X6uq6vIaaPsboXEah4hk12zYh4WF4R//+IfzdYcOHVxet/WN0LhAS0TkRti31w3QGqkc2RMRub83TnvFvXGIiGQIe8FpHCIi/Ye9ymkcIiL9hz1H9kRE+g97LtASEUkQ9lygJSJqwTNor9XTTz+NwMBAGI1G+Pn5IS0tTZN2uZ89EZGGYQ8Ar732GkJDQ7VssmGBliN7IpKc7se8Kh9LSESk7cj+jTfeAACMGTPmik+9stlssNlsAIC0tDRYrdZWtWMymX451nAawUEBrf6u9sKlZonIWLeMNQNy1u3Jmg3it3sYe4ndbofFYkFpaSnmzZuH5ORk9OvX76rH5Ofnt6otq9WKoqIiAMCUdacwsEsIZt51Xau+q734dc0ykbFuGWsG5Ky7pTVHR0c3+Z5m0zgWiwVAw8ZqgwcPxqlTpzRplwu0REQahX1NTQ2qq6ud/3348GF0795di6b5wHEiImg0Z19aWoq3334bQMP++MOGDcOtt96qRdN84DgRETQK+86dOyM9PV2Lpi7D/eyJiCS49FLhpZdERPoPe+6NQ0QkQdgrKsCsJyLZ6TrsVSEgAI7siUh6ug57RW34yQVaIpKdrsNevXRzMBdoiUh2ug57pTHsOY1DRJLTd9hfmsZh1hOR7PQd9hzZExEB0HvYq5yzJyICdB72l7Keu14SkfR0HYONI3s+cJyIZKfvsG8c2TPriUhyOg97LtASEQE6D3uVC7RERAB0HvaN0zhGXVdJRNQ8XccgL70kImqg77DnnD0REQCdh73KXS+JiADoPOwV7npJRARA92Hf8JMLtEQkO13HIBdoiYga6DvsBbdLICICdB72zgVaXVdJRNQ8TWNQVVW8+OKLSEtL06Y9LtASEQHQOOy/+OILxMTEaNYeF2iJiBpoFoPFxcXYv38/4uPjtWqSC7RERJeYtGpoxYoVeOKJJ1BdXd3kZ2w2G2w2GwAgLS0NVqu1VW2ZTCZYrVYEFygAgE6RFlhDA1v1Xe1FY82ykbFuGWsG5KzbkzVrEvb79u1DWFgYevbsiby8vCY/l5CQgISEBOfroqKiVrVntVpRVFSE0vJyAEDpxRKY6vxb9V3tRWPNspGxbhlrBuSsu6U1R0dHN/meJmF//Phx7N27FwcOHEBdXR2qq6uxaNEizJw506vtchqHiKiBJmE/adIkTJo0CQCQl5eHnJwcrwc98Kvr7LkRGhFJTtfXqSjcCI2ICICGC7SN+vfvj/79+2vSFrc4JpKXEAI1NTVQVRWGdjqVW1BQgNraWpffCSFgNBoRGBjYoro0D3stcYtjInnV1NTA398fJlP7jTmTyQQ/P7/Lfu9wOFBTU4OgoCC3v0vf0zjcG4dIWqqqtuugvxqTyQS1cTTrJknC3scdISLNtdepG3e1tD59h73aMIWj95NORNQcXYe9KgQXZ4moTXE4HHjrrbcwdOhQjBkzBmPGjMF7773n8pmNGzciJiYGJ0+e9Fi7ug57RRWcryeiNmX+/PkoKCjAli1bsHnzZqxbtw4Oh8PlM9nZ2bjzzjuxbt06j7Wrz9WLSxTBveyJCFA//ADi3GmPfqehWw8YH/3TVT9TVVWFadOm4eeff4aqqkhJScGaNWuwe/duBAY27NfVoUMHvPDCC85jKisrsWfPHnz88cdITk7G888/75H+6joKFVVwqwQi8plt27ahS5cusNls2Lp1K/r374+YmBh06NChyWM2bdqEUaNGoVevXoiIiMDhw4c90hddj+xVwWvsiQjNjsC95aabbsLrr7+ON954AwkJCejYsaPL+x999BH++c9/oqSkBOvXr0dMTAyys7MxdepUAMCDDz6I7OxsDBgw4Jr7ouuwV4TgvjhE5DO9evXCxo0bsXXrVsyfPx/Dhg3DTz/9hIqKCnTo0AETJ07ExIkTMXr0aKiqipKSEuzcuRPHjh2DwWBwXkv/yiuvXPNVhZzGISLykvPnzyMoKAgPP/wwUlJSkJubi8ceewwvv/wyampqAACKoqCurg4A8Pnnn+Phhx/GN998g927d+PAgQPo3r07du/efc190fnIngu0ROQ7x44dw7x582AwGODv74+33noL/fr1Q3p6OuLj4xESEoLAwED88Y9/ROfOnZGdnY2nn37a5TvGjh2L7OxsxMXFXVNfDEJcus20DcrPz2/VcY0b/s//7084e7EWGeN7erhnbY+MD3YA5KxbxpqBltddVVWF4OBgL/bI+0wm02WXZTa6Un1Xe3iJrse9quA0DhERoPOwVwRg1HWFRETu0XUUcoGWiKiBvsOeC7RERAB0HvYqR/ZERAB0Hva8qYqIqIG+w17ldglE1Pb8+9//RkJCAu655x4kJCRg1qxZKC0tdb5vt9tx/fXXY+XKlR5rU99hz0sviaiN2bZtGz744AOsXr0a27Ztw6ZNmzBo0CBcuHDB+ZmcnBzcfvvt3OLYXQ0PL/F1L4jI1/65twCnS2o8+p09IgIxdVDnZj/3ySefYMmSJQCAvn374scff8Qrr7yC6667DgDg5+eHRx991OWY9evX49VXX8WMGTOQn59/1Zul3KXrsFdUPmyciHzn+PHjeO+99/DZZ5/BYrGgpKQEw4YNwy233NLkMT/99BMKCgpw22234fe//z0+++wzpKSkXHNf9B32fCwhEQFujcC9YefOnRg3bhwsFgsAICIiwuX9o0ePYubMmaisrMTs2bMxYcIE5OTkYPz48QAatjh+9tln20/Y19XV4bXXXoPD4YCiKIiLi0NiYqLX2+UCLRG1Nb1790Zubi6GDh2Kvn37YvPmzS67YGZnZ+PChQtYt24dDAYDzp8/j++//x49e17bHl+azGj7+/vjtddeQ3p6OubPn4+DBw/ixIkTXm+Xe+MQkS8NHToUGzZsgN1uBwCUlJRgxowZ+Nvf/uay0WNj0H/33XeorKzEvn37sHv3buzduxczZszA+vXrr7kvmozsDQaD83mLiqJAUZRr3oi/Kc//5wwU/ABFceBCZT36RQV5pR0ioub06dMHM2fOxCOPPAKj0Yibb74ZCxcuRHFxMZ588kkoioLQ0FDcdNNNGDVqFNasWYP777/f5TvGjh2L6dOn47nnnrumvmi2xbGqqpg9ezbOnz+P3/3ud3jiiScu+4zNZoPNZgMApKWlOTf0b4n/23gcDgGIS094+cOA63BHt/Br63w7cLWtUPVMxrplrBloed0FBQUICAjwYo98q7a2Fp07u65FmM3mJj+v+X72lZWVePvtt5GcnIzu3btf9bPXup+9TGSsGZCzbhlrBrif/W+1+f3sQ0JC0L9/fxw8eFDrpomIpKVJ2JeVlaGyshJAw5U5hw8fRkxMjBZNE5Gk2vBD+DyipfVpskBbUlKCjIwMqKoKIQTuuusu3HHHHVo0TUSSMhqNcDgcMJn0dzuRw+GAsYVPZtLkT+H666/H/PnztWiKiAgAEBgYiJqaGtTW1nrt6j9vCwgIQG1trcvvhBAwGo3OKxzdpb+/8oiI0HDJd1BQ+7702pOL8dwmjIhIAgx7IiIJMOyJiCSg+U1VRESkPV2O7OfMmePrLmhOxpoBOeuWsWZAzro9WbMuw56IiFwx7ImIJOA3d+7cub7uhDdc60b/7ZGMNQNy1i1jzYCcdXuqZi7QEhFJgNM4REQSYNgTEUlAV3vjHDx4EMuXL4eqqoiPj8eDDz7o6y55RVFRETIyMnDx4kUYDAYkJCRg7NixqKiowLvvvosLFy6gU6dOeO6559ChQwdfd9ejVFXFnDlzYLFYMGfOHBQWFmLhwoUoLy9Hz5498cwzz+hul8PKykpkZWXh3LlzMBgMmD59OqKjo3V9rjds2ICtW7fCYDCgW7duSE1NxcWLF3V3rjMzM7F//36EhYVhwYIFANDk/8dCCCxfvhwHDhxAQEAAUlNTWzafL3RCURQxY8YMcf78eVFfXy9mzZolzp075+tueYXdbhffffedEEKIqqoqMXPmTHHu3DmxevVqsW7dOiGEEOvWrROrV6/2ZTe9IicnRyxcuFC89dZbQgghFixYIL766ishhBBLliwRmzZt8mX3vOL9998XNptNCCFEfX29qKio0PW5Li4uFqmpqaK2tlYI0XCOt23bpstznZeXJ7777jvx/PPPO3/X1Lndt2+feOONN4SqquL48ePipZdealFbupnGOXXqFLp06YLOnTvDZDLh7rvvxp49e3zdLa+IiIhw/o0eFBSEmJgY2O127NmzByNHjgQAjBw5Unf1FxcXY//+/YiPjwfQsNVrXl4e4uLiAACjRo3SXc1VVVU4evQoRo8eDaDhMXUhISG6P9eqqqKurg6KoqCurg7h4eG6PNf9+vW77F9kTZ3bvXv3YsSIETAYDOjduzcqKytRUlLidlvt+99Av2K32xEZGel8HRkZiZMnT/qwR9ooLCzE6dOnceONN6K0tBQREREAgPDwcJSWlvq4d561YsUKPPHEE6iurgYAlJeXIzg4GH5+fgAAi8UCu93uyy56XGFhIUJDQ5GZmYmzZ8+iZ8+eSEpK0vW5tlgsGD9+PKZPnw6z2YyBAweiZ8+euj/XjZo6t3a7HVar1fm5yMhI2O1252ebo5uRvYxqamqwYMECJCUlXfbgYYPB0G4f2HAl+/btQ1hYmHTXWSuKgtOnT+Pee+/F/PnzERAQgOzsbJfP6O1cV1RUYM+ePcjIyMCSJUtQU1Mj7TOrPXludTOyt1gsKC4udr4uLi6GxWLxYY+8y+FwYMGCBRg+fDiGDBkCAAgLC0NJSQkiIiJQUlKC0NBQH/fSc44fP469e/fiwIEDqKurQ3V1NVasWIGqqiooigI/Pz/Y7XbdnfPIyEhERkYiNjYWABAXF4fs7Gxdn+vc3FxERUU5axoyZAiOHz+u+3PdqKlza7FYXB5k0tKM083IvlevXvj5559RWFgIh8OBXbt2YdCgQb7ullcIIZCVlYWYmBiMGzfO+ftBgwbhyy+/BAB8+eWXGDx4sK+66HGTJk1CVlYWMjIy8Oyzz+Lmm2/GzJkz0b9/f3z99dcAgO3bt+vunIeHhyMyMhL5+fkAGoKwa9euuj7XVqsVJ0+eRG1tLYQQzpr1fq4bNXVuBw0ahB07dkAIgRMnTiA4ONjtKRxAZ3fQ7t+/HytXroSqqrjnnnvw0EMP+bpLXnHs2DG8+uqr6N69u/OfeI899hhiY2Px7rvvoqioSJeX4zXKy8tDTk4O5syZg4KCAixcuBAVFRXo0aMHnnnmGfj7+/u6ix515swZZGVlweFwICoqCqmpqRBC6Ppcf/zxx9i1axf8/Pxwww03ICUlBXa7XXfneuHChThy5AjKy8sRFhaGxMREDB48+IrnVgiBpUuX4tChQzCbzUhNTUWvXr3cbktXYU9ERFemm2kcIiJqGsOeiEgCDHsiIgkw7ImIJMCwJyKSAMOeSGNPPvkkCgoKfN0NkgwvvaR2aefOnfj8889x7tw5BAQEICoqCiNHjsS9997bprYOmDt3LoYPH+7cvI3IV3SzXQLJIycnB5999hmmTJmCgQMHIjAwEGfOnEFOTg5Gjx6t2Y02jbfuE7UHHNlTu1JVVYVp06bh6aefdm53+1v19fVYu3Yt/ve//8HhcGDw4MFISkqC2WxGXl4e3n//fTzwwANYv349jEYjHnvsMdxzzz1uH3vffffh888/x4ABA5CcnIzFixfj5MmTUFUVffr0wZ/+9CdERkZi7dq1yM7OhslkgtFoxKhRozBlyhQkJiZi0aJF6NKlC6qqqrBs2TLnAyni4+Pxhz/8AUajEdu3b8eWLVsQGxuLbdu2ITg4GFOnTsVtt92m5R856QTn7KldOXHiBOrr66+6F8yaNWvw888/Iz09HYsWLYLdbsenn37qfP/ixYuoqqpCVlYWUlJSsHTpUlRUVLh9bEVFBTIzMzFt2jQIITBq1ChkZmYiMzMTZrMZS5cuBdCwhUXfvn0xefJkrF69GlOmTLmsr8uWLUNVVRUWL16MuXPnYseOHdi+fbvz/VOnTiE6OhpLly7FhAkTkJWVBY7PqDUY9tSulJWVoWPHji7TJ3/961+RlJSExx9/HEeOHMGWLVvw1FNPoUOHDggKCsJDDz2EnTt3Oj/v5+eHRx55BCaTCbfffjsCAwORn58PIUSzxxoMBiQmJsLf3x9msxkdO3ZEXFwcAgICnJ8/evSoW7WoqoqdO3di0qRJCAoKQlRUFMaNG4cdO3Y4P2O1WpGQkACj0YiRI0eipKREV3vXk3Y4Z0/tSseOHVFeXu4yXz5v3jwAQEpKCi5evIja2lrMmTPHeYwQAqqqunzHr/+yCAgIQE1NDcrKypo9NjQ0FGaz2fm6trYWK1euxMGDB1FZWQkAqK6uhqqqMBqvPpYqKyuDoiguD6To1KmTy0M5wsPDXfoJNDzHgKilGPbUrvTu3Rv+/v7Ys2fPFefsG8P4nXfeafF+5x07dmz22N9e6ZOTk4P8/Hy8+eabCA8Px5kzZ/Diiy86p1qudiLvU3YAAAFASURBVGVQaGgo/Pz8UFRUhK5duwJoeJi8XvdpJ9/iNA61KyEhIXjkkUewdOlSfP31185R9JkzZ1BbWwuDwYD4+HisWLHC5XFu7jzpyGg0tvjYmpoamM1mBAcHo6KiAp988onL+2FhYU1eU280GnHXXXdh7dq1qK6uxoULF7BhwwYMHz7c3T8OIrdxZE/tzoQJE2CxWLB+/XosXrwYAQEB6Ny5Mx5//HH06dMHsbGx+PTTT/Hyyy+jvLwcFosFY8aMwa233trsdz/++OMtOnbs2LFYtGgRpkyZAovFgnHjxrk8CHvs2LHIyMjA5s2bMXz4cEyePNnl+MmTJ2PZsmWYMWMGzGYz4uPjnVcGEXkSL70kIpIAp3GIiCTAsCcikgDDnohIAgx7IiIJMOyJiCTAsCcikgDDnohIAgx7IiIJ/H9e0Ytt4D4glgAAAABJRU5ErkJggg==\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "################################################################################\n", "## Imports\n", "\n", "from random import random\n", "from pyeasyga import pyeasyga\n", "import matplotlib as mpl\n", "import matplotlib.pyplot as plt\n", "plt.style.use('ggplot')\n", "\n", "################################################################################\n", "## Common code\n", "\n", "# Data\n", "data = [0] * 5\n", "\n", "# Define fitness function A (ftrap5)\n", "def ff_a(individual, data=None):\n", " u = sum(individual)\n", " if u < 5:\n", " return 4 - u\n", " return 5\n", "\n", "# Define fitness function B (invftrap5)\n", "def ff_b(individual, data=None):\n", " u = sum(individual)\n", " if u > 0:\n", " return u - 1\n", " return 5\n", "\n", "# Define the main fitness function\n", "def fitness_function(individual, data=None):\n", " return (ff_a(individual, data), ff_b(individual, data))\n", "\n", "################################################################################\n", "## Simple Genetic Algorithm (sGA)\n", "\n", "# Best score progress\n", "progress_sga = []\n", "\n", "# Initialize genetic algorithm\n", "sga = pyeasyga.GeneticAlgorithm(data)\n", "\n", "# Set fitness function\n", "sga.fitness_function = fitness_function\n", "\n", "# Sort function: fast non-dominated sort\n", "def nsgaii(population):\n", " # Initialize the sorted population\n", " front = [[]]\n", " # Initialize the set of solutions that are dominated\n", " s = [[] for i in range(len(population))]\n", " # Initialize the number of solutions which dominate an individual\n", " n = [0 for i in range(len(population))]\n", " # Initialize the rank of solutions\n", " rank = [0 for i in range(len(population))]\n", " # Looks for the `p`-dominated solutions and\n", " # calculates the degree of domination over `p`\n", " for p in range(len(population)):\n", " s[p] = []\n", " n[p] = 0\n", " # Get `p` fitness\n", " pfa, pfb = population[p].fitness\n", " for q in range(len(population)):\n", " # Get `q` fitness\n", " qfa, qfb = population[q].fitness\n", " # Check which dominates which\n", " if ((pfa > qfa and pfb > qfb) or (pfa >= qfa and pfb > qfb)\n", " or (pfa > qfa and pfb >= qfb)):\n", " s[p].append(q)\n", " elif ((qfa > pfa and qfb > pfb) or (qfa >= pfa and qfb > pfb)\n", " or (qfa > pfa and qfb >= pfb)):\n", " n[p] += 1\n", " # Check if `p` belongs to the fisrt front\n", " if n[p] == 0:\n", " rank[p] = 0\n", " if p not in front[0]:\n", " front[0].append(p)\n", " # Initiliaze the front counter\n", " i = 0\n", " while front[i] != []:\n", " aux = []\n", " for p in front[i]:\n", " for q in s[p]:\n", " n[q] = n[q] - 1\n", " if n[q] == 0:\n", " rank[q] = i + 1\n", " if q not in aux:\n", " aux.append(q)\n", " i += 1\n", " front.append(aux)\n", " # Remove the last set of individuals\n", " del front[len(front) - 1]\n", " # Convert to a usual population list\n", " sorted_pop = []\n", " for f in front:\n", " for i in f:\n", " sorted_pop.append(population[i])\n", " return sorted_pop\n", "\n", "# Set rank population function (now it uses NSGA-II algorithm)\n", "def rank_population(self):\n", " self.current_generation = nsgaii(self.current_generation)\n", "sga.rank_population = rank_population\n", "\n", "# Set initial population generation function (fix rank population call)\n", "def create_first_generation(self):\n", " self.create_initial_population()\n", " self.calculate_population_fitness()\n", " self.rank_population(self)\n", "sga.create_first_generation = create_first_generation\n", "\n", "# Set next population generation function (fix rank population call)\n", "def create_next_generation(self):\n", " self.create_new_population()\n", " self.calculate_population_fitness()\n", " self.rank_population(self)\n", "sga.create_next_generation = create_next_generation\n", "\n", "# Set evolution function\n", "def run(self):\n", " self.create_first_generation(self)\n", " for _ in range(1, self.generations):\n", " self.create_next_generation(self)\n", " fitness, _ = sga.best_individual()\n", " fa, fb = fitness\n", " progress_sga.append((fa + fb))\n", "sga.run = run\n", "\n", "# Run sGA\n", "sga.run(sga)\n", "# Get best individual\n", "result = sga.best_individual()\n", "# Print result\n", "print('The sGA best solution is: {}'.format(result))\n", "\n", "################################################################################\n", "## Compact Genetic Algorithm (cGA)\n", "\n", "# Best score progress\n", "progress_cga = []\n", "\n", "# Initialize genetic algorithm\n", "cga = pyeasyga.GeneticAlgorithm(data)\n", "\n", "# Update probability vector\n", "def update_prob(winner, loser, prob, popsize):\n", " for i in range(0, len(prob)):\n", " if winner[i] != loser[i]:\n", " if winner[i] == 1:\n", " prob[i] += 1.0 / float(popsize)\n", " else:\n", " prob[i] -= 1.0 / float(popsize)\n", "\n", "# Create a new individual\n", "def create_individual(prob):\n", " individual = []\n", " for p in prob:\n", " if random() < p:\n", " individual.append(1)\n", " else:\n", " individual.append(0)\n", " return pyeasyga.Chromosome(individual)\n", "cga.create_individual = create_individual\n", "\n", "# Make competition between two individuals\n", "def compete(a, b):\n", " pfa, pfb = a.fitness\n", " qfa, qfb = b.fitness\n", " if ((pfa > qfa and pfb > qfb) or (pfa >= qfa and pfb > qfb)\n", " or (pfa > qfa and pfb >= qfb)):\n", " return a, b\n", " else:\n", " return b, a\n", "\n", "# Set fitness function\n", "cga.fitness_function = fitness_function\n", "\n", "# Set evolution function\n", "def run(self):\n", " # Initialize probability vector\n", " prob = [0.5] * len(self.seed_data)\n", " # Initialize best solution\n", " best = None\n", " # Run `i` generations\n", " for _ in range(0, self.generations):\n", " # Create individuals\n", " a = self.create_individual(prob)\n", " b = self.create_individual(prob)\n", " # Calculate fitness for each individual\n", " a.fitness = self.fitness_function(a.genes)\n", " b.fitness = self.fitness_function(b.genes)\n", " # Get the best and worst individual\n", " winner, loser = compete(a, b)\n", " # Update best solution\n", " if best:\n", " if winner.fitness > best.fitness:\n", " best = winner\n", " else:\n", " best = winner\n", " # Update the probability vector based on the success of each bit\n", " update_prob(winner.genes, loser.genes, prob, self.population_size)\n", " fa, fb = best.fitness\n", " progress_cga.append((fa + fb))\n", " # Add final solution\n", " self.current_generation.append(best)\n", "cga.run = run\n", "\n", "# Run evolution\n", "cga.run(cga)\n", "# Get best individual\n", "result = cga.best_individual()\n", "# Print result\n", "print('The cGA best solution is: {}'.format(result))\n", "\n", "################################################################################\n", "## Plot comparison chart\n", "\n", "line_sga, = plt.plot(progress_sga, label='sGA')\n", "line_cga, = plt.plot(progress_cga, label='cGA')\n", "plt.legend([line_sga, line_cga], ['sGA', 'cGA'])\n", "plt.xlabel('Generation')\n", "plt.ylabel('Fitness')\n", "plt.show()\n", "\n", "################################################################################" ] } ], "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.2" } }, "nbformat": 4, "nbformat_minor": 4 }