title: How to do Binary Encoding in Genetic Algorithm for better results in Timetable Scheduling Problem?
body: <p>I have a problem of University Timetable Scheduling which I am trying to solve with <strong>Genetic Algorithm</strong>. I want to know the best encoding type for this problem that can also help me in satisfying few of the constraints. For this problem, the timetable will have the following structure,</p>
  <ul>
  <li>There will be a total of 5 days in which the timetable will be scheduled (Monday to Friday).</li>
  <li>Every day, there will be 5 different slots, and one slot will have one lecture.</li>
  <li>However, <strong>Lab Lectures</strong> will be conducted over two consecutive slots.</li>
  <li>Timetable will also tell the Room Number (or Lab number) of each lecture and also the name of Instructor for every lecture.</li>
  </ul>
  <p>Now, the timetable looks something like this, (<em>in the picture, there are multiple slots, but I will be considering only 5 slots instead of dividing the timetable into so many slots</em>)</p>
  <p><a href="https://i.stack.imgur.com/4dLFa.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4dLFa.jpg" alt="enter image description here" /></a></p>
  <p>This is a timetable of only one section. There are around 25 sections in one single timetable.</p>
  <p>Now, what I have done is written the data of every course, its section, and its instructor in one file in a format like this,</p>
  <pre><code>1
  Object Oriented Programming 
  CS-3B
  Dr Ali Hassan 
  ,
  2
  Object Oriented Programming 
  SE-3A
  Dr Ali Hassan 
  ,
  3
  Remote Sensing and GIS 
  CS-7F
  Dr Tom Baker
  </code></pre>
  <p>And to represent the Timetable, I have made the file like this,</p>
  <pre><code>0
  1
  2 2 9
  3 2 9
  0
  2
  2 1 9
  3 1 9
  0
  3
  2 5 36
  4 1 36
  </code></pre>
  <ul>
  <li>0 is a separator, which separates one object from another.</li>
  <li>First number is basically the ID of the course. &quot;1&quot; actually represents the first object in my first file (i.e. Object Oriented Programming, CS-3A, Dr. Ali Hassan).</li>
  <li>Second row represents the first lecture of course (with id = 1) in the timetable. The format is as follows, <strong>First number</strong> is the <strong>day</strong>. <strong>Second number</strong> is the <strong>Slot</strong>. <strong>Third number</strong> is the <strong>Room Number.</strong>.
  So, in this case, it is saying that the first lecture of course id = 1 will be held on &quot;Tuesday&quot;, in the &quot;2nd Slot&quot; and in &quot;Room Number 9&quot;.</li>
  <li>Third row represents the <strong>second lecture</strong> of the same course.</li>
  </ul>
  <p>Now I need to <strong>encoding</strong> of this timetable. I have opted to go with <strong>Binary Encoding</strong> for now (obviously, I can shift to others but need to know which and how) and done the encoding like this,</p>
  <pre><code>00000001 00000010 00000010 00001001 00000011 00000010 00001001 
  00000010 00000010 00000001 00001001 00000011 00000001 00001001 
  00000011 00000010 00000101 00100100 00000100 00000001 00100100 
  00000100 00000010 00000001 00001101 00000100 00000010 00000110 
  00000101 00000010 00000010 00001101 00000011 00000001 00000011 
  </code></pre>
  <p>Since the total number of courses are likely to fall between 200-220 so I went with <strong>8-bit encoding</strong>.</p>
  <p>Encoding is done in this format,</p>
  <pre><code>Course_ID First_Lecture_Day First_Lecture_Slot First_Lecture_Room 2nd_Lec_Day 2nd_Lec_Slot 2nd_Lec_Room
  </code></pre>
  <p>Now, I want to know few things regarding this,</p>
  <ul>
  <li>Is this encoding the right approach? or should I have done this in any other way?</li>
  <li>A serious issue with this is this that I have the following two constraints,</li>
  </ul>
  <p>ss</p>
  <ol>
  <li>Lab Lectures must be conducted in two consecutive slots.</li>
  <li>Course Lectures must be conducted on different days, i.e. no course should have both lectures on same day.</li>
  </ol>
  <p>Now, I can resolve the 2nd issue by implementing it in the <em>fitness function</em> (I assume. I haven't yet went there but I am thinking that I can solve this issue there)</p>
  <p>However, I do not know how can I solve the first issue? Is there any particular way in which I can instruct the Genetic Algorithm to ALWAYS keep the lab lectures in consecutive slots? For example, I use another bit in my Binary Encoding, like maybe this,</p>
  <p>00000001 00000010 00000010 00001001 00000011 00000010 00001001 <strong>00000000</strong></p>
  <p>00000010 00000010 00000001 00001001 00000011 00000001 00001001 <strong>00000001</strong></p>
  <p>Where the last bit will tell whether the course is of lab or of course.. And depending upon that bit, if you are changing the lecture slots, then <strong>if the lab bit is on, then change both the lecture slots so that they stay with each other</strong> and hence, lab is conducted over consecutive slots? How can I make sure of this? Can anyone guide me, please?</p>
  <p>And also if any other approach I should have used in the Encoding Process for Genetic Algorithm? Thank you.</p>