3-Bio-Inspired/02-bio-inspired-genetic-algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "# Genetic Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "<p style='text-align: justify;'> \n",
    "In this section, we will study the concepts of genetic algorithm and your applications.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Objectives"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* **Understand** how a genetic algorithm works,\n",
    "* **Learn** the basic concepts of genetic algorithms,\n",
    "* **Create** a genetic algorithm using Intel® Python,\n",
    "* **Resolve** searching problems using a genetic algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## The problem: Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'> \n",
    "Within the field of optimization, we encounter search problems where the task is to find the best solution within a vast space of possibilities. Conventional methods often face difficulties in navigating through the complexities of these problems, resulting in suboptimal or time-consuming solutions. To solve this challenge, we need to implement algorithms capable of searching for the solution that optimizes the results.\n",
    "</p>   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The solution: Genetic algorithm (GA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "Genetic algorithms are algorithms whose inspiration is based on the process of biological evolution proposed by Charles Darwin. They rely on concepts such as natural selection, heredity, and genetic crossover. This algorithm was initially proposed by John Holland in the 1960s as part of his work in adaptive systems. Since then, they have shown themselves to be a powerful approach for solving optimization problems in various areas.\n",
    "</p>\n",
    "\n",
    "<div style=\"text-align:center\">\n",
    "<img src=\"./images/figure01_darwin_evolution.jpg\" style=\"width: 400px;\">\n",
    "</div>\n",
    "\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "Genetic algorithms are applied to solve search problems. They are particularly useful when the search for the solution space is complex, extensive, or cannot be carried out directly and deterministically. By simulating processes of biological evolution, genetic algorithms can explore and improve candidate solutions over several generations, aiming to achieve the best possible result within the search space. Problems involving traffic routes, route optimization in logistics, protein chain sequencing, finding the shortest path between two cities, and even problems like automatic planning and routing of electronic circuits can be solved using this algorithm.\n",
    "</p>\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "The genetic algorithms are based on a population of candidate solutions treated as a population of individuals, and the evaluation function (fitness) determines how well each individual adapts to the environment or objective of the problem. The fitter individuals have a higher probability of being selected for reproduction, allowing their characteristics to be passed on to the next generation. This logic is quite similar to what we observe in the reproduction of the human population. Just like in biological evolution, where the fittest individuals have a better chance of passing on their genes to the next generation, genetic algorithms use the principles of natural selection and genetic crossover to explore and improve solutions over successive generations, ultimately converging towards optimal or near-optimal solutions to the given problem.\n",
    "</p>    \n",
    "\n",
    "<div style=\"text-align:center\">\n",
    "<img src=\"./images/figure02_human_population.png\" style=\"width: 600px;\">\n",
    "</div>\n",
    " \n",
    "<p style='text-align: justify;'>\n",
    "Throughout generations, genetic algorithms explore different combinations of solutions, seeking to find the best possible solution within the search space. This nature-inspired approach allows genetic algorithms to be a powerful optimization tool capable of handling complex problems and finding approximate or optimal solutions in a variety of practical applications.\n",
    "</p>\n",
    "<p style='text-align: justify;'>\n",
    "By mimicking the principles of natural selection, genetic crossover, and mutation, these algorithms efficiently explore the solution space and can adapt to changing conditions, leading to the discovery of solutions that might be difficult or time-consuming to find through traditional optimization methods. As a result, genetic algorithms have proven to be versatile and widely used in various fields, including engineering, logistics, computer science, finance, and more. They provide an effective means of tackling real-world problems and obtaining satisfactory solutions in scenarios where other traditional algorithms may struggle or be less efficient.\n",
    "</p>\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "These are just a few examples of existing bio-inspired algorithms. Each of them is suitable for different types of problems, and the choice of the right algorithm will depend on the specific nature of the problem at hand. These bio-inspired approaches have proven to be useful in various areas, including optimization, machine learning, robotics, and artificial intelligence.\n",
    "</p>\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "Let us now approach the structure of the genetic algorithm since we already understand its nature and functioning.    \n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Structure of the genetic algorithm\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "The genetic algorithm is composed of different components that work together to solve optimization problems. These components represent key steps of the nature-inspired evolutionary process. Below, we can see how a genetic algorithm is structured.\n",
    "</p>\n",
    "\n",
    "<div style=\"text-align:center\">\n",
    "<img src=\"./images/figure03_genetic_algoritm_structure.png\" style=\"width: 500px;\">\n",
    "</div>\n",
    "</br>\n",
    "<p style='text-align: justify;'>\n",
    "Now that we have become familiar with the basic structure of a genetic algorithm, it is of utmost importance to understand the functioning of each element of this structure. Our study journey begins with the analysis of the creation of the initial population, and subsequently the other elements that compose this structure.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### ⊗ **Population creation** \n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "The process of creating a population is the initial and fundamental step for the operation of a genetic algorithm. This population is composed of a set of individuals that represent potential solutions to the optimization problem. The population is usually created randomly, but it can also be based on prior knowledge or specific heuristics, depending on the problem at hand. In the case of genetic algorithms, the population can be represented by lists, real numbers, or a string of bits, with the latter being the most commonly used representation.\n",
    "</p>\n",
    "<div style=\"text-align:center\">\n",
    "<img src=\"./images/figure04_digital_population.png\" style=\"width: 850px;\">\n",
    "</div>\n",
    "<p style='text-align: justify;'>\n",
    "The size of the population is an important parameter to be considered. Larger populations can explore the search space more extensively, but they may also require more computational resources. On the other hand, smaller populations can converge more quickly, but they may also run the risk of getting stuck in local minima.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "Let us see how the creation of a population is done using a computational algorithm.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "POPULATION_SIZE = 4\n",
    "\n",
    "MAX_GENERATIONS = 100\n",
    "\n",
    "MUTATION_RATE = 0.1\n",
    "\n",
    "def create_population(population_size, individual_length):\n",
    "    population = []\n",
    "    for _ in range(population_size):\n",
    "        individual = \"\".join(random.choice(\"01\") for _ in range(individual_length))\n",
    "        population.append(individual)\n",
    "    return population\n",
    "\n",
    "def objective_function(individual):\n",
    "    return int(individual, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "Now that our population has been created, it is necessary to evaluate the fitness of the individuals to select parents for reproduction. This evaluation is crucial to determine which individuals are more likely to contribute their genetic characteristics in forming the next generations.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### ⊗ **Evaluation function**\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "The evaluation function, also known as the fitness function, is responsible for measuring how good each individual is in relation to the problem's objective. It assigns a score or numerical value to each candidate solution, indicating how well it is adapted to the environment or objective being optimized. The better the solution's performance, the higher its fitness score will be.\n",
    "</p>\n",
    "\n",
    "The choice of the appropriate evaluation function depends on the specific context and the objective of the genetic algorithm. Some of the most commonly used evaluation functions in genetic algorithms include:\n",
    "\n",
    "* **Objective function:** it is a function whose goal is to maximize or minimize a function in an optimization problem. It represents the main objective of the problem and guides the search for suitable solutions.\n",
    "\n",
    "* **Normalized fitness function:** it is a normalized version of the objective or cost function, ensuring that all solutions are comparable, regardless of the units used.\n",
    "\n",
    "* **Distance to target:** a function that measures the distance between the candidate solution and the desired target or ideal solution.\n",
    "\n",
    "* **Mean squared error:** applied in regression problems, it measures the difference between predicted values and known actual values.\n",
    "\n",
    "* **Convergence Index:** used in clustering problems, it evaluates the quality of the formed clusters.\n",
    "\n",
    "* **Feasibility function:** in problems with constraints, it measures the extent to which a candidate solution violates or complies with the imposed constraints.\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "In our study, we will focus on the development of the genetic algorithm, using the objective function for evaluating the generated populations. The objective function is a measure that represents the performance of each individual in the population regarding the optimization problem. The formula of the objective function can be given by:\n",
    "</p>\n",
    "\n",
    "    \n",
    "$$ Fit = \\sum_{i=1}^{N} f(x_i)$$\n",
    "\n",
    "where we have:\n",
    "* $Fit$ is the value of the objective function,\n",
    "* $N$ is the size of the population,\n",
    "* $i$ is the number of the individual,\n",
    "* $f(x_i)$ is the objective function that represents the performance of individual $i$ in the population."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>    \n",
    "The evaluation function is created through an algorithm that follows the logic below.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def evaluate_population(population):\n",
    "    return [objective_function(individual) for individual in population]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>    \n",
    "Once we have defined the evaluation function, we should now proceed with the selection of parents and their reproduction, as we will see next.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### ⊗ **Selection of parents process**\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "In the selection of parents, the most adapted individuals have a higher probability of being chosen for reproduction. This step is crucial to ensure that the most promising characteristics of the solutions are transmitted to the subsequent generations, allowing for an efficient exploration of the search space.\n",
    "</p>\n",
    "<p style='text-align: justify;'>\n",
    "One of the most commonly used strategies is the roulette wheel selection, where a virtual roulette wheel is created, and each portion of this wheel is proportional to the number of individuals in the population with higher fitness. From this point, the roulette wheel is spun, and the sector where the arrow stops determines which individual has been selected as a parent. This process is repeated to select the second parent.\n",
    "</p>\n",
    "\n",
    "<div style=\"text-align:center\">\n",
    "<img src=\"./images/figure05_roulette.png\" style=\"width: 300px;\">\n",
    "</div>\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "But how is each of the roulette wheel's slices determined? This is done using a mathematical equation that calculates the probability of selection proportional to the fitness of the individuals, ensuring that the most adapted ones have a higher chance of being chosen as parents. The equation is given by:\n",
    "</p>\n",
    "\n",
    "$$p_1 = \\frac{f(x_i)}{\\sum_{k=1}^{N} f(x_k)}$$\n",
    "\n",
    "Where we have:\n",
    "\n",
    "* $p_1$ represents the probability of individual $x_i$ being selected as a parent,\n",
    "* $f(x_i)$  is the cost function (or fitness function) of individual $x_i$, representing the performance or quality measure of the individual,\n",
    "* $N$  represents the total size of the population of individuals,\n",
    "* $k$  is an iteration variable that ranges from $1$ to $N$,\n",
    "* $i$  represents a specific individual in the population for which we are calculating the probability of proportional selection.\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "There are other methods whose objective is to favor the fittest individuals (with higher fitness values) to ensure the convergence of the algorithm towards better solutions over the generations. Some of the most common selection methods are:\n",
    "</p>\n",
    "\n",
    "* **Tournament selection:** in this method, a fixed number of individuals is randomly selected from the population, and the individual with the best fitness value among these participants is chosen to be part of the next generation.\n",
    "\n",
    "* **Rank selection:** individuals are sorted based on their fitness values, and the selection probability is determined by the ranking of the individuals.\n",
    "\n",
    "* **Elitism:** this is a strategy that aims to preserve the fittest individuals (with higher fitness values) from one generation to the next without any changes. It means that the best individuals do not undergo crossover or mutation and are directly copied to the next generation.\n",
    "\n",
    "* **Stochastic universal sampling:** a variation of roulette wheel selection that selects multiple individuals simultaneously, creating proportional \"slices\" on the roulette wheel and randomly selecting points for individual selection.\n",
    "\n",
    "* **Linear ranking selection:** a variation of rank selection, where individuals are sorted based on their fitness values and are assigned weights with a linear progression, so that individuals with higher fitness values have a higher probability of being selected, but the difference between the weights is smaller compared to Rank Selection.\n",
    "\n",
    "* **Boltzmann selection:** inspired by the Boltzmann distribution function in physics, this method assigns selection probabilities to individuals based on a formula that takes into account the current temperature of the population and the fitness value of each individual."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "From these concepts, we can determine that our algorithm consists of:    \n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def roulette_selection(population, fitness):\n",
    "    total_fitness = sum(fitness)\n",
    "    probabilities = [fit / total_fitness for fit in fitness]\n",
    "    selected_parents = random.choices(population, weights=probabilities, k=2)\n",
    "    return selected_parents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "Now that the parents have been selected, let's perform the crossover between the pairs. We will see how this is done using the genetic operators.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "### ⊗ **Reproduction process of individuals**\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "The reproduction process in genetic algorithms is based on some genetic operators, among which crossover and mutation stand out. Each of these operators plays a crucial role in the evolution of the population of solutions over several generations, allowing new features to be introduced, valuable characteristics to be preserved, and solutions to be refined to achieve optimal results. Let's learn about each of them.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### ⊗ **Crossover**\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "Crossover is a form of genetic recombination where two selected individuals are combined to generate new individuals (offspring). In this process, parts of the chromosomes from the parents are exchanged or combined to create offspring with mixed characteristics from the parents. Crossover helps to explore the search space by combining the good characteristics of the parental solutions.\n",
    "</p>\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "In genetic algorithms, chromosomes are represented by a sequence of bits, where one part represents the genetic material of the father and the other part represents the genetic material of the mother. Crossover is a process where we randomly select a crossover point in the gene sequences of the parents. The genes before this point are copied from one parent to a child, and the genes after this point are copied from the other parent to the other child. This process of crossing genetic information increases the diversity of the population and can generate new individuals with beneficial characteristics inherited from both parents.  \n",
    "</p>\n",
    "\n",
    "<div style=\"text-align:center\">\n",
    "<img src=\"./images/figure06_crossover.png\" style=\"width: 600px;\">\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "It is important to know that besides crossover, there are other important methods that can be used in genetic algorithms to improve the diversity of the population and increase the chances of finding optimal solutions. Some of these additional methods are:\n",
    "</p>    \n",
    "\n",
    "* **Inversion:** this is a technique that alters the order of a specific segment of an individual's genes. This process is performed randomly and creates a new solution with different characteristics from the original individual. Inversion can be particularly useful in problems where the order of genes has a significant impact on the solution.\n",
    "\n",
    "* **Transposition:** this is an operator that moves a subsequence of genes from one position to another within an individual's chromosome. This operation creates variations in the gene configuration, resulting in new candidate solutions.\n",
    "\n",
    "* **Insertion:** this method adds a new gene at a random position in an individual's chromosome. This technique is useful for exploring new combinations of features and increasing diversity in the population.\n",
    "\n",
    "* **Linear Crossover:** this is a variation of traditional crossover that performs a linear combination of the parents' genes to form the offspring. In this method, the parents' genes are weighted by random coefficients, creating a new solution that combines characteristics from both parents.\n",
    "\n",
    "* **Mask Crossover:** this is a crossover method that uses a binary mask to determine which genes are inherited from each parent. The mask is a sequence of random bits that define which genes from parent 1 and parent 2 are copied to the offspring.\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "Let us now, that we understand the concept of crossover, create the respective algorithm.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def crossover(parent1, parent2):\n",
    "    split_point = len(parent1) // 2\n",
    "    child1 = parent1[:split_point] + parent2[split_point:]\n",
    "    child2 = parent2[:split_point] + parent1[split_point:]\n",
    "    return child1, child2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "After performing the crossover of parents, generating offspring, it will be necessary to undergo a mutation in the individuals. This step introduces variation in the genetic material of the population, allowing the exploration of new solutions and avoiding the stagnation of the search in a local minimum. The combination of crossover and mutation makes the genetic algorithm more powerful, enabling the discovery of optimal or approximate solutions over generations.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### ⊗ **Mutation** \n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "Mutation is an operator that introduces random changes in individuals. These changes should occur with low probability (usually from 1% to 5%), allowing the algorithm to explore new regions of the search space. Mutation plays a crucial role in diversifying the population, preventing the algorithm from getting trapped in undesirable local optima.\n",
    "</p>\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "In genetic algorithms, the mutation rate is represented by a value randomly generated between 0 and 1 and represents the probability that a gene in an individual undergoes mutation. This rate is an adjustable parameter of the algorithm and is important for controlling the level of genetic variation introduced into the population in each generation.\n",
    "</p>\n",
    "\n",
    "\n",
    "<div style=\"text-align:center\">\n",
    "<img src=\"./images/figure07_mutation.png\" style=\"width: 600px;\">\n",
    "</div>\n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "The probability of mutation of a set of bits is given by:   \n",
    "</p>\n",
    "\n",
    "$$N_g = {P_m}*{N}$$\n",
    "\n",
    "Where:\n",
    "\n",
    "* $N_g$ is probability of mutation of a set of genes,\n",
    "* $P_m$ is mutation rate of a set of genes, which can range from 1 to 5% of the total number of bits,\n",
    "* $N$ is total number of genes in a chromosome."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "In mutation, besides operating at the bit level, it is possible to apply this operator to different types of data, depending on the nature of the problem and the type of encoding used to represent the candidate solutions in the genetic algorithm. Some of the other data types where mutation can be applied include:\n",
    "</p>\n",
    "\n",
    "* **Integer numbers:** when solutions are represented by integer numbers, mutation can consist of altering the value of one or more digits of the number.\n",
    "\n",
    "* **Floating-point numbers:** in problems with solutions represented by floating-point numbers (real numbers), mutation can consist of adding or subtracting a random value, or multiplying/dividing by a factor, to create variations in the solution.\n",
    "\n",
    "* **Strings and sequences:** if solutions are represented by sequences of characters, such as in DNA string optimization problems or task sequencing, mutation can alter or swap specific characters to create new candidate solutions.\n",
    "\n",
    "* **Sets:** in problems involving the representation of solutions as sets of elements, mutation can add, remove, or swap elements of the set to generate variations.\n",
    "\n",
    "* **Permutations:** when solutions are represented by permutations, as in routing or sequencing problems, mutation can swap the order of elements in the permutation.\n",
    "\n",
    "* **Complex data structures:** in problems that use more complex data structures, such as trees or graphs, mutation can perform specific operations, such as adding, removing, or swapping nodes or edges to generate new solutions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "Now that we understand the concept of mutation, we can represent it using the following algorithm.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mutate(individual, mutation_rate):\n",
    "    mutated_individual = \"\"\n",
    "    for bit in individual:\n",
    "        if random.random() < mutation_rate:\n",
    "            mutated_bit = \"0\" if bit == \"1\" else \"1\"\n",
    "        else:\n",
    "            mutated_bit = bit\n",
    "        mutated_individual += mutated_bit\n",
    "    return mutated_individual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "After performing the mutation of individuals, we must now analyze and verify if the generated population has evolved significantly and is close to the optimal solution of the proposed problem.    \n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ⊗ **Generated population** \n",
    "\n",
    "<p style='text-align: justify;'>\n",
    "After the steps of reproduction, crossover, and mutation, the individuals go through a validation process where it is checked whether the generated population is close to the optimal or approximate solution for the optimization problem. The algorithm responsible for this step is given by: \n",
    "</p>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generation 0:\n",
      "Individual: 1101, Fitness: 13\n",
      "Individual: 1000, Fitness: 8\n",
      "Individual: 1110, Fitness: 14\n",
      "Individual: 0001, Fitness: 1\n",
      "Best Individual: 1110, Best Fitness: 14\n",
      "---------------------------------------\n",
      "Generation 1:\n",
      "Individual: 1001, Fitness: 9\n",
      "Individual: 1101, Fitness: 13\n",
      "Individual: 1101, Fitness: 13\n",
      "Individual: 0000, Fitness: 0\n",
      "Best Individual: 1101, Best Fitness: 13\n",
      "---------------------------------------\n",
      "Generation 2:\n",
      "Individual: 1100, Fitness: 12\n",
      "Individual: 1001, Fitness: 9\n",
      "Individual: 1101, Fitness: 13\n",
      "Individual: 1001, Fitness: 9\n",
      "Best Individual: 1101, Best Fitness: 13\n",
      "---------------------------------------\n",
      "Generation 3:\n",
      "Individual: 0000, Fitness: 0\n",
      "Individual: 1100, Fitness: 12\n",
      "Individual: 0110, Fitness: 6\n",
      "Individual: 1101, Fitness: 13\n",
      "Best Individual: 1101, Best Fitness: 13\n",
      "---------------------------------------\n",
      "Generation 4:\n",
      "Individual: 1101, Fitness: 13\n",
      "Individual: 1010, Fitness: 10\n",
      "Individual: 1100, Fitness: 12\n",
      "Individual: 1101, Fitness: 13\n",
      "Best Individual: 1101, Best Fitness: 13\n",
      "---------------------------------------\n",
      "Generation 5:\n",
      "Individual: 1001, Fitness: 9\n",
      "Individual: 1100, Fitness: 12\n",
      "Individual: 0101, Fitness: 5\n",
      "Individual: 1101, Fitness: 13\n",
      "Best Individual: 1101, Best Fitness: 13\n",
      "---------------------------------------\n",
      "Generation 6:\n",
      "Individual: 1100, Fitness: 12\n",
      "Individual: 1100, Fitness: 12\n",
      "Individual: 1101, Fitness: 13\n",
      "Individual: 0111, Fitness: 7\n",
      "Best Individual: 1101, Best Fitness: 13\n",
      "---------------------------------------\n",
      "Generation 7:\n",
      "Individual: 1100, Fitness: 12\n",
      "Individual: 1101, Fitness: 13\n",
      "Individual: 1111, Fitness: 15\n",
      "Individual: 0100, Fitness: 4\n",
      "Best Individual: 1111, Best Fitness: 15\n",
      "---------------------------------------\n"
     ]
    }
   ],
   "source": [
    "def genetic_algorithm():\n",
    "    population = create_population(POPULATION_SIZE, 4)\n",
    "\n",
    "    for generation in range(MAX_GENERATIONS):\n",
    "        print(f\"Generation {generation}:\")\n",
    "        fitness = evaluate_population(population)\n",
    "        for individual, fit in zip(population, fitness):\n",
    "            print(f\"Individual: {individual}, Fitness: {fit}\")\n",
    "\n",
    "        best_individual_idx = fitness.index(max(fitness))\n",
    "        best_individual = population[best_individual_idx]\n",
    "        print(f\"Best Individual: {best_individual}, Best Fitness: {max(fitness)}\")\n",
    "        print(\"---------------------------------------\")\n",
    "\n",
    "        if max(fitness) == 15:\n",
    "            break\n",
    "\n",
    "        new_population = []\n",
    "        for _ in range(POPULATION_SIZE // 2):\n",
    "            parent1, parent2 = roulette_selection(population, fitness)\n",
    "            child1, child2 = crossover(parent1, parent2)\n",
    "            child1 = mutate(child1, MUTATION_RATE)\n",
    "            child2 = mutate(child2, MUTATION_RATE)\n",
    "            new_population.extend([child1, child2])\n",
    "\n",
    "        population = new_population\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    genetic_algorithm()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style='text-align: justify;'>\n",
    "Now that we are familiar with the complete structure of a genetic algorithm, it's time to apply our knowledge through a practical challenge. Let's engage in an exercise that will allow us to put the learned concepts into practice and enhance our problem-solving skills using this powerful evolutionary approach.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ☆ Challenge: Traveling through Spain ☆"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the following problem:\n",
    "<p style=\"text-align: justify;\">\n",
    "After years dedicated to tending and protecting his precious plantations on the farm, a farmer finally decided to treat himself to well-deserved vacations and set off on a journey through the beautiful landscapes of Spain. He then decided to visit eight renowned cities during this unique adventure.\n",
    "</p>\n",
    "\n",
    "<p style=\"text-align: justify;\">\n",
    "Recognizing the value of time, the farmer understands the importance of finding the most efficient route to travel through all the cities, ensuring a seamless journey with the shortest travel time between each destination.\n",
    "</p>\n",
    "    \n",
    "<p style=\"text-align: justify;\">\n",
    "The map of Spain takes the form of a graph, where cities are represented as nodes and the roads connecting them as edges. Each edge is associated with a specific distance in miles between each pair of cities. Although the farmer is free to choose a starting city, he must visit exactly eight distinct cities, avoiding revisits during his expedition.\n",
    "</p>\n",
    "\n",
    "<p style=\"text-align: center;\">\n",
    " <img src=\"./images/figure08_cities.png\"  width=\"500\" height=\"500\">\n",
    "</p>\n",
    "\n",
    "`Your mission is to assist the farmer in creating the optimal order to visit all the cities, allowing him to explore their wonders while spending the least amount of time on the road`. To do that, answer the following items:\n",
    "\n",
    "a) Implement a bio-inspired algorithm using **GA**,\n",
    "\n",
    "b) Find the best route between the cities using **GA**.\n",
    "\n",
    "<p style=\"text-align: justify;\">\n",
    "As support, you will have at your disposal an adjacency matrix, where you will have access to all possible distances between each of the cities. This table will help you in solving the proposed problem.\n",
    "</p>\n",
    "\n",
    "<p style=\"text-align: center;\">\n",
    " <img src=\"./images/figure09_cities_distances_table.png\"  width=\"500\" height=\"500\">\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ☆ Solution ☆ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Valencia', 'Barcelona', 'Zaragoza', 'Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia']\n",
      "---------------------------------------\n"
     ]
    }
   ],
   "source": [
    "# Import the packages\n",
    "import random\n",
    "import time\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# City distance table (indexes are used as city representations)\n",
    "distance_table = [\n",
    "    [0, 620, 956, 621, 590, 349, 814, 296],\n",
    "    [620, 0, 730, 395, 796, 969, 280, 324],\n",
    "    [956, 730, 0, 335, 368, 609, 528, 660],\n",
    "    [621, 395, 335, 0, 401, 642, 193, 325],\n",
    "    [590, 796, 368, 401, 0, 241, 594, 726],\n",
    "    [349, 969, 609, 642, 241, 0, 835, 645],\n",
    "    [814, 280, 528, 193, 594, 835, 0, 518],\n",
    "    [296, 324, 660, 325, 726, 645, 518, 0]\n",
    "]\n",
    "\n",
    "# Mapping city indexes to their respective names\n",
    "city_names = {\n",
    "    0: \"Barcelona\",\n",
    "    1: \"Bilbao\",\n",
    "    2: \"Jaén\",\n",
    "    3: \"Madrid\",\n",
    "    4: \"Murcia\",\n",
    "    5: \"Valencia\",\n",
    "    6: \"Valladolid\",\n",
    "    7: \"Zaragoza\"\n",
    "}\n",
    "\n",
    "POPULATION_SIZE = 50\n",
    "MAX_GENERATIONS = 1000\n",
    "CROSSOVER_RATE = 0.8\n",
    "MUTATION_RATE = 0.2\n",
    "NUM_CITIES = len(distance_table)\n",
    "\n",
    "# Objective function (total path distance)\n",
    "def total_distance(path):\n",
    "    dist = 0\n",
    "    for i in range(len(path) - 1):\n",
    "        dist += distance_table[path[i]][path[i + 1]]\n",
    "    dist += distance_table[path[-1]][path[0]] \n",
    "    return dist\n",
    "\n",
    "# Step 1: Creating the population\n",
    "def create_population(population_size, num_cities):\n",
    "    population = []\n",
    "    for _ in range(population_size):\n",
    "        path = list(range(num_cities))\n",
    "        random.shuffle(path)\n",
    "        population.append(path)\n",
    "    return population\n",
    "\n",
    "# Step 2: Evaluation function (calculates fitness for each individual)\n",
    "def evaluate_population(population):\n",
    "    return [total_distance(path) for path in population]\n",
    "\n",
    "# Step 3: Selection of parents (roulette wheel method)\n",
    "def roulette_selection(population, fitness):\n",
    "    total_fitness = sum(fitness)\n",
    "    probabilities = [fit / total_fitness for fit in fitness]\n",
    "    selected_parents = random.choices(population, weights=probabilities, k=2)\n",
    "    return selected_parents\n",
    "\n",
    "# Step 4: Crossover (partial order)\n",
    "def crossover(parent1, parent2):\n",
    "    if random.random() < CROSSOVER_RATE:\n",
    "        start = random.randint(0, len(parent1) - 1)\n",
    "        end = random.randint(start + 1, len(parent1))\n",
    "        child = [-1] * len(parent1)\n",
    "\n",
    "        for i in range(start, end):\n",
    "            child[i] = parent1[i]\n",
    "\n",
    "        idx = 0\n",
    "        for city in parent2:\n",
    "            if city not in child:\n",
    "                while child[idx] != -1:\n",
    "                    idx += 1\n",
    "                child[idx] = city\n",
    "        return child\n",
    "    else:\n",
    "        return parent1\n",
    "\n",
    "# Step 5: Mutation (switching positions between two cities)\n",
    "def mutate(path):\n",
    "    if random.random() < MUTATION_RATE:\n",
    "        idx1, idx2 = random.sample(range(len(path)), 2)\n",
    "        path[idx1], path[idx2] = path[idx2], path[idx1]\n",
    "\n",
    "# Run the genetic algorithm\n",
    "def genetic_algorithm():\n",
    "    population = create_population(POPULATION_SIZE, NUM_CITIES)\n",
    "    best_distance = float('inf')\n",
    "    best_path = []\n",
    "\n",
    "    for generation in range(MAX_GENERATIONS):\n",
    "        fitness = evaluate_population(population)\n",
    "        best_idx = fitness.index(min(fitness))\n",
    "        current_best_path = population[best_idx]\n",
    "        current_best_distance = total_distance(current_best_path)\n",
    "\n",
    "        if current_best_distance < best_distance:\n",
    "            best_distance = current_best_distance\n",
    "            best_path = current_best_path[:]\n",
    "\n",
    "        if generation == MAX_GENERATIONS - 1:\n",
    "            print(f\"Generation {generation + 1}: Best Distance = {best_distance}\")\n",
    "            print(\"Best Path:\", [city_names[idx] for idx in best_path])\n",
    "            print(\"---------------------------------------\")\n",
    "            return best_path\n",
    "\n",
    "        new_population = []\n",
    "        for _ in range(POPULATION_SIZE // 2):\n",
    "            parent1, parent2 = roulette_selection(population, fitness)\n",
    "            child1 = crossover(parent1, parent2)\n",
    "            child2 = crossover(parent2, parent1)\n",
    "            mutate(child1)\n",
    "            mutate(child2)\n",
    "            new_population.extend([child1, child2])\n",
    "\n",
    "        population = new_population\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    genetic_algorithm()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### ⊗ Visualization the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running with population size: 50\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia', 'Valencia', 'Barcelona', 'Zaragoza']\n",
      "---------------------------------------\n",
      "Running with population size: 53\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Madrid', 'Jaén', 'Murcia', 'Valencia', 'Barcelona', 'Zaragoza', 'Bilbao', 'Valladolid']\n",
      "---------------------------------------\n",
      "Running with population size: 56\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Barcelona', 'Zaragoza', 'Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia', 'Valencia']\n",
      "---------------------------------------\n",
      "Running with population size: 59\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Zaragoza', 'Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia', 'Valencia', 'Barcelona']\n",
      "---------------------------------------\n",
      "Running with population size: 62\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Jaén', 'Murcia', 'Valencia', 'Barcelona', 'Zaragoza', 'Bilbao', 'Valladolid', 'Madrid']\n",
      "---------------------------------------\n",
      "Running with population size: 65\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Barcelona', 'Valencia', 'Murcia', 'Jaén', 'Madrid', 'Valladolid', 'Bilbao', 'Zaragoza']\n",
      "---------------------------------------\n",
      "Running with population size: 68\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Jaén', 'Madrid', 'Valladolid', 'Bilbao', 'Zaragoza', 'Barcelona', 'Valencia', 'Murcia']\n",
      "---------------------------------------\n",
      "Running with population size: 71\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia', 'Valencia', 'Barcelona', 'Zaragoza']\n",
      "---------------------------------------\n",
      "Running with population size: 74\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Barcelona', 'Zaragoza', 'Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia', 'Valencia']\n",
      "---------------------------------------\n",
      "Running with population size: 77\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Zaragoza', 'Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia', 'Valencia', 'Barcelona']\n",
      "---------------------------------------\n",
      "Running with population size: 80\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Valencia', 'Murcia', 'Jaén', 'Madrid', 'Valladolid', 'Bilbao', 'Zaragoza', 'Barcelona']\n",
      "---------------------------------------\n",
      "Running with population size: 83\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Jaén', 'Murcia', 'Valencia', 'Barcelona', 'Zaragoza', 'Bilbao', 'Valladolid', 'Madrid']\n",
      "---------------------------------------\n",
      "Running with population size: 86\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Valladolid', 'Madrid', 'Jaén', 'Murcia', 'Valencia', 'Barcelona', 'Zaragoza', 'Bilbao']\n",
      "---------------------------------------\n",
      "Running with population size: 89\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Valencia', 'Barcelona', 'Zaragoza', 'Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia']\n",
      "---------------------------------------\n",
      "Running with population size: 92\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Zaragoza', 'Barcelona', 'Valencia', 'Murcia', 'Jaén', 'Madrid', 'Valladolid', 'Bilbao']\n",
      "---------------------------------------\n",
      "Running with population size: 95\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Valencia', 'Barcelona', 'Zaragoza', 'Bilbao', 'Valladolid', 'Madrid', 'Jaén', 'Murcia']\n",
      "---------------------------------------\n",
      "Running with population size: 98\n",
      "Generation 1000: Best Distance = 2386\n",
      "Best Path: ['Murcia', 'Jaén', 'Madrid', 'Valladolid', 'Bilbao', 'Zaragoza', 'Barcelona', 'Valencia']\n",
      "---------------------------------------\n"
     ]
    }
   ],
   "source": [
    "# Function to plot the graph with selected cities in the last generation\n",
    "def plot_best_path(best_path):\n",
    "    x_coords = [city_names[idx] for idx in best_path]\n",
    "    y_coords = [idx for idx in range(len(best_path))]\n",
    "\n",
    "    plt.figure(figsize=(8, 6))\n",
    "    plt.plot(x_coords, y_coords, 'bo-')\n",
    "    plt.xticks(rotation=45)\n",
    "    plt.xlabel('Cities')\n",
    "    plt.ylabel('Index')\n",
    "    plt.title('Best Path in the Last Generation')\n",
    "    plt.grid()\n",
    "    plt.tight_layout()\n",
    "    plt.show()\n",
    "\n",
    "# Function to run the genetic algorithm and measure the running time\n",
    "def run_genetic_algorithm_with_population_sizes(min_pop_size, max_pop_size, step):\n",
    "    population_sizes = list(range(min_pop_size, max_pop_size + 1, step))\n",
    "    execution_times = []\n",
    "\n",
    "    for pop_size in population_sizes:\n",
    "        print(f\"Running with population size: {pop_size}\")\n",
    "        start_time = time.time()\n",
    "        POPULATION_SIZE = pop_size\n",
    "        genetic_algorithm()\n",
    "        end_time = time.time()\n",
    "        execution_times.append(end_time - start_time)\n",
    "\n",
    "# Execution of the genetic algorithm and plotting the graphs\n",
    "if __name__ == \"__main__\":\n",
    "    # Run the algorithm for different sizes of POPULATION_SIZE (from 50 to 100, increasing by 3 by 3)\n",
    "    run_genetic_algorithm_with_population_sizes(min_pop_size=50, max_pop_size=100, step=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we have shown: \n",
    "\n",
    "- Implement a bio-inspired algorithm using a **GA**,\n",
    "- Find the best route between the cities using a **GA**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Clear the memory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before moving on, please execute the following cell to clear up the CPU memory. This is required to move on to the next notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import IPython\n",
    "app = IPython.Application.instance()\n",
    "app.kernel.do_shutdown(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section, you learned how genetic algorithms can find an optimal solution to a problem. In the next section, you will learn about other bio-inspired algorithms such as the one based on a flock of ants using [_03-bio-inspired-ant-colony-algorithm.ipynb_](03-bio-inspired-ant-colony-algorithm.ipynb)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.8"
  },
  "toc-autonumbering": false,
  "toc-showtags": false
 },
 "nbformat": 4,
 "nbformat_minor": 4
}