{"cells":[{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"code","source":"import numpy as np\nimport pandas as pd\nimport random\n\nfrom Levenshtein import distance","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"SEED = 42\n\nrandom.seed = SEED","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"df = pd.read_csv(\"../input/bms-molecular-translation/train_labels.csv\")\ndf","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Pick some important constants. Note this gets O(TEST_POP_SIZE * INIT_POP_SIZE) so be careful!\nTEST_POP_SIZE = 100\nINIT_POP_SIZE = 500\nMUTATIONS = 50\nGENERATIONS = 100","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"total_population = len(df)\nprint(f\"total_population: {total_population}\")\n\n# Sample an initial population from the complete training set.\ninitial_population = df[\"InChI\"].sample(INIT_POP_SIZE, random_state=SEED).reset_index(drop=True)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Simplest possible Genetic Algorithm helper methods.\n\ndef cross_over(parent1, parent2):\n    \"\"\" Splice two parents together at a random point to generate a child. \"\"\"\n    min_len = min(len(parent1), len(parent2))\n    splice_idx = random.randint(0, min_len)\n    child = parent1[:splice_idx] + parent2[splice_idx:]\n    return child\n    \ndef mutate(individual):\n    \"\"\" Mutate an individual by swapping two characters at a random point.\"\"\"\n    mutation_idx = random.randint(0, len(individual)-2)\n    return individual[:mutation_idx] + individual[mutation_idx+1] + individual[mutation_idx] + individual[mutation_idx+2:]\n\ndef select_best(population, n_best):\n    \"\"\" Score the given population against a sample from the total training population. \"\"\"\n    test_population = df[\"InChI\"].sample(TEST_POP_SIZE, random_state=SEED).reset_index(drop=True)\n    scores = []\n    for p in population:\n        score = 0\n        for t in test_population:\n            score += distance(p,t)\n        score = score/TEST_POP_SIZE\n        scores.append(score)\n    sorted_population = [p for _, p in sorted(zip(scores, population))]\n    return sorted_population[:n_best], min(scores)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Test cross_over and mutate on some simple srtings.\nprint(cross_over(\"abcdef\", \"vwxyz\"))\nprint(cross_over(\"abcdef\", \"vwxyz\"))\nprint(cross_over(\"abcdef\", \"vwxyz\"))\nprint(cross_over(\"vwxyz\", \"abcdef\"))\nprint(cross_over(\"vwxyz\", \"abcdef\"))\nprint(cross_over(\"vwxyz\", \"abcdef\"))\n\nprint(mutate(\"abcdef\"))\nprint(mutate(\"abcdef\"))\nprint(mutate(\"abcdef\"))\nprint(mutate(\"abcdef\"))","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Start the Genetic Algorithm"},{"metadata":{"trusted":true},"cell_type":"code","source":"# What is the fittest member of the population to start with?\nselect_best(initial_population, 1)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"def genetic_algorithm():\n    \"\"\" This is just meant to be a simple naive baseline. No need to make it more complex that it needs to be. \"\"\"\n    population = initial_population\n\n    for gen in range(GENERATIONS):\n        # Select the top half of the population and then fill back to the original population limit by making children.\n        population, _ = select_best(population, INIT_POP_SIZE//2)\n        children = []\n        for child in range(INIT_POP_SIZE//2):\n            children.append(cross_over(population[random.randint(0, INIT_POP_SIZE//2 - 1)], population[random.randint(0, INIT_POP_SIZE//2 - 1)]))\n        population.extend(children)\n        \n        # Add some mutations.\n        for m in range(MUTATIONS):\n            mutant = random.randint(0, INIT_POP_SIZE - 1)\n            population[mutant] = mutate(population[mutant])\n        \n        # Report on the best so far.\n        _, best_score = select_best(population, 1)        \n        print(f\"Generation: {gen} : {best_score}\")\n    \n    return select_best(population, 1)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"best_string, score = genetic_algorithm()\n\n# What single string did we generate?\nprint(best_string[0], score)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"# Build the submission. The csv is huge and very repitative. .gz files can be submitted directly, so let's compress it.\nsubm = pd.read_csv('../input/bms-molecular-translation/sample_submission.csv')\nsubm['InChI'] = best_string[0]\nsubm.to_csv('submission.csv', index=False)","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat":4,"nbformat_minor":4}