遗传算法解决排课问题详细代码

以下是一个较为详细的遗传算法解决排课问题的PYTHON代码示例，包含了遗传算法的核心逻辑和排课问题的相关约束条件。

import random

# 定义排课问题的数据
time_slots = list(range(1, 11))  # 时间段
courses = list(range(1, 21))     # 课程
rooms = list(range(1, 6))        # 教室

course_data = [
    (2, 3), (3, 4), (2, 2), (4, 4), (3, 3),
    (2, 2), (3, 3), (2, 2), (4, 4), (2, 2),
    (3, 3), (2, 2), (3, 3), (3, 3), (4, 4),
    (2, 2), (3, 3), (4, 4), (2, 2), (3, 3),
]

# 定义遗传算法的参数
POPULATION_SIZE = 100
GENERATION_LIMIT = 100
CROSSOVER_RATE = 0.8
MUTATION_RATE = 0.1
ELITIST = True

class Schedule:
    """代表一个课程表"""
    def __init__(self, gene=None):
        if gene is None:
            # 随机生成一个课程表
            gene = [[[random.randint(0, 1) for _ in rooms] for _ in courses] for _ in time_slots]
        self.gene = gene
        
    def fitness(self):
        """计算适应度"""
        # 计算每个时间段每个教室所上的课程数
        time_room_count = [[[0 for _ in rooms] for _ in courses] for _ in time_slots]
        for t in time_slots:
            for r in rooms:
                for c in courses:
                    if self.gene[t-1][r-1][c-1] == 1:
                        time_room_count[t-1][c-1][r-1] += 1
        
        # 计算每个课程所需的时间
        course_time = [course_data[c-1][0] for c in courses]
        
        # 计算每个课程所需的教室容量
        course_capacity = [course_data[c-1][1] for c in courses]
        
        # 计算课程表的适应度
        fitness = 0
        for c in courses:
            # 每个课程必须在一个时间段内上课
            if sum([time_room_count[t-1][c-1][r-1] for t in time_slots for r in rooms]) != 1:
                fitness -= 100
                
            # 每个时间段每个教室只能有一个课程
            if max([time_room_count[t-1][c-1][r-1] for c in courses for t in time_slots]) > 1:
                fitness -= 100
                
            # 每个时间段每个教室的容量不能超过规定值
            if max([time_room_count[t-1][c-1][r-1] * course_capacity[c-1] for c in courses for t in time_slots]) > 30:
                fitness -= 100
                
            # 计算每个课程所需的时间
            course_time_left = course_time[c-1]
            for t in time_slots:
                if sum([self.gene[t-1][r-1][c-1] for r in rooms]) == 1:
                    course_time_left -= 1
                    if course_time_left == 0:
                        break
            
            # 计算每个课程上课时间与所需时间的差距
            fitness -= abs(course_time_left) * 10
            
        return fitness
        
    def crossover(self, other):
        """交叉操作"""
        # 随机选择两个时间段
        t1, t2 = random.sample(time_slots, 2)
        # 随机选择一个教室
        r = random.choice(rooms)
        # 交换两个时间段中该教室的课程安排
        gene1 = self.gene[:t1-1] + [self.gene[t1-1][:r-1] + other.gene[t1-1][r-1:r] + self.gene[t1-1][r:]] + self.gene[t1:]
        gene2 = other.gene[:t1-1] + [other.gene[t1-1][:r-1] + self.gene[t1-1][r-1:r] + other.gene[t1-1][r:]] + other.gene[t1:]
        return Schedule(gene1), Schedule(gene2)
        
    def mutate(self):
        """变异操作"""
        # 随机选择一个时间段、一个教室和一个课程，将其安排变为另一种状态
        t = random.choice(time_slots)
        r = random.choice(rooms)
        c = random.choice(courses)
        self.gene[t-1][r-1][c-1] = 1 - self.gene[t-1][r-1][c-1]
        
def selection(population):
    """选择操作"""
    # 选择适应度最高的几个个体
    sorted_population = sorted(population, key=lambda x: x.fitness(), reverse=True)
    return sorted_population[:int(POPULATION_SIZE*0.3)]

def genetic_algorithm():
    """遗传算法"""
    # 初始化种群
    population = [Schedule() for _ in range(POPULATION_SIZE)]
    for i in range(GENERATION_LIMIT):
        # 选择操作
        selected_population = selection(population)
        
        # 交叉操作
        offspring_population = []
        for j in range(int(POPULATION_SIZE * CROSSOVER_RATE)):
            parent1, parent2 = random.sample(selected_population, 2)
            offspring1, offspring2 = parent1.crossover(parent2)
            offspring_population.extend([offspring1, offspring2])
        
        # 变异操作
        for j in range(int(POPULATION_SIZE * MUTATION_RATE)):
            selected = random.choice(selected_population)
            selected.mutate()
            offspring_population.append(selected)
        
        # 精英策略
        if ELITIST:
            offspring_population.append(selected_population[0])
        
        # 更新种群
        population = offspring_population
        
        # 打印当前种群中适应度最高的个体
        print("Generation:", i+1, "Best fitness:", max([p.fitness() for p in population]))
            
    return max(population, key=lambda x: x.fitness())

# 运行遗传算法求解排课问题
best_schedule = genetic_algorithm()

# 打印最优的课程表
for t in time_slots:
    print(f"Time slot {t}:")
    for r in rooms:
        courses = [c for c in range(1, 21) if best_schedule.gene[t-1][r-1][c-1] == 1]
        if len(courses) > 0:
            print(f"Room {r}: {' '.join(str(c) for c in courses)}")

在这个代码中，我们首先定义了排课问题所需的数据。然后定义了一个 `Schedule` 类，代表一个课程表，其中包含了课程表的遗传基因、计算适应度的方法、交叉和变异操作等。接着定义了遗传算法的核心逻辑，包括初始化种群、选择操作、交叉操作、变异操作和精英策略等。最后使用遗传算法求解排课问题，并打印出最优的课程表。

需要注意的是，这个代码中的约束条件只是一个简单的示例，实际情况下可能需要根据具体问题进行修改。同时，由于遗传算法的随机性，每次运行可能得到不同的结果。