Genetic programming.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gc\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from tqdm import tqdm_notebook\n",
    "\n",
    "from IPython.display import clear_output, display\n",
    "from sklearn.externals.joblib import Parallel, delayed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GeneticOptimizer():\n",
    "    \n",
    "    def __init__(self, \n",
    "                 n_population=100,\n",
    "                 n_breeders=10, \n",
    "                 n_lucky=2, \n",
    "                 n_generations=10, \n",
    "                 max_row_mutations=10, \n",
    "                 max_col_mutations=10, \n",
    "                 max_combined_rows=10, \n",
    "                 max_combined_cols=10):\n",
    "        \n",
    "        # Set variables\n",
    "        self.n_population = n_population\n",
    "        self.n_generations = n_generations\n",
    "        self.n_breeders = n_breeders\n",
    "        self.n_lucky = n_lucky\n",
    "        self.max_row_mutations = max_row_mutations\n",
    "        self.max_col_mutations = max_col_mutations\n",
    "        self.max_combined_rows = max_combined_rows\n",
    "        self.max_combined_cols = max_combined_cols\n",
    "        self.history = []\n",
    "        self.fittest = []\n",
    "    \n",
    "    @staticmethod\n",
    "    def fitness(X, weights, individual):\n",
    "        \"\"\"\n",
    "        Lower score means better alignment, see sample df at:\n",
    "        https://www.kaggle.com/titericz/the-property-by-giba\n",
    "        \"\"\"\n",
    "\n",
    "        # Get a copy of our dataframe       \n",
    "        X = X.loc[individual['rows'], ['target','target+1'] + individual['cols'].tolist()]\n",
    "\n",
    "        # Shift matrix to get fitness\n",
    "        shiftLeftUp = X.iloc[1:, 1:].values\n",
    "        deleteRightDown = X.iloc[:-1, :-1].values    \n",
    "\n",
    "        # Calculate & return score\n",
    "        score = np.sum((shiftLeftUp - deleteRightDown).astype(bool).astype(int) * weights)\n",
    "        return score\n",
    "    \n",
    "    @staticmethod\n",
    "    def hash_individual(individual):\n",
    "        return hash(frozenset(individual))\n",
    "    \n",
    "    @staticmethod\n",
    "    def swap_random(seq, n):\n",
    "        \"\"\"Swaps a n-length subsequence around in seq\"\"\"\n",
    "        l = len(seq)\n",
    "        idx = range(l)\n",
    "        i1, i2 = np.random.choice(idx, 2, replace=False)\n",
    "        i1 = l-n if n + i1 >= l else i1\n",
    "        i2 = l-n if n + i2 >= l else i2\n",
    "        for m in range(n):\n",
    "            seq[i1+m], seq[i2+m] = seq[i2+m], seq[i1+m]\n",
    "            \n",
    "    @staticmethod\n",
    "    def get_parallel(verbose=0, n_jobs=-1, pre_dispatch='2*n_jobs'):\n",
    "        return Parallel(\n",
    "            n_jobs=n_jobs,\n",
    "            pre_dispatch=pre_dispatch,\n",
    "            verbose=verbose\n",
    "        )\n",
    "            \n",
    "    def create_initial_population(self, columns, index):\n",
    "        population = []\n",
    "        for _ in range(self.n_population):\n",
    "            np.random.shuffle(columns)\n",
    "            np.random.shuffle(index)\n",
    "            population.append({'cols': np.copy(columns), 'rows': np.copy(index)})\n",
    "        return np.array(population)\n",
    "    \n",
    "    def compute_population_performance(self, population, X, weights, **kwargs):        \n",
    "        parallel = self.get_parallel(**kwargs)\n",
    "        performance = parallel(\n",
    "            delayed(self.fitness)(X, weights, individual) for individual in population\n",
    "        )\n",
    "        return np.array(performance)\n",
    "    \n",
    "    def select_from_population(self, population, performance, best_sample=3, lucky_few=1):\n",
    "        \n",
    "        # Sort the population to have best first\n",
    "        sorted_population = population[np.argsort(performance)]\n",
    "        \n",
    "        # Save the fittest individual of the generation\n",
    "        self.fittest.append(sorted_population[0])\n",
    "        \n",
    "        # Create next generation with best and random\n",
    "        nextGeneration = []\n",
    "        for i in range(best_sample):\n",
    "            nextGeneration.append(sorted_population[i])\n",
    "        for i in range(lucky_few):\n",
    "            nextGeneration.append(np.random.choice(sorted_population))\n",
    "            \n",
    "        # Shuffle new generation and return\n",
    "        np.random.shuffle(nextGeneration)        \n",
    "        return nextGeneration\n",
    "    \n",
    "    def create_child(self, breeders):\n",
    "        \n",
    "        # Mom, dad and child\n",
    "        mom = breeders[np.random.randint(0, len(breeders))]\n",
    "        dad = breeders[np.random.randint(0, len(breeders))]        \n",
    "        child_columns, child_index = [0]*self.n_cols, [0]*self.n_rows\n",
    "        \n",
    "        # Convenience function\n",
    "        def set_trait(array, index, mom_trait, dad_trait):\n",
    "            if np.random.rand() > 0.5:\n",
    "                if mom_trait not in array:\n",
    "                    array[index] = mom_trait\n",
    "            else:\n",
    "                if dad_trait not in array:\n",
    "                    array[index] = dad_trait\n",
    "        \n",
    "        # Get characteristics from parent 1\n",
    "        for i in range(self.n_cols):\n",
    "            set_trait(child_columns, i, mom['cols'][i], dad['cols'][i])\n",
    "        for i in range(self.n_rows):\n",
    "            set_trait(child_index, i, mom['rows'][i], dad['rows'][i])\n",
    "            \n",
    "        # Fill in missing values (in a sense also a mutation factor)\n",
    "        missing_cols = [c for c in mom['cols'] if c not in child_columns]\n",
    "        for i in range(self.n_cols):\n",
    "            if child_columns[i] == 0:\n",
    "                child_columns[i] = missing_cols.pop()\n",
    "                \n",
    "        missing_rows = [c for c in mom['rows'] if c not in child_index]\n",
    "        for i in range(self.n_rows):\n",
    "            if child_index[i] == 0:\n",
    "                child_index[i] = missing_rows.pop()\n",
    "                \n",
    "        return {'cols': np.array(child_columns), 'rows': np.array(child_index)}\n",
    "    \n",
    "    def create_children(self, breeders, n_children, **kwargs):\n",
    "        parallel = self.get_parallel(**kwargs)\n",
    "        nextPopulation = parallel(\n",
    "            delayed(self.create_child)(breeders) for _ in range(n_children)\n",
    "        )\n",
    "        return np.array(nextPopulation)\n",
    "    \n",
    "    def mutate_individual(self, individual):\n",
    "        if self.max_row_mutations > 0:\n",
    "            for _ in np.arange(0, np.random.randint(0, self.max_row_mutations)):\n",
    "                n = np.random.randint(1, self.max_combined_rows)\n",
    "                self.swap_random(individual['rows'], n)\n",
    "        if self.max_col_mutations > 0:\n",
    "            for _ in np.arange(0, np.random.randint(0, self.max_col_mutations)):\n",
    "                n = np.random.randint(1, self.max_combined_cols)\n",
    "                self.swap_random(individual['cols'], n)\n",
    "        return individual\n",
    "    \n",
    "    def mutate_population(self, population, **kwargs):\n",
    "        parallel = self.get_parallel(**kwargs)\n",
    "        nextPopulation = parallel(\n",
    "            delayed(self.mutate_individual)(individual) for individual in population\n",
    "        )\n",
    "        return np.array(nextPopulation)\n",
    "    \n",
    "    def get_fittest_target_error(self, X, validation_index):\n",
    "        \"\"\"Assume first column in individual is 2 steps behind target\"\"\"\n",
    "        \n",
    "        individual = self.fittest[-1]\n",
    "        \n",
    "        target_idx = [i for i in individual['rows'] if i in validation_index]\n",
    "        target = np.log1p(X.loc[target_idx, 'target'])\n",
    "        \n",
    "        target2p_col = individual['cols'][0]\n",
    "        target2p = np.log1p(X.loc[target_idx, target2p_col].shift(-2))\n",
    "        \n",
    "        return np.sqrt((target-target2p).dropna()**2).sum()        \n",
    "    \n",
    "    def fit(self, X, y, weights=None, validation_index=None, **kwargs): \n",
    "        \n",
    "        # Do not modify original\n",
    "        X = X.copy()\n",
    "    \n",
    "        # How many rows & columns do we have\n",
    "        self.n_cols = len(X.columns)\n",
    "        self.n_rows = len(X.index)        \n",
    "        \n",
    "        # Create initial population\n",
    "        population = self.create_initial_population(X.columns.tolist(), X.index.tolist())\n",
    "        \n",
    "        # Add target and target+1 to X, so as to direct the order of result\n",
    "        X.insert(0, 'target+1', y.shift(1))\n",
    "        X.insert(0, 'target', y)\n",
    "        X.fillna(0, inplace=True)\n",
    "        \n",
    "        # If no weights specified, all columns equally important\n",
    "        if weights is None:\n",
    "            weights = np.ones(X.shape[1])\n",
    "        \n",
    "        # Run the algorithm for n_generations\n",
    "        for epoch in range(self.n_generations):\n",
    "            \n",
    "            # Get performance for each individual in population            \n",
    "            performance = self.compute_population_performance(population, X, weights, **kwargs)\n",
    "            \n",
    "            # Get breeders\n",
    "            breeders = self.select_from_population(population, performance)\n",
    "            \n",
    "            # If we have a validation index, then get the train error for the best performer\n",
    "            if validation_index is not None:\n",
    "                train_error = self.get_fittest_target_error(X, validation_index)\n",
    "            else:\n",
    "                train_error = 'NaN'   \n",
    "            \n",
    "            # Update population\n",
    "            population = self.create_children(breeders, self.n_population, **kwargs)\n",
    "            \n",
    "            # Mutate population before next generation\n",
    "            population = self.mutate_population(population, **kwargs)            \n",
    "            \n",
    "            # Save to history & display\n",
    "            clear_output()\n",
    "            self.history.append({\n",
    "                \"pop_loss\": np.mean(performance),\n",
    "                \"std_pop_loss\": np.std(performance),\n",
    "                \"top_performer_loss\": np.min(performance),\n",
    "                'generation': epoch+1,\n",
    "                'Train RMSLE': train_error\n",
    "            })\n",
    "            display(pd.DataFrame(self.history).set_index('generation'))\n",
    "            \n",
    "            # Just in case\n",
    "            gc.collect()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "df_train = pd.read_csv('data/train.csv')\n",
    "X_train = df_train.drop(['ID_code', 'target'], axis=1)\n",
    "y_train = df_train.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "weights = np.exp(-np.linspace(0, np.sqrt(X_train.shape[1]), X_train.shape[1]))\n",
    "\n",
    "# Instantiate class and run on training data        \n",
    "gp_opt = GeneticOptimizer(\n",
    "    n_population=1000000,\n",
    "    n_breeders=1000,\n",
    "    n_lucky=100,\n",
    "    n_generations=10,\n",
    "    max_row_mutations=5,\n",
    "    max_col_mutations=5,\n",
    "    max_combined_rows=5,\n",
    "    max_combined_cols=5\n",
    ")\n",
    "\n",
    "# Fit to data\n",
    "gp_opt.fit(\n",
    "    X_train, y_train, \n",
    "    n_jobs=4,\n",
    "    verbose=1,\n",
    "    weights=weights,\n",
    "    validation_index=X_train.index.values\n",
    ")"
   ]
  },
  {
   "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}