排課問(wèn)題的本質(zhì)是將課程彪腔、教師和學(xué)生在合適的時(shí)間段內(nèi)分配到合適的教室中森枪，涉及到的因素較多辽社，是一個(gè)多目標(biāo)的調(diào)度問(wèn)題喘先，在運(yùn)籌學(xué)中被稱為時(shí)間表問(wèn)題（Timetable Problem，TTP）解幽。設(shè)一個(gè)星期有n個(gè)時(shí)段可排課贴见，有m位教師需要參與排課，平均每位教師一個(gè)星期上k節(jié)課躲株，在不考慮其他限制的情況下片部，能夠推出的可能組合就有種，如此高的復(fù)雜度是目前計(jì)算機(jī)所無(wú)法承受的霜定。因此眾多研究者提出了多種其他排課算法档悠，如模擬退火，列表尋優(yōu)搜索和約束滿意等望浩。
Github：https://github.com/xiaochus/GeneticClassSchedule
環(huán)境
- Python 3.6
- prettytable
遺傳算法原理
遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型辖所，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。遺傳算法的流程如下所示：
GA
遺傳算法首先針對(duì)待解決問(wèn)題隨機(jī)生成一組解磨德，我們稱之為種群（Population）缘回。種群中的每個(gè)個(gè)體都是問(wèn)題的解，在優(yōu)化的過(guò)程中，算法會(huì)計(jì)算整個(gè)種群的成本函數(shù)切诀，從而得到一個(gè)與種群相關(guān)的適應(yīng)度的序列揩环。如下圖所示：
population
為了得到新的下一代種群，首先根據(jù)適應(yīng)度對(duì)種群進(jìn)行排序幅虑，從中挑選出最優(yōu)的幾個(gè)個(gè)體加入下一代種群，這一個(gè)過(guò)程也被稱為精英選拔顾犹。新種群余下的部分通過(guò)對(duì)選拔出來(lái)的精英個(gè)體進(jìn)行修改得到倒庵。
對(duì)種群進(jìn)行修改的方法參考了生物DAN進(jìn)化的方法，一般使用兩種方法：變異和交叉炫刷。變異的做法是對(duì)種群做一個(gè)微小的擎宝、隨機(jī)的改變。如果解的編碼方式是二進(jìn)制浑玛，那么就隨機(jī)選取一個(gè)位置進(jìn)行0和1的互相突變绍申；如果解的編碼方式是十進(jìn)制，那么就隨機(jī)選取一個(gè)位置進(jìn)行隨機(jī)加減顾彰。交叉的做法是隨機(jī)從最優(yōu)種群中選取兩個(gè)個(gè)體极阅，以某個(gè)位置為交叉點(diǎn)合成一個(gè)新的個(gè)體。
mutation
crossover
經(jīng)過(guò)突變和交叉后我們得到新的種群（大小與上一代種群一致）涨享，對(duì)新種群重復(fù)重復(fù)上述過(guò)程筋搏，直到達(dá)到迭代次數(shù)（失敗）或者解的適應(yīng)性達(dá)到我們的要求（成功）厕隧，GA算法就結(jié)束了奔脐。
基于遺傳算法的排課優(yōu)化
算法實(shí)現(xiàn)
首先定義一個(gè)課程類，這個(gè)類包含了課程吁讨、班級(jí)髓迎、教師、教室建丧、星期排龄、時(shí)間幾個(gè)屬性，其中前三個(gè)是我們自定義的茶鹃，后面三個(gè)是需要算法來(lái)優(yōu)化的涣雕。
class Schedule:
"""Class Schedule.
"""
def __init__(self, courseId, classId, teacherId):
"""Init
Arguments:
courseId: int, unique course id.
classId: int, unique class id.
teacherId: int, unique teacher id.
"""
self.courseId = courseId
self.classId = classId
self.teacherId = teacherId
self.roomId = 0
self.weekDay = 0
self.slot = 0
def random_init(self, roomRange):
"""random init.
Arguments:
roomSize: int, number of classrooms.
"""
self.roomId = np.random.randint(1, roomRange + 1, 1)[0]
self.weekDay = np.random.randint(1, 6, 1)[0]
self.slot = np.random.randint(1, 6, 1)[0]
接下來(lái)定義cost函數(shù)，這個(gè)函數(shù)用來(lái)計(jì)算課表種群的沖突闭翩。當(dāng)被測(cè)試課表沖突為0的時(shí)候挣郭，這個(gè)課表就是個(gè)符合規(guī)定的課表。沖突檢測(cè)遵循下面幾條規(guī)則：
- 同一個(gè)教室在同一個(gè)時(shí)間只能有一門課疗韵。
- 同一個(gè)班級(jí)在同一個(gè)時(shí)間只能有一門課 兑障。
- 同一個(gè)教師在同一個(gè)時(shí)間只能有一門課。
- 同一個(gè)班級(jí)在同一天不能有相同的課。
def schedule_cost(population, elite):
"""calculate conflict of class schedules.
Arguments:
population: List, population of class schedules.
elite: int, number of best result.
Returns:
index of best result.
best conflict score.
"""
conflicts = []
n = len(population[0])
for p in population:
conflict = 0
for i in range(0, n - 1):
for j in range(i + 1, n):
# check course in same time and same room
if p[i].roomId == p[j].roomId and p[i].weekDay == p[j].weekDay and p[i].slot == p[j].slot:
conflict += 1
# check course for one class in same time
if p[i].classId == p[j].classId and p[i].weekDay == p[j].weekDay and p[i].slot == p[j].slot:
conflict += 1
# check course for one teacher in same time
if p[i].teacherId == p[j].teacherId and p[i].weekDay == p[j].weekDay and p[i].slot == p[j].slot:
conflict += 1
# check same course for one class in same day
if p[i].classId == p[j].classId and p[i].courseId == p[j].courseId and p[i].weekDay == p[j].weekDay:
conflict += 1
conflicts.append(conflict)
index = np.array(conflicts).argsort()
return index[: elite], conflicts[index[0]]
使用遺傳算法進(jìn)行優(yōu)化的過(guò)程如下流译，與上一節(jié)的流程圖過(guò)程相同逞怨。
init_population：隨機(jī)初始化不同的種群。
mutate：變異操作福澡，隨機(jī)對(duì)Schedule對(duì)象中的某個(gè)可改變屬性在允許范圍內(nèi)進(jìn)行隨機(jī)加減叠赦。
crossover：交叉操作，隨機(jī)對(duì)兩個(gè)對(duì)象交換不同位置的屬性革砸。
evolution：?jiǎn)?dòng)GA算法進(jìn)行優(yōu)化除秀。
import copy
import numpy as np
from schedule import schedule_cost
class GeneticOptimize:
"""Genetic Algorithm.
"""
def __init__(self, popsize=30, mutprob=0.3, elite=5, maxiter=100):
# size of population
self.popsize = popsize
# prob of mutation
self.mutprob = mutprob
# number of elite
self.elite = elite
# iter times
self.maxiter = maxiter
def init_population(self, schedules, roomRange):
"""Init population
Arguments:
schedules: List, population of class schedules.
roomRange: int, number of classrooms.
"""
self.population = []
for i in range(self.popsize):
entity = []
for s in schedules:
s.random_init(roomRange)
entity.append(copy.deepcopy(s))
self.population.append(entity)
def mutate(self, eiltePopulation, roomRange):
"""Mutation Operation
Arguments:
eiltePopulation: List, population of elite schedules.
roomRange: int, number of classrooms.
Returns:
ep: List, population after mutation.
"""
e = np.random.randint(0, self.elite, 1)[0]
pos = np.random.randint(0, 2, 1)[0]
ep = copy.deepcopy(eiltePopulation[e])
for p in ep:
pos = np.random.randint(0, 3, 1)[0]
operation = np.random.rand()
if pos == 0:
p.roomId = self.addSub(p.roomId, operation, roomRange)
if pos == 1:
p.weekDay = self.addSub(p.weekDay, operation, 5)
if pos == 2:
p.slot = self.addSub(p.slot, operation, 5)
return ep
def addSub(self, value, op, valueRange):
if op > 0.5:
if value < valueRange:
value += 1
else:
value -= 1
else:
if value - 1 > 0:
value -= 1
else:
value += 1
return value
def crossover(self, eiltePopulation):
"""Crossover Operation
Arguments:
eiltePopulation: List, population of elite schedules.
Returns:
ep: List, population after crossover.
"""
e1 = np.random.randint(0, self.elite, 1)[0]
e2 = np.random.randint(0, self.elite, 1)[0]
pos = np.random.randint(0, 2, 1)[0]
ep1 = copy.deepcopy(eiltePopulation[e1])
ep2 = eiltePopulation[e2]
for p1, p2 in zip(ep1, ep2):
if pos == 0:
p1.weekDay = p2.weekDay
p1.slot = p2.slot
if pos == 1:
p1.roomId = p2.roomId
return ep1
def evolution(self, schedules, roomRange):
"""evolution
Arguments:
schedules: class schedules for optimization.
elite: int, number of best result.
Returns:
index of best result.
best conflict score.
"""
# Main loop .
bestScore = 0
bestSchedule = None
self.init_population(schedules, roomRange)
for i in range(self.maxiter):
eliteIndex, bestScore = schedule_cost(self.population, self.elite)
print('Iter: {} | conflict: {}'.format(i + 1, bestScore))
if bestScore == 0:
bestSchedule = self.population[eliteIndex[0]]
break
# Start with the pure winners
newPopulation = [self.population[index] for index in eliteIndex]
# Add mutated and bred forms of the winners
while len(newPopulation) < self.popsize:
if np.random.rand() < self.mutprob:
# Mutation
newp = self.mutate(newPopulation, roomRange)
else:
# Crossover
newp = self.crossover(newPopulation)
newPopulation.append(newp)
self.population = newPopulation
return bestSchedule
實(shí)驗(yàn)結(jié)果
下面定義了3個(gè)班，6種課程算利、教師和3個(gè)教室來(lái)對(duì)排課效果進(jìn)行測(cè)試册踩。
import prettytable
from schedule import Schedule
from genetic import GeneticOptimize
def vis(schedule):
"""visualization Class Schedule.
Arguments:
schedule: List, Class Schedule
"""
col_labels = ['week/slot', '1', '2', '3', '4', '5']
table_vals = [[i + 1, '', '', '', '', ''] for i in range(5)]
table = prettytable.PrettyTable(col_labels, hrules=prettytable.ALL)
for s in schedule:
weekDay = s.weekDay
slot = s.slot
text = 'course: {} \n class: {} \n room: {} \n teacher: {}'.format(s.courseId, s.classId, s.roomId, s.teacherId)
table_vals[weekDay - 1][slot] = text
for row in table_vals:
table.add_row(row)
print(table)
if __name__ == '__main__':
schedules = []
# add schedule
schedules.append(Schedule(201, 1201, 11101))
schedules.append(Schedule(201, 1201, 11101))
schedules.append(Schedule(202, 1201, 11102))
schedules.append(Schedule(202, 1201, 11102))
schedules.append(Schedule(203, 1201, 11103))
schedules.append(Schedule(203, 1201, 11103))
schedules.append(Schedule(206, 1201, 11106))
schedules.append(Schedule(206, 1201, 11106))
schedules.append(Schedule(202, 1202, 11102))
schedules.append(Schedule(202, 1202, 11102))
schedules.append(Schedule(204, 1202, 11104))
schedules.append(Schedule(204, 1202, 11104))
schedules.append(Schedule(206, 1202, 11106))
schedules.append(Schedule(206, 1202, 11106))
schedules.append(Schedule(203, 1203, 11103))
schedules.append(Schedule(203, 1203, 11103))
schedules.append(Schedule(204, 1203, 11104))
schedules.append(Schedule(204, 1203, 11104))
schedules.append(Schedule(205, 1203, 11105))
schedules.append(Schedule(205, 1203, 11105))
schedules.append(Schedule(206, 1203, 11106))
schedules.append(Schedule(206, 1203, 11106))
# optimization
ga = GeneticOptimize(popsize=50, elite=10, maxiter=500)
res = ga.evolution(schedules, 3)
# visualization
vis_res = []
for r in res:
if r.classId == 1203:
vis_res.append(r)
vis(vis_res)
優(yōu)化結(jié)果如下，迭代到第68次時(shí)效拭，課程安排不存在任何沖突暂吉。
...
Iter: 57 | conflict: 1
Iter: 58 | conflict: 1
Iter: 59 | conflict: 1
Iter: 60 | conflict: 1
Iter: 61 | conflict: 1
Iter: 62 | conflict: 1
Iter: 63 | conflict: 1
Iter: 64 | conflict: 1
Iter: 65 | conflict: 1
Iter: 66 | conflict: 1
Iter: 67 | conflict: 1
Iter: 68 | conflict: 0
選擇1203班的課表進(jìn)行可視化，如下所示缎患，算法合理的安排了對(duì)應(yīng)的課程慕的。
+-----------+-----------------+-----------------+-----------------+-----------------+-----------------+
| week/slot | 1 | 2 | 3 | 4 | 5 |
+-----------+-----------------+-----------------+-----------------+-----------------+-----------------+
| 1 | | | course: 204 | | |
| | | | class: 1203 | | |
| | | | room: 3 | | |
| | | | teacher: 11104 | | |
+-----------+-----------------+-----------------+-----------------+-----------------+-----------------+
| 2 | | course: 204 | | course: 206 | |
| | | class: 1203 | | class: 1203 | |
| | | room: 3 | | room: 3 | |
| | | teacher: 11104 | | teacher: 11106 | |
+-----------+-----------------+-----------------+-----------------+-----------------+-----------------+
| 3 | | course: 203 | | | |
| | | class: 1203 | | | |
| | | room: 3 | | | |
| | | teacher: 11103 | | | |
+-----------+-----------------+-----------------+-----------------+-----------------+-----------------+
| 4 | course: 205 | | | | |
| | class: 1203 | | | | |
| | room: 1 | | | | |
| | teacher: 11105 | | | | |
+-----------+-----------------+-----------------+-----------------+-----------------+-----------------+
| 5 | course: 206 | | | course: 205 | course: 203 |
| | class: 1203 | | | class: 1203 | class: 1203 |
| | room: 2 | | | room: 3 | room: 1 |
| | teacher: 11106 | | | teacher: 11105 | teacher: 11103 |
+-----------+-----------------+-----------------+-----------------+-----------------+-----------------+
