• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
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)
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].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]) 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]):
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:
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))
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))
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.

Top