Genetic_Algorithm.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of Genetic_Algorithm.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyPBDL1cxgGE0fYu2xR6R6Pn"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yFRQXoV2Pkua"
      },
      "source": [
        "# **Genetic Algorithm :**\r\n",
        "Evolutionary algorithms are a family of optimization algorithms based on the principle of Darwinian natural selection. As part of natural selection, a given environment has a population of individuals that compete for survival and reproduction. The ability of each individual to achieve these goals determines their chance to have children, in other words to pass on their genes to the next generation of individuals, who for genetic reasons will have an increased chance of doing well, even better, in realizing these two objectives.\r\n",
        "\r\n",
        "Genetic algorithms are optimization methods based on population genetics, where individual solutions are represented, evaluated, and combined together at each step. They are able to escape local optima better than other algorithms because of the mutation/recombination steps.\r\n",
        "\r\n",
        "It is a programming language that mimics the evolution of biology. It was inspired by Darwins theory that is “*survival of the fittest*”.\r\n",
        "\r\n",
        "It has following are the basic operators -\r\n",
        "\r\n",
        "1.**Selection** : The selection process determines which chromosomes participate in reproduction to generate the next population (in the next generation) according to their fitness values in the current population.\r\n",
        "\r\n",
        "2.**Crossover** : The crossover operator is used to create new chromosomes for the next generation by randomly combining two selected chromosomes from the current generation through the selection process\r\n",
        "\r\n",
        "3.**Mutation** : Mutation introduces innovation into the population by randomly modifying the chromosomes. It prevents the population from becoming saturated with chromosomes that are all similar and reduces the chance of premature convergence\r\n",
        "\r\n",
        "4.**Population size** : Population size is the number of chromosomes present in a population. Larger population sizes increase the amount of variation present in the population (or population diversity), but at the expense of requiring more fitness evaluations. Furthermore, when the population size is too large, there is a tendency by the user to reduce the number of generations in order to reduce the computing effort, since the computing effort depends on both population size and the number of generations. Reduction in the number of generations reduces the overall solution quality. \r\n",
        "\r\n",
        "5.**Fitness score **:- Fitness score is the number of characters which differ from characters in target string at a particular index. So individual having lower fitness value is given more preference\r\n",
        "\r\n",
        "\r\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "iWa0Cw1GUaOL"
      },
      "source": [
        "# **Implementation : -**"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "IwqZXeB4KsTy",
        "outputId": "b51d70b4-c7ed-4e15-9331-8067365deab9"
      },
      "source": [
        "from random import randint\r\n",
        "import random as rn\r\n",
        "\r\n",
        "\r\n",
        "\r\n",
        "\r\n",
        "class Sample:\r\n",
        "    def __init__(self,s,score):\r\n",
        "        self.s = s\r\n",
        "        self.score = score\r\n",
        "\r\n",
        "class GeneticEvolution:\r\n",
        "    def __init__(self,s):\r\n",
        "        self.s = s\r\n",
        "        #97 122\r\n",
        "        self.population = []\r\n",
        "        self.mutation_rate = 0.1\r\n",
        "        for i in range(100):\r\n",
        "            sample = ''\r\n",
        "            for i in range(len(s)):\r\n",
        "                sample+= chr(int(randint(97,122)))\r\n",
        "            self.population.append(Sample(sample,self.fitness(sample)))\r\n",
        "    def fitness(self,sample):\r\n",
        "        score=0\r\n",
        "        for i,j in zip(list(sample),list(self.s)):\r\n",
        "            if i==j:\r\n",
        "                score+=1\r\n",
        "        return score\r\n",
        "    def selection(self):\r\n",
        "        new_population = []\r\n",
        "       \r\n",
        "        self.population.sort(key = lambda x: x.score,reverse=True)\r\n",
        "        new_population = self.population[:40]\r\n",
        "       \r\n",
        "        r_sample = rn.sample(self.population[40:],10)\r\n",
        "        for i in r_sample:\r\n",
        "            new_population.append(i)\r\n",
        "        self.population = new_population\r\n",
        "    def crossover(self):\r\n",
        "        for i in range(100-len(self.population)):\r\n",
        "            parents = rn.sample(self.population,2)\r\n",
        "            child = ''\r\n",
        "            for i,j in zip(list(parents[0].s),list(parents[1].s)):\r\n",
        "                if rn.random()<0.5:\r\n",
        "                    child+=i\r\n",
        "                else:\r\n",
        "                    child+=j\r\n",
        "            self.population.append(Sample(child,self.fitness(child)))\r\n",
        "           \r\n",
        "    def mutation(self):\r\n",
        "        new_population = []\r\n",
        "       \r\n",
        "        for sample in self.population:\r\n",
        "            mutated = ''\r\n",
        "            for i in sample.s:\r\n",
        "                if rn.random()<self.mutation_rate:\r\n",
        "                    mutated += chr(int(randint(97,122)))\r\n",
        "                else:\r\n",
        "                    mutated += i\r\n",
        "       \r\n",
        "            new_population.append(Sample(mutated,self.fitness(mutated)))\r\n",
        "        self.population = new_population\r\n",
        "   \r\n",
        "    def evolution(self):\r\n",
        "        generation = 0\r\n",
        "        while True:\r\n",
        "            generation+=1\r\n",
        "            print(generation)\r\n",
        "            self.selection()\r\n",
        "            #condition\r\n",
        "            if self.population[0].score==self.fitness(self.s):\r\n",
        "                print(self.population[0].s,self.population[0].score)\r\n",
        "                return self.population[0]\r\n",
        "            self.crossover()\r\n",
        "            self.mutation()\r\n",
        "            if generation>1000:\r\n",
        "                return None\r\n",
        "           \r\n",
        "           \r\n",
        "   \r\n",
        "     \r\n",
        "     \r\n",
        "       \r\n",
        "g = GeneticEvolution('geneticalgorithm')\r\n",
        "g.evolution()\r\n",
        "def brute_force(s):\r\n",
        "    count = 0\r\n",
        "    while True:\r\n",
        "        e = ''\r\n",
        "        for i in range(len(s)):\r\n",
        "            e+=chr(int(randint(97,122)))\r\n",
        "        if e==s:\r\n",
        "            return count\r\n",
        "        print(e)\r\n",
        "        if count>10000:\r\n",
        "            return -1\r\n",
        "        count+=1"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "5\n",
            "6\n",
            "7\n",
            "8\n",
            "9\n",
            "10\n",
            "11\n",
            "12\n",
            "13\n",
            "14\n",
            "15\n",
            "16\n",
            "17\n",
            "18\n",
            "19\n",
            "20\n",
            "21\n",
            "22\n",
            "23\n",
            "24\n",
            "25\n",
            "26\n",
            "27\n",
            "28\n",
            "29\n",
            "30\n",
            "31\n",
            "32\n",
            "33\n",
            "34\n",
            "35\n",
            "36\n",
            "37\n",
            "38\n",
            "39\n",
            "40\n",
            "41\n",
            "42\n",
            "43\n",
            "44\n",
            "45\n",
            "46\n",
            "47\n",
            "48\n",
            "49\n",
            "50\n",
            "51\n",
            "52\n",
            "53\n",
            "54\n",
            "55\n",
            "56\n",
            "57\n",
            "58\n",
            "59\n",
            "60\n",
            "61\n",
            "62\n",
            "63\n",
            "64\n",
            "65\n",
            "66\n",
            "67\n",
            "68\n",
            "69\n",
            "70\n",
            "71\n",
            "72\n",
            "73\n",
            "74\n",
            "75\n",
            "76\n",
            "77\n",
            "78\n",
            "79\n",
            "80\n",
            "81\n",
            "82\n",
            "83\n",
            "84\n",
            "85\n",
            "86\n",
            "87\n",
            "88\n",
            "89\n",
            "90\n",
            "91\n",
            "92\n",
            "93\n",
            "94\n",
            "95\n",
            "96\n",
            "97\n",
            "98\n",
            "99\n",
            "100\n",
            "101\n",
            "102\n",
            "103\n",
            "104\n",
            "105\n",
            "106\n",
            "107\n",
            "108\n",
            "109\n",
            "110\n",
            "111\n",
            "112\n",
            "113\n",
            "114\n",
            "115\n",
            "116\n",
            "117\n",
            "118\n",
            "119\n",
            "120\n",
            "121\n",
            "122\n",
            "123\n",
            "124\n",
            "125\n",
            "126\n",
            "127\n",
            "128\n",
            "129\n",
            "130\n",
            "131\n",
            "132\n",
            "133\n",
            "134\n",
            "135\n",
            "136\n",
            "137\n",
            "138\n",
            "139\n",
            "140\n",
            "141\n",
            "142\n",
            "143\n",
            "144\n",
            "145\n",
            "146\n",
            "geneticalgorithm 16\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}