{"cells":[{"metadata":{},"cell_type":"markdown","source":"# Top 10 Position with First Genetic Algorithm on GPU! 🔥\n\n\n## How I came up with this solution?\n\nFor the Kaggle [Conway's Reverse Game of Life 2020](https://www.kaggle.com/c/conways-reverse-game-of-life-2020/overview) competition, I tried many approaches and I also wanted to try something new for me: **Genetic Algorithm**. \n\nI looked up existing Kaggle notebooks using Genetic Algorithm, but none of them were using a GPU accelerator (sorry if I am wrong and missed one). It puzzled me as the GPU is faster than the CPU. I told myself \"challenge accepted, let's make a genetic algorithm on the GPU!\".\n\nImplementing this genetic algorithm from scratch was tought but I learned a lot in the process about genetic algorithm (first purpose), but also on `pytorch` and how to optimize using `NVIDIA Nsight`.\n\n\n## Results\n\nThis solution performed very well during this competition as this present notebook alone [scores in the top-10 leaderboard](https://www.kaggle.com/c/conways-reverse-game-of-life-2020/leaderboard). This new approach helped improving final solution of our team `Under a Penny`.\n\nI noticed the algorithm is running faster on RTX-2080 than Kaggle's P-100, probably thanks to the newer version of tensor-cores.\n\n\n## Requirements\n\nAll we need are :\n\n - `pytorch` to implement the Genetic Algorithm on GPU\n - `pandas` to load and write .csv files\n\n## Implementation"},{"metadata":{"trusted":true},"cell_type":"code","source":"import time\nimport pandas as pd\nimport torch","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"torch.backends.cudnn.benchmark = True\ntorch.backends.cudnn.deterministic = False","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Constants"},{"metadata":{"trusted":true},"cell_type":"code","source":"N = 25  # grid dimension\ndevice = 'cuda'\nTEST_CSV = '../input/conways-reverse-game-of-life-2020/test.csv'\nOUTPUT_CSV = 'submission.csv'","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Apply Game Of Life steps\n\n`forward` : applies Game Of Life rules `delta` times on a board of cells (`grid`).\n\nThe rules are simple and are defined in the [Kaggle competition description](https://www.kaggle.com/c/conways-reverse-game-of-life-2020/overview/description):\n\n> The Game of Life is a cellular automaton created by mathematician John Conway in 1970. The game consists of a board of cells that are either on or off. One creates an initial configuration of these on/off states and observes how it evolves. There are four simple rules to determine the next state of the game board, given the current state:\n>\n>    - *Overpopulation*: if a living cell is surrounded by more than three living cells, it dies.\n>    - *Stasis*: if a living cell is surrounded by two or three living cells, it survives.\n>    - *Underpopulation*: if a living cell is surrounded by fewer than two living cells, it dies.\n>    - *Reproduction*: if a dead cell is surrounded by exactly three cells, it becomes a live cell.\n"},{"metadata":{"trusted":true},"cell_type":"code","source":"cv = torch.nn.Conv2d(1, 1, kernel_size=3, padding=1, padding_mode='circular', bias=False)\ncv.requires_grad=False\ncv.weight = torch.nn.Parameter(\n    torch.tensor(\n        [[[[ 1., 1., 1.],\n           [ 1., 0., 1.],\n           [ 1., 1., 1.]]]],\n        device=device,\n        dtype=torch.float16\n    ),\n    requires_grad=False,\n)\n\n\n@torch.jit.script\ndef forward(grid, delta: int):\n    N=25\n    g = grid.reshape(-1, 1, N, N)\n    for _ in torch.arange(delta):\n        g = g.to(torch.float16)\n        neighbor_sum = cv(g)\n        g = ((neighbor_sum == 3) | ((g == 1) & (neighbor_sum == 2)))\n    return g.reshape(-1, N, N)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Genetic algorithm\n\nI highly suggest to read [How the Genetic Algorithm works](https://www.mathworks.com/help/gads/how-the-genetic-algorithm-works.html) webpage as it explains many concepts mentionned in following sections of this notebook.\n\n`random_parents` : create a random initial population made of `n_parents` NxN grids"},{"metadata":{"trusted":true},"cell_type":"code","source":"@torch.jit.script\ndef random_parents(n_parents: int, device: str):\n    N = 25\n    RANDOM_ALIVE = .2\n    return torch.rand((n_parents, N, N), device=device) > (1-RANDOM_ALIVE)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"`select_best`: Scores each member of the current population `parents` by computing its fitness value. For this competition, the fitness value is the number of errors between a `target` and a population individual after applying `delta` time the Game Of Live rules. The functions returns the `n_best` best performing individuals."},{"metadata":{"trusted":true},"cell_type":"code","source":"@torch.jit.script\ndef loss(input, target):\n    return torch.sum(input ^ target, dim=(-1,-2))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"@torch.jit.script\ndef select_best(parents, delta: int, target, n_best: int):\n    scores = loss(forward(parents, delta), target)\n    best_values, best_indices = torch.topk(scores, n_best, dim=0, largest=False, sorted=True)\n    new_parents = parents[best_indices, ...]\n    return new_parents, best_values[0], new_parents[0, ...]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"`random_combine`: combining the vector entries of a pair of parents. It is also called _crossover_."},{"metadata":{"trusted":true},"cell_type":"code","source":"@torch.jit.script\ndef random_combine(parents, n_offsprings: int, device: str, pre_masks):\n    N = 25\n    \n    dads = torch.randint(low=0, high=parents.shape[0], size=(n_offsprings,),\n                         device=device, dtype=torch.long)\n    dads = parents[dads, ...]\n    \n    moms = torch.randint(low=0, high=parents.shape[0], size=(n_offsprings,),\n                         device=device, dtype=torch.long)\n    moms = parents[moms, ...]\n    \n    masks = pre_masks[torch.randint(low=0, high=pre_masks.shape[0], size=(n_offsprings,),\n                                    device=device, dtype=torch.long)]\n\n    return torch.where(masks, dads, moms)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"`precomputes_masks`: pre-computes masked used for combining the vector entries of a pair of parents in `random_combine`."},{"metadata":{"trusted":true},"cell_type":"code","source":"def precomputes_masks():\n    N = 25\n    BLOCK_SIZE = 17\n\n    block = torch.nn.Conv2d(1, 1, kernel_size=BLOCK_SIZE, padding=BLOCK_SIZE//2,\n                            padding_mode='circular', bias=False)\n    block.requires_grad=False\n    block.weight = torch.nn.Parameter(\n        torch.ones((1, 1, BLOCK_SIZE, BLOCK_SIZE),\n            device=device,\n            dtype=torch.float16\n        ),\n        requires_grad=False,\n    )\n\n    masks = torch.zeros((N * N, 1, N, N), device=device, dtype=torch.float16)\n    \n    for x in range(N):\n        for y in range(N):\n            masks[x * N + y, 0, x, y] = 1.\n    masks = block(masks)\n    \n    return masks[:, 0, ...] > .5","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"`mutate`: makes random changes on parents."},{"metadata":{"trusted":true},"cell_type":"code","source":"@torch.jit.script\ndef mutate(parents, device: str):\n    MUTATION = .0016  # .005 \n    mutations = torch.rand(parents.shape, device=device) < MUTATION\n    return parents ^ mutations","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"`optimize_one_puzzle`: runs our genetic algorithm on one puzzle"},{"metadata":{"trusted":true},"cell_type":"code","source":"@torch.jit.script\ndef optimize_one_puzzle(delta: int, data, device: str, pre_masks):\n    N = 25\n    N_GENERATION = 30  # Number of generations\n    P = 4_500  # population\n    N_BEST = P // 30  # best to keep as new parents\n    N_ELITES = 8  # parents unchanged for next generation\n    \n    best_score = torch.tensor([N*N], device=device)\n    best = torch.zeros((N,N), device=device).to(torch.bool)\n    parents = random_parents(P, device)\n\n    elites = torch.empty((1, N, N), dtype=torch.bool, device=device)\n    elites[0, ...] = data  # set target as potential dad ;)\n\n    for i in range(N_GENERATION):\n        parents = random_combine(parents, P, device, pre_masks)\n        parents = mutate(parents, device)\n        parents[:N_ELITES, ...] = elites\n        parents, best_score, best = select_best(parents, delta, data, N_BEST)\n        # Some of the individuals in the current population that have lower fitness are chosen as elite.\n        # These elite individuals are passed to the next population.\n        elites = parents[:N_ELITES, ...]\n        if best_score == 0:  # early stopping\n            break\n\n    return best_score, best","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"`optimize_all_puzzles`: It tries to find approximate solution for all puzzles 😃"},{"metadata":{"scrolled":false,"trusted":true},"cell_type":"code","source":"@torch.jit.script\ndef optimize_all_puzzles(deltas, df, device: str, pre_masks):\n    sub = df.clone()\n    \n    for n in torch.arange(df.shape[0]):\n        delta = deltas[n]\n        data = df[n, ...]\n        _, sub[n, ...] = optimize_one_puzzle(delta, data, device, pre_masks)\n\n    return sub","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Load Puzzles to solve"},{"metadata":{"trusted":true},"cell_type":"code","source":"df = pd.read_csv(TEST_CSV, index_col='id')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Use final state as our baseline for submission"},{"metadata":{"trusted":true},"cell_type":"code","source":"submission = df.copy()\nsubmission.drop(['delta'], inplace=True, axis=1)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Push data to GPU"},{"metadata":{"trusted":true},"cell_type":"code","source":"indexes = df.index\ndeltas = torch.from_numpy(df.delta.values).to(device)\ndf = torch.BoolTensor(df.values[:, 1:].reshape((-1, N, N))).to(device)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Let's optimize puzzles!"},{"metadata":{"scrolled":false,"trusted":true},"cell_type":"code","source":"start_time = time.time()\npre_masks = precomputes_masks()\nsub = optimize_all_puzzles(deltas, df, device, pre_masks)\nprint(f'Processed {sub.shape[0]:,} puzzles in {time.time() - start_time:.2f} seconds 🔥🔥🔥')","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Save our submission"},{"metadata":{"trusted":true},"cell_type":"code","source":"submission.rename(columns={f'stop_{x}': f'start_{x}' for x in range(N*N)}, inplace=True)\nsubmission.iloc[:sub.shape[0], :] = sub.reshape((-1, N*N)).cpu().numpy().astype(int)\nsubmission.to_csv(OUTPUT_CSV)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"### Compute leaderboard score"},{"metadata":{"trusted":true},"cell_type":"code","source":"def leaderboard_score(deltas, df, sub, device: str):\n    result = torch.empty(sub.shape[0], device=device, dtype=torch.long)\n    for delta in range(1, 6):\n        start = sub[deltas == delta]\n        end   = df[deltas == delta]\n        result[deltas == delta] = loss(forward(start, delta), end)\n    print('Leaderboard score:', torch.sum(result).item() / (result.shape[0]*N*N))","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"leaderboard_score(deltas, df, sub, device)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# Conclusion\n\nI learned a lot along the way about Genetic Algorithm, pytorch and how to optimize computation on the GPU.\n\nIf you like this notebook, please leave a comment 🖊, upvote 👍, and put a smile on your face 😀."}],"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}