Genetic Algorithm implementation on N-Queen.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "874c1cd9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution found in generation 3!\n",
      "Solution:\n",
      "[5, 3, 8, 4, 2, 4, 6, 1]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "class GeneticAlgorithm:\n",
    "    def __init__(self, population_size, mutation_rate, max_generations):\n",
    "        self.population_size = population_size\n",
    "        self.mutation_rate = mutation_rate\n",
    "        self.max_generations = max_generations\n",
    "\n",
    "    def solve_n_queens(self, n):\n",
    "        population = self._initialize_population(n)\n",
    "        generation = 1\n",
    "\n",
    "        while generation <= self.max_generations:\n",
    "            fitness_scores = self._calculate_fitness(population, n)\n",
    "            if max(fitness_scores) == n:\n",
    "                print(f\"Solution found in generation {generation}!\")\n",
    "                return population[fitness_scores.index(max(fitness_scores))]\n",
    "\n",
    "            population = self._reproduce(population, fitness_scores)\n",
    "            generation += 1\n",
    "\n",
    "        print(\"Solution not found!\")\n",
    "        return None\n",
    "\n",
    "    def _initialize_population(self, n):\n",
    "        population = []\n",
    "        for _ in range(self.population_size):\n",
    "            chromosome = [i+1 for i in range(n)]\n",
    "            random.shuffle(chromosome)\n",
    "            population.append(chromosome)\n",
    "        return population\n",
    "\n",
    "    def _calculate_fitness(self, population, n):\n",
    "        fitness_scores = []\n",
    "        for chromosome in population:\n",
    "            clashes = 0\n",
    "            for i in range(n):\n",
    "                for j in range(i+1, n):\n",
    "                    if abs(chromosome[i] - chromosome[j]) == abs(i - j):\n",
    "                        clashes += 1\n",
    "            fitness_scores.append(n - clashes)\n",
    "        return fitness_scores\n",
    "\n",
    "    def _reproduce(self, population, fitness_scores):\n",
    "        new_population = []\n",
    "\n",
    "        for _ in range(self.population_size):\n",
    "            parent1 = self._select_parent(population, fitness_scores)\n",
    "            parent2 = self._select_parent(population, fitness_scores)\n",
    "\n",
    "            child = self._crossover(parent1, parent2)\n",
    "            child = self._mutate(child)\n",
    "\n",
    "            new_population.append(child)\n",
    "\n",
    "        return new_population\n",
    "\n",
    "    def _select_parent(self, population, fitness_scores):\n",
    "        # Roulette wheel selection\n",
    "        total_fitness = sum(fitness_scores)\n",
    "        selection_probabilities = [score / total_fitness for score in fitness_scores]\n",
    "\n",
    "        while True:\n",
    "            random_index = random.choices(range(self.population_size), selection_probabilities)[0]\n",
    "            if random.random() < selection_probabilities[random_index]:\n",
    "                return population[random_index]\n",
    "\n",
    "    def _crossover(self, parent1, parent2):\n",
    "        n = len(parent1)\n",
    "        crossover_point = random.randint(0, n-1)\n",
    "        child = parent1[:crossover_point] + parent2[crossover_point:]\n",
    "        return child\n",
    "\n",
    "    def _mutate(self, chromosome):\n",
    "        n = len(chromosome)\n",
    "        if random.random() < self.mutation_rate:\n",
    "            mutation_point1 = random.randint(0, n-1)\n",
    "            mutation_point2 = random.randint(0, n-1)\n",
    "            chromosome[mutation_point1], chromosome[mutation_point2] = chromosome[mutation_point2], chromosome[mutation_point1]\n",
    "        return chromosome\n",
    "\n",
    "# Usage example:\n",
    "population_size = 100\n",
    "mutation_rate = 0.1\n",
    "max_generations = 1000\n",
    "\n",
    "ga = GeneticAlgorithm(population_size, mutation_rate, max_generations)\n",
    "solution = ga.solve_n_queens(8)  # Solve 8-queens problem\n",
    "\n",
    "if solution:\n",
    "    print(\"Solution:\")\n",
    "    print(solution)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55b17849",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}