Assignment-5.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "items = {'A': {'weight': 45, 'value': 3},\n",
    "         'B': {'weight': 40, 'value': 5},\n",
    "         'C': {'weight': 50, 'value': 8},\n",
    "         'D': {'weight': 90, 'value': 10}}\n",
    "chromosome_size = 4\n",
    "population_size = 4\n",
    "max_capacity = 100\n",
    "mutation_order = ['D', 'C', 'B', 'A']\n",
    "\n",
    "def fitness(chromosome):\n",
    "    weight = sum(items[key]['weight'] * chromosome[i] for i, key in enumerate(items))\n",
    "    if weight > max_capacity:\n",
    "        return 0\n",
    "    value = sum(items[key]['value'] * chromosome[i] for i, key in enumerate(items))\n",
    "    return value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 0, 1, 0], [1, 0, 1, 0]]\n"
     ]
    }
   ],
   "source": [
    "population = [[random.randint(0, 1) for _ in range(chromosome_size)] for _ in range(population_size)]\n",
    "fitness_scores = [fitness(chromosome) for chromosome in population]\n",
    "fittest_indices = sorted(range(len(fitness_scores)), key=lambda i: fitness_scores[i], reverse=True)[:2]\n",
    "fittest_chromosomes = [population[i] for i in fittest_indices]\n",
    "\n",
    "crossover_index = chromosome_size // 2\n",
    "offspring1 = population[2][:crossover_index] + population[3][crossover_index:]\n",
    "offspring2 = population[3][:crossover_index] + population[2][crossover_index:]\n",
    "mutation_index = mutation_order.index('D')\n",
    "offspring1[mutation_index] = 1 - offspring1[mutation_index]\n",
    "\n",
    "offspring_fitness_scores = [fitness(offspring) for offspring in [offspring1, offspring2]]\n",
    "\n",
    "least_fit_indices = sorted(range(len(fitness_scores)), key=lambda i: fitness_scores[i])[:2]\n",
    "population[least_fit_indices[0]] = offspring1\n",
    "population[least_fit_indices[1]] = offspring2\n",
    "\n",
    "for i in range(9):\n",
    "    fitness_scores = [fitness(chromosome) for chromosome in population]\n",
    "\n",
    "    fittest_indices = sorted(range(len(fitness_scores)), key=lambda i: fitness_scores[i], reverse=True)[:2]\n",
    "    fittest_chromosomes = [population[i] for i in fittest_indices]\n",
    "\n",
    "    crossover_index = chromosome_size // 2\n",
    "    offspring1 = population[2][:crossover_index] + population[3][crossover_index:]\n",
    "    offspring2 = population[3][:crossover_index] + population[2][crossover_index:]\n",
    "    mutation_index = mutation_order[i % len(mutation_order)]\n",
    "    mutation_index = [key for key in items.keys()].index(mutation_index)\n",
    "    offspring1[mutation_index] = 1 - offspring1[mutation_index]\n",
    "\n",
    "    offspring_fitness_scores = [fitness(offspring) for offspring in [offspring1, offspring2]]\n",
    "\n",
    "    least_fit_indices = sorted(range(len(fitness_scores)), key=lambda i: fitness_scores[i])[:2]\n",
    "    population[least_fit_indices[0]] = offspring1\n",
    "    population[least_fit_indices[1]] = offspring2\n",
    "\n",
    "print(fittest_chromosomes)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Q.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "items = {'A': {'weight': 2, 'value': 3},\n",
    "         'B': {'weight': 3, 'value': 5},\n",
    "         'C': {'weight': 4, 'value': 7},\n",
    "         'D': {'weight': 5, 'value': 9}}\n",
    "\n",
    "chromosome_size = 4\n",
    "population_size = 4\n",
    "max_weight = 9\n",
    "mutation_order = ['C', 'A', 'D', 'B']\n",
    "\n",
    "def fitness(chromosome):\n",
    "    weight = sum(items[key]['weight'] * chromosome[i] for i, key in enumerate(items))\n",
    "    if weight > max_weight:\n",
    "        return 0\n",
    "    value = sum(items[key]['value'] * chromosome[i] for i, key in enumerate(items))\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0, 0, 1]\n"
     ]
    }
   ],
   "source": [
    "\n",
    "population = [[1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1]]\n",
    "\n",
    "for i in range(4):\n",
    "    fitness_scores = [fitness(chromosome) for chromosome in population]\n",
    "\n",
    "    fittest_indices = sorted(range(len(fitness_scores)), key=lambda i: fitness_scores[i], reverse=True)[:2]\n",
    "    fittest_chromosomes = [population[i] for i in fittest_indices]\n",
    "\n",
    "    offspring1 = population[2][:chromosome_size//2] + population[3][chromosome_size//2:]\n",
    "    offspring2 = population[3][:chromosome_size//2] + population[2][chromosome_size//2:]\n",
    "    mutation_index = mutation_order[i % len(mutation_order)]\n",
    "    mutation_index = [key for key in items.keys()].index(mutation_index)\n",
    "    offspring1[mutation_index] = 1 - offspring1[mutation_index]\n",
    "\n",
    "    offspring_fitness_scores = [fitness(offspring) for offspring in [offspring1, offspring2]]\n",
    "\n",
    "    least_fit_indices = sorted(range(len(fitness_scores)), key=lambda i: fitness_scores[i])[:2]\n",
    "    population[least_fit_indices[0]] = fittest_chromosomes[0]\n",
    "    population[least_fit_indices[1]] = offspring1\n",
    "\n",
    "print(fittest_chromosomes[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "\n",
    "# Define the 2-SAT problem\n",
    "def formula(a, b, c, d):\n",
    "    return (not a or d) and (c or b) and (not c or not d) and (not d or not b) and (not a or not d)\n",
    "\n",
    "# Define the MOVEGEN function\n",
    "def movegen(candidate):\n",
    "    index = random.randint(0, 3)\n",
    "    new_candidate = list(candidate)\n",
    "    new_candidate[index] = int(not new_candidate[index])\n",
    "    return tuple(new_candidate)\n",
    "\n",
    "# Define the heuristic to evaluate each solution\n",
    "def evaluate(candidate):\n",
    "    a, b, c, d = candidate\n",
    "    score = 0\n",
    "    if formula(a, b, c, d): score += 1\n",
    "    if formula(a, b, not c, d): score += 1\n",
    "    if formula(not a, b, c, d): score += 1\n",
    "    if formula(not a, b, not c, d): score += 1\n",
    "    return score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration 1:\n",
      "Random number: 0.655\n",
      "Best candidate: (1, 1, 0, 0)\n",
      "Best score: 2\n",
      "\n",
      "Iteration 2:\n",
      "Random number: 0.254\n",
      "Best candidate: (0, 1, 1, 0)\n",
      "Best score: 2\n",
      "\n",
      "Iteration 3:\n",
      "Random number: 0.432\n",
      "Best candidate: (1, 1, 1, 0)\n",
      "Best score: 2\n",
      "\n"
     ]
    }
   ],
   "source": [
    "\n",
    "# Define the simulated annealing algorithm\n",
    "def simulated_annealing(initial_candidate, T, cooling_function):\n",
    "    current_candidate = initial_candidate\n",
    "    current_score = evaluate(current_candidate)\n",
    "    best_candidate = current_candidate\n",
    "    best_score = current_score\n",
    "    while T > 0:\n",
    "        new_candidate = movegen(current_candidate)\n",
    "        new_score = evaluate(new_candidate)\n",
    "        delta = new_score - current_score\n",
    "        if delta > 0 or math.exp(delta / T) > random.random():\n",
    "            current_candidate = new_candidate\n",
    "            current_score = new_score\n",
    "        if current_score > best_score:\n",
    "            best_candidate = current_candidate\n",
    "            best_score = current_score\n",
    "        T = cooling_function(T)\n",
    "    return best_candidate\n",
    "\n",
    "# Solve the problem with simulated annealing\n",
    "initial_candidate = (1, 1, 1, 1)\n",
    "T = 500\n",
    "cooling_function = lambda x: x - 50\n",
    "random_numbers = [0.655, 0.254, 0.432]\n",
    "\n",
    "random.seed(42) # Ensure reproducibility\n",
    "for i, rand in enumerate(random_numbers):\n",
    "    print(f\"Iteration {i+1}:\")\n",
    "    candidate = simulated_annealing(initial_candidate, T, cooling_function)\n",
    "    print(f\"Random number: {rand}\")\n",
    "    print(f\"Best candidate: {candidate}\")\n",
    "    print(f\"Best score: {evaluate(candidate)}\")\n",
    "    print()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.9.13"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}