{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Making a Custom Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An evolutionary algorithm iteratively optimises one or more\n",
    "populations using a collection of evolutionary operators.\n",
    "Algorithms in EvoKit follow this structure: the algorithm\n",
    "should accept the initial population(s) and operators during\n",
    "initialisation, then iterate by calling `.step(...)`.\n",
    "\n",
    "<img src='media/emperor.svg' style='width: 35em'></img>\n",
    "\n",
    "This tutorial defines an $(\\mu+\\lambda)$ algorithm that maintains\n",
    "one population and accepts one suite of operators: one\n",
    "evaluator, one selector, and one variator. \n",
    "\n",
    "The following table indexes guides on how to construct these components:\n",
    "\n",
    "| Component  | Guide                                          |\n",
    "| ---------- | ---------------------------------------------- |\n",
    "|`Individual`|[OneMax tutorial](./onemax.ipynb#Individual)|\n",
    "|`Evaluator`|[Selector tutorial](./onemax.ipynb#Evaluator)|\n",
    "|`Selector`|[OneMax tutorial](./selector.ipynb)|\n",
    "|`Variator`|[OneMax tutorial](./onemax.ipynb#Variator)|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Setting the Seed\n",
    "\n",
    "EvoKit uses only one source of randomness: the `random` module.\n",
    "Setting random.seed fixes all randomness."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "random.seed(44313)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Manual Selection\n",
    "\n",
    "Before defining the algorithm, it might be helpful to see how\n",
    "things work \"under the hood\" and construct a simple algorithm by\n",
    "hand.\n",
    "\n",
    "For how to automate this process with an `core.Algorithm`,\n",
    "see section [Designing the Algorithm](#Designing-the-Algorithm)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Initialise Population\n",
    "\n",
    "The evolutionary process acts not on individuals, but populations.\n",
    "\n",
    "To begin, create the initial `Population` of bit string\n",
    "representations, then check that the individuals are correctly\n",
    "initialised. A population in EvoKit implements `list`: its items\n",
    "can be directly accessed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from evokit.core import Population\n",
    "from evokit.evolvables.binstring import BinaryString"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 1, 1, 1, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 0]]\n"
     ]
    }
   ],
   "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",
    "\n",
    "print(pop)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `.fitness` attribute of an individual stores its fitness.\n",
    "If this property is accessed while not set, the tuple `(\"nan\",)`\n",
    "is returned instead.\n",
    "\n",
    "To check if the `.fitness` is initialised, call `.has_fitness`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The fitness of an unevaluated individual is (nan,)\n",
      "It is _False_ that the fitness of `pop[0]` is defined.\n"
     ]
    }
   ],
   "source": [
    "print(\"The fitness of an unevaluated individual is\"\n",
    "      f\" {pop[0].fitness}\")\n",
    "\n",
    "print(f\"It is _{pop[0].has_fitness()}_ that the fitness of `pop[0]` is defined.\") "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Variate\n",
    "\n",
    "A variator creates new individuals (offspring) from existing\n",
    "ones. A mutator, in particular, is a variator that uses only\n",
    "one parent. All variators in EvoKit must ensure that operations\n",
    "performed on offspring do not affect the parent, this is best\n",
    "done by calling `Individual.copy`.\n",
    "\n",
    "The canonical mutator (`MutateBits`) flips each digit in a bit\n",
    "string with probability `mutation_rate`. Applying the mutator\n",
    "to the population creates a new population."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parent:    [[1, 1, 1, 1, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 0]]\n",
      "Offspring: [[1, 1, 1, 0, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 0]]\n"
     ]
    }
   ],
   "source": [
    "from evokit.evolvables.binstring import MutateBits\n",
    "variator = MutateBits(mutation_rate=0.1)\n",
    "\n",
    "offspring = variator.vary_population(pop)\n",
    "print (f\"Parent:    {pop}\")\n",
    "print (f\"Offspring: {offspring}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate\n",
    "\n",
    "The evaluator assigns to the `.fitness` of all individuals in a population.\n",
    "\n",
    "Evaluation sets the stage for selection. Consider which population the algorithm selects from: using $(\\mu+\\lambda)$, offspring competes with parents for selection. To implement this, call `Population.join` to create a population that includes individuals from `pop` and `offspring`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "joined_pool = pop + offspring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The canonical evaluator (`CountBits`) sums all digits in\n",
    "the string. Once the evaluator is initialised, call\n",
    "`.evaluate_population(...)` with the population as argument.\n",
    "Check that all individuals in the population are correctly evaluated.\n",
    "\n",
    "Note: Unlike its counterparts `Variator.vary_population` and\n",
    "`Selector.select_population`, `.evaluate_population` modifies its\n",
    "argument in place (by assigning to their `.fitness` attributes).\n",
    "To highlight this, `.evaluate_population(...)` returns `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "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, 1, 0, 1] is (4,)\n",
      "Fitness of [1, 1, 1, 1, 0] is (4,)\n",
      "Fitness of [1, 1, 1, 0, 0] is (3,)\n"
     ]
    }
   ],
   "source": [
    "from evokit.evolvables.binstring import CountBits\n",
    "\n",
    "CountBits().evaluate_population(joined_pool)\n",
    "\n",
    "for individual in joined_pool:\n",
    "    print(f\"Fitness of {individual} is {individual.fitness}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Select\n",
    "\n",
    "A selector selects from a `Population` into a strict subset.\n",
    "The `TruncationSelector`, in particular, selects individuals\n",
    "with the highest `.fitness`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The truncation selector selects [[1, 1, 1, 0, 1], [1, 1, 1, 1, 0], [1, 1, 1, 1, 1]].\n"
     ]
    }
   ],
   "source": [
    "from evokit.evolvables.selectors import TruncationSelector\n",
    "\n",
    "new_pop = TruncationSelector[BinaryString](budget=3)\\\n",
    "      .select_population(joined_pool)  # type: ignore\n",
    "print(f\"The truncation selector selects {new_pop}.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Designing the Algorithm\n",
    "\n",
    "Let's automate! To implement a custom algorithm, extend `Algorithm` and override at least two of its methods:\n",
    "\n",
    "* `.__init__(..)` initialises parameters of the algorithm itself. In this example, it accepts the initial population and a minimal set of operators.\n",
    "\n",
    "* `.step(..)` performs one iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from evokit.core import Algorithm\n",
    "from typing import override\n",
    "\n",
    "from evokit.core import Evaluator, Selector, Variator\n",
    "\n",
    "class SimpleMuPlusLambda(Algorithm):\n",
    "\n",
    "    @override\n",
    "    def __init__(self,\n",
    "                 population: Population[BinaryString],\n",
    "                 evaluator: Evaluator[BinaryString],\n",
    "                 selector: Selector[BinaryString],\n",
    "                 variator: Variator[BinaryString]) -> None:\n",
    "        self.population = population\n",
    "        self.evaluator = evaluator\n",
    "        self.selector = selector\n",
    "        self.variator = variator\n",
    "\n",
    "    @override\n",
    "    def step(self) -> None:\n",
    "        self.population = self.population + self.variator.vary_population(self.population)\n",
    "\n",
    "        self.evaluator.evaluate_population(self.population)\n",
    "\n",
    "        self.population = \\\n",
    "            self.selector.select_population(self.population)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The creation of individuals can also be automated. For example, `BinaryString.random` creates random binary strings of a given length. Take advantage of this to create a initial population."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial population: [[1, 0, 1, 0, 0], [0, 1, 1, 0, 1], [1, 1, 1, 1, 1]]\n"
     ]
    }
   ],
   "source": [
    "another_pop = Population((BinaryString.random(size=5)\n",
    "                                      for _ in range(3)))\n",
    "\n",
    "print(f\"Initial population: {another_pop}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initialise an algorithm with `another_pop` as its initial population, using operators mentioned above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "ctrl = SimpleMuPlusLambda(another_pop,\n",
    "                          CountBits(),\n",
    "                          TruncationSelector(budget=3),\n",
    "                          MutateBits(mutation_rate=0.1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the algorithm. Observe an increase in fitness across generations: the algorithm runs correctly!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current population: [[1, 1, 1, 0, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(4,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n",
      "Current population: [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]\n",
      "Current fitnesses: [(5,), (5,), (5,)]\n"
     ]
    }
   ],
   "source": [
    "for _ in range (10):\n",
    "    ctrl.step()\n",
    "    print(f\"Current population: {ctrl.population}\")\n",
    "    print(f\"Current fitnesses: {[ind.fitness for ind in ctrl.population]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Congratulations! You have implemented an evolutionary algorithm.\n",
    "This algorithm can be used with any combination of individuals and operators.\n",
    "\n",
    "In fact, `SimpleMuPlusLambda` differs by one line from the stock algorithm\n",
    "`evolvables.algorithms.SimpleLinearAlgorithm`, which implements\n",
    "$(\\mu, \\lambda)$ selection instead. A shortened version with\n",
    "event reporting removed is provided below:\n",
    "\n",
    "```python\n",
    "...\n",
    "class SimpleLinearAlgorithm(Algorithm, Generic[T]):\n",
    "    @override\n",
    "    def __init__(self,\n",
    "                 population: Population[T],\n",
    "                 evaluator: Evaluator[T],\n",
    "                 selector: Selector[T],\n",
    "                 variator: Variator[T]) -> None:\n",
    "        self.population = population\n",
    "        self.evaluator = evaluator\n",
    "        self.selector = selector\n",
    "        self.variator = variator\n",
    "        self.accountants: list[Accountant[SimpleLinearAlgorithm[T], Any]] = []\n",
    "\n",
    "    @override\n",
    "    def step(self) -> None:\n",
    "        self.population = self.variator.vary_population(self.population)\n",
    "        self.evaluator.evaluate_population(self.population)\n",
    "        self.population = self.selector.select_population(self.population)\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
}