代码包含教师（及其教授的科目）、科目、教学时间和时段以及教师可以教授的最大连续课程数，并根据这些输入生成时间表。
生成的最终输出不满足硬约束（例如教师不能同时教授两个课程，没有空位）。我尝试过增加对硬约束、各种突变和交叉率的惩罚，增加人口，但似乎都不起作用。我能做什么？
from PyQt5.QtWidgets import QApplication, QWidget, QVBoxLayout, QPushButton, QLabel, QLineEdit, QFormLayout, QComboBox, QTimeEdit, QSpinBox, QListWidget, QInputDialog, QErrorMessage, QGridLayout, QTableWidget, QTableWidgetItem, QMainWindow, QScrollArea
from PyQt5.QtCore import Qt
from PyQt5.QtGui import QStandardItemModel, QStandardItem
from deap import base, creator, tools
import random
from collections import defaultdict
import time
import numpy as np
class TimetableWindow(QMainWindow):
def __init__(self, parent=None):
super(TimetableWindow, self).__init__(parent)
self.setWindowTitle("Timetable")
self.setGeometry(100, 100, 800, 600)
self.scrollArea = QScrollArea(self)
self.setCentralWidget(self.scrollArea)
self.sectionWidgets = []
def updateTable(self, section, workingDays, timeSlots, timetable_dict):
tableWidget = QTableWidget()
tableWidget.setRowCount(len(workingDays))
tableWidget.setColumnCount(len(timeSlots))
tableWidget.setHorizontalHeaderLabels(timeSlots)
tableWidget.setVerticalHeaderLabels(workingDays)
for i, day in enumerate(workingDays):
for j, slot in enumerate(timeSlots):
item = QTableWidgetItem(timetable_dict[day][slot])
tableWidget.setItem(i, j, item)
self.sectionWidgets.append((section, tableWidget))
def show(self):
widget = QWidget()
layout = QVBoxLayout()
for section, tableWidget in self.sectionWidgets:
layout.addWidget(QLabel(f"Section: {section}"))
layout.addWidget(tableWidget)
widget.setLayout(layout)
self.scrollArea.setWidget(widget)
self.scrollArea.setWidgetResizable(True) # Make the widget resizable
super().show()
self.showMaximized() # Show the window maximized
class SchedulerUI(QWidget):
def __init__(self):
super().__init__()
self.timetableWindow = TimetableWindow(self)
self.initUI()
def initUI(self):
layout = QVBoxLayout()
# Create labels and fields for user input
self.sectionsLabel = QLabel("Sections:")
self.sectionsInput = QLineEdit()
self.teachersLabel = QLabel("Teachers, their Subjects and their constraints (comma separated):")
self.teachersInput = QListWidget()
self.timeSlotsLabel = QLabel("Time Slots (comma separated):")
self.timeSlotsInput = QLineEdit()
self.lunchBreakLabel = QLabel("Lunch Breaks (Start-End, comma separated):")
self.lunchBreakInput = QListWidget()
self.workingDaysLabel = QLabel("Working Days:")
self.workingDaysInput = QListWidget()
self.classDurationLabel = QLabel("Class Duration (minutes):")
self.classDurationInput = QSpinBox()
# Configure input widgets
self.workingDaysInput.addItems(["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"])
self.workingDaysInput.setSelectionMode(QListWidget.MultiSelection)
self.classDurationInput.setRange(1, 180) # Class duration between 1 and 180 minutes
# Add labels and fields to layout
layout.addWidget(self.sectionsLabel)
layout.addWidget(self.sectionsInput)
layout.addWidget(self.teachersLabel)
layout.addWidget(self.teachersInput)
layout.addWidget(self.timeSlotsLabel)
layout.addWidget(self.timeSlotsInput)
layout.addWidget(self.lunchBreakLabel)
layout.addWidget(self.lunchBreakInput)
layout.addWidget(self.workingDaysLabel)
layout.addWidget(self.workingDaysInput)
layout.addWidget(self.classDurationLabel)
layout.addWidget(self.classDurationInput)
# Create buttons for adding and removing teachers and lunch breaks
self.addTeacherButton = QPushButton("Add Teacher", self)
self.addTeacherButton.clicked.connect(self.addTeacher)
self.removeTeacherButton = QPushButton("Remove Teacher", self)
self.removeTeacherButton.clicked.connect(self.removeTeacher)
self.addLunchBreakButton = QPushButton("Add Lunch Break", self)
self.addLunchBreakButton.clicked.connect(self.addLunchBreak)
self.removeLunchBreakButton = QPushButton("Remove Lunch Break",self)
self.removeLunchBreakButton.clicked.connect(self.removeLunchBreak)
# Add buttons to layout
layout.addWidget(self.addTeacherButton)
layout.addWidget(self.removeTeacherButton)
layout.addWidget(self.addLunchBreakButton)
layout.addWidget(self.removeLunchBreakButton)
# Create a button for submitting the form
self.submitButton = QPushButton("Submit", self)
self.submitButton.clicked.connect(self.submitForm)
# Add button to layout
layout.addWidget(self.submitButton)
# Set the layout for the widget
self.setLayout(layout)
def addTeacher(self):
teacher, ok = QInputDialog.getText(self, "Add Teacher", "Enter teacher's name, their subjects, max classes per week and max consecutive classes (comma separated):\nFormat: TeacherName,Subject1,Subject2,...,MaxClassesPerWeek,MaxConsecutiveClasses")
if ok and teacher:
self.teachersInput.addItem(teacher)
def removeTeacher(self):
for item in self.teachersInput.selectedItems():
self.teachersInput.takeItem(self.teachersInput.row(item))
def addLunchBreak(self):
lunchBreak, ok = QInputDialog.getText(self, "Add Lunch Break", "Enter lunch break start and end time (comma separated):\nFormat: Start-End")
if ok and lunchBreak:
self.lunchBreakInput.addItem(lunchBreak)
def removeLunchBreak(self):
for item in self.lunchBreakInput.selectedItems():
self.lunchBreakInput.takeItem(self.lunchBreakInput.row(item))
def submitForm(self):
# Get user input from form
sections = self.sectionsInput.text().split(',')
teachers = [self.teachersInput.item(i).text().split(",") for i in range(self.teachersInput.count())]
timeSlots = self.timeSlotsInput.text().split(',')
lunchBreaks = [self.lunchBreakInput.item(i).text().split('-') for i in range(self.lunchBreakInput.count())]
workingDays = [self.workingDaysInput.item(i).text() for i in range(self.workingDaysInput.count()) if self.workingDaysInput.item(i).isSelected()]
classDuration = self.classDurationInput.value()
# Run the genetic algorithm for all sections
self.runGeneticAlgorithm(sections, teachers, timeSlots, workingDays, lunchBreaks, classDuration)
self.timetableWindow.show()
def generate_class(self, sections, teachers, time_slots, working_days, teacher_slot_classes, subject_section_classes):
while True:
section = random.choice(sections)
teacher = random.choice(teachers)
subject = random.choice(teacher[1:-2])
time_slot = random.choice(time_slots)
working_day = random.choice(working_days)
if teacher_slot_classes[(teacher[0], time_slot)] < int(teacher[-2]) and subject_section_classes[(subject, time_slot, working_day)] == 0:
return (teacher[0], subject, time_slot, working_day, section)
def mutate(self, individual, sections, teachers, time_slots, working_days, teacher_slot_classes, subject_section_classes):
index = random.randrange(len(individual))
individual[index] = self.generate_class(sections, teachers, time_slots, working_days, teacher_slot_classes, subject_section_classes)
def repair(self, individual, sections, teachers, time_slots, working_days, teacher_slot_classes, subject_section_classes):
timetable_dict = defaultdict(lambda: defaultdict(str))
for class_info in individual:
teacher, subject, slot, day, section = class_info
timetable_dict[day][slot] = f"{subject} ({teacher})"
for day in working_days:
for slot in time_slots:
if timetable_dict[day][slot] == "":
individual.append(self.generate_class(sections, teachers, time_slots, working_days, teacher_slot_classes, subject_section_classes))
def runGeneticAlgorithm(self, sections, teachers, timeSlots, workingDays, lunchBreaks, classDuration):
# Define the fitness function
def fitness(individual, lunchBreaks, teachers):
penalty = 0
# Constraint: Class should not be allotted during lunch break
for class_info in individual:
teacher, subject, slot, day, section = class_info
for lunchBreak in lunchBreaks:
start, end = lunchBreak
if start <= slot <= end:
penalty += 100
# Constraint: More classes per week than a teacher can handle should not be allotted
teacher_classes = defaultdict(int)
for class_info in individual:
teacher, subject, slot, day, section = class_info
teacher_classes[teacher] += 1
for teacher in teachers:
if teacher_classes[teacher[0]] > int(teacher[-2]):
penalty += 1
# Constraint: More consecutive classes than a teacher can handle should not be allotted
teacher_consecutive_classes = defaultdict(int)
for class_info in sorted(individual, key=lambda x: (x[0], x[3], x[2])): # Sort by teacher, day, and slot
teacher, subject, slot, day, section = class_info
if teacher_consecutive_classes[teacher] > 0 and teacher_consecutive_classes[teacher] != day:
teacher_consecutive_classes[teacher] = 0
teacher_consecutive_classes[teacher] += 1
max_consecutive_classes = next(int(val[-1]) for val in teachers if val[0] == teacher)
if teacher_consecutive_classes[teacher] > max_consecutive_classes:
penalty += 1
# Constraint: Teacher should not teach more than one section at the same time
teacher_sections = defaultdict(lambda: defaultdict(set))
for class_info in individual:
teacher, subject, slot, day, section = class_info
teacher_sections[teacher][day, slot].add(section)
for teacher, sections in teacher_sections.items():
for _, section_set in sections.items():
if len(section_set) > 1:
penalty += 100 # High penalty for hard constraint
# Constraint: There should be no empty slots (this is a hard constraint)
timetable_dict = defaultdict(lambda: defaultdict(str))
for class_info in individual:
teacher, subject, slot, day, section = class_info
timetable_dict[day][slot] = f"{subject} ({teacher})"
for day in workingDays:
for slot in timeSlots:
if timetable_dict[day][slot] == "":
penalty += 100 # High penalty for hard constraint
# Constraint: There should be a balanced number of classes across different days
day_classes = defaultdict(int)
for class_info in individual:
teacher, subject, slot, day, section = class_info
day_classes[day] += 1
average_classes = sum(day_classes.values()) / len(workingDays)
for day in workingDays:
if day_classes[day] > average_classes:
penalty += 1
return penalty,
# Define the individual and population
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register("attr_class", self.generate_class, sections=sections, teachers=teachers, time_slots=timeSlots, working_days=workingDays, teacher_slot_classes=defaultdict(int), subject_section_classes=defaultdict(int))
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_class, n=len(timeSlots)*len(workingDays)*len(sections))
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
# Define the genetic operators
toolbox.register("evaluate", fitness, lunchBreaks=lunchBreaks, teachers=teachers)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", self.mutate, sections=sections, teachers=teachers, time_slots=timeSlots, working_days=workingDays, teacher_slot_classes=defaultdict(int), subject_section_classes=defaultdict(int))
toolbox.register("select", tools.selTournament, tournsize=3)
# Initialize the population and evolve it
pop = toolbox.population(n=2000) # Increased population size
fitnesses = list(map(toolbox.evaluate, pop))
for ind, fit in zip(pop, fitnesses):
ind.fitness.values = fit
# Performance measures
start_time = time.time()
fitness_scores = []
diversity_scores = []
# Adaptive parameters
mutation_rate = 0.3 # Increase the mutation rate
crossover_rate = 0.8 # Increase the crossover rate
for g in range(2000): # Increased number of generations
# Adapt mutation and crossover rates
fitness_values = [ind.fitness.values[0] for ind in pop]
fitness_variance = np.var(fitness_values)
fitness_mean = np.mean(fitness_values)
mutation_rate = min(1, max(0.01, mutation_rate + (fitness_variance / (fitness_mean ** 2))))
crossover_rate = min(1, max(0.01, crossover_rate + (fitness_mean / (fitness_variance ** 2))))
offspring = toolbox.select(pop, len(pop))
offspring = list(map(toolbox.clone, offspring))
for child1, child2 in zip(offspring[::2], offspring[1::2]):
if random.random() < crossover_rate:
toolbox.mate(child1, child2)
del child1.fitness.values
del child2.fitness.values
for mutant in offspring:
if random.random() < mutation_rate:
toolbox.mutate(mutant)
del mutant.fitness.values
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
# Elitism: Preserve the best individuals
elite = tools.selBest(pop, 1)
offspring = tools.selBest(offspring, len(offspring) - 1)
offspring.append(elite[0])
# Repair function: Fill in empty slots
for ind in offspring:
self.repair(ind, sections, teachers, timeSlots, workingDays, defaultdict(int), defaultdict(int))
pop[:] = offspring
# Track fitness scores and diversity
fitness_scores.append(min(ind.fitness.values[0] for ind in pop))
diversity_scores.append(np.var([ind.fitness.values[0] for ind in pop]))
execution_time = time.time() - start_time
# Get the best individual in the population
best_ind = tools.selBest(pop, 1)[0]
# Create a dictionary to store the timetable
timetable_dict = defaultdict(lambda: defaultdict(lambda: defaultdict(str)))
for class_info in best_ind:
teacher, subject, slot, day, section = class_info
timetable_dict[section][day][slot] = f"{subject} ({teacher})"
# Add lunch breaks to the timetable
for lunchBreak in lunchBreaks:
start, end = lunchBreak
for day in workingDays:
for slot in timeSlots:
if start <= slot <= end:
timetable_dict[section][day][slot] = "Lunch Break"
# Update the timetable widget
for section in sections:
self.timetableWindow.updateTable(section, workingDays, timeSlots, timetable_dict[section])
# Print performance measures
print(f"Fitness Score: {best_ind.fitness.values[0]}")
print(f"Execution Time: {execution_time} seconds")
print(f"Convergence: {fitness_scores}")
print(f"Diversity: {diversity_scores}")
def main():
app = QApplication([])
ui = SchedulerUI()
ui.show()
app.exec_()
if __name__ == "__main__":
main()