AI - Lab 04 - Genetic Algorithm - 8 Queens.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Artificial Intelligence — Lab — Exercise 04 — Question 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 15 September 2020"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solve 8-queen’s problem. Place 8 queens in a chessboard so that no\n",
    "<br>queen is under attack from any other queen. One such “safe”\n",
    "<br>configuration of 8 queens is shown below.\n",
    "<br><br>State: Position of 8 queens\n",
    "<br>Population: K randomly generated states\n",
    "<br>Fitness function: Non- attacking pairs in 8-queens\n",
    "<br>Implement Genetic algorithm to find any one safe configuration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>[X, X, X, Q, X, X, X, X]\n",
    "<br>[X, X, X, X, X, Q, X, X]\n",
    "<br>[X, X, X, X, X, X, X, Q]\n",
    "<br>[X, Q, X, X, X, X, X, X]\n",
    "<br>[X, X, X, X, X, X, Q, X]\n",
    "<br>[Q, X, X, X, X, X, X, X]\n",
    "<br>[X, X, Q, X, X, X, X, X]\n",
    "<br>[X, X, X, X, Q, X, X, X]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Board:\n",
    "    \"\"\"Class to represent a state of the chessboard. \"\"\"\n",
    "    \n",
    "    def __init__(self, state):\n",
    "        self.state = state\n",
    "        self.size = len(state)\n",
    "        self.fitness = self.find_fitness()\n",
    "\n",
    "    def __str__(self):\n",
    "        \"\"\"To print the board in a formatted manner. \"\"\"\n",
    "        \n",
    "        ret_str = \"\\t\\t\"\n",
    "        for pos in self.state:\n",
    "            for i in range(0, self.size):\n",
    "                if i == pos:\n",
    "                    ret_str += \"👑 \"\n",
    "                else:\n",
    "                    ret_str += \"❌ \"\n",
    "            \n",
    "            ret_str += \"\\n\\t\\t\"\n",
    "        \n",
    "        return ret_str\n",
    "\n",
    "    \n",
    "    def find_fitness(self):\n",
    "        \"\"\"Finds the fitness value of a given board configuration. \"\"\"\n",
    "\n",
    "        attacks = 28\n",
    "\n",
    "        for i in range(self.size):\n",
    "            for j in range(i+1, self.size):\n",
    "                \n",
    "                #Same row\n",
    "                if self.state[i] == self.state[j]:\n",
    "                    attacks -= 1\n",
    "                \n",
    "                #Diagonal\n",
    "                elif self.state[i] + i == self.state[j] + j:\n",
    "                    attacks -= 1\n",
    "\n",
    "                #Anti-Diagonal\n",
    "                elif self.state[i] - i == self.state[j] - j:\n",
    "                    attacks -= 1\n",
    "                \n",
    "        return attacks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Board_Solver:\n",
    "    \"\"\"Class to encapsulate the solver functions and members of the 8 Queens problem using Genetic Algorithm. \"\"\"\n",
    "\n",
    "    def __init__(self, mutation_probability, generations, pop_size, no_queens):\n",
    "         self.iterations = 0\n",
    "         self.final_board = None\n",
    "         self.MUTATION_PROBABILITY = mutation_probability\n",
    "         self.GENERATIONS = generations\n",
    "         self.POPULATION_SIZE = pop_size\n",
    "         self.NO_QUEENS = no_queens\n",
    "\n",
    "    def reproduce(self, mother, father):\n",
    "        \"\"\"Reproduce a set of parent states (mother, father) to produce a child state(child) \"\"\"\n",
    "\n",
    "        crossover = random.randint(0, mother.size - 1)\n",
    "        child = mother.state[:crossover] + father.state[crossover:]\n",
    "\n",
    "        return Board(child)\n",
    "\n",
    "    def random_selection(self, population):\n",
    "        \"\"\"Randomly select an individual from the given population, based on its survival probability. \"\"\"\n",
    "\n",
    "        population_fitness = [each.fitness for each in population]\n",
    "        total_fitness = sum(population_fitness)\n",
    "        normalized_probabilities = [fitness/total_fitness for fitness in population_fitness]\n",
    "\n",
    "        random_choice = random.choices(population = population, weights = normalized_probabilities)\n",
    "        #randomly selects an individual\n",
    "\n",
    "        return random_choice[0]\n",
    "\n",
    "    def mutation_chance(self):\n",
    "        \"\"\"Calculate the chance for a child to be mutated, based on the mutation probability. \"\"\"\n",
    "\n",
    "        x = random.randint(1, self.MUTATION_PROBABILITY)\n",
    "        if x == 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def mutate(self, child):\n",
    "        \"\"\"Mutate a given child to form a mutated child. \"\"\"\n",
    "\n",
    "        mutated_child = Board(list(child.state))\n",
    "        random_move = random.randint(0, child.size - 1)\n",
    "        mutated_child.state[random_move] = random.randint(0, child.size - 1)\n",
    "        #random position change in a randomly-chosen column\n",
    "\n",
    "        return mutated_child\n",
    "\n",
    "    def grow_population(self, size, no_queens):\n",
    "        \"\"\"Grow a population based upon the given population size to serve as the initial world's population. \"\"\"\n",
    "\n",
    "        population = []\n",
    "\n",
    "        for each in range(size):\n",
    "            #randomly generate individuals as part of the population\n",
    "            random_state = [random.randint(0, no_queens-1) for i in range(no_queens)]\n",
    "            population.append(Board(random_state))\n",
    "    \n",
    "        return population\n",
    "\n",
    "    def genetic_algorithm(self):\n",
    "        \"\"\"Performs the Genetic Algorithm on a given population, and returns the fittest individual. \"\"\"\n",
    "\n",
    "        max_iterations = self.GENERATIONS\n",
    "        iteration = 0\n",
    "\n",
    "        population = self.grow_population(self.POPULATION_SIZE, self.NO_QUEENS)\n",
    "        fittest = max(population, key = lambda x: x.fitness) #finds the fittest individual based on fitness value\n",
    "        print(\"\\n\\tInitial Board:\\n{0}\".format(fittest))\n",
    "\n",
    "        print(\"\\tStarting with fitness\\t:\\t{0}\".format(fittest.fitness))\n",
    "\n",
    "        while iteration < max_iterations:\n",
    "            new_population = []\n",
    "\n",
    "            for i in range(len(population)):\n",
    "                mother = self.random_selection(population)\n",
    "                father = self.random_selection(population)\n",
    "\n",
    "                while mother == father: #Do not select same parents\n",
    "                    father = self.random_selection(population)\n",
    "\n",
    "                child = self.reproduce(mother, father)\n",
    "                \n",
    "                if self.mutation_chance():  #Chance to allow mutation to occur\n",
    "                    child = self.mutate(child)\n",
    "                    \n",
    "                new_population.append(child)\n",
    "\n",
    "                if child.fitness > fittest.fitness: #If a fitter child is found\n",
    "                    print(\"\\tFitness improved to\\t:\\t{0} at iteration {1}\".format(child.fitness, iteration))\n",
    "                    fittest = child\n",
    "\n",
    "            if fittest.fitness == 28:   #If the maximum fitness level is reached\n",
    "                break\n",
    "\n",
    "            population = new_population     #Use the new population as the next world's population\n",
    "            iteration += 1\n",
    "            \n",
    "        self.final_board = fittest\n",
    "        self.iterations = iteration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\t\t\tN - Queens Problem : Genetic Algorithm\n",
      "\n",
      "\n",
      "\tInitial Board:\n",
      "\t\t❌ ❌ ❌ 👑 ❌ ❌ ❌ ❌ \n",
      "\t\t❌ ❌ ❌ ❌ ❌ ❌ ❌ 👑 \n",
      "\t\t❌ ❌ ❌ ❌ ❌ 👑 ❌ ❌ \n",
      "\t\t❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "\t\t👑 ❌ ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "\t\t❌ ❌ ❌ ❌ ❌ 👑 ❌ ❌ \n",
      "\t\t❌ ❌ ❌ ❌ ❌ ❌ ❌ 👑 \n",
      "\t\t❌ ❌ ❌ ❌ 👑 ❌ ❌ ❌ \n",
      "\t\t\n",
      "\tStarting with fitness\t:\t25\n",
      "\tFitness improved to\t:\t26 at iteration 0\n",
      "\tFitness improved to\t:\t27 at iteration 6\n",
      "\tFitness improved to\t:\t28 at iteration 82\n",
      "\n",
      "\n",
      "\tIterations taken\t:\t 82\n",
      "\n",
      "\tFinal Board:\n",
      "\t\t👑 ❌ ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "\t\t❌ ❌ ❌ ❌ ❌ ❌ 👑 ❌ \n",
      "\t\t❌ ❌ ❌ ❌ 👑 ❌ ❌ ❌ \n",
      "\t\t❌ ❌ ❌ ❌ ❌ ❌ ❌ 👑 \n",
      "\t\t❌ 👑 ❌ ❌ ❌ ❌ ❌ ❌ \n",
      "\t\t❌ ❌ ❌ 👑 ❌ ❌ ❌ ❌ \n",
      "\t\t❌ ❌ ❌ ❌ ❌ 👑 ❌ ❌ \n",
      "\t\t❌ ❌ 👑 ❌ ❌ ❌ ❌ ❌ \n",
      "\t\t\n",
      "\n",
      "\tFitness Value: 28\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "    \"\"\"Driver code to execute the Genetic Algorithm to solve the 8 - Queens problem. \"\"\"\n",
    "\n",
    "    print(\"\\n\\t\\t\\tN - Queens Problem : Genetic Algorithm\\n\")\n",
    "\n",
    "    #Arbitrarily chosen hyperparameters, can be changed to see different results.\n",
    "    mutation_probability = 1000\n",
    "    generations = 100\n",
    "    pop_size = 500\n",
    "    no_queens = 8\n",
    "    \n",
    "    solution = Board_Solver(mutation_probability, generations, pop_size, no_queens)\n",
    "    solution.genetic_algorithm()\n",
    "\n",
    "    print(\"\\n\\n\\tIterations taken\\t:\\t\", solution.iterations)\n",
    "    print(\"\\n\\tFinal Board:\\n{0}\".format(solution.final_board))\n",
    "    print(\"\\n\\tFitness Value:\", solution.final_board.fitness)"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}