Genetic-Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import xgboost as xgb\n",
    "\n",
    "from copy import copy\n",
    "import datetime\n",
    "import pickle\n",
    "from geopy.geocoders import Nominatim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Open saved XGBoost Model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "filename = \"xgb_model.sav\"\n",
    "loaded_model = pickle.load(open(filename, 'rb'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Genetic Algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Sample date\n",
    "date_list = [5, 8, 2016] # May 8, 2016\n",
    "\n",
    "year = int(date_list[2])\n",
    "month = int(date_list[1])\n",
    "day = int(date_list[0])\n",
    "\n",
    "my_date = datetime.date(year, month, day)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Sample test locations\n",
    "\n",
    "test_locations = {'L1': (40.819688, -73.915091),\n",
    "                  'L2': (40.815421, -73.941761),\n",
    "                  'L3': (40.764198, -73.910785),\n",
    "                  'L4': (40.768790, -73.953285),\n",
    "                  'L5': (40.734851, -73.952950),\n",
    "                  'L6': (40.743613, -73.977998),\n",
    "                  'L7': (40.745313, -73.993793),\n",
    "                  'L8': (40.662713, -73.946101),\n",
    "                  'L9': (40.703761, -73.886496),\n",
    "                  'L10': (40.713620, -73.943076),\n",
    "                  'L11': (40.725212, -73.809179)\n",
    "             }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "geolocator = Nominatim()\n",
    "addresses = []\n",
    "\n",
    "for key in test_locations:\n",
    "    location = geolocator.reverse(test_locations[key])\n",
    "    addresses.append(location.address)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['424, East 155th Street, Melrose, Bronx County, NYC, New York, 10455, USA',\n",
       " '137, West 136th Street, Harlem, Manhattan, Manhattan Community Board 10, New York County, NYC, New York, 10030, USA',\n",
       " '43-11, 28th Avenue, Steinway, Queens County, NYC, New York, 11103, USA',\n",
       " '435, East 74th Street, Upper East Side, Manhattan, Manhattan Community Board 8, New York County, NYC, New York, 10021, USA',\n",
       " '211, Freeman Street, Greenpoint, Kings County, NYC, New York, 11222, USA',\n",
       " '232, East 32nd Street, Kips Bay, Manhattan, Manhattan Community Board 6, New York County, NYC, New York, 10016, USA',\n",
       " '159, West 25th Street, Penn South, Chelsea, Manhattan, Manhattan Community Board 4, New York County, NYC, New York, 10001, USA',\n",
       " '486, Brooklyn Avenue, Crown Heights, BK, Kings County, NYC, New York, 11225, USA',\n",
       " '70-38, 67th Place, Glendale, Queens County, NYC, New York, 11385, USA',\n",
       " '194, Devoe Street, Williamsburg, Kings County, NYC, New York, 11211, USA',\n",
       " '158-46, 76th Avenue, Utopia, Queens, Queens County, NYC, New York, 11366, USA']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "addresses"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "test_addresses = {'L1': '424 East 155th Street NY',\n",
    "                  'L2': '137 West 136th Street NY',\n",
    "                  'L3': '43-11 28th Avenue NY',\n",
    "                  'L4': '435 East 74th Street NY',\n",
    "                  'L5': '211 Freeman Street NY',\n",
    "                  'L6': '232 East 32nd Street NY',\n",
    "                  'L7': '159 West 25th Street NY',\n",
    "                  'L8': '486 Brooklyn Avenue NY',\n",
    "                  'L9': '70-38 67th Place NY',\n",
    "                  'L10': '194 Devoe Street NY',\n",
    "                  'L11': '158-46 76th Avenue NY'\n",
    "             }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['L11', 'L9', 'L4', 'L2', 'L1', 'L7', 'L5', 'L10', 'L3', 'L6', 'L8', 'L11']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def create_guess(points):\n",
    "    \"\"\"\n",
    "    Creates a possible path between all points, returning to the original.\n",
    "    Input: List of point IDs\n",
    "    \"\"\"\n",
    "    guess = copy(points)\n",
    "    np.random.shuffle(guess)\n",
    "    guess.append(guess[0])\n",
    "    return list(guess)\n",
    "\n",
    "create_guess(list(test_locations.keys()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['L8', 'L5', 'L6', 'L4', 'L2', 'L10', 'L9', 'L1', 'L3', 'L7', 'L11', 'L8'], ['L8', 'L11', 'L4', 'L9', 'L5', 'L1', 'L7', 'L6', 'L3', 'L2', 'L10', 'L8'], ['L8', 'L10', 'L1', 'L4', 'L3', 'L5', 'L6', 'L11', 'L2', 'L9', 'L7', 'L8'], ['L11', 'L4', 'L6', 'L7', 'L9', 'L2', 'L8', 'L1', 'L3', 'L10', 'L5', 'L11'], ['L8', 'L7', 'L6', 'L11', 'L2', 'L9', 'L4', 'L10', 'L5', 'L1', 'L3', 'L8'], ['L1', 'L11', 'L6', 'L2', 'L10', 'L5', 'L4', 'L3', 'L9', 'L7', 'L8', 'L1'], ['L6', 'L7', 'L3', 'L4', 'L8', 'L2', 'L5', 'L1', 'L9', 'L10', 'L11', 'L6'], ['L5', 'L2', 'L7', 'L4', 'L8', 'L10', 'L6', 'L11', 'L9', 'L1', 'L3', 'L5'], ['L9', 'L1', 'L3', 'L5', 'L4', 'L8', 'L10', 'L7', 'L2', 'L6', 'L11', 'L9'], ['L2', 'L3', 'L1', 'L9', 'L8', 'L7', 'L11', 'L6', 'L5', 'L10', 'L4', 'L2']]\n"
     ]
    }
   ],
   "source": [
    "def create_generation(points, population=100):\n",
    "    \"\"\"\n",
    "    Makes a list of guessed point orders given a list of point IDs.\n",
    "    Input:\n",
    "    points: list of point ids\n",
    "    population: how many guesses to make\n",
    "    \"\"\"\n",
    "    generation = [create_guess(points) for _ in range(population)]\n",
    "    return generation\n",
    "\n",
    "test_generation = create_generation(list(test_locations.keys()), population=10)\n",
    "print(test_generation)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def travel_time_between_points(point1_id, point2_id, hour, date, passenger_count = 1, \n",
    "                               store_and_fwd_flag = 0, pickup_minute = 0):\n",
    "    \"\"\"\n",
    "    Given two points, this calculates travel between them based on a XGBoost predictive model\n",
    "    \"\"\"\n",
    "    \n",
    "    model_data = {'passenger_count': passenger_count,\n",
    "                  'pickup_longitude' : point1_id[1],\n",
    "                  'pickup_latitude' : point1_id[0],\n",
    "                  'dropoff_longitude' : point2_id[1],\n",
    "                  'dropoff_latitude' : point2_id[0],\n",
    "                  'store_and_fwd_flag' : store_and_fwd_flag,\n",
    "                  'pickup_month' : my_date.month,\n",
    "                  'pickup_day' : my_date.day,\n",
    "                  'pickup_weekday' : my_date.weekday(),\n",
    "                  'pickup_hour': hour,\n",
    "                  'pickup_minute' : pickup_minute,\n",
    "                  'latitude_difference' : point2_id[0] - point1_id[0],\n",
    "                  'longitude_difference' : point2_id[1] - point1_id[1],\n",
    "                  'trip_distance' : 0.621371 * 6371 * (abs(2 * np.arctan2(np.sqrt(np.square(np.sin((abs(point2_id[0] - point1_id[0]) * np.pi / 180) / 2))), \n",
    "                                  np.sqrt(1-(np.square(np.sin((abs(point2_id[0] - point1_id[0]) * np.pi / 180) / 2)))))) + \\\n",
    "                                     abs(2 * np.arctan2(np.sqrt(np.square(np.sin((abs(point2_id[1] - point1_id[1]) * np.pi / 180) / 2))), \n",
    "                                  np.sqrt(1-(np.square(np.sin((abs(point2_id[1] - point1_id[1]) * np.pi / 180) / 2)))))))\n",
    "                 }\n",
    "\n",
    "    df = pd.DataFrame([model_data], columns=model_data.keys())\n",
    "    \n",
    "    pred = np.exp(loaded_model.predict(xgb.DMatrix(df))) - 1\n",
    "    \n",
    "    return pred[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "coordinates = test_locations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(['L8', 'L5', 'L6', 'L4', 'L2', 'L10', 'L9', 'L1', 'L3', 'L7', 'L11', 'L8'], 311.97076988220215), (['L8', 'L11', 'L4', 'L9', 'L5', 'L1', 'L7', 'L6', 'L3', 'L2', 'L10', 'L8'], 338.0717763900757), (['L8', 'L10', 'L1', 'L4', 'L3', 'L5', 'L6', 'L11', 'L2', 'L9', 'L7', 'L8'], 338.63061904907227), (['L11', 'L4', 'L6', 'L7', 'L9', 'L2', 'L8', 'L1', 'L3', 'L10', 'L5', 'L11'], 330.1195888519287), (['L8', 'L7', 'L6', 'L11', 'L2', 'L9', 'L4', 'L10', 'L5', 'L1', 'L3', 'L8'], 329.3325500488281), (['L1', 'L11', 'L6', 'L2', 'L10', 'L5', 'L4', 'L3', 'L9', 'L7', 'L8', 'L1'], 345.65248584747314), (['L6', 'L7', 'L3', 'L4', 'L8', 'L2', 'L5', 'L1', 'L9', 'L10', 'L11', 'L6'], 337.89298915863037), (['L5', 'L2', 'L7', 'L4', 'L8', 'L10', 'L6', 'L11', 'L9', 'L1', 'L3', 'L5'], 328.7141628265381), (['L9', 'L1', 'L3', 'L5', 'L4', 'L8', 'L10', 'L7', 'L2', 'L6', 'L11', 'L9'], 328.89237785339355), (['L2', 'L3', 'L1', 'L9', 'L8', 'L7', 'L11', 'L6', 'L5', 'L10', 'L4', 'L2'], 327.78211784362793)]\n"
     ]
    }
   ],
   "source": [
    "def fitness_score(guess):\n",
    "    \"\"\"\n",
    "    Loops through the points in the guesses order and calculates\n",
    "    how much distance the path would take to complete a loop.\n",
    "    Lower is better.\n",
    "    \"\"\"\n",
    "    score = 0\n",
    "    for ix, point_id in enumerate(guess[:-1]):\n",
    "        score += travel_time_between_points(coordinates[point_id], coordinates[guess[ix+1]], 11, my_date)\n",
    "    return score\n",
    "\n",
    "def check_fitness(guesses):\n",
    "    \"\"\"\n",
    "    Goes through every guess and calculates the fitness score. \n",
    "    Returns a list of tuples: (guess, fitness_score)\n",
    "    \"\"\"\n",
    "    fitness_indicator = []\n",
    "    for guess in guesses:\n",
    "        fitness_indicator.append((guess, fitness_score(guess)))\n",
    "    return fitness_indicator\n",
    "\n",
    "print(check_fitness(test_generation))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_breeders_from_generation(guesses, take_best_N=10, take_random_N=5, verbose=False, mutation_rate=0.1):\n",
    "    \"\"\"\n",
    "    This sets up the breeding group for the next generation. You have\n",
    "    to be very careful how many breeders you take, otherwise your\n",
    "    population can explode. These two, plus the \"number of children per couple\"\n",
    "    in the make_children function must be tuned to avoid exponential growth or decline!\n",
    "    \"\"\"\n",
    "    # First, get the top guesses from last time\n",
    "    fit_scores = check_fitness(guesses)\n",
    "    sorted_guesses = sorted(fit_scores, key=lambda x: x[1]) # sorts so lowest is first, which we want\n",
    "    new_generation = [x[0] for x in sorted_guesses[:take_best_N]]\n",
    "    best_guess = new_generation[0]\n",
    "    \n",
    "    if verbose:\n",
    "        # If we want to see what the best current guess is!\n",
    "        print(best_guess)\n",
    "    \n",
    "    # Second, get some random ones for genetic diversity\n",
    "    for _ in range(take_random_N):\n",
    "        ix = np.random.randint(len(guesses))\n",
    "        new_generation.append(guesses[ix])\n",
    "        \n",
    "    # No mutations here since the order really matters.\n",
    "    # If we wanted to, we could add a \"swapping\" mutation,\n",
    "    # but in practice it doesn't seem to be necessary\n",
    "    \n",
    "    np.random.shuffle(new_generation)\n",
    "    return new_generation, best_guess\n",
    "\n",
    "def make_child(parent1, parent2):\n",
    "    \"\"\" \n",
    "    Take some values from parent 1 and hold them in place, then merge in values\n",
    "    from parent2, filling in from left to right with cities that aren't already in \n",
    "    the child. \n",
    "    \"\"\"\n",
    "    list_of_ids_for_parent1 = list(np.random.choice(parent1, replace=False, size=len(parent1)//2))\n",
    "    child = [-99 for _ in parent1]\n",
    "    \n",
    "    for ix in range(0, len(list_of_ids_for_parent1)):\n",
    "        child[ix] = parent1[ix]\n",
    "    for ix, gene in enumerate(child):\n",
    "        if gene == -99:\n",
    "            for gene2 in parent2:\n",
    "                if gene2 not in child:\n",
    "                    child[ix] = gene2\n",
    "                    break\n",
    "    child[-1] = child[0]\n",
    "    return child\n",
    "\n",
    "def make_children(old_generation, children_per_couple=1):\n",
    "    \"\"\"\n",
    "    Pairs parents together, and makes children for each pair. \n",
    "    If there are an odd number of parent possibilities, one \n",
    "    will be left out. \n",
    "    \n",
    "    Pairing happens by pairing the first and last entries. \n",
    "    Then the second and second from last, and so on.\n",
    "    \"\"\"\n",
    "    mid_point = len(old_generation)//2\n",
    "    next_generation = [] \n",
    "    \n",
    "    for ix, parent in enumerate(old_generation[:mid_point]):\n",
    "        for _ in range(children_per_couple):\n",
    "            next_generation.append(make_child(parent, old_generation[-ix-1]))\n",
    "    return next_generation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generation 0: 500\n",
      "['L1', 'L2', 'L3', 'L8', 'L9', 'L10', 'L5', 'L4', 'L6', 'L7', 'L11', 'L1']\n",
      "Generation 5: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L8', 'L9', 'L3', 'L11', 'L1']\n",
      "Generation 10: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 15: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 20: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 25: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 30: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 35: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 40: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 45: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 50: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 55: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 60: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 65: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 70: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 75: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 80: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 85: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 90: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n",
      "Generation 95: 525\n",
      "['L1', 'L2', 'L4', 'L7', 'L6', 'L5', 'L10', 'L9', 'L11', 'L8', 'L3', 'L1']\n"
     ]
    }
   ],
   "source": [
    "current_generation = create_generation(list(test_locations.keys()),population=500)\n",
    "print_every_n_generations = 5\n",
    "\n",
    "for i in range(100):\n",
    "    if not i % print_every_n_generations:\n",
    "        print(\"Generation %i: \"%i, end='')\n",
    "        print(len(current_generation))\n",
    "        is_verbose = True\n",
    "    else:\n",
    "        is_verbose = False\n",
    "    breeders, best_guess = get_breeders_from_generation(current_generation, \n",
    "                                                        take_best_N=250, take_random_N=100, \n",
    "                                                        verbose=is_verbose)\n",
    "    current_generation = make_children(breeders, children_per_couple=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generation 5: 330\n",
      "Current Best Score:  244.65431213378906\n",
      "['L3', 'L10', 'L11', 'L8', 'L9', 'L7', 'L6', 'L5', 'L4', 'L2', 'L1', 'L3']\n",
      "Generation 10: 330\n",
      "Current Best Score:  248.8752145767212\n",
      "['L11', 'L8', 'L3', 'L1', 'L2', 'L4', 'L6', 'L7', 'L10', 'L5', 'L9', 'L11']\n",
      "Generation 15: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 20: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 25: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 30: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 35: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 40: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 45: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 50: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 55: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 60: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 65: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 70: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 75: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 80: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 85: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 90: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n",
      "Generation 95: 330\n",
      "Current Best Score:  254.2485990524292\n",
      "['L2', 'L1', 'L4', 'L8', 'L9', 'L3', 'L11', 'L10', 'L5', 'L6', 'L7', 'L2']\n"
     ]
    }
   ],
   "source": [
    "def evolve_to_solve(current_generation, max_generations, take_best_N, take_random_N,\n",
    "                    mutation_rate, children_per_couple, print_every_n_generations, verbose=False):\n",
    "    \"\"\"\n",
    "    Takes in a generation of guesses then evolves them over time using our breeding rules.\n",
    "    Continue this for \"max_generations\" times.\n",
    "    Inputs:\n",
    "    current_generation: The first generation of guesses\n",
    "    max_generations: how many generations to complete\n",
    "    take_best_N: how many of the top performers get selected to breed\n",
    "    take_random_N: how many random guesses get brought in to keep genetic diversity\n",
    "    mutation_rate: How often to mutate (currently unused)\n",
    "    children_per_couple: how many children per breeding pair\n",
    "    print_every_n_geneartions: how often to print in verbose mode\n",
    "    verbose: Show printouts of progress\n",
    "    Returns:\n",
    "    fitness_tracking: a list of the fitness score at each generations\n",
    "    best_guess: the best_guess at the end of evolution\n",
    "    \"\"\"\n",
    "    fitness_tracking = []\n",
    "    for i in range(max_generations):\n",
    "        if verbose and not i % print_every_n_generations and i > 0:\n",
    "            print(\"Generation %i: \"%i, end='')\n",
    "            print(len(current_generation))\n",
    "            print(\"Current Best Score: \", fitness_tracking[-1])\n",
    "            is_verbose = True\n",
    "        else:\n",
    "            is_verbose = False\n",
    "        breeders, best_guess = get_breeders_from_generation(current_generation, \n",
    "                                                            take_best_N=take_best_N, take_random_N=take_random_N, \n",
    "                                                            verbose=is_verbose, mutation_rate=mutation_rate)\n",
    "        fitness_tracking.append(fitness_score(best_guess))\n",
    "        current_generation = make_children(breeders, children_per_couple=children_per_couple)\n",
    "    \n",
    "    return fitness_tracking, best_guess\n",
    "\n",
    "current_generation = create_generation(list(test_locations.keys()),population=500)\n",
    "fitness_tracking, best_guess = evolve_to_solve(current_generation, 100, 150, 70, 0.5, 3, 5, verbose=True)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}