排课表软件在农业大学中的应用与实现

张伟：李明，你最近在忙什么项目？我听说你在做排课表的软件，是农业大学那边的吗？

李明：对，是农业大学的一个教务系统升级项目。他们之前用的是手工排课，效率低、出错率高，现在想引入一个自动化排课系统。

张伟：听起来挺复杂的。排课表需要考虑哪些因素？比如课程时间、教师资源、教室容量这些吧？

李明：没错，而且还要处理很多约束条件。比如同一门课不能安排在同一个时间段，不同班级之间不能冲突，还有教师的可用时间等等。

张伟：那你们是怎么实现自动排课的？有没有用到什么算法？

李明：我们用了遗传算法（Genetic Algorithm）来解决这个问题。因为这是一个典型的组合优化问题，传统的回溯法效率太低，而遗传算法可以快速找到近似最优解。

张伟：遗传算法？能讲讲具体怎么实现的吗？

李明：当然可以。首先，我们需要定义一个“染色体”结构，用来表示一个可能的排课方案。每个基因代表一门课程的时间安排，比如课程A安排在周一上午10点，课程B安排在周三下午3点等。

张伟：那这个染色体怎么生成呢？是不是随机生成的？

李明：是的，初始种群是随机生成的。然后我们计算每个个体的适应度函数，也就是这个排课方案是否满足所有约束条件，以及是否尽可能地优化了资源利用。

张伟：那适应度函数怎么设计？

李明：适应度函数主要考虑几个方面：一是课程之间的冲突数量；二是教师和教室的利用率；三是学生选课的合理性。如果某个方案有多个冲突，那么它的适应度就会比较低。

张伟：明白了。那遗传算法的步骤是怎样的？

李明：大致分为以下几个步骤：初始化种群、计算适应度、选择、交叉、变异、替换，然后重复直到达到终止条件，比如迭代次数或适应度足够高。

张伟：听起来挺像机器学习的过程。那你们有没有写代码实现？

李明：有的，下面是我用Python写的简单示例代码，虽然只是一个简化版，但可以说明基本原理。


# 简化版排课表算法示例（使用遗传算法）
import random
# 定义课程信息
courses = [
{"name": "数学", "teacher": "张老师", "time": ["Mon 9:00", "Wed 14:00"]},
{"name": "物理", "teacher": "李老师", "time": ["Tue 10:00", "Thu 15:00"]},
{"name": "化学", "teacher": "王老师", "time": ["Mon 10:00", "Fri 13:00"]}
]
# 定义染色体结构：每个基因是一个课程的时间安排
def create_chromosome():
return {course["name"]: random.choice(course["time"]) for course in courses}
# 计算适应度（越小越好）
def fitness(chromosome):
conflicts = 0
# 检查是否有时间冲突
for course in courses:
if chromosome[course["name"]] in [chromosome[c]["name"] for c in courses if c["name"] != course["name"]]:
conflicts += 1
# 检查教师是否在同一时间授课
teacher_times = {}
for course in courses:
teacher = course["teacher"]
time = chromosome[course["name"]]
if teacher in teacher_times and teacher_times[teacher] == time:
conflicts += 1
else:
teacher_times[teacher] = time
return conflicts
# 遗传算法主逻辑
def genetic_algorithm(pop_size=100, generations=1000):

population = [create_chromosome() for _ in range(pop_size)]
for gen in range(generations):
# 计算适应度
fitness_scores = [(chromosome, fitness(chromosome)) for chromosome in population]
# 排序并选择前一半作为下一代
fitness_scores.sort(key=lambda x: x[1])
next_generation = [x[0] for x in fitness_scores[:pop_size//2]]
# 交叉

while len(next_generation) < pop_size:
parent1, parent2 = random.sample(fitness_scores[:10], 2)
child = {}
for course in courses:
child[course["name"]] = random.choice([parent1[0][course["name"]], parent2[0][course["name"]]])
next_generation.append(child)
# 变异
for i in range(len(next_generation)):
if random.random() < 0.1:
course = random.choice(courses)
next_generation[i][course["name"]] = random.choice(course["time"])
population = next_generation
best = min(population, key=lambda x: fitness(x))
return best
# 运行算法
result = genetic_algorithm()
print("最佳排课方案：", result)