ga_demo.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "#get_ipython().magic('load_ext autoreload')\n",
    "#get_ipython().magic('autoreload')\n",
    "%matplotlib inline\n",
    "\n",
    "import pandas as pd \n",
    "import os\n",
    "import numpy as np\n",
    "import random\n",
    "import copy\n",
    "import matplotlib\n",
    "#matplotlib.use('TkAgg')\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.neighbors import BallTree\n",
    "import itertools as it\n",
    "from collections import defaultdict\n",
    "import time\n",
    "import multiprocessing\n",
    "from concurrent.futures import ProcessPoolExecutor\n",
    "from itertools import combinations\n",
    "from opt import Optimizer\n",
    "import copy\n",
    "import math\n",
    "import sys\n",
    "import matplotlib.animation\n",
    "import matplotlib as mpl\n",
    "from IPython.display import HTML\n",
    "mpl.rcParams['animation.embed_limit'] = 500\n",
    "\n",
    "np.random.seed(42)\n",
    "num_cpus = multiprocessing.cpu_count()\n",
    "#get_ipython().magic('matplotlib inline')\n",
    "np.set_printoptions(threshold=1000, linewidth=75)\n",
    "pd.options.mode.chained_assignment = None\n",
    "pd.set_option('display.max_columns', 15)\n",
    "\n",
    "\n",
    "class Point():\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "\n",
    "    def dist_to(self, point):\n",
    "        return math.sqrt((self.x - point.x)**2 + (self.y - point.y)**2)\n",
    "    \n",
    "class Customer(Point):\n",
    "    def __init__(self, i, x, y, d, q):\n",
    "        super(Customer, self).__init__(x, y)\n",
    "        self.id = i\n",
    "        self.duration = d\n",
    "        self.demand = q\n",
    "        self.swappable_to = []\n",
    "\n",
    "class Depot(Point):\n",
    "    def __init__(self, i, x, y, max_dur, max_load, max_veh):\n",
    "        super(Depot, self).__init__(x, y)\n",
    "        self.id = i\n",
    "        self.max_duration = max_dur if max_dur != 0 else 1e9\n",
    "        self.max_load = max_load \n",
    "        self.max_vehicle_num = max_veh\n",
    "\n",
    "def read_problem(problem=\"01\"):\n",
    "    with open(\"Testing Data/Data Files/p\"+problem, \"r\") as d:\n",
    "        data = d.readlines()\n",
    "    def clean_line(row):\n",
    "        row = list(map(int, row.strip().split()))\n",
    "        return row\n",
    "    m, n, t = clean_line(data[0])\n",
    "    depot_limits = list(map(clean_line, data[1:t+1]))\n",
    "    cust_rows = list(map(clean_line, data[t+1:t+n+1]))\n",
    "    depot_pos = list(map(clean_line, data[t+n+1:]))\n",
    "    depot_rows = list(zip(depot_limits, depot_pos))\n",
    "    num_rows = m*t\n",
    "    num_customers = n\n",
    "    depots = [Depot(i,d[1][1], d[1][2], d[0][0], d[0][1], m) for i, d in enumerate(depot_rows)]\n",
    "    customers = [Customer(c[0],c[1], c[2], c[3], c[4]) for c in cust_rows]\n",
    "    return depots, customers\n",
    "\n",
    "class Individual(object):\n",
    "    def __init__(self, chromosome):\n",
    "        self.genes = chromosome\n",
    "        self.subroutes = [[] for i in range(len(chromosome))]\n",
    "        for i in range(len(chromosome)):\n",
    "            try:\n",
    "                self.subroutes[i] = self.split_cluster(chromosome[i], depots[i])\n",
    "            except:\n",
    "                print(len(chromosome))\n",
    "                print(chromosome)\n",
    "                print(i)\n",
    "        self.cost = 0\n",
    "        self.loads = {}\n",
    "        for depind, depot in enumerate(self.subroutes):\n",
    "            self.loads[depind] = {}\n",
    "            for subr_ind, subroute in enumerate(depot):\n",
    "                self.cost += self.calc_subr_dist(subroute)\n",
    "                self.loads[depind][subr_ind] = self.calc_subr_load(subroute)\n",
    "    \n",
    "    def get_copy(self):\n",
    "        genes_copy = []\n",
    "        for gene in self.genes:\n",
    "            genes_copy.append(gene[:])\n",
    "        return Individual(genes_copy)\n",
    "    \n",
    "    def recalc_subroute(self, cluster, depind):\n",
    "        for subr_ind, subroute in enumerate(self.subroutes[depind]):\n",
    "            self.cost -= self.calc_subr_dist(subroute)\n",
    "        self.subroutes[depind] = self.split_cluster(cluster, depots[depind])\n",
    "        for subr_ind, subroute in enumerate(self.subroutes[depind]):\n",
    "            self.cost += self.calc_subr_dist(subroute)\n",
    "            self.loads[depind][subr_ind] = self.calc_subr_load(subroute)\n",
    "\n",
    "    def split_cluster(self, cluster, d):\n",
    "        routes = []\n",
    "        length = 0\n",
    "        load = 0\n",
    "        subroute = [d]\n",
    "        for c in cluster:\n",
    "            total_duration = length + c.dist_to(subroute[-1]) + c.duration + d.dist_to(c)\n",
    "            if load + c.demand <= d.max_load and d.max_duration > total_duration :\n",
    "                subroute.append(c)\n",
    "                length += c.dist_to(subroute[-1]) + c.duration\n",
    "                load += c.demand\n",
    "            else:\n",
    "                subroute.append(d)\n",
    "                routes.append(subroute)\n",
    "                length = 0\n",
    "                load = 0\n",
    "                subroute = [d]\n",
    "                total_duration = length + c.dist_to(subroute[-1]) + c.duration + d.dist_to(c)\n",
    "                subroute.append(c)\n",
    "                length += c.dist_to(subroute[-1]) + c.duration\n",
    "                load += c.demand\n",
    "        subroute.append(d)\n",
    "        routes.append(subroute)\n",
    "        return routes\n",
    "\n",
    "    def calc_subr_dist(self, subroute):\n",
    "        distance = 0\n",
    "        for i in range(1, len(subroute)):\n",
    "            distance += subroute[i].dist_to(subroute[i-1])\n",
    "        return distance\n",
    "\n",
    "    def route_dist(self, subroutes):\n",
    "        dist = 0\n",
    "        for subr in subroutes:\n",
    "            dist += self.calc_subr_dist(subr)\n",
    "        return dist\n",
    "    \n",
    "    def eval_subr(self, subroute, d):\n",
    "        cost = self.calc_subr_dist(subroute)\n",
    "        load = self.calc_subr_load(subroute)\n",
    "        f = load <= d.max_load\n",
    "        fill_perc = (100*load)/d.max_load\n",
    "        return cost, load, f, fill_perc\n",
    "        \n",
    "    def eval_ind(self):\n",
    "        evaldf = pd.DataFrame([(depind, rind, self.eval_subr(r, depots[depind])) for depind, route in enumerate(self.subroutes) for rind, r in enumerate(route)], columns=[\"depind\", \"routeind\", \"eval\"])\n",
    "        evaldf[[\"duration\", \"load\", \"feasible\", \"fill_perc\"]] = evaldf.loc[:,\"eval\"].apply(pd.Series)\n",
    "        del evaldf[\"eval\"]\n",
    "        return evaldf\n",
    "\n",
    "    def calc_subr_load(self, subroute):\n",
    "        load = 0\n",
    "        for customer in subroute[1:-1]:\n",
    "            load += customer.demand\n",
    "        return load\n",
    "    \n",
    "    def opt_som(self, route, d):\n",
    "        '''\n",
    "        Optimize a single (sub)route through a Self Organizing Map. Route must contain depot.\n",
    "        '''\n",
    "        old_dur, old_load, old_f, f_p = self.eval_subr(route, d)\n",
    "        poslist = list(map(lambda point: (point.x,point.y), route))\n",
    "        r_arr = np.array(poslist[:-1])\n",
    "        o = Optimizer(r_arr)\n",
    "        s, _ = o.run()\n",
    "        if len(s)!=len(route)-1:\n",
    "            print(\"som failed..\")\n",
    "            print(r_arr)\n",
    "            print(s)\n",
    "            return route\n",
    "\n",
    "        dep_ind = np.argmin(s)\n",
    "        s = s[dep_ind:]+s[:dep_ind]\n",
    "        new = [route[i] for i in s]+[d]\n",
    "        dur, load, f, new_f_p  = self.eval_subr(new, d)\n",
    "        if (dur < old_dur) and (load <= d.max_load) and f:\n",
    "            print(\"saved by SOM: \" +str(old_dur-dur))\n",
    "            return new\n",
    "        else:\n",
    "            return route\n",
    "    \n",
    "    def optimize_routes(self):\n",
    "        print(\"Cost before SOM:\")\n",
    "        print(self.cost)\n",
    "        for depind, depr in enumerate(self.subroutes):\n",
    "            d = depots[depind]\n",
    "            for subind, subr in enumerate(depr):\n",
    "                self.cost -= self.calc_subr_dist(subr)\n",
    "                new_subr = self.opt_som(subr, d)\n",
    "                self.subroutes[depind][subind] = new_subr\n",
    "                self.cost += self.calc_subr_dist(new_subr)\n",
    "                self.loads[depind][subind] = self.calc_subr_load(new_subr)\n",
    "        print(\"Cost after SOM:\")\n",
    "        print(self.cost)\n",
    "    \n",
    "    def write_solution(self):\n",
    "        with open(\"solutions_ga/p\"+p_no+\"_solution\", \"w\") as f:\n",
    "            f.write(\"{0:.2f}\".format(self.cost)+\"\\n\")\n",
    "            for depind, dep in enumerate(self.subroutes):\n",
    "                for subr_ind, subr in enumerate(dep):\n",
    "                    f.write(str(depind+1)+\"   \")\n",
    "                    f.write(str(subr_ind+1)+\"   \")\n",
    "                    f.write(\"{0:.2f}\".format(self.calc_subr_dist(subr))+\"   \")\n",
    "                    f.write(str(self.calc_subr_load(subr))+\"   0 \")\n",
    "                    for c in subr[1:-1]:\n",
    "                        f.write(str(c.id)+\" \")\n",
    "                    f.write(\"0 \\n\")\n",
    "                        \n",
    "    def plot(self):\n",
    "        customer_x = [c.x for c in customers]\n",
    "        customer_y = [c.y for c in customers]\n",
    "        depot_x = [d.x for d in depots]\n",
    "        depot_y = [d.y for d in depots]\n",
    "        fig, ax = plt.subplots()\n",
    "        ax.scatter(customer_x, customer_y, marker='d')\n",
    "        for depot in self.subroutes:\n",
    "            for subroute in depot:\n",
    "                xs = [point.x for point in subroute]\n",
    "                ys = [point.y for point in subroute]\n",
    "                ax.plot(xs, ys, c=list(np.random.rand(3,1).flatten()))\n",
    "        ax.scatter(depot_x, depot_y, marker='o', s=200, c = 'r')\n",
    "        plt.title(\"Problem: \"+ str(p_no) + \" Cost: \"+str(self.cost))\n",
    "        plt.show()\n",
    "        \n",
    "    def save_plot(self, gen):\n",
    "        customer_x = [c.x for c in customers]\n",
    "        customer_y = [c.y for c in customers]\n",
    "        depot_x = [d.x for d in depots]\n",
    "        depot_y = [d.y for d in depots]\n",
    "        fig, ax = plt.subplots()\n",
    "        ax.scatter(customer_x, customer_y, marker='d')\n",
    "        for depot in self.subroutes:\n",
    "            for subroute in depot:\n",
    "                xs = [point.x for point in subroute]\n",
    "                ys = [point.y for point in subroute]\n",
    "                ax.plot(xs, ys, c=list(np.random.rand(3,1).flatten()))\n",
    "        ax.scatter(depot_x, depot_y, marker='o', s=200, c = 'r')\n",
    "        plt.title(\"Generation: \"+ str(gen) + \" Cost: \"+str(round(self.cost, 2)))\n",
    "        files = os.listdir(\"plots/\")\n",
    "        plt.savefig(\"plots/\"+str(p_no)+str(len(files)))\n",
    "        plt.close(fig)\n",
    "\n",
    "def cluster_to_depot():\n",
    "    '''\n",
    "    params: \n",
    "    customers: list of the customers in the dataset.\n",
    "    depots: list of the depots in the dataset.\n",
    "    \n",
    "    returns: a Chromosome where customers are assigned to their closest depot, but randomized order within each depot.\n",
    "    '''\n",
    "    closest_dep = []\n",
    "    for c in customers:\n",
    "        dists = sorted([(d, c.dist_to(d)) for d in depots], key=lambda x: x[1])\n",
    "        min_dist = dists[0][1]\n",
    "        next_dist = dists[1][1]\n",
    "        two = min_dist+next_dist\n",
    "        #print(dists)\n",
    "        c.swappable_to = [dep for dep, dist in dists if dist<(2*min_dist)]\n",
    "        if not allow_second:\n",
    "            closest_dep.append((c, dists[0][0]))\n",
    "        else:\n",
    "            if np.random.rand() > ((two-min_dist)/(3*two)):\n",
    "                closest_dep.append((c, dists[0][0]))\n",
    "            else:\n",
    "                closest_dep.append((c, dists[1][0]))\n",
    "    dna = []\n",
    "    for d in depots:\n",
    "        cust_for_dep = [c for c, dep in closest_dep if dep==d]\n",
    "        np.random.shuffle(cust_for_dep)\n",
    "        dna.append(cust_for_dep)\n",
    "    return Individual(dna)\n",
    "        \n",
    "def get_pop(popsize):\n",
    "    return [cluster_to_depot() for i in range(popsize)] \n",
    "\n",
    "def select_parents(population, random_winner_prob):\n",
    "    parents = random.sample(population, 2)\n",
    "    if random.random() > random_winner_prob:\n",
    "        return min(parents, key=lambda x: x.cost)\n",
    "    else:\n",
    "        return parents[0]\n",
    "\n",
    "def bcrxo(genes, depot, subroute):\n",
    "    # Remove all customers belonging to subroute from \n",
    "    # genes.\n",
    "    for d in genes:\n",
    "        for c in subroute:\n",
    "            if c in d:\n",
    "                d.remove(c)\n",
    "    # Get the phenotype for the stripped chromosome.\n",
    "    stripped_repr = Individual(genes)\n",
    "    # For all customers in the subroute...\n",
    "    for c in subroute:\n",
    "        stripped_cost = stripped_repr.cost\n",
    "        # Keep a list of insertion at each position.\n",
    "        insertion_costs = []\n",
    "        for i in range(len(genes[depot])+1):\n",
    "            genes[depot].insert(i, c)\n",
    "            stripped_repr.recalc_subroute(genes[depot], depot)\n",
    "            insertion_costs.append(stripped_repr.cost - stripped_cost)\n",
    "            del genes[depot][i]\n",
    "        # insert at best position.\n",
    "        genes[depot].insert(insertion_costs.index(min(insertion_costs)), c)\n",
    "        stripped_repr.recalc_subroute(genes[depot], depot)\n",
    "    return genes\n",
    "\n",
    "def rev_mut(gene):\n",
    "    spl_ind = random.sample(range(len(gene)), 2)\n",
    "    spl_ind.sort()\n",
    "    gene[spl_ind[0]:spl_ind[1]] = gene[spl_ind[0]:spl_ind[1]][::-1]\n",
    "    return gene\n",
    "\n",
    "def swap_mut(gene):\n",
    "    points = random.sample(range(len(gene)), 2)\n",
    "    gene[points[0]], gene[points[1]] = gene[points[1]], gene[points[0]]\n",
    "    return gene\n",
    "\n",
    "def mutate_genes(genes):\n",
    "    geneind = random.choice(range(len(genes)))\n",
    "    gene = genes[geneind]\n",
    "    if random.random() < 0.5:\n",
    "        genes[geneind] = rev_mut(gene)\n",
    "    else:\n",
    "        genes[geneind] = swap_mut(gene)\n",
    "    return genes\n",
    "        \n",
    "def mate(p1, p2, mutate, bcrxo_prob):\n",
    "    c1_genes = p1.get_copy().genes\n",
    "    c2_genes = p2.get_copy().genes\n",
    "    if random.random() < bcrxo_prob:\n",
    "        depot = random.randrange(0, len(depots))\n",
    "        p1_subroute = random.choice(p1.subroutes[depot])[1:-1]\n",
    "        p2_subroute = random.choice(p2.subroutes[depot])[1:-1]\n",
    "        c2_genes = bcrxo(c2_genes, depot, p1_subroute)\n",
    "        c1_genes = bcrxo(c1_genes, depot, p2_subroute)\n",
    "    if mutate:\n",
    "        mutate_genes(c1_genes)\n",
    "        mutate_genes(c2_genes)\n",
    "    return Individual(c1_genes), Individual(c2_genes)\n",
    "\n",
    "def mate2(args):\n",
    "    p1, p2, mutate = args\n",
    "    c1_genes = p1.get_copy().genes\n",
    "    c2_genes = p2.get_copy().genes\n",
    "    if random.random() <= bcrxo_prob:\n",
    "        depot = random.randrange(0, len(depots))\n",
    "        p1_subroute = random.choice(p1.subroutes[depot])[1:-1]\n",
    "        p2_subroute = random.choice(p2.subroutes[depot])[1:-1]\n",
    "        c2_genes = bcrxo(c2_genes, depot, p1_subroute)\n",
    "        c1_genes = bcrxo(c1_genes, depot, p2_subroute)\n",
    "    if mutate:\n",
    "        c1_genes = mutate_genes(c1_genes[:])\n",
    "        c2_genes = mutate_genes(c2_genes[:])\n",
    "    return [Individual(c1_genes), Individual(c2_genes)]\n",
    "    \n",
    "    \n",
    "def evaluate_pop(pop, sel_scheme, popsize, div_imp=0.5, fp_imp=0.5):\n",
    "    '''\n",
    "    Calculate all desired metrics in order to perform selection.\n",
    "    '''\n",
    "    subrdf = pd.concat([p.eval_ind() for p in pop],keys=range(len(pop)), names=[\"individual\", \"subroute\"])\n",
    "    rankdf = subrdf.loc[:,[\"duration\", \"feasible\", \"fill_perc\"]].groupby(\"individual\").agg({\"duration\": sum,\n",
    "                                                                                              \"feasible\": all,\n",
    "                                                                                              \"fill_perc\": \"mean\"})\n",
    "    rankdf.columns = [\"cost\", \"feasible\", \"avg_fp\"]\n",
    "\n",
    "    rankdf[\"index\"] = rankdf.index\n",
    "    rankdf[\"cost_frac\"] = rankdf.cost/rankdf.cost.sum()\n",
    "    rankdf[\"cost_prob\"] = (1/rankdf.cost_frac)/(1/rankdf.cost_frac).sum()\n",
    "\n",
    "    rankdf[\"avg_fp_rank\"] = rankdf.avg_fp.rank()\n",
    "    rankdf[\"avg_fp_rank_frac\"] = rankdf.avg_fp_rank/rankdf.avg_fp_rank.sum()\n",
    "    rankdf[\"avg_fp_rank_prob\"] = (1/rankdf.avg_fp_rank_frac)/(1/rankdf.avg_fp_rank_frac).sum()\n",
    "\n",
    "    rankdf[\"cost_rank\"] = rankdf.cost.rank()\n",
    "    rankdf[\"cost_rank_frac\"] = rankdf.cost_rank/rankdf.cost_rank.sum()\n",
    "    rankdf[\"cost_rank_prob\"] = (1/rankdf.cost_rank_frac)/(1/rankdf.cost_rank_frac).sum()\n",
    "\n",
    "    rankdf[\"cost_log_rank\"] = np.log(rankdf.cost_rank.rank(ascending=False))\n",
    "    rankdf[\"cost_log_frac\"] = rankdf.cost_log_rank/rankdf.cost_log_rank.sum()\n",
    "    rankdf[\"cost_log_prob\"] = (1/rankdf.cost_log_frac)/(1/rankdf.cost_log_frac).sum()\n",
    "\n",
    "    individs = [flatten_pos(p) for p in pop]\n",
    "    individs = pd.DataFrame(individs).values\n",
    "    tree = BallTree(list(individs), metric=\"hamming\")\n",
    "    get_diversity = lambda x: sum(tree.query(np.array(flatten_pos(x)).reshape(1,-1), k=4)[0][0])\n",
    "    rankdf[\"diversity\"] = list(map(get_diversity, pop))\n",
    "    rankdf[\"div_rank\"] = rankdf.diversity.rank(ascending=False)\n",
    "    rankdf[\"agg_rank\"] = rankdf.cost_rank+(rankdf.div_rank*div_imp)+(rankdf.avg_fp_rank*fp_imp)\n",
    "\n",
    "    rankdf[\"final_rank\"] = rankdf.agg_rank.rank()\n",
    "    rankdf[\"final_rank_frac\"] = rankdf.final_rank/rankdf.final_rank.sum()\n",
    "    rankdf[\"final_rank_prob\"] = (1/rankdf.final_rank_frac)/(1/rankdf.final_rank_frac).sum()\n",
    "\n",
    "    rankdf[\"final_log_rank\"] = np.log(rankdf.final_rank.rank(ascending=False).values)\n",
    "    rankdf[\"final_log_prob\"] = rankdf.final_log_rank/rankdf.final_log_rank.sum()\n",
    "    rankdf.sort_values(sel_scheme, inplace=True)\n",
    "    return rankdf.head(popsize)\n",
    "\n",
    "def flatten_pos(ind):\n",
    "    return [p.id for g in ind.genes for p in g]\n",
    "\n",
    "def evolve(population, rankdf, sel_scheme, elite_sel_scheme, mut_prob, popsize, random_winner_prob, bcrxo_prob, num_elite=2):\n",
    "    new_pop = []\n",
    "    #inserting elites\n",
    "    for i in range(num_elite):\n",
    "        new_pop.append(population[int(rankdf.sort_values(elite_sel_scheme).iloc[i][sel_scheme])-1])\n",
    "    #filling in with children\n",
    "    mutate = False\n",
    "    if random.random() <= mut_prob:\n",
    "        mutate = True\n",
    "    while len(new_pop) < popsize:\n",
    "        p1 = select_parents(population, random_winner_prob)\n",
    "        p2 = select_parents(population, random_winner_prob)\n",
    "        children = mate(p1, p2, mutate, bcrxo_prob)\n",
    "        new_pop.extend(children)\n",
    "    return new_pop\n",
    "\n",
    "def run_ga(stopping_val, popsize, num_generations, num_elite, sel_scheme, elite_sel_scheme, div_imp, fp_imp, mut_prob, bcrxo_prob, random_winner_prob):\n",
    "    np.random.seed(42)\n",
    "    start_time = time.time()\n",
    "    pop = get_pop(popsize)\n",
    "    rankdf = evaluate_pop(pop, sel_scheme, popsize)\n",
    "    min_score = rankdf.cost.min()\n",
    "    pop = [pop[i] for i in list(rankdf.index)]\n",
    "    fitness_scores = []\n",
    "    gen_since_imp = 0\n",
    "    gen_since_mut_inc = 0\n",
    "    for gen in range(num_generations):\n",
    "        curr_score = rankdf.cost.min()\n",
    "        if curr_score < min_score:\n",
    "            min_score = curr_score\n",
    "            gen_since_imp = 0\n",
    "        else:\n",
    "            gen_since_imp += 1\n",
    "        if True:\n",
    "            print(\"Generation \"+str(gen+1)+\": \")\n",
    "            print(\"Minimum cost: \"+ str(min_score))\n",
    "        fitness_scores.append(min_score)\n",
    "        pop = evolve(pop, rankdf, sel_scheme, elite_sel_scheme, mut_prob, popsize, random_winner_prob, bcrxo_prob)\n",
    "        rankdf = evaluate_pop(pop, sel_scheme, popsize)\n",
    "        pop = [pop[i] for i in list(rankdf.index)]\n",
    "        best = pop[int(rankdf.sort_values(\"cost\").iloc[0][\"final_rank\"])-1]\n",
    "        best.save_plot(gen)\n",
    "        if min_score < stopping_val and (rankdf.sort_values(\"cost\").iloc[0][\"feasible\"]):\n",
    "            print(\"Stopping criteria reached.\")\n",
    "            rankdf = evaluate_pop(pop, sel_scheme, popsize)\n",
    "            break\n",
    "        if (time.time()-start_time > time_limit):\n",
    "            print(\"Time limit reached\")\n",
    "            rankdf = evaluate_pop(pop, sel_scheme, popsize)\n",
    "            break\n",
    "    return best, best.cost, fitness_scores, rankdf\n",
    "\n",
    "\n",
    "def evolve_mp(population, sel_scheme=lambda x: x.cost, num_elite=2):\n",
    "    new_pop = []\n",
    "    moms = [select_parents(population) for _ in range((len(population))//2)]\n",
    "    dads = [select_parents(population) for _ in range((len(population))//2)]\n",
    "    combs = [c for c in list(zip(moms, dads, np.random.rand(len(moms))>mut_prob)) if len(set(c))==3]\n",
    "    result = mp(mate2, combs, 8)\n",
    "    offspring = list(it.chain.from_iterable(result))\n",
    "    new_pop.extend(offspring)\n",
    "    new_pop.sort(key=sel_scheme)\n",
    "    return new_pop\n",
    "\n",
    "def mp(func, args, workers):\n",
    "    '''\n",
    "    maps content of args to func in parallel processes with nu_workers processes.\n",
    "    '''\n",
    "    with ProcessPoolExecutor(workers) as ex:\n",
    "        res = ex.map(func, args)\n",
    "    return list(res)\n",
    "\n",
    "\n",
    "def run_exp(combs):\n",
    "    ind, score, fitness = run_ga(**combs)\n",
    "    res = (combs, score, ind)\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Params: \n",
      "{'bcrxo_prob': 0.7, 'div_imp': 0.3, 'elite_sel_scheme': 'cost', 'fp_imp': 0.1, 'mut_prob': 0.1, 'num_elite': 2, 'num_generations': 1000, 'popsize': 100, 'random_winner_prob': 0.1, 'sel_scheme': 'final_rank'}\n",
      "Stopping criteria: \n",
      "Cost: 4659.564\n",
      "Time: 1800\n"
     ]
    }
   ],
   "source": [
    "# Problem number to load\n",
    "p = 8 #int(sys.argv[1])\n",
    "time_limit = 60*30 # Number of seconds to run\n",
    "# Convert problem no to string padded with zero if less than 9.\n",
    "if p<10:\n",
    "    p_no = \"0\"+str(p)\n",
    "else:\n",
    "    p_no = str(p)\n",
    "    \n",
    "# Read optimal cost (if any)\n",
    "try:\n",
    "    with open(\"Testing Data/Solution Files/p\"+p_no+\".res\", \"r\") as d:\n",
    "        optimal = float(d.readline().strip())\n",
    "except:\n",
    "    optimal = 0\n",
    "    \n",
    "# Read problem\n",
    "with open(\"Testing Data/Data Files/p\"+p_no, \"r\") as d:\n",
    "    data = d.readlines()\n",
    "stopping_val = optimal*1.05\n",
    "def clean_line(row):\n",
    "    row = list(map(int, row.strip().split()))\n",
    "    return row\n",
    "m, n, t = clean_line(data[0])\n",
    "depot_limits = list(map(clean_line, data[1:t+1]))\n",
    "cust_rows = list(map(clean_line, data[t+1:t+n+1]))\n",
    "depot_pos = list(map(clean_line, data[t+n+1:]))\n",
    "depot_rows = list(zip(depot_limits, depot_pos))\n",
    "num_rows = m*t\n",
    "num_customers = n\n",
    "depots = [Depot(i,d[1][1], d[1][2], d[0][0], d[0][1], m) for i, d in enumerate(depot_rows)]\n",
    "customers = [Customer(c[0],c[1], c[2], c[3], c[4]) for c in cust_rows]\n",
    "\n",
    "\n",
    "if p in [1,2,3]:\n",
    "    allow_second = True\n",
    "else:\n",
    "    allow_second = False\n",
    "\n",
    "if n<=50:\n",
    "    ps = 300\n",
    "elif n <= 80:\n",
    "    ps = 400\n",
    "elif n <=100:\n",
    "    ps = 80\n",
    "\n",
    "params = {\"popsize\": [100],\n",
    "    \"num_generations\": [1000],\n",
    "    \"num_elite\": [2],\n",
    "    \"sel_scheme\": [\"final_rank\"],\n",
    "    \"elite_sel_scheme\": [\"cost\"],\n",
    "    \"div_imp\": [0.3],\n",
    "    \"fp_imp\": [0.1],\n",
    "    \"mut_prob\": [0.1],\n",
    "    \"bcrxo_prob\": [0.7],\n",
    "    \"random_winner_prob\": [0.1]}\n",
    "\n",
    "all_combs = sorted(params)\n",
    "combinations = [dict(zip(all_combs, prod)) for prod in it.product(*(params[var] for var in all_combs))]\n",
    "print(\"Params: \")\n",
    "print(combinations[0])\n",
    "print(\"Stopping criteria: \")\n",
    "print(\"Cost: \"+str(stopping_val))\n",
    "print(\"Time: \"+str(time_limit))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generation 1: \n",
      "Minimum cost: 19578.991746398595\n",
      "Generation 2: \n",
      "Minimum cost: 18430.53824382376\n",
      "Generation 3: \n",
      "Minimum cost: 17573.33063172603\n",
      "Generation 4: \n",
      "Minimum cost: 16994.148152701157\n",
      "Generation 5: \n",
      "Minimum cost: 16382.733838747225\n",
      "Generation 6: \n",
      "Minimum cost: 15624.884157429824\n",
      "Generation 7: \n",
      "Minimum cost: 15166.736473699144\n",
      "Generation 8: \n",
      "Minimum cost: 14901.92653203273\n"
     ]
    }
   ],
   "source": [
    "best, score, fit, rankdf = run_ga(stopping_val, **combinations[0])\n",
    "\n",
    "print(\"Final best score: \"+str(score))\n",
    "print()\n",
    "print(\"Rankdf:\")\n",
    "print(rankdf.loc[:, [\"cost\", \"feasible\", \"avg_fp\", \"diversity\", \"final_rank\"]].head())\n",
    "print()\n",
    "best.write_solution()\n",
    "best.plot()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}