{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Making a Custom Selector"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In an evolutionary algorithm, a selector selects from a set\n",
    "of individuals into a subset. Because the process uses the\n",
    "fitness of individuals, selection must take place after evaluation.\n",
    "\n",
    "This tutorial explains the selection operator (selector) and how\n",
    "to construct custom selectors.\n",
    "\n",
    "<img src='media/ec-locate-variator.svg' style='width: 30em'></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Initialise Population\n",
    "\n",
    "Evokit represents the population with `core.Population`. The\n",
    "selector can only act on populations.\n",
    "\n",
    "To begin, initialise a `Population` of binary string\n",
    "representations. For now, manually assign a `.fitness` to\n",
    "each individual. The `Evaluator` automates this process:\n",
    "see the [OneMax Tutorial](./onemax.ipynb) for an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from evokit.core import Population\n",
    "from evokit.evolvables.binstring import BinaryString"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "pop : Population[BinaryString] = Population[BinaryString]()\n",
    "\n",
    "pop.append(BinaryString(int('11111', 2), 5))\n",
    "pop.append(BinaryString(int('11110', 2), 5))\n",
    "pop.append(BinaryString(int('11100', 2), 5))\n",
    "pop.append(BinaryString(int('11000', 2), 5))\n",
    "pop.append(BinaryString(int('10000', 2), 5))\n",
    "pop.append(BinaryString(int('00000', 2), 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each individual, assign to its `.fitness` the sum of\n",
    "its bits. For compatibility with multi-objective problems,\n",
    "the `.fitness` should be a tuple (though EvoKit also\n",
    "accepts `float`, it would not pass type checking)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "for ind in pop:\n",
    "    ind.fitness = (sum(ind.to_bit_list()),)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Fitness of [1, 1, 1, 1, 1] is (5,)\n",
      "Fitness of [1, 1, 1, 1, 0] is (4,)\n",
      "Fitness of [1, 1, 1, 0, 0] is (3,)\n",
      "Fitness of [1, 1, 0, 0, 0] is (2,)\n",
      "Fitness of [1, 0, 0, 0, 0] is (1,)\n",
      "Fitness of [0, 0, 0, 0, 0] is (0,)\n"
     ]
    }
   ],
   "source": [
    "for individual in pop:\n",
    "    print(f\"Fitness of {individual} is {individual.fitness}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Selector\n",
    "\n",
    "The `core.Selector` automates the selection process. For\n",
    "compatibility with `core.Algorithm`, all custom selectors\n",
    "must derive `Selector`.\n",
    "\n",
    "The behaviour of a `Selector` is defined on two levels.\n",
    "A custom implementation must override at least one of the\n",
    "following methods:\n",
    "\n",
    "1. `.select_population` receives a population and returns\n",
    "a population.\n",
    " \n",
    "2. `.select` receives a tuple of individuals and returns a\n",
    "subset of it. It has no default implementation.\n",
    "\n",
    "The default implementation of `.select_population` repeatedly\n",
    "applies `.select` to the population, with replacement, until\n",
    "a given number of individuals are selected. The following\n",
    "figure describes its behaviour; see documentations\n",
    "for more information.\n",
    "\n",
    "<img src='media\\ek-selector-internals.svg' style='width: 20em'></img>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Create Selector\n",
    "\n",
    "Begin with creating the truncation selector. Because `.select_population`\n",
    "samples with replacement, simply overriding `.select` would not work: the\n",
    "selector would then repeatedly select and copy the best individual.\n",
    "\n",
    "Instead, override `.select_population` to take the _budget_ best individuals:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import override, Self\n",
    "from evokit.core import Selector\n",
    "from operator import attrgetter\n",
    "\n",
    "class TruncationSelector(Selector[BinaryString]):\n",
    "    @override\n",
    "    def select_population(self: Self,\n",
    "                          from_population: Population[BinaryString])\\\n",
    "            -> Population[BinaryString]:\n",
    "        \n",
    "        return Population(sorted(list(from_population), key=attrgetter(\"fitness\"))\n",
    "                          [-self.budget:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Apply Selector\n",
    "\n",
    "An `Algorithm` typically [^1] uses a selector by calling\n",
    "`.select_population(...)`. With a budget of 2, the selector\n",
    "returns the top two individuals by fitness.\n",
    "\n",
    "Apply the newly defined TruncationSelector to `pop`. The selector\n",
    "should return `[1, 1, 1, 1, 1]` and `[1, 1, 1, 1, 0]`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "From [[1, 1, 1, 1, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 0], [1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]],\n",
      "the selector selects [[1, 1, 1, 1, 0], [1, 1, 1, 1, 1]].\n"
     ]
    }
   ],
   "source": [
    "SELECTION_BUDGET: int = 2\n",
    "\n",
    "old_pop = pop\n",
    "\n",
    "selector = TruncationSelector(SELECTION_BUDGET)\n",
    "\n",
    "new_pop = selector.select_population(old_pop)\n",
    "\n",
    "print(f\"From {old_pop},\\nthe selector selects {new_pop}.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Congratulations! You have implemented a canonical selector.\n",
    "\n",
    "In fact, the code used in this tutorial is an near exact copy\n",
    "of `evolvables.selectors.TruncationSelector`. Its source code in a past\n",
    "version is reproduced below.\n",
    "\n",
    "The source code of EvoKit is permissively licensed, transparent, and\n",
    "copyable. Be free to take, in whole or in part, from stock operators\n",
    "to make your own!\n",
    "\n",
    "```python\n",
    "...\n",
    "class TruncationSelector(Selector[D]):\n",
    "    \"\"\"Simple selector that select individuals with highest fitness.\n",
    "    \"\"\"\n",
    "    @override\n",
    "    def __init__(self: Self, budget: int):\n",
    "        super().__init__(budget)\n",
    "\n",
    "    @override\n",
    "    def select_population(self: Self,\n",
    "                          from_population: Population[D]) -> Population[D]:\n",
    "        return Population[D](*sorted(list(from_population),\n",
    "                                     key=attrgetter(\"fitness\"))[-self.budget:])\n",
    "...\n",
    "```"
   ]
  }
 ],
 "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.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}