-
Notifications
You must be signed in to change notification settings - Fork 0
/
algorithm.py
184 lines (165 loc) · 7.01 KB
/
algorithm.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
import data as dt
import cost_functions
import mutation
from copy import deepcopy
max_generations = 5000
num_runs = 1
input_file = 'classes/input2.json'
output_file = 'classes/output2.json'
cost_function = cost_functions.cost
# Soft constraint not important yet
# cost_function2 = cost_functions.cost2
def evolutionary_algorithm():
best_timetable = None
data = dt.load_data(input_file)
neighbour = mutation.neighbour # call the neighbour function from mutation file
for i in range(num_runs):
chromosome = dt.generate_chromosome(data) # generate a chromosome by creating the first timetable by random
for j in range(max_generations):
# change the new chromosome by calling the neighbour from mutation by getteing a deepcopy from the original chromosom
new_chromosome = neighbour(deepcopy(chromosome))
# calculate the cost for the chromosome
ft = cost_function(chromosome)
# if the cost for the chromosome == 0 -> optimal solution (no violate of hard and soft constraint)
if ft == 0:
break
# calculate the cost for the chromosome
ftn = cost_function(new_chromosome)
# ---- if the cost for the new_chromosome less than or equal the cost chromosome
# change the value of chromosome to new_chromosome ----
if ftn <= ft:
chromosome = new_chromosome
# print the iteration number and the cost for the current chromosome
if j % 200 == 0:
print('Iteration', j, 'cost', cost_function(chromosome))
print('Run', i + 1, 'cost', cost_function(chromosome), 'chromosome', chromosome)
# Soft constraint not important yet
# if best_timetable is None or cost_function2(chromosome) <= cost_function2(best_timetable):
if best_timetable is None:
best_timetable = deepcopy(chromosome)
chromosome = best_timetable
neighbour2 = mutation.neighbour2
"""
Soft constraint not important yet
"""
# for j in range(3 * max_generations):
# new_chromosome = neighbour2(deepcopy(chromosome))
# ft = cost_function2(chromosome)
# ftn = cost_function2(new_chromosome)
# if ftn <= ft:
# chromosome = new_chromosome
# if j % 200 == 0:
# print('Iteration', j, 'cost', cost_function2(chromosome))
#
# print('Run', 'cost', cost_function2(chromosome), 'chromosome', chromosome)
dt.write_data(chromosome[0], output_file)
professor_hard = True
classroom_hard = True
group_hard = True
allowed_classrooms = True
# Check hard constraints
for single_class in chromosome[0]:
if single_class['Zadata_ucionica'] not in single_class['Ucionica']:
allowed_classrooms = False
for profesor in chromosome[1]:
for i in range(len(chromosome[1][profesor])):
if chromosome[1][profesor][i] > 1:
professor_hard = False
for ucionica in chromosome[2]:
for i in range(len(chromosome[2][ucionica])):
if chromosome[2][ucionica][i] > 1:
classroom_hard = False
for grupa in chromosome[3]:
for i in range(len(chromosome[3][grupa])):
if chromosome[3][grupa][i] > 1:
group_hard = False
print('Are hard restrictions for professors satisfied:', professor_hard)
print('Are hard restrictions for classrooms satisfied:', classroom_hard)
print('Are hard restrictions for groups satisfied:', group_hard)
print('Are hard restrictions for allowed classrooms satisfied:', allowed_classrooms)
# Check preferred order statistics
subjects_cost = 0
for single_class in chromosome[4]:
subromject_cost = 0
for lab in chromosome[4][single_class]['L']:
for practice in chromosome[4][single_class]['V']:
for grupa in lab[1]:
if grupa in practice[1] and lab[0] < practice[0]:
subject_cost += 1
for lecture in chromosome[4][single_class]['P']:
for grupa in lab[1]:
if grupa in lecture[1] and lab[0] < lecture[0]:
subject_cost += 1
for practice in chromosome[4][single_class]['V']:
for lecture in chosome[4][single_class]['P']:
for grupa in practice[1]:
if grupa in lecture[1] and practice[0] < lecture[0]:
subject_cost += 1
subjects_cost += subject_cost
print('Subject cost for subject', single_class, 'is:', subject_cost)
print('Total subject cost:', subjects_cost)
# Check group statistics
total_group_cost = 0
total_group_load = 0
max_group_cost = 0
for group in chromosome[3]:
group_cost = 0
group_load = 0
for day in range(5):
last_seen = 0
found = False
current_load = 0
for hour in range(12):
time = day * 12 + hour
if chromosome[3][group][time] >= 1:
current_load += 1
if not found:
found = True
else:
group_cost += (time - last_seen - 1)
last_seen = time
if current_load > 6:
group_load += 1
print('Group cost for group', group, 'is:', group_cost, ', number of hard days:', group_load)
if max_group_cost < group_cost:
max_group_cost = group_cost
total_group_cost += group_cost
total_group_load += group_load
print('Maximum group cost is:', max_group_cost)
print('Average group cost is:', total_group_cost / len(chromosome[3]))
print('Total group load is:', total_group_load)
# Check professor statistics
total_prof_cost = 0
total_prof_load = 0
free_hour = True
max_prof_cost = 0
for prof in chromosome[1]:
prof_cost = 0
prof_load = 0
for day in range(5):
last_seen = 0
found = False
current_load = 0
for hour in range(12):
time = day * 12 + hour
if chromosome[1][prof][time] >= 1:
if time == 59:
free_hour = False
current_load += 1
if not found:
found = True
else:
prof_cost += (time - last_seen - 1)
last_seen = time
if current_load > 6:
prof_load += 1
print('Prof cost for prof', prof, 'is:', prof_cost, ', number of hard days:', prof_load)
if max_prof_cost < prof_cost:
max_prof_cost = prof_cost
total_prof_cost += prof_cost
total_prof_load += prof_load
print('Max prof cost is:', max_prof_cost)
print('Average prof cost is:', total_prof_cost / len(chromosome[1]))
print('Total prof load is:', total_prof_load)
print('Free hour:', free_hour, ', 59')
evolutionary_algorithm()