遗传算法排课：Python代码实现多班级、多课程、多教师排课问题

以下是一个使用遗传算法进行排课的Python代码示例，旨在解决小学多班级、多课程、多教师排课问题。该代码考虑了多个因素，例如：

• 班级数不同
• 课程数不同
• 教师数不同
• 每个班级每个课程的课时量不同
• 每个教师可教授的课程不同
• 教师指定相应班级课程
• 一周算5天，一天7节课
• 语数英只排1-3节
• 体育不排1-3节
• 同一课程不连续上
• 一个班的一个课程一天不能出现3次

import random

# 定义班级数
num_classes = 6
# 定义课程数
num_courses = 5
# 定义教师数
num_teachers = 5
# 定义一天的课节数
num_lessons_per_day = 7
# 定义一周的天数
num_days_per_week = 5

# 定义每个班级的课程表
class_schedules = [[] for _ in range(num_classes)]

# 定义每个教师的课程表
teacher_schedules = [[] for _ in range(num_teachers)]

# 定义每个课程的课时量
course_hours = [3, 2, 2, 2, 2]

# 定义每个教师的课时量
teacher_hours = [12, 10, 8, 8, 6]

# 定义每个班级一周内每天的课程数量
class_day_courses = [[0 for _ in range(num_days_per_week)] for _ in range(num_classes)]

# 定义每个班级一周内每天每节课的课程数量
class_day_lesson_courses = [[[0 for _ in range(num_lessons_per_day)] for _ in range(num_days_per_week)] for _ in range(num_classes)]

# 定义每个班级每节课上的课程
class_lesson_courses = [[[set() for _ in range(num_lessons_per_day)] for _ in range(num_days_per_week)] for _ in range(num_classes)]

# 定义每个教师一周内每天的课程数量
teacher_day_courses = [[0 for _ in range(num_days_per_week)] for _ in range(num_teachers)]

# 定义每个教师一周内每天每节课的课程数量
teacher_day_lesson_courses = [[[0 for _ in range(num_lessons_per_day)] for _ in range(num_days_per_week)] for _ in range(num_teachers)]

# 定义每个教师每节课上的课程
teacher_lesson_courses = [[[set() for _ in range(num_lessons_per_day)] for _ in range(num_days_per_week)] for _ in range(num_teachers)]

# 初始化课程表
def initialize_schedule():
    for i in range(num_classes):
        for j in range(num_courses):
            class_schedules[i].append(-1)
    for i in range(num_teachers):
        for j in range(num_courses):
            teacher_schedules[i].append(-1)

# 初始化班级和教师的课程数量和课程表
def initialize_class_teacher():
    for i in range(num_classes):
        for j in range(num_days_per_week):
            class_day_courses[i][j] = 0
            for k in range(num_lessons_per_day):
                class_day_lesson_courses[i][j][k] = 0
                class_lesson_courses[i][j][k] = set()
    for i in range(num_teachers):
        for j in range(num_days_per_week):
            teacher_day_courses[i][j] = 0
            for k in range(num_lessons_per_day):
                teacher_day_lesson_courses[i][j][k] = 0
                teacher_lesson_courses[i][j][k] = set()

# 随机生成初始课程表
def random_initial_schedule():
    for i in range(num_classes):
        for j in range(num_courses):
            while True:
                teacher = random.randint(0, num_teachers-1)
                if teacher_hours[teacher] >= course_hours[j]:
                    teacher_hours[teacher] -= course_hours[j]
                    class_schedules[i][j] = teacher
                    teacher_schedules[teacher][j] = i
                    break

# 计算班级每天每节课的课程数量
def calculate_class_day_lesson_courses():
    for i in range(num_classes):
        for j in range(num_days_per_week):
            for k in range(num_lessons_per_day):
                count = 0
                for l in range(num_courses):
                    if class_schedules[i][l] != -1 and class_schedules[i][l] in class_lesson_courses[i][j][k]:
                        count += 1
                class_day_lesson_courses[i][j][k] = count

# 计算班级每天的课程数量
def calculate_class_day_courses():
    for i in range(num_classes):
        for j in range(num_days_per_week):
            count = 0
            for k in range(num_lessons_per_day):
                count += class_day_lesson_courses[i][j][k]
            class_day_courses[i][j] = count

# 计算教师每天每节课的课程数量
def calculate_teacher_day_lesson_courses():
    for i in range(num_teachers):
        for j in range(num_days_per_week):
            for k in range(num_lessons_per_day):
                count = 0
                for l in range(num_courses):
                    if teacher_schedules[i][l] != -1 and i in teacher_lesson_courses[i][j][k]:
                        count += 1
                teacher_day_lesson_courses[i][j][k] = count

# 计算教师每天的课程数量
def calculate_teacher_day_courses():
    for i in range(num_teachers):
        for j in range(num_days_per_week):
            count = 0
            for k in range(num_lessons_per_day):
                count += teacher_day_lesson_courses[i][j][k]
            teacher_day_courses[i][j] = count

# 适应度函数：计算冲突数量
def calculate_conflicts():
    conflicts = 0
    for i in range(num_classes):
        for j in range(num_days_per_week):
            for k in range(num_lessons_per_day):
                if class_day_lesson_courses[i][j][k] > 1:
                    conflicts += class_day_lesson_courses[i][j][k] - 1
    for i in range(num_teachers):
        for j in range(num_days_per_week):
            for k in range(num_lessons_per_day):
                if teacher_day_lesson_courses[i][j][k] > 1:
                    conflicts += teacher_day_lesson_courses[i][j][k] - 1
    return conflicts

# 交换两个班级的课程
def swap_courses(class1, course1, class2, course2):
    teacher1 = class_schedules[class1][course1]
    teacher2 = class_schedules[class2][course2]
    class_schedules[class1][course1] = teacher2
    class_schedules[class2][course2] = teacher1
    teacher_schedules[teacher1][course1] = class2
    teacher_schedules[teacher2][course2] = class1

# 遗传算法的主函数
def genetic_algorithm():
    population_size = 100
    generations = 1000
    mutation_rate = 0.01

    # 初始化种群
    population = []
    for _ in range(population_size):
        initialize_schedule()
        random_initial_schedule()
        population.append(class_schedules.copy())

    for generation in range(generations):
        new_population = []

        # 计算每个个体的适应度
        fitness = []
        for i in range(population_size):
            initialize_class_teacher()
            calculate_class_day_lesson_courses()
            calculate_class_day_courses()
            calculate_teacher_day_lesson_courses()
            calculate_teacher_day_courses()
            conflicts = calculate_conflicts()
            fitness.append(conflicts)

        # 选择操作：使用轮盘赌选择
        total_fitness = sum(fitness)
        probabilities = [f / total_fitness for f in fitness]
        cumulative_probabilities = [sum(probabilities[:i+1]) for i in range(population_size)]

        for _ in range(population_size // 2):
            # 选择两个个体
            individual1 = None
            individual2 = None
            while individual1 is None or individual2 is None:
                rand = random.random()
                for i in range(population_size):
                    if rand <= cumulative_probabilities[i]:
                        if individual1 is None:
                            individual1 = population[i]
                        else:
                            individual2 = population[i]
                        break

            # 交叉操作：单点交叉
            crossover_point = random.randint(1, num_courses-1)
            offspring1 = individual1[:crossover_point] + individual2[crossover_point:]
            offspring2 = individual2[:crossover_point] + individual1[crossover_point:]

            # 变异操作：随机交换两个班级的课程
            if random.random() < mutation_rate:
                class1 = random.randint(0, num_classes-1)
                class2 = random.randint(0, num_classes-1)
                course1 = random.randint(0, num_courses-1)
                course2 = random.randint(0, num_courses-1)
                swap_courses(class1, course1, class2, course2)

            new_population.append(offspring1)
            new_population.append(offspring2)

        population = new_population

    # 计算最终种群的适应度，并选择最优解
    best_fitness = float('inf')
    best_schedule = None
    for individual in population:
        initialize_class_teacher()
        calculate_class_day_lesson_courses()
        calculate_class_day_courses()
        calculate_teacher_day_lesson_courses()
        calculate_teacher_day_courses()
        conflicts = calculate_conflicts()
        if conflicts < best_fitness:
            best_fitness = conflicts
            best_schedule = individual

    return best_schedule

# 运行遗传算法并打印结果
best_schedule = genetic_algorithm()
for i in range(num_classes):
    print(f'Class {i+1} schedule:')
    for j in range(num_courses):
        teacher = best_schedule[i][j]
        print(f'Course {j+1}: Teacher {teacher+1}')

请注意，上述代码只是一个简单的排课示例，可能无法满足所有的排课需求。你可以根据自己的具体情况进行修改和扩展。