Spaces:
Sleeping
Sleeping
github-actions[bot]
chore(sync): mirror Scheduler-Backend from GitHub 1d9e21b5e7395f3b80bb90cd74cb357b4bef1efa
30abf21 Download differential_evolution_api.py from PAU-001/CP-SAT_Timetable_Scheduler: direct link, hf CLI and curl.
- Browser
- Download file 82.4 kB
-
https://huggingface.co/spaces/PAU-001/CP-SAT_Timetable_Scheduler/resolve/main/differential_evolution_api.py
- Command line
-
hf download hf://spaces/PAU-001/CP-SAT_Timetable_Scheduler/differential_evolution_api.py
-
curl -L -o differential_evolution_api.py https://huggingface.co/spaces/PAU-001/CP-SAT_Timetable_Scheduler/resolve/main/differential_evolution_api.py
82.4 kB
# differential_evolution_api.py
"""
API-compatible differential evolution algorithm that works with input_data instances
passed from the Flask application instead of static imports.
"""
import random
from typing import List
import copy
from utils import Utility
from entitities.Class import Class
import numpy as np
from constraints import Constraints
import re
class DifferentialEvolution:
def __init__(self, input_data, pop_size: int, F: float, CR: float):
self.desired_fitness = 0
self.input_data = input_data
self.rooms = input_data.rooms
self.timeslots = input_data.create_time_slots(
no_hours_per_day=input_data.hours,
no_days_per_week=input_data.days,
day_start_time=8.5
)
self.student_groups = input_data.student_groups
self.courses = input_data.courses
self.events_list, self.events_map = self.create_events()
self.pop_size = pop_size
self.F = F
self.CR = CR
self.constraints = Constraints(input_data)
# If True, treat soft constraints as hard (must be 0 to accept improvements).
# This is used by the "strict-if-possible" probe and strict runs.
self.strict_mode = False
# Optimization: Cache fitness values to avoid recalculation
self.fitness_cache = {}
# Optimization: Pre-calculate building assignments for rooms to speed up evaluation
self.room_building_cache = {}
for idx, room in enumerate(self.rooms):
self.room_building_cache[idx] = self.get_room_building(room)
# Optimization: Pre-calculate SST groups (explicit building first; keywords as fallback).
self.engineering_groups = {sg.id for sg in self.student_groups if getattr(sg, 'is_sst', False)}
self.population = self.initialize_population()
def set_strict_mode(self, enabled: bool) -> None:
self.strict_mode = bool(enabled)
def _hard_constraint_keys(self) -> list[str]:
"""Constraint keys that are prioritized lexicographically during selection.
In normal mode, only true hard constraints are included.
In strict mode, soft constraints are also treated as hard.
"""
base = [
'student_group_constraints',
'lecturer_availability',
'course_allocation_completeness',
'room_time_conflict',
'break_time_constraint',
'room_constraints',
'same_course_same_room_per_day',
'lecturer_schedule_constraints',
'building_assignments',
'no_free_day',
'consecutive_timeslots',
]
if not self.strict_mode:
return base
# Treat soft constraints as hard when strict_mode is enabled.
return base + [
'single_event_per_day',
'three_unit_split_across_days_TYD',
'spread_events',
'extremely_late_classes',
'lecturer_workload_constraints',
]
def _can_place_event_id(
self,
chromosome,
room_idx: int,
timeslot_idx: int,
event_id,
*,
ignore_event_ids=None,
ignore_faculty_availability: bool = False,
) -> bool:
"""Return True if event_id can be placed at (room_idx, timeslot_idx) without violating
immediate feasibility checks.
This is a local feasibility gate used by mutation/crossover so they don't introduce
obvious hard violations (room suitability, break time, building rule, lecturer windows,
and same-timeslot lecturer/group overlaps).
"""
if event_id is None:
return True
if ignore_event_ids is None:
ignore_event_ids = set()
else:
ignore_event_ids = set(ignore_event_ids)
ev = self.events_map.get(event_id)
if ev is None:
return False
# Cell occupancy check: allow overwriting only if the existing value is being ignored.
existing = chromosome[room_idx][timeslot_idx]
if existing is not None and existing not in ignore_event_ids:
return False
# Room suitability check
try:
course = self.input_data.getCourse(ev.course_id)
except Exception:
course = None
if not self.is_room_suitable(self.rooms[room_idx], course):
return False
# Same-timeslot student-group / lecturer overlap checks (ignore specified event ids).
sg_id = None
try:
sg_id = ev.student_group.id
except Exception:
sg_id = None
for r_idx in range(len(self.rooms)):
other_id = chromosome[r_idx][timeslot_idx]
if other_id is None or other_id in ignore_event_ids:
continue
other_ev = self.events_map.get(other_id)
if not other_ev:
continue
try:
if sg_id is not None and other_ev.student_group and other_ev.student_group.id == sg_id:
return False
except Exception:
pass
try:
if ev.faculty_id is not None and other_ev.faculty_id == ev.faculty_id:
return False
except Exception:
pass
# Use the canonical slot checks (break time, building rule, lecturer day/time windows).
# Temporarily clear the destination cell so is_slot_available_for_event sees an empty slot.
chromosome[room_idx][timeslot_idx] = None
try:
ok = self.is_slot_available_for_event(
chromosome,
room_idx,
timeslot_idx,
ev,
ignore_faculty_availability=ignore_faculty_availability,
)
return bool(ok)
finally:
chromosome[room_idx][timeslot_idx] = existing
@staticmethod
def _parse_time_point(value):
"""Parse a time point into minutes since midnight.
Supports:
- 'HH:MM' (e.g., '08:30')
- 'H' / 'HH' whole-hour strings (e.g., '8')
- fractional hours (e.g., '8.5' -> 08:30)
"""
def maybe_assume_pm(hour: int, minute: int) -> int:
# Heuristic: treat ambiguous early-hours as afternoon/evening.
# Users often enter '3:30' intending 15:30, not 03:30.
# Apply for 1:00–6:30 inclusive; do not touch normal morning times like 08:30.
if 1 <= hour <= 5:
return hour + 12
if hour == 6 and minute <= 30:
return 18
return hour
if value is None:
return None
s = str(value).strip()
# Strip wrappers from stringified lists like "['8:30-16:30']".
while s and s[0] in "[({'\"":
s = s[1:].lstrip()
while s and s[-1] in "])}'\"":
s = s[:-1].rstrip()
if not s:
return None
m = re.match(r'^\s*(\d{1,2})\s*:\s*(\d{2})\s*$', s)
if m:
hour = int(m.group(1))
minute = int(m.group(2))
hour = maybe_assume_pm(hour, minute)
return hour * 60 + minute
m = re.match(r'^\s*(\d{1,2})\s*\.\s*(\d+)\s*$', s)
if m:
hours = int(m.group(1))
frac = float('0.' + m.group(2))
minute = int(round(frac * 60))
hours = maybe_assume_pm(hours, minute)
return hours * 60 + minute
m = re.match(r'^\s*(\d{1,2})\s*$', s)
if m:
hours = int(m.group(1))
hours = maybe_assume_pm(hours, 0)
return hours * 60
try:
f = float(s)
hours = int(f)
minute = int(round((f - hours) * 60))
hours = maybe_assume_pm(hours, minute)
return hours * 60 + minute
except Exception:
return None
@staticmethod
def parse_time_range(spec_str: str):
"""Parse a time range like '08:30-12:30' into (start_min, end_min)."""
if not spec_str:
return None, None
s = str(spec_str).strip()
if not s:
return None, None
parts = re.split(r'\s*(?:-|–|—|(?i:\\bto\\b))\s*', s, maxsplit=1)
if len(parts) != 2:
return None, None
start_min = DifferentialEvolution._parse_time_point(parts[0])
end_min = DifferentialEvolution._parse_time_point(parts[1])
if start_min is None or end_min is None:
return None, None
if end_min <= start_min:
return None, None
return start_min, end_min
def create_events(self):
"""Create events list and mapping for the timetabling problem"""
events_list = []
event_map = {}
idx = 0
for student_group in self.student_groups:
for i in range(student_group.no_courses):
# Match core behavior: 1-credit courses are treated as 3 hours.
course = self.input_data.getCourse(student_group.courseIDs[i])
if course and getattr(course, 'credits', None) == 1:
required_hours = 3
else:
required_hours = student_group.hours_required[i]
hourcount = 1
while hourcount <= required_hours:
event = Class(student_group, student_group.teacherIDS[i], student_group.courseIDs[i])
events_list.append(event)
event_map[idx] = event
idx += 1
hourcount += 1
return events_list, event_map
def initialize_population(self):
"""Initialize the population with valid chromosomes"""
population = []
for i in range(self.pop_size):
chromosome = self.create_chromosome()
population.append(chromosome)
return np.array(population)
def create_chromosome(self):
"""Create a single chromosome (timetable solution)"""
chromosome = np.empty((len(self.rooms), len(self.timeslots)), dtype=object)
# Group events by student group and course to handle them as blocks
events_by_group_course = {}
for idx, event in enumerate(self.events_list):
key = (event.student_group.id, event.course_id)
if key not in events_by_group_course:
events_by_group_course[key] = []
events_by_group_course[key].append(idx)
# Trackers for optimized placement
hours_per_day_for_group = {sg.id: [0] * self.input_data.days for sg in self.student_groups}
non_sst_course_count_for_group = {sg.id: 0 for sg in self.student_groups}
course_days_used = {}
# Randomize course processing order for population diversity
course_items = list(events_by_group_course.items())
random.shuffle(course_items)
for (student_group_id, course_id), event_indices in course_items:
course = self.input_data.getCourse(course_id)
student_group = self.input_data.getStudentGroup(student_group_id)
hours_required = len(event_indices)
if hours_required == 0:
continue
# Decide on a split strategy based on course credits
if hours_required == 3:
is_engineering = student_group.id in self.engineering_groups
if is_engineering:
# SST: 3-hour courses are primarily 3 consecutive hours (fallback to 2,1 internally during repair if needed)
# We will randomly allow 2,1 occasionally but strongly prefer 3
split_strategy = (3,) if random.random() < 0.85 else (2, 1)
else:
# TYD: 3-hour courses are scheduled as 2 hours on one day, 1 hour on another
split_strategy = (2, 1)
elif hours_required == 2:
split_strategy = (2,)
else:
split_strategy = (hours_required,)
event_idx_counter = 0
course_key = (student_group_id, course_id)
course_days_used[course_key] = set()
is_course_placed_in_non_sst = False
for block_hours in split_strategy:
placed = False
block_event_indices = event_indices[event_idx_counter : event_idx_counter + block_hours]
event_idx_counter += block_hours
# Prioritize days with fewer hours and those not yet used by this course
available_days = [d for d in range(self.input_data.days) if d not in course_days_used[course_key]]
sorted_days = sorted(available_days, key=lambda d: hours_per_day_for_group[student_group_id][d])
for day_idx in sorted_days:
day_start = day_idx * self.input_data.hours
day_end = (day_idx + 1) * self.input_data.hours
possible_slots = []
for room_idx, room in enumerate(self.rooms):
if self.is_room_suitable(room, course):
room_building = self.room_building_cache[room_idx]
is_engineering = student_group.id in self.engineering_groups
req_room_val = str(getattr(course, 'required_room_type', '') or '').lower()
room_type_val = str(getattr(room, 'room_type', '') or '').lower()
course_name_val = str(getattr(course, 'name', '') or '').lower()
needs_computer_lab = (
req_room_val in ['comp lab', 'computer_lab'] or
room_type_val in ['comp lab', 'computer_lab'] or
('lab' in course_name_val and any(k in course_name_val for k in ['computer', 'programming', 'software']))
)
building_allowed = True
if needs_computer_lab:
# Requirement: TYD groups must NEVER use SST rooms (even labs).
if (not is_engineering) and room_building == 'SST':
building_allowed = False
elif is_engineering:
if room_building != 'SST' and non_sst_course_count_for_group[student_group_id] >= 2:
building_allowed = False
elif room_building == 'SST':
building_allowed = False
if building_allowed:
# Find consecutive slots
for timeslot_start in range(day_start, day_end):
if timeslot_start + block_hours > day_end:
continue
def _ok(i: int) -> bool:
ts = timeslot_start + i
ev = self.events_list[block_event_indices[i]]
return (
self.is_slot_available_for_event(chromosome, room_idx, ts, ev)
and self._is_student_group_available(chromosome, student_group_id, ts)
and self._is_lecturer_available(chromosome, ev.faculty_id, ts)
)
if all(_ok(i) for i in range(block_hours)):
possible_slots.append((room_idx, timeslot_start))
if possible_slots:
# Prefer SST rooms for SST groups when available (soft preference).
if is_engineering:
sst_slots = [s for s in possible_slots if str(self.room_building_cache.get(s[0], '')).upper() == 'SST']
if sst_slots and random.random() < 0.85:
room_idx, timeslot_start = random.choice(sst_slots)
else:
room_idx, timeslot_start = random.choice(possible_slots)
else:
room_idx, timeslot_start = random.choice(possible_slots)
for i in range(block_hours):
chromosome[room_idx, timeslot_start + i] = block_event_indices[i]
# Update trackers
hours_per_day_for_group[student_group_id][day_idx] += block_hours
course_days_used[course_key].add(day_idx)
if not is_course_placed_in_non_sst and self.room_building_cache[room_idx] != 'SST' and not needs_computer_lab and is_engineering:
non_sst_course_count_for_group[student_group_id] += 1
is_course_placed_in_non_sst = True
placed = True
break
if placed:
break
# Final verification to place any unassigned events
chromosome = self.verify_and_repair_course_allocations(chromosome)
return chromosome
def is_slot_available(self, chromosome, room_idx, timeslot_idx):
"""Check if a timeslot is available"""
if chromosome[room_idx][timeslot_idx] is not None:
return False
# Check if this is break time (13:00 - 14:00)
break_hour = 4 # 13:00 is the 5th hour (index 4) starting from 9:00
day = timeslot_idx // self.input_data.hours
hour_in_day = timeslot_idx % self.input_data.hours
# No break time on Tuesday (1) and Thursday (3)
if hour_in_day == break_hour and day not in [1, 3]:
return False
return True
def is_slot_available_for_event(self, chromosome, room_idx, timeslot_idx, event, ignore_faculty_availability: bool = False):
"""Check if a slot is available for a specific event.
By default, enforces lecturer day/time availability windows.
When repairing missing events, we may relax lecturer availability (but still keep
lecturer clashes and student-group clashes prevented by the caller).
"""
# Check if the slot is physically empty
if chromosome[room_idx][timeslot_idx] is not None:
return False
# Check for break time
break_hour = 4
day = timeslot_idx // self.input_data.hours
hour_in_day = timeslot_idx % self.input_data.hours
if hour_in_day == break_hour and day not in [1, 3]:
return False
# Hard rule: TYD (non-SST) student groups must never be placed in SST rooms.
# Enforce at the feasibility layer so crossover/mutation/repairs can't introduce it.
try:
if event is not None and getattr(event, 'student_group', None) is not None:
if not getattr(event.student_group, 'is_sst', False):
room_building = self.room_building_cache.get(room_idx)
if not room_building:
room_building = self.get_room_building(self.rooms[room_idx])
if str(room_building).upper() == 'SST':
return False
except Exception:
pass
# Check lecturer schedule constraints
if (not ignore_faculty_availability) and event and event.faculty_id is not None:
faculty = self.input_data.getFaculty(event.faculty_id)
if faculty:
days_map = {0: "Mon", 1: "Tue", 2: "Wed", 3: "Thu", 4: "Fri"}
day_abbr = days_map.get(day)
def _clean_token(v) -> str:
s = str(v or '').strip()
while s and s[0] in "[({'\"":
s = s[1:].lstrip()
while s and s[-1] in "])'}\"":
s = s[:-1].rstrip()
return s
def parse_hhmm(s):
# Delegate to shared parser so the PM heuristic applies consistently.
return DifferentialEvolution._parse_time_point(s)
timeslot_obj = self.timeslots[timeslot_idx]
# 08:30-based slots: index 0 -> 08:30
if isinstance(getattr(timeslot_obj, 'start_time', None), (int, np.integer)):
slot_min = (8 * 60 + 30) + int(timeslot_obj.start_time) * 60
else:
slot_min = parse_hhmm(getattr(timeslot_obj, 'start_time', ''))
# Check day availability
is_day_ok = False
if isinstance(faculty.avail_days, str):
days_raw = _clean_token(faculty.avail_days)
if (not days_raw) or (days_raw.upper() == "ALL") or ("ALL" in days_raw.upper()):
is_day_ok = True
else:
avail_days = [_clean_token(d).strip().capitalize() for d in days_raw.split(',') if _clean_token(d).strip()]
if day_abbr in avail_days:
is_day_ok = True
elif isinstance(faculty.avail_days, list):
if not faculty.avail_days:
is_day_ok = True
else:
cleaned = [_clean_token(d).strip() for d in faculty.avail_days if _clean_token(d).strip()]
if any((d.upper() == 'ALL') or ('ALL' in d.upper()) for d in cleaned):
is_day_ok = True
else:
avail_days = [d.capitalize() for d in cleaned]
if day_abbr in avail_days:
is_day_ok = True
else:
days_raw = _clean_token(faculty.avail_days)
if (not days_raw) or (days_raw.upper() == "ALL") or ("ALL" in days_raw.upper()):
is_day_ok = True
else:
avail_days = [_clean_token(d).strip().capitalize() for d in str(days_raw).split(',') if _clean_token(d).strip()]
if day_abbr in avail_days:
is_day_ok = True
if not is_day_ok:
return False
# Check time availability (supports str/list/dict and ALL)
avail_times = faculty.avail_times
def iter_time_specs(av):
def normalize_to_list(specs):
if not specs:
return []
if isinstance(specs, list):
out = []
for x in specs:
if isinstance(x, str) and ',' in x:
out.extend([_clean_token(t) for t in x.split(',') if _clean_token(t)])
else:
out.append(_clean_token(x))
return out
if isinstance(specs, str):
raw = _clean_token(specs)
if raw.upper() == 'ALL' or 'ALL' in raw.upper():
return ['ALL']
if ',' in raw:
return [_clean_token(t) for t in raw.split(',') if _clean_token(t)]
return [raw]
return [_clean_token(specs)]
if not av:
return []
if isinstance(av, dict):
specs = None
if day_abbr:
specs = av.get(day_abbr) or av.get(day_abbr.capitalize())
if not specs:
specs = av.get('All') or av.get('ALL')
return normalize_to_list(specs)
if isinstance(av, list):
return normalize_to_list(av)
return normalize_to_list(av)
specs_list = iter_time_specs(avail_times)
if specs_list and not any((str(s).strip().upper() == 'ALL') or ('ALL' in str(s).upper()) for s in specs_list):
# If we cannot parse the slot time, be permissive.
if slot_min is None:
pass
else:
is_time_ok = False
for spec in specs_list:
spec_str = _clean_token(spec)
if not spec_str:
continue
if re.search(r'[-–—]|\bto\b', spec_str, flags=re.IGNORECASE):
start_min, end_min = self.parse_time_range(spec_str)
if start_min is not None and end_min is not None:
# Inclusive end: users expect 9:30-15:30 to allow a 15:30 start.
if start_min <= slot_min <= end_min:
is_time_ok = True
break
else:
m = parse_hhmm(spec_str)
if m is not None and m == slot_min:
is_time_ok = True
break
if not is_time_ok:
return False
return True
def is_room_suitable(self, room, course):
"""Check if room is suitable for course"""
if course is None:
return False
return room.room_type == course.required_room_type
def get_room_building(self, room):
"""Helper method to determine room building"""
if hasattr(room, 'building'):
return room.building.upper()
elif hasattr(room, 'name') and room.name:
room_name = room.name.upper()
if 'SST' in room_name:
return 'SST'
elif 'TYD' in room_name:
return 'TYD'
elif hasattr(room, 'room_id'):
room_id = str(room.room_id).upper()
if 'SST' in room_id:
return 'SST'
elif 'TYD' in room_id:
return 'TYD'
return 'UNKNOWN'
def _is_student_group_available(self, chromosome, student_group_id, timeslot_idx):
"""Check if a student group is already scheduled at a given timeslot"""
for r_idx in range(len(self.rooms)):
event_id = chromosome[r_idx][timeslot_idx]
for event_id in chromosome[:, timeslot_idx]:
if event_id is not None:
event = self.events_map.get(event_id)
if event and event.student_group.id == student_group_id:
return False
return True
def _is_lecturer_available(self, chromosome, faculty_id, timeslot_idx):
"""Check if a lecturer is already scheduled at a given timeslot"""
if faculty_id is None:
return True
for r_idx in range(len(self.rooms)):
event_id = chromosome[r_idx][timeslot_idx]
if event_id is not None:
event = self.events_map.get(event_id)
if event and event.faculty_id == faculty_id:
return False
return True
def find_clash(self, chromosome):
"""Find a random timeslot with a student or lecturer clash"""
clash_slots = []
for t_idx in range(len(self.timeslots)):
simultaneous_events = chromosome[:, t_idx]
student_group_watch = set()
lecturer_watch = set()
has_student_clash = False
has_lecturer_clash = False
event_ids_in_slot = [e for e in simultaneous_events if e is not None]
if len(event_ids_in_slot) <= 1:
continue
for event_id in event_ids_in_slot:
event = self.events_map.get(event_id)
if not event:
continue
# Check for student clash
if event.student_group.id in student_group_watch:
has_student_clash = True
student_group_watch.add(event.student_group.id)
# Check for lecturer clash
if event.faculty_id and event.faculty_id in lecturer_watch:
has_lecturer_clash = True
if event.faculty_id:
lecturer_watch.add(event.faculty_id)
if has_student_clash or has_lecturer_clash:
clash_slots.append(t_idx)
if clash_slots:
return random.choice(clash_slots)
return None
def hamming_distance(self, chromosome1, chromosome2):
"""Calculate Hamming distance between two chromosomes"""
return np.sum(chromosome1.flatten() != chromosome2.flatten())
def calculate_population_diversity(self):
"""Calculate population diversity using sampling for efficiency"""
if self.pop_size <= 10:
total_distance = 0
comparisons = 0
for i in range(self.pop_size):
for j in range(i + 1, self.pop_size):
total_distance += self.hamming_distance(self.population[i], self.population[j])
comparisons += 1
return total_distance / comparisons if comparisons > 0 else 0
else:
# For larger populations, sample 10 random pairs
total_distance = 0
comparisons = 10
for _ in range(comparisons):
i, j = random.sample(range(self.pop_size), 2)
total_distance += self.hamming_distance(self.population[i], self.population[j])
return total_distance / comparisons
def mutate(self, target_idx):
"""Mutation operation with targeted clash resolution"""
mutant_vector = self.population[target_idx].copy()
# Strategy 1: Targeted Clash Resolution
if random.random() < 0.7:
clash_timeslot = self.find_clash(mutant_vector)
if clash_timeslot is not None:
events_in_clash = [mutant_vector[r][clash_timeslot] for r in range(len(self.rooms)) if mutant_vector[r][clash_timeslot] is not None]
if events_in_clash:
event_id_to_move = random.choice(events_in_clash)
event_to_move = self.events_map.get(event_id_to_move)
if event_to_move:
# Find original position and remove it
for r_idx in range(len(self.rooms)):
if mutant_vector[r_idx][clash_timeslot] == event_id_to_move:
mutant_vector[r_idx][clash_timeslot] = None
break
# Find a new, completely valid slot for this event
possible_slots = []
course = self.input_data.getCourse(event_to_move.course_id)
for r_idx, room in enumerate(self.rooms):
if self.is_room_suitable(room, course):
for t_idx in range(len(self.timeslots)):
if (self.is_slot_available_for_event(mutant_vector, r_idx, t_idx, event_to_move) and
self._is_student_group_available(mutant_vector, event_to_move.student_group.id, t_idx) and
(event_to_move.faculty_id is None or self._is_lecturer_available(mutant_vector, event_to_move.faculty_id, t_idx))):
possible_slots.append((r_idx, t_idx))
if possible_slots:
r, t = random.choice(possible_slots)
mutant_vector[r][t] = event_id_to_move
# Strategy 2: Perform a few swaps to introduce small variations
if random.random() < 0.2:
for _ in range(random.randint(1, 2)):
occupied_slots = np.argwhere(mutant_vector != None)
if len(occupied_slots) < 2:
continue
# Try a few times to find a swap that remains feasible.
for _try in range(8):
idx1, idx2 = random.sample(range(len(occupied_slots)), 2)
pos1, pos2 = tuple(occupied_slots[idx1]), tuple(occupied_slots[idx2])
if pos1 == pos2:
continue
e1 = mutant_vector[pos1]
e2 = mutant_vector[pos2]
if e1 is None or e2 is None:
continue
ignore_ids = {e1, e2}
r1, t1 = int(pos1[0]), int(pos1[1])
r2, t2 = int(pos2[0]), int(pos2[1])
# Check feasibility of swapping the two events.
if not self._can_place_event_id(mutant_vector, r2, t2, e1, ignore_event_ids=ignore_ids):
continue
if not self._can_place_event_id(mutant_vector, r1, t1, e2, ignore_event_ids=ignore_ids):
continue
mutant_vector[pos1], mutant_vector[pos2] = mutant_vector[pos2], mutant_vector[pos1]
break
return mutant_vector
def crossover(self, target_vector, mutant_vector):
"""Enhanced Strategic Crossover with conflict resolution"""
trial_vector = target_vector.copy()
conflicts = self.constraints.get_all_conflicts(trial_vector)
# Combine all hard conflicts to be resolved
all_clashes = conflicts.get('student_group', []) + conflicts.get('lecturer', [])
if not all_clashes:
# If no clashes, perform a more standard DE crossover
for r in range(len(self.rooms)):
for t in range(len(self.timeslots)):
if random.random() < self.CR:
gene = mutant_vector[r, t]
if gene is None:
trial_vector[r, t] = None
continue
# Only accept the gene if it is feasible in the target slot.
# Allow overwriting the existing target gene by ignoring it.
existing = trial_vector[r, t]
if self._can_place_event_id(trial_vector, r, t, gene, ignore_event_ids={existing} if existing is not None else None):
trial_vector[r, t] = gene
return trial_vector
# Create a set of positions that have clashes for quick lookup
clash_positions = set()
for clash in all_clashes:
for pos in clash['positions']:
clash_positions.add(tuple(pos))
# Iterate through the mutant and bring in non-conflicting genes
for r in range(len(self.rooms)):
for t in range(len(self.timeslots)):
if (r, t) in clash_positions:
mutant_gene = mutant_vector[r, t]
target_gene = trial_vector[r, t]
if mutant_gene != target_gene and mutant_gene is not None:
mutant_event = self.events_map.get(mutant_gene)
if not mutant_event:
continue
is_safe_to_swap = True
# Check against all other events in the same timeslot in the trial vector
for r_check in range(len(self.rooms)):
if r_check != r:
existing_event_id = trial_vector[r_check, t]
if existing_event_id is not None:
existing_event = self.events_map.get(existing_event_id)
if existing_event:
if (existing_event.student_group.id == mutant_event.student_group.id or
existing_event.faculty_id == mutant_event.faculty_id):
is_safe_to_swap = False
break
if is_safe_to_swap:
# Finally, enforce full feasibility in the destination slot.
if self._can_place_event_id(trial_vector, r, t, mutant_gene, ignore_event_ids={target_gene} if target_gene is not None else None):
trial_vector[r, t] = mutant_gene
return trial_vector
def evaluate_fitness(self, chromosome):
"""Evaluate fitness using cached results"""
chromosome_key = str(chromosome.tobytes())
if chromosome_key in self.fitness_cache:
return self.fitness_cache[chromosome_key]
# Use the centralized Constraints class for consistent evaluation
fitness = self.constraints.evaluate_fitness(chromosome)
# Cache management: prevent unlimited growth
if len(self.fitness_cache) > 1000:
keys_to_remove = list(self.fitness_cache.keys())[:-500]
for key in keys_to_remove:
del self.fitness_cache[key]
# Cache the result
self.fitness_cache[chromosome_key] = fitness
return fitness
def select(self, target_idx, trial_vector):
"""Selection operation with hard constraint prioritization"""
trial_violations = self.constraints.get_constraint_violations(trial_vector)
target_violations = self.constraints.get_constraint_violations(self.population[target_idx])
hard_constraints = self._hard_constraint_keys()
trial_hard_violations = sum(trial_violations.get(c, 0) for c in hard_constraints)
target_hard_violations = sum(target_violations.get(c, 0) for c in hard_constraints)
accept = False
if trial_hard_violations < target_hard_violations:
accept = True
elif trial_hard_violations == target_hard_violations:
if trial_violations.get('total', float('inf')) <= target_violations.get('total', float('inf')):
accept = True
if accept:
self.population[target_idx] = trial_vector
def run(self, max_generations):
"""Run the differential evolution algorithm"""
fitness_history = []
best_solution = self.population[0]
diversity_history = []
hard_constraints = self._hard_constraint_keys()
def hard_violation_sum(violations: dict) -> float:
return float(sum(violations.get(c, 0) for c in hard_constraints))
# Calculate initial fitness and find best solution
initial_fitness = [self.evaluate_fitness(ind) for ind in self.population]
best_idx = np.argmin(initial_fitness)
best_solution = self.population[best_idx].copy()
best_fitness = initial_fitness[best_idx]
# Track fitness for early convergence detection
stagnation_counter = 0
for generation in range(max_generations):
generation_improved = False
for i in range(self.pop_size):
old_vector = self.population[i].copy()
old_violations = self.constraints.get_constraint_violations(old_vector)
old_hard = hard_violation_sum(old_violations)
old_total = old_violations.get('total', float('inf'))
# Step 1: Mutation
mutant_vector = self.mutate(i)
# Step 2: Crossover
target_vector = self.population[i]
trial_vector = self.crossover(target_vector, mutant_vector)
# Step 3: Evaluation and Selection
self.select(i, trial_vector)
# Ensure population member has all events after selection
candidate = self.verify_and_repair_course_allocations(self.population[i])
# Accept repaired candidate only if it doesn't worsen hard feasibility,
# or if it improves total score at equal hard-feasibility.
cand_violations = self.constraints.get_constraint_violations(candidate)
cand_hard = hard_violation_sum(cand_violations)
cand_total = cand_violations.get('total', float('inf'))
keep_candidate = False
if cand_hard < old_hard:
keep_candidate = True
elif cand_hard == old_hard and cand_total <= old_total:
keep_candidate = True
if keep_candidate:
self.population[i] = candidate
if cand_total < old_total:
generation_improved = True
else:
self.population[i] = old_vector
# Find best solution more efficiently
current_fitness = [self.evaluate_fitness(ind) for ind in self.population]
current_best_idx = np.argmin(current_fitness)
current_best_fitness = current_fitness[current_best_idx]
if current_best_fitness < best_fitness:
best_solution = self.population[current_best_idx].copy()
best_fitness = current_best_fitness
stagnation_counter = 0
# Ensure best solution has all courses properly allocated
best_solution = self.verify_and_repair_course_allocations(best_solution)
else:
stagnation_counter += 1
fitness_history.append(best_fitness)
# Elitism: keep the global best inside the population to prevent regression.
worst_idx = int(np.argmax(current_fitness))
self.population[worst_idx] = best_solution.copy()
# Calculate diversity less frequently for speed
if generation % 20 == 0:
population_diversity = self.calculate_population_diversity()
diversity_history.append(population_diversity)
print(f"Best solution for generation {generation+1}/{max_generations} has a fitness of: {best_fitness}")
if best_fitness == self.desired_fitness:
print(f"Solution with desired fitness of {self.desired_fitness} found at Generation {generation}!")
break
# NOTE: Do not early-terminate purely on stagnation.
# Perfect fitness (0) can require long runs, especially when repairs are active.
# Final verification and repair of the best solution
best_solution = self.verify_and_repair_course_allocations(best_solution)
# Post-algorithm repairs (best-effort, never drop events). Keep them only if they don't worsen fitness.
best_before_repairs = best_solution.copy()
best_before_repairs_fitness = self.evaluate_fitness(best_before_repairs)
repaired = best_solution.copy()
repaired = self.reduce_extremely_late_classes(repaired, max_total=10, max_per_group=1)
repaired = self.reduce_lecturer_clashes(repaired, max_passes=5)
repaired = self.reduce_full_time_lecturer_workload_violations(repaired, max_passes=6)
repaired = self.verify_and_repair_course_allocations(repaired)
repaired = self.repair_multi_hour_blocks(repaired, max_passes=2)
repaired = self.reduce_full_time_lecturer_workload_violations(repaired, max_passes=4)
repaired = self.verify_and_repair_course_allocations(repaired)
repaired_fitness = self.evaluate_fitness(repaired)
if repaired_fitness <= best_before_repairs_fitness:
best_solution = repaired
return best_solution, fitness_history, generation, diversity_history
def repair_multi_hour_blocks(self, chromosome, max_passes: int = 2):
"""Best-effort repair to reduce consecutive-slot and room inconsistency violations.
Targets:
- 2-credit courses: MUST be scheduled as a 2-hour consecutive block (same day, same room).
- 3-credit courses: MUST have at least one 2-hour consecutive block.
Never introduces student-group or lecturer clashes.
"""
hours = self.input_data.hours
n_rooms = len(self.rooms)
n_timeslots = len(self.timeslots)
# Map (group_id, course_id) -> list[event_id]
events_by_group_course = {}
for event_id, ev in enumerate(self.events_list):
try:
sg_id = ev.student_group.id
except Exception:
continue
events_by_group_course.setdefault((sg_id, ev.course_id), []).append(event_id)
# Fast list of suitable rooms per room type
rooms_by_type = {}
for r_idx, room in enumerate(self.rooms):
rooms_by_type.setdefault(getattr(room, 'room_type', None), []).append(r_idx)
def find_positions(event_ids: list[int]):
pos = {}
for r in range(n_rooms):
for t in range(n_timeslots):
eid = chromosome[r][t]
if eid in event_ids:
pos[eid] = (r, t)
return pos
def sg_free_excluding(sg_id, t_idx, ignore_ids: set[int]) -> bool:
for r in range(n_rooms):
eid = chromosome[r][t_idx]
if eid is None or eid in ignore_ids:
continue
ev = self.events_map.get(eid)
if ev and ev.student_group and ev.student_group.id == sg_id:
return False
return True
def lec_free_excluding(faculty_id, t_idx, ignore_ids: set[int]) -> bool:
if faculty_id is None:
return True
for r in range(n_rooms):
eid = chromosome[r][t_idx]
if eid is None or eid in ignore_ids:
continue
ev = self.events_map.get(eid)
if ev and ev.faculty_id == faculty_id:
return False
return True
def slot_ok_for_event(room_idx: int, t_idx: int, ev, ignore_ids: set[int]) -> bool:
existing = chromosome[room_idx][t_idx]
if existing is not None and existing not in ignore_ids:
return False
# Temporarily clear the cell so is_slot_available_for_event can run its own checks.
chromosome[room_idx][t_idx] = None
try:
return self.is_slot_available_for_event(chromosome, room_idx, t_idx, ev)
finally:
chromosome[room_idx][t_idx] = existing
for _ in range(max_passes):
changed_any = False
for (sg_id, course_id), event_ids in events_by_group_course.items():
course = self.input_data.getCourse(course_id)
if not course:
continue
credits = getattr(course, 'credits', 0) or 0
if credits not in (2, 3):
continue
# Ensure all events exist; if missing, let verify_and_repair handle it.
positions = find_positions(event_ids)
if len(positions) < min(len(event_ids), credits):
continue
# Collect currently scheduled timeslots
placed = sorted([(eid, positions[eid][0], positions[eid][1]) for eid in positions], key=lambda x: x[2])
placed_t = [t for _, _, t in placed]
def has_consecutive_pair_same_room() -> bool:
for i in range(len(placed) - 1):
_, r1, t1 = placed[i]
_, r2, t2 = placed[i + 1]
if (t2 - t1) == 1 and (t1 // hours) == (t2 // hours) and r1 == r2:
return True
return False
# 2-credit: need exactly a consecutive pair (same room)
if credits == 2:
if len(placed) >= 2:
eid_a, _, _ = placed[0]
eid_b, _, _ = placed[1]
r_a, t_a = positions[eid_a]
r_b, t_b = positions[eid_b]
if (abs(t_b - t_a) == 1) and (t_a // hours) == (t_b // hours) and r_a == r_b:
continue
# Try to re-place as a 2-hour block
ignore_ids = {eid_a, eid_b}
ev_a = self.events_map.get(eid_a)
ev_b = self.events_map.get(eid_b)
if not ev_a or not ev_b:
continue
suitable_rooms = rooms_by_type.get(getattr(course, 'required_room_type', None), [])
if not suitable_rooms:
continue
found = None
rooms_order = suitable_rooms[:]
random.shuffle(rooms_order)
for day in range(self.input_data.days):
day_start = day * hours
for room_idx in rooms_order:
for h in range(0, hours - 1):
t1 = day_start + h
t2 = t1 + 1
if t2 >= n_timeslots:
continue
if not sg_free_excluding(sg_id, t1, ignore_ids) or not sg_free_excluding(sg_id, t2, ignore_ids):
continue
if not lec_free_excluding(ev_a.faculty_id, t1, ignore_ids) or not lec_free_excluding(ev_b.faculty_id, t2, ignore_ids):
continue
if not slot_ok_for_event(room_idx, t1, ev_a, ignore_ids):
continue
if not slot_ok_for_event(room_idx, t2, ev_b, ignore_ids):
continue
found = (room_idx, t1)
break
if found:
break
if found:
break
if found:
# Clear old positions then place new
chromosome[positions[eid_a][0]][positions[eid_a][1]] = None
chromosome[positions[eid_b][0]][positions[eid_b][1]] = None
room_idx, t1 = found
chromosome[room_idx][t1] = eid_a
chromosome[room_idx][t1 + 1] = eid_b
changed_any = True
continue
# 3-credit: ensure at least one consecutive pair exists
if credits == 3:
if has_consecutive_pair_same_room():
continue
# Take any two events and make them consecutive
if len(placed) < 2:
continue
eid_a = placed[0][0]
eid_b = placed[1][0]
ignore_ids = {eid_a, eid_b}
ev_a = self.events_map.get(eid_a)
ev_b = self.events_map.get(eid_b)
if not ev_a or not ev_b:
continue
suitable_rooms = rooms_by_type.get(getattr(course, 'required_room_type', None), [])
if not suitable_rooms:
continue
found = None
rooms_order = suitable_rooms[:]
random.shuffle(rooms_order)
for day in range(self.input_data.days):
day_start = day * hours
for room_idx in rooms_order:
for h in range(0, hours - 1):
t1 = day_start + h
t2 = t1 + 1
if t2 >= n_timeslots:
continue
if not sg_free_excluding(sg_id, t1, ignore_ids) or not sg_free_excluding(sg_id, t2, ignore_ids):
continue
if not lec_free_excluding(ev_a.faculty_id, t1, ignore_ids) or not lec_free_excluding(ev_b.faculty_id, t2, ignore_ids):
continue
if not slot_ok_for_event(room_idx, t1, ev_a, ignore_ids):
continue
if not slot_ok_for_event(room_idx, t2, ev_b, ignore_ids):
continue
found = (room_idx, t1)
break
if found:
break
if found:
break
if found:
chromosome[positions[eid_a][0]][positions[eid_a][1]] = None
chromosome[positions[eid_b][0]][positions[eid_b][1]] = None
room_idx, t1 = found
chromosome[room_idx][t1] = eid_a
chromosome[room_idx][t1 + 1] = eid_b
changed_any = True
if not changed_any:
break
return chromosome
def reduce_extremely_late_classes(self, chromosome, max_total=10, max_per_group=1):
"""Post-processing repair to reduce 17:00 allocations (best effort).
Tries to MOVE events out of the last hour into earlier empty slots while respecting:
- break-time rules
- room suitability
- lecturer availability window
- no student-group overlap
- no lecturer overlap
Leaves events in place if no valid destination exists.
"""
hours = self.input_data.hours
last_hour_index = hours - 1
days = self.input_data.days
late_cells = [] # list[(room_idx, timeslot_idx, event_id, event, sg_id)]
late_by_group = {}
for day in range(days):
t_idx = day * hours + last_hour_index
if t_idx >= len(self.timeslots):
continue
for r_idx in range(len(self.rooms)):
event_id = chromosome[r_idx][t_idx]
if event_id is None:
continue
event = self.events_map.get(event_id)
if not event or not event.student_group:
continue
sg_id = event.student_group.id
late_cells.append((r_idx, t_idx, event_id, event, sg_id))
late_by_group[sg_id] = late_by_group.get(sg_id, 0) + 1
def should_move(sg_id: str, total_late: int) -> bool:
if late_by_group.get(sg_id, 0) > max_per_group:
return True
return total_late > max_total
total_late = len(late_cells)
if total_late == 0:
return chromosome
# Always try to reduce late classes as much as possible.
# We prioritize cap violations first, but continue trying to move remaining late classes too.
changed = True
while changed:
changed = False
total_late = len(late_cells)
# Prioritize moving groups that exceed per-group cap or global cap, then try others.
def _prio(cell):
_sg = cell[4]
return (
0 if should_move(_sg, total_late) else 1,
-late_by_group.get(_sg, 0)
)
late_cells.sort(key=_prio)
for (src_r, src_t, event_id, event, sg_id) in list(late_cells):
course = self.input_data.getCourse(event.course_id)
# Prefer moving earlier within the same day
day = src_t // hours
day_start = day * hours
candidate_t_idxs = [day_start + h for h in range(0, last_hour_index) if (day_start + h) < len(self.timeslots)]
moved = False
# Try same room first, then other rooms
room_order = [src_r] + [r for r in range(len(self.rooms)) if r != src_r]
for dst_r in room_order:
room_obj = self.rooms[dst_r]
if not self.is_room_suitable(room_obj, course):
continue
for dst_t in candidate_t_idxs:
if not self.is_slot_available_for_event(chromosome, dst_r, dst_t, event):
continue
if not self._is_student_group_available(chromosome, sg_id, dst_t):
continue
if event.faculty_id and not self._is_lecturer_available(chromosome, event.faculty_id, dst_t):
continue
chromosome[src_r][src_t] = None
chromosome[dst_r][dst_t] = event_id
moved = True
break
if moved:
break
if moved:
# update tracking
late_by_group[sg_id] = max(0, late_by_group.get(sg_id, 0) - 1)
late_cells.remove((src_r, src_t, event_id, event, sg_id))
changed = True
break
return chromosome
def reduce_lecturer_clashes(self, chromosome, max_passes=5):
"""Post-processing repair to reduce lecturer overlaps (best effort).
For each timeslot where the same lecturer appears more than once across rooms,
tries to move the extra events into safe empty slots.
"""
hours = self.input_data.hours
last_hour_index = hours - 1
for _pass in range(max_passes):
moved_any = False
for t_idx in range(len(self.timeslots)):
faculty_to_cells = {}
for r_idx in range(len(self.rooms)):
event_id = chromosome[r_idx][t_idx]
if event_id is None:
continue
event = self.events_map.get(event_id)
if not event or not event.faculty_id:
continue
faculty_to_cells.setdefault(event.faculty_id, []).append((r_idx, event_id, event))
for faculty_id, cells in faculty_to_cells.items():
if len(cells) <= 1:
continue
# Keep the first; relocate the rest
for (src_r, event_id, event) in cells[1:]:
course = self.input_data.getCourse(event.course_id)
sg_id = event.student_group.id if event.student_group else None
if sg_id is None:
continue
# Prefer same room, then any other suitable room
room_order = [src_r] + [r for r in range(len(self.rooms)) if r != src_r]
found = False
for dst_r in room_order:
room_obj = self.rooms[dst_r]
if not self.is_room_suitable(room_obj, course):
continue
for dst_t in range(len(self.timeslots)):
# Avoid creating new 17:00 placements if possible
if (dst_t % hours) == last_hour_index:
continue
if not self.is_slot_available_for_event(chromosome, dst_r, dst_t, event):
continue
if not self._is_student_group_available(chromosome, sg_id, dst_t):
continue
if not self._is_lecturer_available(chromosome, faculty_id, dst_t):
continue
chromosome[src_r][t_idx] = None
chromosome[dst_r][dst_t] = event_id
moved_any = True
found = True
break
if found:
break
if not moved_any:
break
return chromosome
@staticmethod
def _is_full_time_faculty(faculty) -> bool:
try:
status = str(getattr(faculty, 'status', '') or '').strip().lower()
except Exception:
status = ''
return any(token in status for token in ('full time', 'full-time', 'fulltime', 'full'))
def reduce_full_time_lecturer_workload_violations(self, chromosome, max_passes=6):
"""Move overloaded full-time lecturers' classes to other available days/times when possible."""
hours = int(self.input_data.hours)
days = int(self.input_data.days)
last_hour_index = hours - 1
def _day_of(t_idx: int) -> int:
return t_idx // hours
def _hour_of(t_idx: int) -> int:
return t_idx % hours
def _faculty_loads():
loads = {}
placements = {}
for r_idx in range(len(self.rooms)):
for t_idx in range(len(self.timeslots)):
event_id = chromosome[r_idx][t_idx]
if event_id is None:
continue
event = self.events_map.get(event_id)
if not event or not event.faculty_id:
continue
faculty = self.input_data.getFaculty(event.faculty_id)
if not faculty or not self._is_full_time_faculty(faculty):
continue
day_idx = _day_of(t_idx)
loads.setdefault(event.faculty_id, [0] * days)[day_idx] += 1
placements.setdefault(event.faculty_id, []).append((r_idx, t_idx, event_id, event, faculty))
return loads, placements
def _day_capacity(faculty, day_idx: int, event) -> bool:
day_abbr = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri'][day_idx] if day_idx < 5 else ''
try:
if not self._is_faculty_available_day(faculty, day_abbr):
return False
except Exception:
pass
try:
slot_hour = 8.5 + _hour_of(0)
except Exception:
slot_hour = 8.5
return True
for _pass in range(max_passes):
loads, placements = _faculty_loads()
if not loads:
break
moved_any = False
for faculty_id, day_loads in loads.items():
faculty = self.input_data.getFaculty(faculty_id)
if not faculty or not self._is_full_time_faculty(faculty):
continue
try:
max_hours_per_day = int(getattr(faculty, 'available_hours', 4) or 4)
max_consecutive_allowed = int(getattr(faculty, 'available_consecutive_hours', 3) or 3)
except Exception:
max_hours_per_day = 4
max_consecutive_allowed = 3
max_hours_per_day = max(2, min(8, max_hours_per_day))
max_consecutive_allowed = max(2, min(8, max_consecutive_allowed))
overloaded_days = [d for d, count in enumerate(day_loads) if count > max_hours_per_day]
if not overloaded_days:
continue
for src_day in overloaded_days:
candidate_events = [p for p in placements.get(faculty_id, []) if _day_of(p[1]) == src_day]
candidate_events.sort(key=lambda p: (_hour_of(p[1]) == last_hour_index, -_hour_of(p[1])))
for src_r, src_t, event_id, event, faculty_obj in candidate_events:
course = self.input_data.getCourse(event.course_id)
if course is None:
continue
# Choose another day with the lowest current load that is still available.
target_days = list(range(days))
target_days.sort(key=lambda d: day_loads[d])
moved = False
for dst_day in target_days:
if dst_day == src_day:
continue
if not self._is_faculty_available_day(faculty_obj, ['Mon', 'Tue', 'Wed', 'Thu', 'Fri'][dst_day] if dst_day < 5 else ''):
continue
# Prefer any available slot on the target day, excluding 17:00 if possible.
slots = list(range(dst_day * hours, (dst_day + 1) * hours))
slots.sort(key=lambda t: (_hour_of(t) == last_hour_index, _hour_of(t)))
for dst_t in slots:
if dst_t == src_t:
continue
if _hour_of(dst_t) == last_hour_index:
# allow as last resort, but keep it later in the ordering
pass
if not self._is_faculty_available_time(faculty_obj, 8.5 + _hour_of(dst_t), ['Mon', 'Tue', 'Wed', 'Thu', 'Fri'][dst_day] if dst_day < 5 else ''):
continue
for dst_r in range(len(self.rooms)):
if not self.is_room_suitable(self.rooms[dst_r], course):
continue
if chromosome[dst_r][dst_t] is not None:
continue
chromosome[src_r][src_t] = None
if self._can_place_event_id(chromosome, dst_r, dst_t, event_id):
chromosome[dst_r][dst_t] = event_id
moved_any = True
moved = True
break
chromosome[src_r][src_t] = event_id
chromosome[dst_r][dst_t] = None
if moved:
break
if moved:
break
if moved:
break
if moved_any:
break
if moved_any:
break
if not moved_any:
break
return chromosome
def print_timetable(self, individual, student_group, days, hours_per_day, day_start_time=8.5):
"""Print timetable for a specific student group"""
timetable = [["" for _ in range(days)] for _ in range(hours_per_day)]
# First, fill break time slots on Mon, Wed, Fri
break_hour = 4
if break_hour < hours_per_day:
for day in range(days):
if day in [0, 2, 4]: # Monday, Wednesday, Friday
timetable[break_hour][day] = "BREAK"
for room_idx, room_slots in enumerate(individual):
for timeslot_idx, event in enumerate(room_slots):
class_event = self.events_map.get(event)
if class_event is not None and class_event.student_group.id == student_group.id:
day = timeslot_idx // hours_per_day
hour = timeslot_idx % hours_per_day
# Check if it's a break slot that should be skipped in the display
is_display_break = (hour == break_hour and day in [0, 2, 4])
if day < days and not is_display_break:
course = self.input_data.getCourse(class_event.course_id)
faculty = self.input_data.getFaculty(class_event.faculty_id)
course_code = course.code if course is not None else "Unknown"
faculty_name = faculty.name if faculty is not None else "Unknown"
room_obj = self.input_data.rooms[room_idx]
room_display = getattr(room_obj, "name", getattr(room_obj, "Id", str(room_idx)))
timetable[hour][day] = f"Course: {course_code}, Lecturer: {faculty_name}, Room: {room_display}"
return timetable
def print_all_timetables(self, individual, days, hours_per_day, day_start_time=8.5):
"""Generate all timetables for the solution"""
def _format_time_label(hour_value) -> str:
try:
total_minutes = int(round(float(hour_value) * 60))
hh = (total_minutes // 60) % 24
mm = total_minutes % 60
return f"{hh:02d}:{mm:02d}"
except Exception:
return str(hour_value)
data = []
student_groups = self.input_data.student_groups
for student_group in student_groups:
timetable = self.print_timetable(individual, student_group, days, hours_per_day, day_start_time)
rows = []
for hour in range(hours_per_day):
time_label = _format_time_label(float(day_start_time) + float(hour))
row = [time_label] + [timetable[hour][day] for day in range(days)]
rows.append(row)
data.append({"student_group": student_group, "timetable": rows})
return data
def verify_and_repair_course_allocations(self, chromosome):
"""
Verify that all courses appear the correct number of times for each student group
and repair any missing allocations with minimal disruption.
"""
max_repair_passes = 6
n_rooms = len(self.rooms)
n_timeslots = len(self.timeslots)
total_events = len(self.events_list)
# Helper: build a fast lookup of suitable rooms for a given required room type.
rooms_by_type = {}
for r_idx, room in enumerate(self.rooms):
rooms_by_type.setdefault(getattr(room, 'room_type', None), []).append(r_idx)
for _ in range(max_repair_passes):
# 1) Remove duplicate placements of the *same event*.
# Duplicates can fully occupy the timetable, leaving no empty slots for genuinely missing events.
scheduled_events = set()
student_group_busy = [set() for _ in range(n_timeslots)]
lecturer_busy = [set() for _ in range(n_timeslots)]
course_day_room_mapping = {} # (course_id, day_idx, student_group_id) -> room_idx
for r_idx in range(n_rooms):
for t_idx in range(n_timeslots):
event_id = chromosome[r_idx][t_idx]
if event_id is None:
continue
if event_id in scheduled_events:
chromosome[r_idx][t_idx] = None
continue
scheduled_events.add(event_id)
event = self.events_map.get(event_id)
if not event:
continue
sg_id = event.student_group.id
student_group_busy[t_idx].add(sg_id)
if event.faculty_id is not None:
lecturer_busy[t_idx].add(event.faculty_id)
day_idx = t_idx // self.input_data.hours
course_day_room_mapping[(event.course_id, day_idx, sg_id)] = r_idx
missing_events = [event_id for event_id in range(total_events) if event_id not in scheduled_events]
if not missing_events:
break
# 2) Index empty slots to speed up placement.
empty_by_room_day = {} # (room_idx, day_idx) -> list[t_idx]
for r_idx in range(n_rooms):
for t_idx in range(n_timeslots):
if chromosome[r_idx][t_idx] is None:
day_idx = t_idx // self.input_data.hours
empty_by_room_day.setdefault((r_idx, day_idx), []).append(t_idx)
random.shuffle(missing_events)
for missing_event_id in missing_events:
event = self.events_list[missing_event_id]
course = self.input_data.getCourse(event.course_id)
if not course:
continue
required_type = getattr(course, 'required_room_type', None)
suitable_rooms = rooms_by_type.get(required_type, [])
if not suitable_rooms:
continue
sg_id = event.student_group.id
faculty_id = event.faculty_id
placed = False
def slot_ok(room_idx: int, timeslot_idx: int, *, relax_faculty: bool = False) -> bool:
if sg_id in student_group_busy[timeslot_idx]:
return False
if faculty_id is not None and faculty_id in lecturer_busy[timeslot_idx]:
return False
return self.is_slot_available_for_event(
chromosome,
room_idx,
timeslot_idx,
event,
ignore_faculty_availability=relax_faculty,
)
# Strategy 1: Prefer same room as the same course for this group on that day.
days_order = list(range(self.input_data.days))
random.shuffle(days_order)
for day_idx in days_order:
preferred_room = course_day_room_mapping.get((event.course_id, day_idx, sg_id))
if preferred_room is None:
continue
if preferred_room not in suitable_rooms:
continue
for t_idx in list(empty_by_room_day.get((preferred_room, day_idx), [])):
if slot_ok(preferred_room, t_idx):
chromosome[preferred_room][t_idx] = missing_event_id
student_group_busy[t_idx].add(sg_id)
if faculty_id is not None:
lecturer_busy[t_idx].add(faculty_id)
scheduled_events.add(missing_event_id)
empty_by_room_day[(preferred_room, day_idx)].remove(t_idx)
course_day_room_mapping[(event.course_id, day_idx, sg_id)] = preferred_room
placed = True
break
if placed:
break
# Strategy 2: Any suitable room/day empty slot.
if not placed:
rooms_order = suitable_rooms[:]
random.shuffle(rooms_order)
for room_idx in rooms_order:
days_order = list(range(self.input_data.days))
random.shuffle(days_order)
for day_idx in days_order:
key = (room_idx, day_idx)
if key not in empty_by_room_day:
continue
for t_idx in list(empty_by_room_day[key]):
if slot_ok(room_idx, t_idx):
chromosome[room_idx][t_idx] = missing_event_id
student_group_busy[t_idx].add(sg_id)
if faculty_id is not None:
lecturer_busy[t_idx].add(faculty_id)
scheduled_events.add(missing_event_id)
empty_by_room_day[key].remove(t_idx)
course_day_room_mapping[(event.course_id, day_idx, sg_id)] = room_idx
placed = True
break
if placed:
break
if placed:
break
# If we still can't place it, leave it missing for this pass; a later pass
# may open up additional empty slots after more duplicate removals.
# Strategy 3 (last resort): relax lecturer availability windows so we never drop classes.
if not placed:
rooms_order = suitable_rooms[:]
random.shuffle(rooms_order)
for room_idx in rooms_order:
days_order = list(range(self.input_data.days))
random.shuffle(days_order)
for day_idx in days_order:
key = (room_idx, day_idx)
if key not in empty_by_room_day:
continue
for t_idx in list(empty_by_room_day[key]):
if slot_ok(room_idx, t_idx, relax_faculty=True):
chromosome[room_idx][t_idx] = missing_event_id
student_group_busy[t_idx].add(sg_id)
if faculty_id is not None:
lecturer_busy[t_idx].add(faculty_id)
scheduled_events.add(missing_event_id)
empty_by_room_day[key].remove(t_idx)
course_day_room_mapping[(event.course_id, day_idx, sg_id)] = room_idx
placed = True
break
if placed:
break
if placed:
break
return chromosome
def count_course_occurrences(self, chromosome, student_group):
"""Count how many times each course appears for a specific student group"""
course_counts = {}
for room_idx in range(len(self.rooms)):
for timeslot_idx in range(len(self.timeslots)):
event_id = chromosome[room_idx][timeslot_idx]
if event_id is not None:
event = self.events_map.get(event_id)
if event and event.student_group.id == student_group.id:
course_id = event.course_id
course_counts[course_id] = course_counts.get(course_id, 0) + 1
return course_counts
def diagnose_course_allocations(self, chromosome):
"""Diagnostic method to check course allocations for debugging"""
print("\n=== COURSE ALLOCATION DIAGNOSIS ===")
# Count total scheduled events
scheduled_events = set()
for room_idx in range(len(self.rooms)):
for timeslot_idx in range(len(self.timeslots)):
event_id = chromosome[room_idx][timeslot_idx]
if event_id is not None:
scheduled_events.add(event_id)
print(f"Total events: {len(self.events_list)}")
print(f"Scheduled events: {len(scheduled_events)}")
print(f"Missing events: {len(self.events_list) - len(scheduled_events)}")
# Check each student group
for student_group in self.student_groups:
print(f"\nStudent Group: {student_group.name}")
course_counts = self.count_course_occurrences(chromosome, student_group)
total_expected = sum(student_group.hours_required)
total_actual = sum(course_counts.values())
print(f" Total hours: Expected {total_expected}, Got {total_actual}")
for i, course_id in enumerate(student_group.courseIDs):
expected = student_group.hours_required[i]
actual = course_counts.get(course_id, 0)
status = "✓" if actual == expected else "✗"
print(f" {course_id}: Expected {expected}, Got {actual} {status}")
print("=== END DIAGNOSIS ===\n")
# differential_evolution_api.py
"""
API-compatible differential evolution algorithm that works with input_data instances
passed from the Flask application instead of static imports.
"""
import random
from typing import List
import copy
from utils import Utility
from entitities.Class import Class
import numpy as np
from constraints import Constraints
import re
class DifferentialEvolution:
def __init__(self, input_data, pop_size: int, F: float, CR: float):
self.desired_fitness = 0
self.input_data = input_data
self.rooms = input_data.rooms
self.timeslots = input_data.create_time_slots(
no_hours_per_day=input_data.hours,
no_days_per_week=input_data.days,
day_start_time=8.5
)
self.student_groups = input_data.student_groups
self.courses = input_data.courses
self.events_list, self.events_map = self.create_events()
self.pop_size = pop_size
self.F = F
self.CR = CR
self.constraints = Constraints(input_data)
# If True, treat soft constraints as hard (must be 0 to accept improvements).
# This is used by the "strict-if-possible" probe and strict runs.
self.strict_mode = False
# Optimization: Cache fitness values to avoid recalculation
self.fitness_cache = {}
# Optimization: Pre-calculate building assignments for rooms to speed up evaluation
self.room_building_cache = {}
for idx, room in enumerate(self.rooms):
self.room_building_cache[idx] = self.get_room_building(room)
# Optimization: Pre-calculate SST groups (explicit building first; keywords as fallback).
self.engineering_groups = {sg.id for sg in self.student_groups if getattr(sg, 'is_sst', False)}
self.population = self.initialize_population()
def set_strict_mode(self, enabled: bool) -> None:
self.strict_mode = bool(enabled)
def _hard_constraint_keys(self) -> list[str]:
"""Constraint keys that are prioritized lexicographically during selection.
In normal mode, only true hard constraints are included.
In strict mode, soft constraints are also treated as hard.
"""
base = [
'student_group_constraints',
'lecturer_availability',
'course_allocation_completeness',
'room_time_conflict',
'break_time_constraint',
'room_constraints',
'same_course_same_room_per_day',
'lecturer_schedule_constraints',
'building_assignments',
'no_free_day',
'consecutive_timeslots',
]
if not self.strict_mode:
return base
# Treat soft constraints as hard when strict_mode is enabled.
return base + [
'single_event_per_day',
'three_unit_split_across_days_TYD',
'spread_events',
'extremely_late_classes',
'lecturer_workload_constraints',
]
def _can_place_event_id(
self,
chromosome,
room_idx: int,
timeslot_idx: int,
event_id,
*,
ignore_event_ids=None,
ignore_faculty_availability: bool = False,
) -> bool:
"""Return True if event_id can be placed at (room_idx, timeslot_idx) without violating
immediate feasibility checks.
This is a local feasibility gate used by mutation/crossover so they don't introduce
obvious hard violations (room suitability, break time, building rule, lecturer windows,
and same-timeslot lecturer/group overlaps).