Genetic Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a035cd2a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "String: ['v', 't', 'y', 'a', 'a', 'o', 'a', 'y', 'a'] Generation: 1 Fitness: 6\n",
      "String: ['r', 't', 'y', 'h', 'n', 's', 'w', 'y', 'i'] Generation: 2 Fitness: 5\n",
      "String: ['r', 't', 'y', 'h', 'n', 's', 'w', 'y', 'i'] Generation: 3 Fitness: 5\n",
      "String: ['r', 'j', 'y', 'a', 'n', 'x', 'r', 'l', 'f'] Generation: 4 Fitness: 4\n",
      "String: ['r', 'j', 'y', 'a', 'n', 'x', 'r', 'l', 'f'] Generation: 5 Fitness: 4\n",
      "String: ['r', 'j', 'y', 'a', 'n', 'x', 'r', 'l', 'f'] Generation: 6 Fitness: 4\n",
      "String: ['r', 'c', 'y', 'a', 'n', ' ', 'o', 'l', 'c'] Generation: 7 Fitness: 3\n",
      "String: ['r', 'c', 'y', 'a', 'n', ' ', 'o', 'l', 'c'] Generation: 8 Fitness: 3\n",
      "String: ['v', 'a', 'y', 'a', 'n', ' ', 'a', 'w', 'i'] Generation: 9 Fitness: 2\n",
      "String: ['v', 'a', 'y', 'a', 'n', ' ', 'a', 'w', 'i'] Generation: 10 Fitness: 2\n",
      "String: ['r', 't', 'y', 'a', 'n', ' ', 'a', 'l', 'i'] Generation: 11 Fitness: 1\n",
      "String: ['r', 't', 'y', 'a', 'n', ' ', 'a', 'l', 'i'] Generation: 12 Fitness: 1\n",
      "Target found\n",
      "String: ['r', 'a', 'y', 'a', 'n', ' ', 'a', 'l', 'i'] Generation: 13 Fitness: 0\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "POP_SIZE = 500\n",
    "MUT_RATE = 0.1\n",
    "TARGET = 'rayan ali'\n",
    "GENES = ' abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "def initialize_pop(TARGET):\n",
    "    population = list()\n",
    "    tar_len = len(TARGET)\n",
    "\n",
    "    for i in range(POP_SIZE):\n",
    "        temp = list()\n",
    "        for j in range(tar_len):\n",
    "            temp.append(random.choice(GENES))\n",
    "        population.append(temp)\n",
    "\n",
    "    return population\n",
    "\n",
    "def crossover(selected_chromo, CHROMO_LEN, population):\n",
    "    offspring_cross = []\n",
    "    for i in range(int(POP_SIZE)):\n",
    "        parent1 = random.choice(selected_chromo)\n",
    "        parent2 = random.choice(population[:int(POP_SIZE*50)])\n",
    "\n",
    "        p1 = parent1[0]\n",
    "        p2 = parent2[0]\n",
    "\n",
    "        crossover_point = random.randint(1, CHROMO_LEN-1)\n",
    "        child =  p1[:crossover_point] + p2[crossover_point:]\n",
    "        offspring_cross.extend([child])\n",
    "    return offspring_cross\n",
    "\n",
    "def mutate(offspring, MUT_RATE):\n",
    "    mutated_offspring = []\n",
    "\n",
    "    for arr in offspring:\n",
    "        for i in range(len(arr)):\n",
    "            if random.random() < MUT_RATE:\n",
    "                arr[i] = random.choice(GENES)\n",
    "        mutated_offspring.append(arr)\n",
    "    return mutated_offspring\n",
    "\n",
    "def selection(population, TARGET):\n",
    "    sorted_chromo_pop = sorted(population, key= lambda x: x[1])\n",
    "    return sorted_chromo_pop[:int(0.5*POP_SIZE)]\n",
    "\n",
    "def fitness_cal(TARGET, chromo_from_pop):\n",
    "    difference = 0\n",
    "    for tar_char, chromo_char in zip(TARGET, chromo_from_pop):\n",
    "        if tar_char != chromo_char:\n",
    "            difference+=1\n",
    "    \n",
    "    return [chromo_from_pop, difference]\n",
    "\n",
    "def replace(new_gen, population):\n",
    "    for _ in range(len(population)):\n",
    "        if population[_][1] > new_gen[_][1]:\n",
    "            population[_][0] = new_gen[_][0]\n",
    "            population[_][1] = new_gen[_][1]\n",
    "    return population\n",
    "\n",
    "def main(POP_SIZE, MUT_RATE, TARGET, GENES):\n",
    "    initial_population = initialize_pop(TARGET)\n",
    "    found = False\n",
    "    population = []\n",
    "    generation = 1\n",
    "\n",
    "    for _ in range(len(initial_population)):\n",
    "        population.append(fitness_cal(TARGET, initial_population[_]))\n",
    "\n",
    "    while not found:\n",
    "        selected = selection(population, TARGET)\n",
    "        population = sorted(population, key= lambda x:x[1])\n",
    "        crossovered = crossover(selected, len(TARGET), population)\n",
    "        mutated = mutate(crossovered, MUT_RATE)\n",
    "        new_gen = []\n",
    "        for _ in mutated:\n",
    "            new_gen.append(fitness_cal(TARGET, _))\n",
    "        population = replace(new_gen, population)\n",
    "        if (population[0][1] == 0):\n",
    "            print('Target found')\n",
    "            print('String: ' + str(population[0][0]) + ' Generation: ' + str(generation) + ' Fitness: ' + str(population[0][1]))\n",
    "            break\n",
    "        print('String: ' + str(population[0][0]) + ' Generation: ' + str(generation) + ' Fitness: ' + str(population[0][1])) \n",
    "        generation += 1\n",
    "\n",
    "main(POP_SIZE, MUT_RATE, TARGET, GENES)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6504d411",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}