SHARE
TWEET

Untitled

a guest Jul 21st, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. __author__ = 'Marcel Glass'
  2.  
  3. # The problem is defined by finding the configuration of a number of school courses assigned to a number of timeslots where the number of collisions is minimal.
  4. # A collision is defined as the number of students, which can't attend all of there courses, because some of them happen at the same timeslot.
  5. # Each Subject consists of one main course, which is already assigned to a timeslot, which can't be changed. This is defined in self.takenSlots
  6. # Each Subject has 2 sets of 3 secondary courses. Each student of a subject has to attend one complete set of 3 courses in addition to the main course.
  7. # E.g. Subject "Mat" has 2 sets "Mat1" and "Mat2" of 3 secondary courses each. A Student of Mat has to attend all 3 "Mat1" courses or all 3 "Mat2" courses.
  8. # Each Student studies 2 subjects. Their combinations are defined in self.combinations. The number indicated how many students have any given combination.
  9.  
  10. # The problem is solved using a simulatedAnnealing algorithm. A random starting configuration is chosen. Then in each step a small changed is made. The likelihood of the change
  11. # to be accepted depends on the improvement and also decreases over time for worse solutions. The algorithm runs for 2000 steps or until a perfect solution is found.
  12.  
  13. from csv import reader
  14. from time import time
  15. from random import randint
  16. from copy import deepcopy
  17. from math import exp
  18. from multiprocessing import Process
  19.  
  20. #helper function for elapsed time in milliseconds
  21. current_milli_time = lambda: int(round(time() * 1000))
  22.  
  23. startm = current_milli_time()
  24.  
  25. class SimAnn(object):
  26.     def __init__(self):
  27.         # Definition of the problem
  28.         self.problem = [['SLOTS'], ['25']]
  29.         self.subjects = ['Bio', 'Che', 'Deu', 'Eng', 'EvR', 'Fra', 'Geo', 'Ges', 'Gri', 'Ita', 'KaR', 'Lat', 'Mat', 'Phi', 'Phy', 'Rus', 'Sok', 'Spa', 'Spo', 'BiW']
  30.         self.takenSlots = [
  31.             ['SLOT 1'], ['Deu'], [],
  32.             ['SLOT 2'], ['EvR', 'Geo', 'Ita'], [],
  33.             ['SLOT 3'], ['Bio', 'Phi'], [],
  34.             ['SLOT 4'], ['Geo', 'KaR', 'Rus'], [],
  35.             ['SLOT 5'], ['Che', 'EvR', 'Rus', 'Spa'], [],
  36.             ['SLOT 6'], ['Eng'], [],
  37.             ['SLOT 7'], ['Ges', 'Ita'], [],
  38.             ['SLOT 8'], ['Che', 'Gri', 'Phi'], [],
  39.             ['SLOT 9'], ['Fra', 'Gri', 'Sok'], [],
  40.             ['SLOT 10'], ['EvR', 'KaR', 'Spo'], [],
  41.             ['SLOT 11'], ['Ges'], [],
  42.             ['SLOT 12'], ['Che', 'Fra', 'Lat'], [],
  43.             ['SLOT 13'], ['Eng', 'Phy'], [],
  44.             ['SLOT 14'], ['Ita', 'Mat', 'Sok'], [],
  45.             ['SLOT 15'], ['Phi', 'Spo'], [],
  46.             ['SLOT 16'], ['Ges'], [],
  47.             ['SLOT 17'], ['Geo', 'Lat'], [],
  48.             ['SLOT 18'], ['Bio', 'Fra', 'Phy'], [],
  49.             ['SLOT 19'], ['Bio', 'KaR', 'Spa'], [],
  50.             ['SLOT 20'], ['Lat', 'Rus', 'Sok', 'Spo'], [],
  51.             ['SLOT 21'], ['Eng', 'Gri'], [],
  52.             ['SLOT 22'], ['Deu', 'Mat'], [],
  53.             ['SLOT 23'], ['Deu', 'Gri', 'Phy'], [],
  54.             ['SLOT 24'], ['Mat', 'Spa'], [],
  55.             ['SLOT 25'], ['BiW'], []
  56.         ]
  57.         self.combinations = [
  58.             ['0'],
  59.             ['34', ' 0'],
  60.             ['36', ' 9', ' 0'],
  61.             ['26', ' 16', ' 146', ' 0'],
  62.             ['5', ' 1', ' 33', ' 26', ' 0'],
  63.             ['8', ' 4', ' 32', ' 95', ' 8', ' 0'],
  64.             ['30', ' 18', ' 70', ' 116', ' 7', ' 39', ' 0'],
  65.             ['16', ' 12', ' 168', ' 186', ' 77', ' 68', ' 48', ' 0'],
  66.             ['0', ' 0', ' 0', ' 0', ' 0', ' 0', ' 0', ' 3', ' 0'],
  67.             ['0', ' 0', ' 3', ' 10', ' 0', ' 7', ' 2', ' 2', ' 0', ' 0'],
  68.             ['2', ' 4', ' 40', ' 27', ' 0', ' 15', ' 8', ' 77', ' 1', ' 3', ' 0'],
  69.             ['7', ' 0', ' 16', ' 24', ' 8', ' 7', ' 5', ' 43', ' 6', ' 2', ' 15', ' 0'],
  70.             ['16', ' 51', ' 16', ' 31', ' 10', ' 21', ' 41', ' 53', ' 1', ' 2', ' 12', ' 24', ' 0'],
  71.             ['8', ' 7', ' 128', ' 111', ' 14', ' 37', ' 35', ' 236', ' 0', ' 3', ' 19', ' 18', ' 47', ' 0'],
  72.             ['1', ' 8', ' 2', ' 7', ' 2', ' 1', ' 12', ' 16', ' 0', ' 0', ' 5', ' 2', ' 82', ' 12', ' 0'],
  73.             ['0', ' 0', ' 4', ' 3', ' 0', ' 4', ' 1', ' 6', ' 0', ' 2', ' 0', ' 0', ' 3', ' 3', ' 0', ' 0'],
  74.             ['9', ' 11', ' 57', ' 53', ' 4', ' 6', ' 23', ' 47', ' 0', ' 0', ' 6', ' 3', ' 16', ' 23', ' 3', ' 0', ' 0'],
  75.             ['4', ' 2', ' 26', ' 54', ' 4', ' 41', ' 17', ' 27', ' 0', ' 6', ' 8', ' 5', ' 8', ' 16', ' 1', ' 2', ' 9', ' 0'],
  76.             ['22', ' 8', ' 27', ' 53', ' 6', ' 10', ' 51', ' 32', ' 0', ' 0', ' 2', ' 6', ' 38', ' 17', ' 10', ' 1', ' 9', ' 9', ' 0'],
  77.             ['224', ' 185', ' 813', ' 984', ' 205', ' 403', ' 523', ' 1117', ' 11', ' 42', ' 244', ' 191', ' 472', ' 734', ' 164', ' 29', ' 279', ' 239', ' 301']
  78.         ]
  79.         self.numberOfSubjects = len(self.subjects)
  80.         self.numberOfSlots = int(self.problem[1][0])
  81.         self.slotsPerSubject = [[[] for j in range(3)] for i in range(self.numberOfSubjects)]
  82.         for id in range(self.numberOfSubjects):
  83.             for n in range(self.numberOfSlots):
  84.                 slot = n*3+1
  85.                 if self.subjects[id] in self.takenSlots[slot]:
  86.                     self.slotsPerSubject[id][0].append((slot-1)/3)
  87.         self.copySlotsPerSubject = deepcopy(self.slotsPerSubject)
  88.         self.copyTakenSlots = deepcopy(self.takenSlots)
  89.  
  90.     #random starting configuration
  91.     def start(self):
  92.         for id in range(self.numberOfSubjects):
  93.             for course in [1,2]:
  94.                 for date in [1,2,3]:
  95.                     while(True):
  96.                         rand = randint(0,self.numberOfSlots-1)
  97.                         randomslot = rand*3+1
  98.                         if (self.subjects[id] not in self.takenSlots[randomslot]) and (self.subjects[id]+str(course) not in self.takenSlots[randomslot+1]):
  99.                             self.slotsPerSubject[id][course].append((randomslot-1)/3)
  100.                             if self.takenSlots[randomslot+1] == None:
  101.                                 self.takenSlots[randomslot+1] = [self.subjects[id]+str(course)]
  102.                             else:
  103.                                 self.takenSlots[randomslot+1].append(self.subjects[id]+str(course))
  104.                             break
  105.  
  106.     #method to count the collisions
  107.     def count(self):
  108.         count = 0
  109.         for n in range(self.numberOfSubjects):
  110.             for m in range(n):
  111.                 flag = 0
  112.                 for x in range(2):
  113.                     for y in range(2):
  114.                         for slot in self.slotsPerSubject[n][x]:
  115.                             if (slot in self.slotsPerSubject[m][0]) or (slot in self.slotsPerSubject[m][y]):
  116.                                 flag += 1
  117.                         if flag == 4:
  118.                             #print("In subjects "+subjects[n]+" and "+subjects[m]+" we have "+(combinations[n][m])+" collisions")
  119.                             count += int(self.combinations[n][m])
  120.         return count
  121.  
  122.     #method to change the solution randomly; neighborhood is defined by changing only one course to a new slot
  123.     def change(self):
  124.         self.copySlotsPerSubject = deepcopy(self.slotsPerSubject)
  125.         self.copyTakenSlots = deepcopy(self.takenSlots)
  126.         sub = randint(0,self.numberOfSubjects-1)
  127.         cou = randint(1,2)
  128.         dat = randint(0,2)
  129.         new = randint(0,self.numberOfSlots-1)
  130.         while(new in self.slotsPerSubject[sub][cou] or new in self.slotsPerSubject[sub][0]):
  131.             new = randint(0, self.numberOfSlots-1)/1
  132.         mark = 30
  133.         markid = 0
  134.         for n in self.takenSlots[int(self.slotsPerSubject[sub][cou][dat])*3+2]:
  135.             if n == self.subjects[sub]+str(cou):
  136.                 mark = markid
  137.                 break
  138.             markid += 1
  139.         del self.takenSlots[int(self.slotsPerSubject[sub][cou][dat])*3+2][mark]
  140.         del self.slotsPerSubject[sub][cou][dat]
  141.         self.takenSlots[int(new*3+2)].append(self.subjects[sub]+str(cou))
  142.         self.slotsPerSubject[sub][cou].append(new)
  143.  
  144.     #undoes the last change
  145.     def redo(self):
  146.         self.slotsPerSubject = deepcopy(self.copySlotsPerSubject)
  147.         self.takenSlots = deepcopy(self.copyTakenSlots)
  148.  
  149.     #The Simulated Annealing; omega is the starting-temperatur, alpha the cool down rate
  150.     def run(self):
  151.         omega = 0.2
  152.         alpha = 0.93
  153.         self.start()
  154.         coll = self.count()
  155.         for n in range(2000):
  156.             self.change()
  157.             collnew = self.count()
  158.             if collnew<coll:
  159.                 coll = collnew
  160.             else:
  161.                 coin = randint(1,100)/100
  162.                 tres = exp(-abs((collnew-coll)/100)/omega)
  163.                 if coin >= tres:
  164.                     self.redo()
  165.                 else:
  166.                     omega *= alpha
  167.                     coll = collnew
  168.             if coll == 0:
  169.                 return coll, n, self.takenSlots
  170.             #print(coll)
  171.         return coll, 2000, self.takenSlots
  172.  
  173. # Function which restarts algorithm, if no perfect solution was found
  174. def f():
  175.     m = 0
  176.     while True:
  177.         sim = SimAnn()
  178.         result = sim.run()
  179.         if result[0] == 0:
  180.             solutionTakenSlots = deepcopy(sim.takenSlots)
  181.             solutionSlotsPerSubject = deepcopy(sim.slotsPerSubject)
  182.             print("Time elapsed:", current_milli_time()-startm, "seconds")
  183.             break
  184.         m += 1
  185.  
  186.     print("M: "+str(m))
  187.     print("Collisions in final solution: "+str(result[0]))
  188.     print("TakenSlots: "+str(solutionTakenSlots))
  189.  
  190.  
  191. if __name__ == '__main__':
  192.  
  193.     # Multi-processing on 4 Cores at the same time. Searches for 4 Solutions independently
  194.     # procs = []
  195.     # for i in range(4):
  196.     #     p = Process(target=f)
  197.     #     procs.append(p)
  198.     #     p.start()
  199.     # for k in procs:
  200.     #     k.join()
  201.     # print(current_milli_time()-startm)
  202.    
  203.     #f()
  204.    
  205.     sim = SimAnn()
  206.     result = sim.run()
  207.     print("Time elapsed:", current_milli_time()-startm, "seconds")
  208.     print("Collisions in final solution: "+str(result[0]))
  209.     print("Final solution: "+str(sim.takenSlots))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top