AI_CA2_810896059.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 style = \"font-size: 30px; text-align: center;\">AI Genetic Hands On</h1>\n",
    "<h2 style = \"font-size: 25px; text-align: center;\">Hospital Job Scheduling</h2>\n",
    "<h2 style = \"font-size: 25px; text-align: center; color: #666\">Name: Sepideh Fatemi</h2>\n",
    "<h2 style = \"font-size: 25px; text-align: center; color: #666\">Student Id: 810896059</h2>\n",
    "<h4 style=\"text-align: center\">Spring 1400</h4>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2 style = \"font-size: 25px;\">Notes</h2>\n",
    "\n",
    "<h3>Tests: </h3>\n",
    "\n",
    "<p style=\"text-indent :2em;\"><b>Test1: </b><mark>Average time < 15s</mark></p>\n",
    "<p style=\"text-indent :2em;\"><b>Test2: </b><mark>Average time < 60s</mark></p>\n",
    "    \n",
    "\n",
    "<h3>Outputs: </h3>\n",
    "<p style=\"text-indent :2em;\">Respectively <mark>output1.txt</mark> and <mark>output2.txt</mark></p>\n",
    "\n",
    "<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>.text_cell .rendered_html * {direction: rtl; text-align: right;}</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%html\n",
    "<style>.text_cell .rendered_html * {direction: rtl; text-align: right;}</style>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import random\n",
    "from heapq import heappop, heappush, nlargest, nsmallest, heapify\n",
    "from collections import Counter\n",
    "import copy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "هدف این پروژه استفاده از الگوریتم ژنتیک برای مسئله برنامه ریزی است.  \n",
    "از این الگوریتم برای مسائل جست و جو و بهینه سازی استفاده می شود."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2 style = \"font-size: 25px;\">Test Files</h2>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "testFile1 = \"test1.txt\"\n",
    "testFile2 = \"test2.txt\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2 style = \"font-size: 25px;\">Reading Test File Content</h2>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def readInput(testFile) :\n",
    "    file = open(testFile, 'r+')\n",
    "    fileList = file.readlines()\n",
    "    fileList = [s.replace('\\n', '') for s in fileList]\n",
    "    \n",
    "    [days, doctors] = [int(i) for i in fileList[0].split()]\n",
    "    maxCapacity = int(fileList[1])\n",
    "    \n",
    "    allShifts = []\n",
    "    for i in range(2, days + 2):\n",
    "        dayRequirements = fileList[i].split()\n",
    "        morningReqs = [int(i) for i in dayRequirements[0].split(\",\")]\n",
    "        eveningReqs = [int(i) for i in dayRequirements[1].split(\",\")]\n",
    "        nightReqs = [int(i) for i in dayRequirements[2].split(\",\")]\n",
    "        \n",
    "        allShifts.append((morningReqs, eveningReqs, nightReqs))\n",
    "\n",
    "    file.close()\n",
    "    return [days, list(range(doctors)), maxCapacity, allShifts]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2 style = \"font-size: 25px;\">Job Scheduler</h2>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Chromosome:\n",
    "    def __init__(self, genes, fitness):\n",
    "        self.genes = genes\n",
    "        self.fitness = fitness\n",
    "\n",
    "    def __lt__(self, other):\n",
    "        return self.fitness <= other.fitness"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class JobScheduler:\n",
    "    def __init__(self, fileInfo):\n",
    "        self.days = fileInfo[0]\n",
    "        self.doctors = len(fileInfo[1])\n",
    "        self.doctorsIds = fileInfo[1]\n",
    "        self.maxCapacity = fileInfo[2]\n",
    "        self.allShifts = fileInfo[3]\n",
    "        self.popSize = 500\n",
    "        self.chromosomes = self.generateInitialPopulation()\n",
    "        self.elitismPercentage = 0.6\n",
    "        self.pc = 0.65\n",
    "        self.pm = 0.8\n",
    "\n",
    "    def generateInitialPopulation(self):\n",
    "        population = []\n",
    "        for i in range(self.popSize):\n",
    "            chromosome_genes = []\n",
    "            for d in range(self.days):\n",
    "                day = {}\n",
    "                for shift in range(3):\n",
    "                    doctor_nom = random.randint(0, self.doctors)\n",
    "                    day[shift] = set(random.sample(range(0, self.doctors), doctor_nom))\n",
    "                chromosome_genes.append(day)\n",
    "            fitness = self.calculateFitness(chromosome_genes)\n",
    "            chromosome = Chromosome(chromosome_genes, fitness)\n",
    "            heappush(population, chromosome)\n",
    "        return population\n",
    "\n",
    "\n",
    "    def crossOver(self, chromosome1, chromosome2):\n",
    "        ch1_genes = copy.deepcopy(chromosome1.genes)\n",
    "        ch2_genes = copy.deepcopy(chromosome2.genes)\n",
    "        for day in range(self.days):\n",
    "            for shift in range(3):\n",
    "                if random.uniform(0, 1) < 0.5:\n",
    "                    ch1_genes[day][shift], ch2_genes[day][shift] = ch2_genes[day][shift],  ch1_genes[day][shift]\n",
    "        return ch1_genes\n",
    "\n",
    "\n",
    "    def mutate(self, chromosome_genes):\n",
    "        child_genes = copy.deepcopy(chromosome_genes)\n",
    "        for day in range(self.days):\n",
    "            for shift in range(3):\n",
    "                if random.uniform(0, 1) < 0.5:\n",
    "                    if not child_genes[day][shift]:\n",
    "                        temp = random.sample(child_genes[day][shift], 1)[0]\n",
    "                        child_genes[day][shift].remove(temp)\n",
    "                if random.uniform(0, 1) < 0.5:\n",
    "                    if not child_genes[day][shift]:\n",
    "                        temp = random.sample(self.doctorsIds, 1)[0]\n",
    "                        child_genes[day][shift].add(temp)\n",
    "        return child_genes\n",
    "\n",
    "    def calculateFitness(self, chromosome_genes):\n",
    "        conflicts_no = 0\n",
    "        dr_counts = Counter()\n",
    "        for day in range(self.days):\n",
    "            for shift in range(3):\n",
    "                dr_counts.update(chromosome_genes[day][shift])\n",
    "                if len(chromosome_genes[day][shift]) < self.allShifts[day][shift][0]:\n",
    "                    conflicts_no += 1\n",
    "                if len(chromosome_genes[day][shift]) > self.allShifts[day][shift][1]:\n",
    "                    conflicts_no += 1\n",
    "\n",
    "            if day + 1 < self.days and chromosome_genes[day][2] & chromosome_genes[day+1][0] and chromosome_genes[day][2] & chromosome_genes[day+1][1]:\n",
    "                conflicts_no += 1\n",
    "            if day + 2 < self.days and chromosome_genes[day][2] & chromosome_genes[day+1][2] & chromosome_genes[day+2][2]:\n",
    "                conflicts_no += 3\n",
    "        for dr in dr_counts:\n",
    "            if dr_counts[dr] > self.maxCapacity:\n",
    "                conflicts_no = conflicts_no + (dr_counts[dr] - self.maxCapacity)\n",
    "        return -1/(conflicts_no+1)\n",
    "\n",
    "\n",
    "    def generateNewPopulation(self):\n",
    "        new_population = nsmallest(int(self.elitismPercentage * self.popSize), self.chromosomes)\n",
    "        heapify(new_population)\n",
    "\n",
    "        parents = copy.deepcopy(new_population)\n",
    "        fitnesses = [ch.fitness for ch in self.chromosomes]\n",
    "        probability_distribution = []\n",
    "        total_fitness = sum(fitnesses)\n",
    "        probability_distribution = [(ch.fitness/total_fitness) for ch in self.chromosomes]\n",
    "        for i in range(int((1-self.elitismPercentage) * self.popSize)):\n",
    "            parents.extend(random.choices(self.chromosomes, weights=probability_distribution))\n",
    "\n",
    "        while len(new_population) < self.popSize:\n",
    "            chromosome1 = random.choice(parents)\n",
    "            chromosome2 = random.choice(parents)\n",
    "            if self.pc > random.uniform(0, 1):\n",
    "                child_genes = self.crossOver(chromosome1, chromosome2)\n",
    "                child_fitness = self.calculateFitness(child_genes)\n",
    "                child = Chromosome(child_genes, child_fitness)\n",
    "                heappush(new_population, child)\n",
    "\n",
    "        while len(new_population) < self.popSize:\n",
    "            if self.pm > random.uniform(0, 1):\n",
    "                chromosome = random.choice(parents)\n",
    "                child_genes = self.mutate(chromosome.genes)\n",
    "                child_fitness = self.calculateFitness(child_genes)\n",
    "                child = Chromosome(child_genes, child_fitness)\n",
    "                chr_dict = {new_population[i]: i for i in range(len(new_population))}\n",
    "                index = chr_dict[chromosome]\n",
    "                new_population[index] = new_population[-1]\n",
    "                new_population.pop()\n",
    "                heapify(new_population)\n",
    "                heappush(new_population, child)\n",
    "\n",
    "        max_fitness_chromosome = heappop(new_population)\n",
    "        self.chromosomes = new_population\n",
    "        return max_fitness_chromosome\n",
    "\n",
    "\n",
    "    def schedule(self):\n",
    "        while True:\n",
    "            result = self.generateNewPopulation()\n",
    "            if result.fitness == -1:\n",
    "                print(result.genes)\n",
    "                return result\n",
    "\n",
    "\n",
    "def writeInFile(result, filename):\n",
    "    a_file = open(filename, \"w\")\n",
    "    for day in range(len(result.genes)):\n",
    "        print(\",\".join(str(e) for e in result.genes[day][0]), end=' ', file=a_file)\n",
    "        print(\",\".join(str(e) for e in result.genes[day][1]), end=' ', file=a_file)\n",
    "        print(\",\".join(str(e) for e in result.genes[day][2]), file=a_file)\n",
    "    a_file.close()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "generateInitialPopulation:  \n",
    "در این متد جمعیت اولیه را به صورت کاملا رندوم انتخاب می کنیم. برای هر شیفت به تعداد رندوم در هر شیفت دکتر رندومی را قرار می دهیم.\n",
    "مدل سازی مسئله به این شکل است که هر کروموزوم لیستی است از روز ها و هر روز دیکشنری است از سه شیفت صبح و عصر و شب.  \n",
    "کروموزوم روز ها و ژن ها شیفت های آن روز می باشد.  \n",
    "\n",
    "\n",
    "در این پیاده سازی یک کلاس chromosome در نظر گرفتم که attribute های آن ژن های آن کروموزوم و fitness آن می باشد.  \n",
    "دلیل این کار استفاده از heap برای کروموزوم می باشد که در این صورت با O(1) می توان کروموزوم با بیشترین فیتنس را در دست داشت . \n",
    "\n",
    "به دلیل این که heap در پایتون به صورت minheapاست و ما به دنبال بزرگ ترین fitness هستیم، مقادیر fitness را در -۱ ضرب کرده ام.  \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "crossOver:   \n",
    "دو کروموزم می گیرد و به ازای هر شیفت به احتمال ۵۰ درصد از کروموزوم ۱ و به احتمال ۵۰ درصد از کروموزوم ۲ را نگه می دارد. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "mutate:  \n",
    "     در این متد به ازای هر شیفت در کروموزوم بااحتمال ۵۰ درصد یا دکتری را از آن حذف می کند و یا اضافه می کند.  \n",
    "     که ممکن است هردو یا هیچ کدام اتفاق بیافتد که در صورتی که هر دو اتفاق بیافتد به معنی عوض کردن یک دکتر با دکتر دیگر است."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "calculateFitness:  \n",
    "    به ازای هر محدودیت که در کروموزوم داده شده وجود دارد یکی به تعداد محدودیت ها اضافه میکنیم.  \n",
    "به دلیل این که تعداد دکتر های اولیه بسیار زیاد به تعداد دکتر های اضافه، تعداد محدودیت را اضافه کردم.  \n",
    "در نهایت فیتنس را معکوس تعداد محدودیت ها قرار دادم.   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "generateNewPopulation:\n",
    "با توجه به مقدار elitismPercentage درصدی از جمعیت اولیه را مستقیما به لیست parent ها اضافه می کنیم.  \n",
    "تعداد parent ها باید برابر با تعداد جمعیت اولیه باشد.  \n",
    "بقیه لیست parent را با استفاده از یک انتخاب رندوم وزن دار به وزن fitness/ total_fitness برای هر کروموزوم در نظر می گیریم.  \n",
    "از لیست parent  ها دو کروموزوم را به صورت رندوم انتخاب می کنیم و آن ها را با احتمال pc کراس اور می کنیم و در جمعیت جدیدی که می خواهیم تشکیل دهیم قرار می دهیم.  \n",
    "به همین ترتیب به صورت رندوم کروموزومی را از لیست parent ها انتخاب می کنیم و به احتمال pm  آ را mutate می کنیم.  \n",
    "در نهایت جمعیت جدید را با جمعیت قبلی جایگزین می کنیم.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2 style = \"font-size: 25px;\">Execution</h2>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{0: {1, 3, 5, 6}, 1: {4}, 2: {0, 1, 6}}, {0: {3, 4, 5}, 1: {4, 5}, 2: {4}}, {0: {6}, 1: {1, 4}, 2: {2}}, {0: {3}, 1: {0, 2}, 2: {3, 4, 6}}, {0: {2, 5}, 1: {5}, 2: {2}}, {0: {2}, 1: {0}, 2: {3}}, {0: {2, 3}, 1: {2}, 2: {0}}, {0: set(), 1: {1}, 2: {3, 5}}, {0: set(), 1: {6}, 2: {2}}, {0: {3}, 1: {4}, 2: {0, 5}}]\n",
      "test 1:  5.83 sec\n"
     ]
    }
   ],
   "source": [
    "fileInfo1 = readInput(testFile1)\n",
    "start = time.time()\n",
    "scheduler = JobScheduler(fileInfo1)\n",
    "result = scheduler.schedule()\n",
    "end = time.time()\n",
    "print(\"test 1: \", '%.2f' % (end - start), 'sec')\n",
    "writeInFile(result, \"output1.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[{0: {0, 4}, 1: {1}, 2: {0, 1, 2, 4, 8}}, {0: {0, 3, 7}, 1: {6}, 2: {0}}, {0: {4}, 1: {3}, 2: {8, 2}}, {0: set(), 1: {1, 5}, 2: {8, 3, 5}}, {0: {1}, 1: {5}, 2: {4}}, {0: {8, 5}, 1: {3, 4, 6}, 2: {5, 7}}, {0: {3, 7}, 1: {6}, 2: {1, 4}}, {0: {5}, 1: {8, 5, 6}, 2: {2, 3}}, {0: {0}, 1: {0, 1, 2, 4}, 2: {8, 1, 3}}, {0: set(), 1: {0}, 2: set()}, {0: set(), 1: {4, 6}, 2: set()}, {0: {8, 1}, 1: {4}, 2: set()}, {0: {5}, 1: {4, 6}, 2: {2, 3}}, {0: {1}, 1: {2, 6}, 2: {8, 0, 6}}, {0: set(), 1: {2, 3}, 2: {1}}]\n",
      "test 1:  11.26 sec\n"
     ]
    }
   ],
   "source": [
    "fileInfo2 = readInput(testFile2)\n",
    "start = time.time()\n",
    "scheduler = JobScheduler(fileInfo2)\n",
    "result = scheduler.schedule()\n",
    "end = time.time()\n",
    "print(\"test 1: \", '%.2f' % (end - start), 'sec')\n",
    "writeInFile(result, \"output2.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import os\n",
    "os.system('jupyter nbconvert --to html genetic-hands-on.ipynb')"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}