abhi-bit-2/Genetic_Algorithm
0
1"""2Simplified Genetic Algorithm for Timetable Generation3 4This module implements a genetic algorithm to generate optimal timetables5for educational institutions. It handles multiple branches, teachers, courses,6and rooms while ensuring each professor has the required number of classes7for each course they teach.8 9Author: Timetable Generator Team10Version: 1.111"""12import cProfile13# Importing all the libraries we need for our program14import random # for generating random numbers15import timeit16import copy # for making deep copies of objects17import time # to measure how long our algorithm takes18import heapq # this helps us with priority queues19from db_operations import fetch_data_from_db, insert_timetable_into_db, get_course_classes20import sqlite3 # for database operations21from tabulate import tabulate # makes our tables look nice when printed22from collections import defaultdict, Counter # special dictionaries that are helpful23 24# TODO: Learn about more efficient data structures for scheduling problems25 26# Constants for our timetable27DAYS = 5 # Monday to Friday28SLOTS_PER_DAY = 9 # 9 time slots per day29LUNCH_SLOT = 4 # Lunch break (5th slot)30POPULATION_SIZE = 30 # Population size for genetic algorithm31ELITE_SIZE = 6 # Top schedules to keep unchanged32TOURNAMENT_SIZE = 4 # Number of schedules to compete in tournament selection33MUTATION_RATE = 0.25 # Probability of mutation34CROSSOVER_RATE = 0.8 # Probability of crossover35MAX_CLASSES_PER_SLOT = 3 # Maximum number of classes in a single time slot36 37# Preferred time slots - morning slots (0-3) are preferred for core subjects38# This encourages important classes to be scheduled in the morning39PREFERRED_MORNING_SLOTS = [0, 1, 2, 3] # First 4 slots of the day40 41# List of core courses that should preferably be scheduled in the morning42# These are typically more demanding subjects that benefit from morning scheduling43CORE_COURSES = ["CSE101", "ECE101", "ME101", "CE101", "EEE101"]44 45# Class to store class data46class ClassSlot:47 def __init__(self, course_code, course_name, teacher, room, branch, day, slot):48 # Store all the information about a class49 self.course_code = course_code50 self.course_name = course_name51 self.teacher = teacher52 self.room = room53 self.branch = branch54 self.day = day55 self.slot = slot56 # print(f"Created new class: {course_code} with {teacher}")57 58 def __str__(self):59 # This helps us print the class in a readable format60 return f"{self.course_code}: {self.teacher} in {self.room} ({self.branch})"61 62 def copy(self):63 return ClassSlot(64 self.course_code,65 self.course_name,66 self.teacher,67 self.room,68 self.branch,69 self.day,70 self.slot71 )72 73 74 75def copy_schedule(schedule):76 if isinstance(schedule, dict):77 return {78 key: [cls.copy() for cls in class_list]79 for key, class_list in schedule.items()80 }81 elif isinstance(schedule, list):82 return [cls.copy() for cls in schedule]83 elif hasattr(schedule, 'copy'):84 return schedule.copy()85 else:86 raise TypeError(f"Unsupported schedule format: {type(schedule)}")87 88 89 90def create_empty_schedule():91 """Create an empty schedule with None values."""92 # This creates a 2D array filled with None values93 # First we make DAYS number of rows94 empty_schedule = []95 for i in range(DAYS):96 # Then for each day, we add SLOTS_PER_DAY number of None values97 day_slots = []98 for j in range(SLOTS_PER_DAY):99 day_slots.append(None)100 empty_schedule.append(day_slots)101 # return [[None for _ in range(SLOTS_PER_DAY)] for _ in range(DAYS)]102 return empty_schedule103 104def check_room_conflicts(schedule):105 """Check for room conflicts in the schedule.106 107 This function identifies instances where the same room is assigned to multiple108 classes at the same time. It's optimized for performance using sets and109 handles all possible schedule data formats.110 111 Args:112 schedule: The timetable schedule to check113 114 Returns:115 A list of conflicts (day, slot, room) or an empty list if no conflicts116 """117 # Handle None schedule case118 if schedule is None:119 return []120 121 conflicts = []122 123 # Pre-allocate a 2D array to track room usage across all days and slots124 # This is more efficient than creating new sets in each iteration125 room_usage = [[set() for _ in range(SLOTS_PER_DAY)] for _ in range(DAYS)]126 127 # First pass: collect all room usage128 for day in range(DAYS):129 for slot in range(SLOTS_PER_DAY):130 # Skip lunch slot131 if slot == LUNCH_SLOT:132 continue133 134 # Skip empty slots135 if schedule[day][slot] is None:136 continue137 138 # Handle multiple classes in the same slot139 classes = schedule[day][slot] if isinstance(schedule[day][slot], list) else [schedule[day][slot]]140 141 for class_data in classes:142 if class_data is None:143 continue144 # Extract room information, handling both object and tuple formats145 room = class_data.room if hasattr(class_data, 'room') else class_data[3]146 # Check for conflict and add to room usage147 if room in room_usage[day][slot]:148 conflicts.append((day, slot, room))149 room_usage[day][slot].add(room)150 return conflicts151def get_course_class_requirements():152 """Get the number of classes required for each course.153 Returns a dictionary mapping course_code to the number of classes required.154 """155 try:156 # Get num course class from the database157 course_classes = get_course_classes()158 # Create a dictionary159 class_requirements = {}160 # Loop through each course and store its requirements161 for course_code, num_classes, _, _ in course_classes:162 num_classes_int = int(num_classes)163 # Store the requirement in our dictionary164 class_requirements[course_code] = num_classes_int165 # Print out the requirement for debugging166 # print(f"Course {course_code} requires {num_classes} classes")167 return class_requirements168 except Exception as e:169 # If there's an error, print it and use a default value170 print(f"Error getting course classes: {e}")171 172 # If there's an error, use a default of 1 class per course173 return defaultdict(lambda: 1)174 175def fix_overassigned_classes(schedule):176 """Fix a schedule by removing extra classes for teachers who have more than required.177 Optimized using a heap (priority queue) to efficiently process the most overassigned classes first.178 """179 fixed_schedule = copy_schedule(schedule)180 class_requirements = get_course_class_requirements()181 teacher_count = count_course_teacher_classes(fixed_schedule)182 183 # Use a heap (priority queue) to efficiently track the most overassigned classes184 overassigned_heap = []185 186 for (course_code, teacher), count in teacher_count.items():187 required = class_requirements.get(course_code, 1)188 if count > required:189 # Negative extra for max-heap behavior (Python's heapq is a min-heap)190 extra = count - required191 heapq.heappush(overassigned_heap, (-extra, course_code, teacher, count, required))192 193 if not overassigned_heap:194 return fixed_schedule195 196 # Process overassigned classes in order of most overassigned first197 while overassigned_heap:198 neg_extra, course_code, teacher, count, required = heapq.heappop(overassigned_heap)199 extra = -neg_extra # Convert back to positive200 201 # Find all slots with this course and teacher202 course_slots = []203 for day in range(DAYS):204 for slot in range(SLOTS_PER_DAY):205 if slot == LUNCH_SLOT or fixed_schedule[day][slot] is None:206 continue207 208 if isinstance(fixed_schedule[day][slot], list):209 for i, class_data in enumerate(fixed_schedule[day][slot]):210 if (class_data is not None and211 class_data.course_code == course_code and212 class_data.teacher == teacher):213 course_slots.append((day, slot, i, class_data))214 elif (fixed_schedule[day][slot].course_code == course_code and215 fixed_schedule[day][slot].teacher == teacher):216 course_slots.append((day, slot, None, fixed_schedule[day][slot]))217 218 # Shuffle to randomize which classes we remove219 random.shuffle(course_slots)220 221 # Remove the extra classes222 removed = 0223 for day, slot, idx, _ in course_slots:224 if removed >= extra:225 break226 227 if idx is None:228 # Single class in this slot229 fixed_schedule[day][slot] = None230 else:231 # Multiple classes in this slot232 fixed_schedule[day][slot].pop(idx)233 if not fixed_schedule[day][slot]:234 fixed_schedule[day][slot] = None235 elif len(fixed_schedule[day][slot]) == 1:236 fixed_schedule[day][slot] = fixed_schedule[day][slot][0]237 238 removed += 1239 240 return fixed_schedule241start_time = timeit.default_timer()242 243def fix_class_assignments(schedule, courses, teachers, rooms):244 """Fix a schedule by removing extra classes and adding missing classes."""245 # First, fix over-assigned classes246 fixed_schedule = fix_overassigned_classes(schedule)247 class_requirements = get_course_class_requirements()248 course_teacher_counts = count_course_teacher_classes(fixed_schedule)249 250 # Use a heap to efficiently track the most underassigned classes251 underassigned_heap = []252 253 # Find teacher-course combinations with too few classes254 for (course_code, teacher), count in course_teacher_counts.items():255 required = class_requirements.get(course_code, 1)256 if count < required:257 # Negative missing for max-heap behavior (Python's heapq is a min-heap)258 missing = required - count259 heapq.heappush(underassigned_heap, (-missing, course_code, teacher, count, required))260 261 # Also check for course-teacher combinations that should exist but don't262 try:263 with sqlite3.connect("timetable.db") as conn:264 cursor = conn.cursor()265 cursor.execute("""266 SELECT c.course_code, c.course_name, b.branch_name, t.teacher_name267 FROM branch_teacher_courses btc268 JOIN branches b ON btc.branch_id = b.branch_id269 JOIN teachers t ON btc.teacher_id = t.teacher_id270 JOIN courses c ON btc.course_code = c.course_code271 """)272 for course_code, course_name, branch, teacher in cursor.fetchall():273 if course_code in class_requirements:274 required = class_requirements[course_code]275 actual = course_teacher_counts.get((course_code, teacher), 0)276 if actual < required:277 # Check if this combination is already in the heap278 key = (course_code, teacher)279 if not any(item[1:3] == key for item in underassigned_heap):280 missing = required - actual281 heapq.heappush(underassigned_heap, (-missing, course_code, teacher, actual, required))282 except sqlite3.Error:283 pass284 285 if not underassigned_heap:286 return fixed_schedule287 288 # Track which slots are used for each teacher, room, and branch289 teacher_slots = defaultdict(set) # teacher -> set of (day, slot)290 room_slots = defaultdict(set) # room -> set of (day, slot)291 branch_slots = defaultdict(set) # branch -> set of (day, slot)292 293 # Fill these tracking structures based on the current schedule294 for day in range(DAYS):295 for slot in range(SLOTS_PER_DAY):296 if slot == LUNCH_SLOT or fixed_schedule[day][slot] is None:297 continue298 299 classes = fixed_schedule[day][slot] if isinstance(fixed_schedule[day][slot], list) else [fixed_schedule[day][slot]]300 301 for class_data in classes:302 if class_data is None:303 continue304 305 if hasattr(class_data, 'teacher'):306 teacher = class_data.teacher307 room = class_data.room308 branch = class_data.branch309 else:310 teacher = class_data[2]311 room = class_data[3]312 branch = class_data[4]313 314 teacher_slots[teacher].add((day, slot))315 room_slots[room].add((day, slot))316 branch_slots[branch].add((day, slot))317 318 # Process underassigned classes in order of most underassigned first319 while underassigned_heap:320 neg_missing, course_code, teacher, actual, required = heapq.heappop(underassigned_heap)321 missing = -neg_missing # Convert back to positive322 323 # Find the course details324 course_details = None325 for c in courses:326 if c[0] == course_code:327 course_details = c328 break329 330 if not course_details:331 continue332 333 _, branch, course_name = course_details334 335 # Try to add the missing classes336 for _ in range(missing):337 # Try multiple slots to find one that works338 success = False339 for attempt in range(30):340 day = random.randint(0, DAYS-1)341 slot = random.randint(0, SLOTS_PER_DAY-1)342 343 if slot == LUNCH_SLOT:344 continue345 346 # Skip if teacher or branch already has a class in this slot347 if (day, slot) in teacher_slots[teacher] or (day, slot) in branch_slots[branch]:348 continue349 350 # Check if slot is available351 if fixed_schedule[day][slot] is not None:352 if isinstance(fixed_schedule[day][slot], list) and len(fixed_schedule[day][slot]) >= MAX_CLASSES_PER_SLOT:353 continue # Slot is full354 355 # Find available rooms not already used in this slot356 available_rooms = [r for r in rooms if (day, slot) not in room_slots[r]]357 358 if not available_rooms:359 continue360 361 # Pick a room and create a class slot362 room = random.choice(available_rooms)363 class_slot = ClassSlot(course_code, course_name, teacher, room, branch, day, slot)364 365 # Add to schedule366 if fixed_schedule[day][slot] is None:367 fixed_schedule[day][slot] = class_slot368 elif isinstance(fixed_schedule[day][slot], list):369 if len(fixed_schedule[day][slot]) < MAX_CLASSES_PER_SLOT:370 fixed_schedule[day][slot].append(class_slot)371 else:372 continue # Slot is full373 else:374 # Convert single class to list375 fixed_schedule[day][slot] = [fixed_schedule[day][slot], class_slot]376 377 # Update tracking378 teacher_slots[teacher].add((day, slot))379 room_slots[room].add((day, slot))380 branch_slots[branch].add((day, slot))381 success = True382 break # Successfully added a class383 384 if not success:385 # If we couldn't add this class after trying all slots, move on386 break387 388 return fixed_schedule389print(timeit.default_timer() - start_time)390 391def get_valid_assignment(schedule, courses, teachers, rooms, day, slot, branch, course_teacher_counts=None, class_requirements=None, specific_course=None, specific_teacher=None):392 """Get a valid course, teacher, and room assignment for a given slot.393 Returns a ClassSlot object or None if no valid assignment is possible394 """395 # Skip lunch slot396 if slot == LUNCH_SLOT:397 return None398 399 # Check if the slot already has the maximum number of classes400 if schedule[day][slot] is not None:401 if isinstance(schedule[day][slot], list) and len(schedule[day][slot]) >= MAX_CLASSES_PER_SLOT:402 return None403 404 # Get all entities already in this slot405 slot_courses = set()406 slot_teachers = set()407 slot_rooms = set()408 slot_branches = set()409 410 if schedule[day][slot] is not None:411 classes = schedule[day][slot] if isinstance(schedule[day][slot], list) else [schedule[day][slot]]412 for class_data in classes:413 if class_data is None:414 continue415 416 if hasattr(class_data, 'course_code'):417 slot_courses.add(class_data.course_code)418 slot_teachers.add(class_data.teacher)419 slot_rooms.add(class_data.room)420 slot_branches.add(class_data.branch)421 else:422 slot_courses.add(class_data[0])423 slot_teachers.add(class_data[2])424 slot_rooms.add(class_data[3])425 slot_branches.add(class_data[4])426 427 # If branch is already in this slot, we can't add another course from the same branch428 if branch in slot_branches:429 return None430 431 # Filter courses for this branch432 if specific_course:433 # If a specific course is requested, only consider that course434 branch_courses = [c for c in courses if c[1] == branch and c[0] == specific_course]435 else:436 branch_courses = [c for c in courses if c[1] == branch and c[0] not in slot_courses]437 438 if not branch_courses:439 return None440 441 # If we have course-teacher counts and class requirements, prioritize courses that need more classes442 if course_teacher_counts and class_requirements and not specific_course:443 # Sort courses by how many more classes they need444 branch_courses.sort(key=lambda c: class_requirements.get(c[0], 1) -445 sum(count for (course, _), count in course_teacher_counts.items() if course == c[0]),446 reverse=True)447 else:448 # Shuffle for randomness449 random.shuffle(branch_courses)450 451 # Try each course452 for course in branch_courses:453 course_code, branch_name, course_name = course454 455 # Find teachers who can teach this course and are not already in this slot456 if specific_teacher:457 # If a specific teacher is requested, only consider that teacher458 available_teachers = [specific_teacher] if specific_teacher not in slot_teachers else []459 # Verify this teacher can teach this course460 teacher_can_teach = False461 for teacher_data in teachers:462 teacher_name, teacher_course_code, teacher_branch = teacher_data463 if teacher_name == specific_teacher and teacher_course_code == course_code and teacher_branch == branch_name:464 teacher_can_teach = True465 break466 if not teacher_can_teach:467 available_teachers = []468 else:469 available_teachers = []470 for teacher_data in teachers:471 teacher_name, teacher_course_code, teacher_branch = teacher_data472 if teacher_branch == branch_name and teacher_course_code == course_code and teacher_name not in slot_teachers:473 available_teachers.append(teacher_name)474 475 if not available_teachers:476 continue477 478 # If we have course-teacher counts and class requirements, prioritize teachers who need more classes479 if course_teacher_counts and class_requirements and not specific_teacher:480 # Sort teachers by how many more classes they need to teach for this course481 available_teachers.sort(key=lambda t: class_requirements.get(course_code, 1) -482 course_teacher_counts.get((course_code, t), 0),483 reverse=True)484 else:485 # Shuffle for randomness486 random.shuffle(available_teachers)487 488 # Try each teacher489 for teacher in available_teachers:490 # Find available rooms not already in this slot491 available_rooms = [r for r in rooms if r not in slot_rooms]492 493 if not available_rooms:494 continue495 496 # Select a random room497 room = random.choice(available_rooms)498 499 # Create a class slot500 return ClassSlot(course_code, course_name, teacher, room, branch_name, day, slot)501 502 return None503 504 505def create_random_schedule(courses, teachers, rooms):506 """Create a timetable with constraint-based scheduling to ensure professors have correct class counts."""507 schedule = create_empty_schedule()508 509 # Get all branches510 branches = set()511 for _, branch, _ in courses:512 branches.add(branch)513 514 # Get course class requirements515 class_requirements = get_course_class_requirements()516 517 # Track which slots are used for each teacher, room, and branch518 teacher_slots = defaultdict(set) # teacher -> set of (day, slot)519 room_slots = defaultdict(set) # room -> set of (day, slot)520 branch_slots = defaultdict(set) # branch -> set of (day, slot)521 522 # Track how many classes have been assigned for each course-teacher pair523 course_counts = defaultdict(int) # course_code -> count524 course_teacher_counts = defaultdict(int) # (course_code, teacher) -> count525 526 # Create a list of all course-teacher combinations that need to be scheduled527 combinations = []528 529 # First, gather all valid course-teacher combinations from the database530 with sqlite3.connect("timetable.db") as conn:531 cursor = conn.cursor()532 cursor.execute("""533 SELECT c.course_code, c.course_name, b.branch_name, t.teacher_name534 FROM branch_teacher_courses btc535 JOIN branches b ON btc.branch_id = b.branch_id536 JOIN teachers t ON btc.teacher_id = t.teacher_id537 JOIN courses c ON btc.course_code = c.course_code538 """)539 db_mappings = cursor.fetchall()540 541 # Add all valid combinations to our list542 for course_code, course_name, branch, teacher in db_mappings:543 if course_code in class_requirements:544 required = class_requirements[course_code]545 combinations.append((course_code, course_name, branch, teacher, required))546 547 # If we couldn't get combinations from the database, create them from the courses and teachers548 if not combinations:549 print("Warning: No course-teacher mappings found in database. Creating from available data.")550 for course_code, required in class_requirements.items():551 # Find all courses with this code552 course_options = [c for c in courses if c[0] == course_code]553 if not course_options:554 continue555 556 # For each branch that offers this course557 for course in course_options:558 branch = course[1]559 course_name = course[2]560 561 # Find teachers who can teach this course in this branch562 course_teachers = []563 for teacher_data in teachers:564 teacher_name, teacher_course, teacher_branch = teacher_data565 if teacher_course == course_code and teacher_branch == branch:566 course_teachers.append(teacher_name)567 568 if not course_teachers:569 continue570 571 # Add all valid combinations to our list572 for teacher in course_teachers:573 combinations.append((course_code, course_name, branch, teacher, required))574 575 # Shuffle combinations for diversity576 random.shuffle(combinations)577 578 print(f"Scheduling {len(combinations)} course-teacher combinations...")579 580 # First pass: Schedule exactly one class for each course-teacher combination581 for course_code, course_name, branch, teacher, required in combinations:582 # Skip if this teacher already has enough classes for this course583 if course_teacher_counts[(course_code, teacher)] >= required:584 continue585 586 # Find the best days and slots for this class587 day_slot_scores = []588 589 for day in range(DAYS):590 for slot in range(SLOTS_PER_DAY):591 if slot == LUNCH_SLOT:592 continue593 594 # Skip if teacher or branch already has a class in this slot595 if (day, slot) in teacher_slots[teacher] or (day, slot) in branch_slots[branch]:596 continue597 598 # Check if slot is available599 if schedule[day][slot] is not None:600 if isinstance(schedule[day][slot], list) and len(schedule[day][slot]) >= MAX_CLASSES_PER_SLOT:601 continue # Slot is full602 603 # Find available rooms not already used in this slot604 available_rooms = []605 for room in rooms:606 if (day, slot) not in room_slots[room]:607 available_rooms.append(room)608 609 if not available_rooms:610 continue611 612 # Calculate a score for this day/slot based on:613 # 1. How many classes are already scheduled at this time614 # 2. How many classes the teacher already has on this day615 616 # Count classes in this slot617 slot_count = 0618 if schedule[day][slot] is not None:619 slot_count = 1 if not isinstance(schedule[day][slot], list) else len(schedule[day][slot])620 621 # Count teacher's classes on this day622 teacher_day_count = sum(1 for d, s in teacher_slots[teacher] if d == day)623 624 # Calculate score (lower is better)625 score = slot_count * 3 + teacher_day_count * 2626 627 # Add a small random factor for diversity628 score += random.random()629 630 # Add to our list of possibilities631 day_slot_scores.append((day, slot, score, available_rooms))632 633 # Sort by score (ascending)634 day_slot_scores.sort(key=lambda x: x[2])635 636 # Try to schedule a class637 for day, slot, _, available_rooms in day_slot_scores:638 # Pick a room639 room = random.choice(available_rooms)640 641 # Create a class slot642 class_slot = ClassSlot(course_code, course_name, teacher, room, branch, day, slot)643 644 # Add to schedule645 if schedule[day][slot] is None:646 schedule[day][slot] = class_slot647 elif isinstance(schedule[day][slot], list):648 if len(schedule[day][slot]) < MAX_CLASSES_PER_SLOT:649 schedule[day][slot].append(class_slot)650 else:651 continue # Slot is full652 else:653 # Convert single class to list654 schedule[day][slot] = [schedule[day][slot], class_slot]655 656 # Update tracking657 teacher_slots[teacher].add((day, slot))658 room_slots[room].add((day, slot))659 branch_slots[branch].add((day, slot))660 course_counts[course_code] += 1661 course_teacher_counts[(course_code, teacher)] += 1662 663 # Successfully scheduled a class664 break665 666 # Verify all course-teacher combinations have the required number of classes667 missing_combinations = []668 for course_code, course_name, branch, teacher, required in combinations:669 actual = course_teacher_counts[(course_code, teacher)]670 if actual < required:671 missing_combinations.append((course_code, course_name, branch, teacher, required, actual))672 673 # Second pass: Try to fix any missing classes674 if missing_combinations:675 print(f"Fixing {len(missing_combinations)} missing course-teacher combinations...")676 677 for course_code, course_name, branch, teacher, required, actual in missing_combinations:678 # Calculate how many more classes we need679 needed = required - actual680 681 # Try to schedule the needed classes682 for _ in range(needed):683 # Try multiple slots to find one that works684 for attempt in range(30): # Try up to 30 different slots685 day = random.randint(0, DAYS-1)686 slot = random.randint(0, SLOTS_PER_DAY-1)687 688 if slot == LUNCH_SLOT:689 continue690 691 # Skip if teacher already has a class in this slot692 if (day, slot) in teacher_slots[teacher]:693 continue694 695 # Skip if branch already has a class in this slot696 if (day, slot) in branch_slots[branch]:697 continue698 699 # Check if slot is available700 if schedule[day][slot] is not None:701 if isinstance(schedule[day][slot], list) and len(schedule[day][slot]) >= MAX_CLASSES_PER_SLOT:702 continue # Slot is full703 704 # Find available rooms not already used in this slot705 available_rooms = []706 for room in rooms:707 if (day, slot) not in room_slots[room]:708 available_rooms.append(room)709 710 if not available_rooms:711 continue712 713 # Pick a room714 room = random.choice(available_rooms)715 716 # Create a class slot717 class_slot = ClassSlot(course_code, course_name, teacher, room, branch, day, slot)718 719 # Add to schedule720 if schedule[day][slot] is None:721 schedule[day][slot] = class_slot722 elif isinstance(schedule[day][slot], list):723 if len(schedule[day][slot]) < MAX_CLASSES_PER_SLOT:724 schedule[day][slot].append(class_slot)725 else:726 continue # Slot is full727 else:728 # Convert single class to list729 schedule[day][slot] = [schedule[day][slot], class_slot]730 731 # Update tracking732 teacher_slots[teacher].add((day, slot))733 room_slots[room].add((day, slot))734 branch_slots[branch].add((day, slot))735 course_counts[course_code] += 1736 course_teacher_counts[(course_code, teacher)] += 1737 738 # Successfully scheduled a) > 0 class739 break740 741 # Final verification742 all_correct = True743 for course_code, course_name, branch, teacher, required in combinations:744 actual = course_teacher_counts[(course_code, teacher)]745 if actual != required:746 all_correct = False747 print(f"Warning: {teacher} teaching {course_code} has {actual} classes instead of {required}")748 749 if all_correct:750 print("All course-teacher combinations have the correct number of classes!")751 752 return schedule753 754def tournament_selection(population):755 """Select a schedule using tournament selection.756 757 Tournament selection works by randomly selecting a small group of schedules758 and then picking the best one from that group.759 """760 # First, let's remove any None values from the population761 valid_population = []762 for p in population:763 if p is not None:764 valid_population.append(p)765 # Check if we have enough valid schedules for a tournament766 if len(valid_population) < TOURNAMENT_SIZE:767 # Not enough schedules for a tournament768 if len(valid_population) > 0:769 # If we have at least one valid schedule, return a random one770 random_index = random.randint(0, len(valid_population) - 1)771 return valid_population[random_index]772 else:773 # If we have no valid schedules, return None774 return None # This will be handled by the crossover function775 776 # Create a tournament by randomly selecting TOURNAMENT_SIZE schedules777 tournament = random.sample(valid_population, TOURNAMENT_SIZE)778 779 # Find the schedule with the highest fitness in the tournament780 best_schedule = tournament[0] # Start with the first schedule781 best_fitness_value = fitness(best_schedule)782 783 # Loop through the rest of the schedules to find the best one784 for i in range(1, len(tournament)):785 current_fitness = fitness(tournament[i])786 if current_fitness > best_fitness_value:787 best_schedule = tournament[i]788 best_fitness_value = current_fitness789 790 # print(f"DEBUG: Selected schedule with fitness {best_fitness_value}") # Helped track selection791 792 # Return the best schedule from the tournament793 return best_schedule794 795def crossover(p1, p2, courses, teachers, rooms):796 """Create a child schedule by intelligently combining two parent schedules."""797 798 if p1 is None or p2 is None:799 return create_random_schedule(courses, teachers, rooms)800 801 child = create_empty_schedule()802 803 # Track current course-teacher assignment counts804 course_teacher_counts = defaultdict(int)805 class_requirements = get_course_class_requirements()806 807 for day in range(DAYS):808 for slot in range(SLOTS_PER_DAY):809 if slot == LUNCH_SLOT:810 continue811 812 slot1 = p1[day][slot]813 slot2 = p2[day][slot]814 815 # Decide which parent's slot is better816 def score_slot(slot_data):817 if slot_data is None:818 return 0819 if not isinstance(slot_data, list):820 slot_data = [slot_data]821 score = 0822 for cls in slot_data:823 key = (cls.course_code, cls.teacher)824 required = class_requirements.get(cls.course_code, 1)825 current = course_teacher_counts[key]826 if current < required:827 score += 1 # Favor classes that are still under-assigned828 return score829 830 score1 = score_slot(slot1)831 score2 = score_slot(slot2)832 833 # Choose the slot with the better score834 selected_slot = slot1 if score1 > score2 else slot2835 836 if selected_slot is not None:837 selected_copy = copy_schedule(selected_slot)838 child[day][slot] = selected_copy839 840 # Update counts841 if not isinstance(selected_copy, list):842 selected_copy = [selected_copy]843 for cls in selected_copy:844 course_teacher_counts[(cls.course_code, cls.teacher)] += 1845 846 # Final fix to ensure the child is valid847 return fix_class_assignments(child, courses, teachers, rooms)848 849import random850 851 852def mutate(schedule, courses, teachers, rooms):853 """Mutate a schedule by changing some assignments, prioritizing fixing course requirements."""854 branches = set(branch for _, branch, _ in courses)855 class_requirements = get_course_class_requirements()856 course_counts = count_course_classes(schedule)857 858 # Identify problem courses where the actual count of classes differs from the required count859 problem_courses = []860 for course_code, required in class_requirements.items():861 actual = course_counts.get(course_code, 0)862 if actual != required:863 problem_courses.append((course_code, actual, required, abs(actual - required)))864 865 # Determine mutation type based on the presence of problem courses866 if problem_courses and random.random() < 0.7:867 mutation_type = "targeted"868 else:869 mutation_type = random.choice(["single", "single", "swap", "multi"])870 871 # Handle different mutation types872 if mutation_type == "single":873 day, slot = random.randint(0, DAYS - 1), random.randint(0, SLOTS_PER_DAY - 1)874 875 # Skip lunch slot876 if slot == LUNCH_SLOT:877 return878 879 # Randomly select a branch for mutation880 branch = random.choice(list(branches))881 882 # Skip if the selected slot is already empty883 if schedule[day][slot] is None:884 return885 886 if isinstance(schedule[day][slot], list):887 schedule[day][slot] = [c for c in schedule[day][slot] if c is not None and c.branch != branch]888 if not schedule[day][slot]:889 schedule[day][slot] = None890 elif len(schedule[day][slot]) == 1:891 schedule[day][slot] = schedule[day][slot][0]892 elif schedule[day][slot].branch == branch:893 schedule[day][slot] = None894 895 class_slot = get_valid_assignment(schedule, courses, teachers, rooms, day, slot, branch)896 897 if class_slot:898 if schedule[day][slot] is None:899 schedule[day][slot] = class_slot900 elif isinstance(schedule[day][slot], list):901 schedule[day][slot].append(class_slot)902 else:903 schedule[day][slot] = [schedule[day][slot], class_slot]904 905 elif mutation_type == "swap":906 day1, slot1 = random.randint(0, DAYS - 1), random.randint(0, SLOTS_PER_DAY - 1)907 day2, slot2 = random.randint(0, DAYS - 1), random.randint(0, SLOTS_PER_DAY - 1)908 909 # Skip lunch slot910 if slot1 == LUNCH_SLOT or slot2 == LUNCH_SLOT:911 return912 913 # Skip empty slots914 if schedule[day1][slot1] is None or schedule[day2][slot2] is None:915 return916 917 # Handle swapping classes918 if isinstance(schedule[day1][slot1], list) and isinstance(schedule[day2][slot2], list):919 if len(schedule[day1][slot1]) > 0 and len(schedule[day2][slot2]) > 0:920 idx1 = random.randint(0, len(schedule[day1][slot1]) - 1)921 idx2 = random.randint(0, len(schedule[day2][slot2]) - 1)922 923 # Swap the classes924 schedule[day1][slot1][idx1], schedule[day2][slot2][idx2] = schedule[day2][slot2][idx2], \925 schedule[day1][slot1][idx1]926 927 # Update class day and slot info928 schedule[day1][slot1][idx1].day, schedule[day1][slot1][idx1].slot = day1, slot1929 schedule[day2][slot2][idx2].day, schedule[day2][slot2][idx2].slot = day2, slot2930 elif isinstance(schedule[day1][slot1], list) and not isinstance(schedule[day2][slot2], list):931 if len(schedule[day1][slot1]) > 0:932 idx = random.randint(0, len(schedule[day1][slot1]) - 1)933 schedule[day1][slot1][idx], schedule[day2][slot2] = schedule[day2][slot2], schedule[day1][slot1][idx]934 935 # Update class day and slot info936 schedule[day1][slot1][idx].day, schedule[day1][slot1][idx].slot = day1, slot1937 schedule[day2][slot2].day, schedule[day2][slot2].slot = day2, slot2938 elif not isinstance(schedule[day1][slot1], list) and isinstance(schedule[day2][slot2], list):939 if len(schedule[day2][slot2]) > 0:940 idx = random.randint(0, len(schedule[day2][slot2]) - 1)941 schedule[day1][slot1], schedule[day2][slot2][idx] = schedule[day2][slot2][idx], schedule[day1][slot1]942 943 # Update class day and slot info944 schedule[day1][slot1].day, schedule[day1][slot1].slot = day1, slot1945 schedule[day2][slot2][idx].day, schedule[day2][slot2][idx].slot = day2, slot2946 else:947 # Swap the classes948 schedule[day1][slot1], schedule[day2][slot2] = schedule[day2][slot2], schedule[day1][slot1]949 950 # Update class day and slot info951 schedule[day1][slot1].day, schedule[day1][slot1].slot = day1, slot1952 schedule[day2][slot2].day, schedule[day2][slot2].slot = day2, slot2953 954 elif mutation_type == "targeted":955 if not problem_courses:956 return # No problems to fix957 958 problem_courses.sort(key=lambda x: x[3], reverse=True)959 course_teacher_counts = count_course_teacher_classes(schedule)960 961 teacher_course_problems = []962 for (course, teacher), count in course_teacher_counts.items():963 required = class_requirements.get(course, 1)964 if count != required:965 teacher_course_problems.append((course, teacher, count, required, abs(count - required)))966 967 teacher_course_problems.sort(key=lambda x: x[4], reverse=True)968 969 if teacher_course_problems:970 course_code, teacher_name, actual, required, diff = teacher_course_problems[0]971 course_details = next((c for c in courses if c[0] == course_code), None)972 if not course_details:973 return # Course not found974 975 _, branch, course_name = course_details976 else:977 course_code, actual, required, diff = problem_courses[0]978 course_details = next((c for c in courses if c[0] == course_code), None)979 if not course_details:980 return # Course not found981 982 _, branch, course_name = course_details983 teacher_name = None # No specific teacher to target984 985 if actual < required:986 classes_to_add = required - actual987 for _ in range(classes_to_add):988 for attempt in range(20):989 day, slot = random.randint(0, DAYS - 1), random.randint(0, SLOTS_PER_DAY - 1)990 991 # Skip lunch slot992 if slot == LUNCH_SLOT:993 continue994 995 # Check if slot is available996 if schedule[day][slot] is not None:997 if isinstance(schedule[day][slot], list) and len(schedule[day][slot]) >= MAX_CLASSES_PER_SLOT:998 continue # Slot is full999 1000 # Get a valid assignment1001 class_slot = get_valid_assignment(1002 schedule, courses, teachers, rooms, day, slot, branch,1003 course_teacher_counts=course_teacher_counts,1004 class_requirements=class_requirements,1005 specific_course=course_code,1006 specific_teacher=teacher_name1007 )1008 1009 if class_slot and class_slot.course_code == course_code:1010 # Add to schedule1011 if schedule[day][slot] is None:1012 schedule[day][slot] = class_slot1013 elif isinstance(schedule[day][slot], list):1014 schedule[day][slot].append(class_slot)1015 else:1016 schedule[day][slot] = [schedule[day][slot], class_slot]1017 break # Successfully added a class1018 1019 elif actual > required:1020 classes_to_remove = actual - required1021 1022 # Find all slots with this course1023 course_slots = []1024 for day in range(DAYS):1025 for slot in range(SLOTS_PER_DAY):1026 if slot == LUNCH_SLOT:1027 continue1028 1029 if schedule[day][slot] is None:1030 continue1031 1032 if isinstance(schedule[day][slot], list):1033 for i, class_data in enumerate(schedule[day][slot]):1034 if class_data is not None and class_data.course_code == course_code:1035 if teacher_name is None or class_data.teacher == teacher_name:1036 course_slots.append((day, slot, i, class_data))1037 elif schedule[day][slot].course_code == course_code:1038 if teacher_name is None or schedule[day][slot].teacher == teacher_name:1039 course_slots.append((day, slot, None, schedule[day][slot]))1040 1041 # Sort and remove classes1042 if teacher_name:1043 course_slots.sort(key=lambda x: 0 if x[3].teacher == teacher_name else 1)1044 else:1045 random.shuffle(course_slots)1046 1047 removed_count = 01048 for day, slot, idx, class_data in course_slots:1049 if removed_count >= classes_to_remove:1050 break1051 1052 if idx is None:1053 schedule[day][slot] = None1054 else:1055 schedule[day][slot].pop(idx)1056 if not schedule[day][slot]:1057 schedule[day][slot] = None1058 elif len(schedule[day][slot]) == 1:1059 schedule[day][slot] = schedule[day][slot][0]1060 1061 removed_count += 11062 1063 elif mutation_type == "multi":1064 num_mutations = random.randint(2, 5)1065 for _ in range(num_mutations):1066 day, slot = random.randint(0, DAYS - 1), random.randint(0, SLOTS_PER_DAY - 1)1067 1068 if slot == LUNCH_SLOT:1069 continue1070 1071 branch = random.choice(list(branches))1072 if schedule[day][slot] is None:1073 continue1074 1075 if isinstance(schedule[day][slot], list):1076 schedule[day][slot] = [c for c in schedule[day][slot] if c is not None and c.branch != branch]1077 if not schedule[day][slot]:1078 schedule[day][slot] = None1079 elif len(schedule[day][slot]) == 1:1080 schedule[day][slot] = schedule[day][slot][0]1081 elif schedule[day][slot].branch == branch:1082 schedule[day][slot] = None1083 1084 class_slot = get_valid_assignment(schedule, courses, teachers, rooms, day, slot, branch)1085 if class_slot:1086 if schedule[day][slot] is None:1087 schedule[day][slot] = class_slot1088 elif isinstance(schedule[day][slot], list):1089 schedule[day][slot].append(class_slot)1090 else:1091 schedule[day][slot] = [schedule[day][slot], class_slot]1092 1093 1094# The check_room_conflicts function has been consolidated at the top of the file1095# The count_course_teacher_classes function has been consolidated and moved below1096def count_classes_per_room(schedule):1097 """Count how many classes are scheduled in each room.1098 1099 This helps us check if rooms are being used efficiently.1100 """1101 # Use a Counter to track room usage1102 room_counts = Counter()1103 1104 # Go through each day and slot1105 for day in range(DAYS):1106 for slot in range(SLOTS_PER_DAY):1107 # Skip lunch slot1108 if slot == LUNCH_SLOT:1109 continue1110 1111 # Skip empty slots1112 if schedule[day][slot] is None:1113 continue1114 1115 # Handle multiple classes in the same slot1116 if isinstance(schedule[day][slot], list):1117 for class_data in schedule[day][slot]:1118 # Skip None values1119 if class_data is None:1120 continue1121 1122 # Get the room based on the type of class_data1123 room = class_data.room if hasattr(class_data, 'room') else class_data[3]1124 room_counts[room] += 11125 else:1126 # Single class in this slot1127 room = schedule[day][slot].room if hasattr(schedule[day][slot], 'room') else schedule[day][slot][3]1128 room_counts[room] += 11129 1130 return room_counts1131 1132def find_room_conflicts(schedule):1133 """Find any conflicts where a room is used more than once in the same time slot.1134 1135 Returns a list of (day, slot, room) tuples where conflicts occur.1136 """1137 conflicts = []1138 1139 # Check each day and slot1140 for day in range(DAYS):1141 for slot in range(SLOTS_PER_DAY):1142 # Skip lunch slot1143 if slot == LUNCH_SLOT:1144 continue1145 1146 # Skip empty slots1147 if schedule[day][slot] is None:1148 continue1149 1150 # Count rooms used in this slot1151 room_counts = Counter()1152 1153 # Handle multiple classes in the same slot1154 if isinstance(schedule[day][slot], list):1155 for class_data in schedule[day][slot]:1156 if class_data is None:1157 continue1158 1159 # Get room based on data type1160 room = class_data.room if hasattr(class_data, 'room') else class_data[3]1161 room_counts[room] += 11162 else:1163 # Single class1164 room = schedule[day][slot].room if hasattr(schedule[day][slot], 'room') else schedule[day][slot][3]1165 room_counts[room] = 11166 1167 # Add conflicts for any room used more than once1168 for room, count in room_counts.items():1169 if count > 1:1170 conflicts.append((day, slot, room))1171 1172 return conflicts1173 1174def count_course_classes(schedule):1175 """Count the number of classes per course in the schedule.1176 Optimized using Counter for faster counting operations.1177 """1178 # Pre-allocate a list to collect all course codes1179 course_codes = []1180 1181 for day in range(DAYS):1182 for slot in range(SLOTS_PER_DAY):1183 if slot == LUNCH_SLOT:1184 continue1185 1186 if not schedule[day][slot]:1187 continue1188 1189 # Handle multiple classes in the same slot1190 if isinstance(schedule[day][slot], list):1191 for class_data in schedule[day][slot]:1192 if class_data is None:1193 continue1194 1195 # Get course code1196 course_code = None1197 if hasattr(class_data, 'course_code'):1198 course_code = class_data.course_code1199 elif isinstance(class_data, tuple) and len(class_data) >= 7:1200 course_code = class_data[0]