ACO_Scheduling.py

import json
import random
import numpy as np
import os
from pathlib import Path
import matplotlib.pyplot as plt

# Create results directory structure
def create_co_results_structure():
    """Create directory structure for CO algorithm results."""
    base_dir = Path("results_CO")
    subdirs = [
        "aco_results",
        "bco_results", 
        "comparison_charts",
        "2d_projections",
        "3d_pareto_fronts",
        "pairwise_plots",
        "pareto_tables",
        "research_tables",
        "summary_statistics",
        "convergence_plots"
    ]
    
    for subdir in subdirs:
        (base_dir / subdir).mkdir(parents=True, exist_ok=True)
    
    return base_dir

# --- Class Definitions (copied from Genetic_Algorithm_Scheduling.ipynb) ---
class Space:
    def __init__(self, *args):
        self.code = args[0]
        self.size = args[1]

    def __repr__(self):
        return f"Space(code={self.code}, size={self.size})"

class Group:
    def __init__(self, *args):
        self.id = args[0]
        self.size = args[1]

    def __repr__(self):
        return f"Group(id={self.id}, size={self.size})"

class Activity:
    def __init__(self, id, *args):
        self.id = id
        self.subject = args[0]
        self.teacher_id = args[1]
        self.group_ids = args[2]
        self.duration = args[3]

    def __repr__(self):
        return f"Activity(id={self.id}, subject={self.subject}, teacher_id={self.teacher_id}, group_ids={self.group_ids}, duration={self.duration})"

class Lecturer:
    def __init__(self, id, first_name, last_name, username, department):
        self.id = id
        self.first_name = first_name
        self.last_name = last_name
        self.username = username
        self.department = department

    def __repr__(self):
        return f"Lecturer(id={self.id}, name={self.first_name} {self.last_name}, department={self.department})"

# --- Data Loading (copied from Genetic_Algorithm_Scheduling.ipynb) ---
with open('sliit_computing_dataset.json', 'r') as file:
    data = json.load(file)

spaces_dict = {}
groups_dict = {}
activities_dict = {}
lecturers_dict = {}
slots = []

for space in data['spaces']:
    spaces_dict[space['code']] = Space(space['code'], space['capacity'])

for group in data['years']:
    groups_dict[group['id']] = Group(group['id'], group['size'])

# Assuming 'teacher_ids' is a list and we take the first one as in the GA.
# Also, 'subgroup_ids' from JSON is mapped to 'group_ids' in Activity class.
for activity in data['activities']:
    activities_dict[activity['code']] = Activity(
        activity['code'], 
        activity['subject'], 
        activity['teacher_ids'][0] if activity['teacher_ids'] else None, # Handle empty teacher_ids
        activity['subgroup_ids'], 
        activity['duration']
    )

for user in data["users"]:
    if user["role"] == "lecturer":
        lecturers_dict[user["id"]] = Lecturer(
            user["id"], user["first_name"], user["last_name"], user["username"], user["department"]
        )

for day in ["MON", "TUE", "WED", "THU", "FRI"]:
    for id_num in range(1, 9): # Corrected variable name from 'id' to 'id_num'
        slots.append(day + str(id_num))

# --- Helper function to get class size (can be adapted from GA) ---
def get_class_size(activity_code, groups_data):
    """Computes total class size for an activity by summing the sizes of associated groups."""
    activity = activities_dict.get(activity_code)
    if not activity:
        return 0
    
    total_size = 0
    for group_id in activity.group_ids:
        group = groups_data.get(group_id)
        if group:
            total_size += group.size
    return total_size

# --- Exact Evaluation Functions from GA Notebook ---
def evaluate_hard_constraints(schedule):
    """
    Evaluates hard constraints and returns a tuple of:
    (total_violations, vacant_rooms, lecturer_conflicts, room_capacity_violations, 
     student_group_conflicts, unassigned_activities)
    """
    vacant_rooms = 0
    lecturer_conflicts = 0
    room_capacity_violations = 0
    student_group_conflicts = 0
    unassigned_activities = 0
    
    # Count vacant rooms (rooms not used at all)
    used_rooms = set()
    for slot_data in schedule.values():
        for room_code, activity in slot_data.items():
            if activity is not None:
                used_rooms.add(room_code)
    vacant_rooms = len(spaces_dict) - len(used_rooms)
    
    # Count unassigned activities
    scheduled_activities = set()
    for slot_data in schedule.values():
        for activity in slot_data.values():
            if activity is not None:
                scheduled_activities.add(activity.id)
    unassigned_activities = len(activities_dict) - len(scheduled_activities)
    
    # Check lecturer conflicts, room capacity, and student group conflicts
    for slot, room_assignments in schedule.items():
        slot_lecturers = set()
        slot_groups = set()
        
        for room_code, activity in room_assignments.items():
            if activity is not None:
                # Check room capacity
                class_size = get_class_size(activity.id, groups_dict)
                room_capacity = spaces_dict[room_code].size
                if class_size > room_capacity:
                    room_capacity_violations += 1
                
                # Check lecturer conflicts
                if activity.teacher_id:
                    if activity.teacher_id in slot_lecturers:
                        lecturer_conflicts += 1
                    else:
                        slot_lecturers.add(activity.teacher_id)
                
                # Check student group conflicts
                for group_id in activity.group_ids:
                    if group_id in slot_groups:
                        student_group_conflicts += 1
                    else:
                        slot_groups.add(group_id)
    
    total_violations = vacant_rooms + lecturer_conflicts + room_capacity_violations + student_group_conflicts + unassigned_activities
    
    print("=== Hard Constraint Evaluation ===")
    print(f"Vacant Rooms: {vacant_rooms}")
    print(f"Lecturer Conflicts: {lecturer_conflicts}")
    print(f"Room Capacity Violations: {room_capacity_violations}")
    print(f"Student Group Conflicts: {student_group_conflicts}")
    print(f"Unassigned Activities: {unassigned_activities}")
    print(f"Total Hard Constraint Violations: {total_violations}")
    print()
    
    return total_violations, vacant_rooms, lecturer_conflicts, room_capacity_violations, student_group_conflicts, unassigned_activities

def evaluate_soft_constraints(schedule):
    """
    Evaluates soft constraints and returns a normalized score between 0-1 (higher is better).
    Also returns individual component scores.
    """
    # Student metrics
    student_fatigue = 0
    student_idle_time = 0
    student_lecture_spread = 0
    
    # Lecturer metrics  
    lecturer_fatigue = 0
    lecturer_idle_time = 0
    lecturer_lecture_spread = 0
    lecturer_workload_balance = 0
    
    # Calculate student metrics per group
    for group_id, group in groups_dict.items():
        group_schedule = []
        for slot in slots:
            has_class = False
            for room_assignments in schedule[slot].values():
                if room_assignments and group_id in room_assignments.group_ids:
                    has_class = True
                    break
            group_schedule.append(has_class)
        
        # Student fatigue (consecutive classes)
        consecutive_count = 0
        max_consecutive = 0
        for has_class in group_schedule:
            if has_class:
                consecutive_count += 1
                max_consecutive = max(max_consecutive, consecutive_count)
            else:
                consecutive_count = 0
        student_fatigue += max_consecutive
        
        # Student idle time (gaps between classes)
        idle_gaps = 0
        in_session = False
        for has_class in group_schedule:
            if has_class:
                in_session = True
            elif in_session and not has_class:
                idle_gaps += 1
        student_idle_time += idle_gaps
        
        # Student lecture spread (distribution across days)
        daily_classes = [0, 0, 0, 0, 0]  # Mon-Fri
        for i, has_class in enumerate(group_schedule):
            if has_class:
                daily_classes[i // 8] += 1
        non_zero_days = sum(1 for day in daily_classes if day > 0)
        student_lecture_spread += non_zero_days
    
    # Calculate lecturer metrics
    for lecturer_id, lecturer in lecturers_dict.items():
        lecturer_schedule = []
        for slot in slots:
            has_class = False
            for room_assignments in schedule[slot].values():
                if room_assignments and room_assignments.teacher_id == lecturer_id:
                    has_class = True
                    break
            lecturer_schedule.append(has_class)
        
        # Lecturer fatigue (consecutive classes)
        consecutive_count = 0
        max_consecutive = 0
        for has_class in lecturer_schedule:
            if has_class:
                consecutive_count += 1
                max_consecutive = max(max_consecutive, consecutive_count)
            else:
                consecutive_count = 0
        lecturer_fatigue += max_consecutive
        
        # Lecturer idle time
        idle_gaps = 0
        in_session = False
        for has_class in lecturer_schedule:
            if has_class:
                in_session = True
            elif in_session and not has_class:
                idle_gaps += 1
        lecturer_idle_time += idle_gaps
        
        # Lecturer spread
        daily_classes = [0, 0, 0, 0, 0]
        for i, has_class in enumerate(lecturer_schedule):
            if has_class:
                daily_classes[i // 8] += 1
        non_zero_days = sum(1 for day in daily_classes if day > 0)
        lecturer_lecture_spread += non_zero_days
    
    # Lecturer workload balance
    lecturer_workloads = []
    for lecturer_id in lecturers_dict.keys():
        workload = 0
        for slot_data in schedule.values():
            for activity in slot_data.values():
                if activity and activity.teacher_id == lecturer_id:
                    workload += activity.duration
        lecturer_workloads.append(workload)
    
    if lecturer_workloads:
        workload_std = np.std(lecturer_workloads)
        workload_mean = np.mean(lecturer_workloads)
        lecturer_workload_balance = workload_std / (workload_mean + 1e-6)
    
    # Normalize metrics (lower values are better, so we invert them)
    num_groups = len(groups_dict)
    num_lecturers = len(lecturers_dict)
    
    # Normalize to 0-1 scale (higher is better)
    student_fatigue_norm = 1 - min(student_fatigue / (num_groups * 8), 1)  # Max 8 consecutive
    student_idle_norm = 1 - min(student_idle_time / (num_groups * 20), 1)  # Max 20 gaps
    student_spread_norm = (student_lecture_spread / (num_groups * 5)) if num_groups > 0 else 0  # Max 5 days
    
    lecturer_fatigue_norm = 1 - min(lecturer_fatigue / (num_lecturers * 8), 1)
    lecturer_idle_norm = 1 - min(lecturer_idle_time / (num_lecturers * 20), 1)
    lecturer_spread_norm = (lecturer_lecture_spread / (num_lecturers * 5)) if num_lecturers > 0 else 0
    lecturer_balance_norm = 1 - min(int(lecturer_workload_balance / 5), 1)  # Normalize workload balance
    
    # Weighted final score
    weights = {
        'student_fatigue': 0.15,
        'student_idle': 0.10,
        'student_spread': 0.15,
        'lecturer_fatigue': 0.15,
        'lecturer_idle': 0.10,
        'lecturer_spread': 0.15,
        'lecturer_balance': 0.20
    }
    
    final_score = (
        weights['student_fatigue'] * student_fatigue_norm +
        weights['student_idle'] * student_idle_norm +
        weights['student_spread'] * student_spread_norm +
        weights['lecturer_fatigue'] * lecturer_fatigue_norm +
        weights['lecturer_idle'] * lecturer_idle_norm +
        weights['lecturer_spread'] * lecturer_spread_norm +
        weights['lecturer_balance'] * lecturer_balance_norm
    )
    
    print("=== Soft Constraint Evaluation ===")
    print(f"Student Fatigue Score: {student_fatigue_norm:.3f}")
    print(f"Student Idle Time Score: {student_idle_norm:.3f}")
    print(f"Student Lecture Spread Score: {student_spread_norm:.3f}")
    print(f"Lecturer Fatigue Score: {lecturer_fatigue_norm:.3f}")
    print(f"Lecturer Idle Time Score: {lecturer_idle_norm:.3f}")
    print(f"Lecturer Lecture Spread Score: {lecturer_spread_norm:.3f}")
    print(f"Lecturer Workload Balance Score: {lecturer_balance_norm:.3f}")
    print(f"Overall Soft Constraint Score: {final_score:.3f}")
    print()
    
    return final_score, {
        'student_fatigue': student_fatigue_norm,
        'student_idle': student_idle_norm,
        'student_spread': student_spread_norm,
        'lecturer_fatigue': lecturer_fatigue_norm,
        'lecturer_idle': lecturer_idle_norm,
        'lecturer_spread': lecturer_spread_norm,
        'lecturer_balance': lecturer_balance_norm
    }

# --- ACO Algorithm Components ---
class Ant:
    def __init__(self, aco_instance):
        self.aco = aco_instance
        # Timetable: {slot_code: {room_code: Activity_object or None}}
        self.timetable = {slot: {room_code: None for room_code in self.aco.rooms.keys()} for slot in self.aco.slots}
        self.fitness = float('inf') # Assuming minimization of a cost function
        self.unassigned_activities = [] # List of Activity objects that couldn't be scheduled

    def construct_solution(self):
        """Constructs a timetable by assigning activities to slots and rooms."""
        activities_to_schedule = list(self.aco.activities.values()) # Work with copies or a fresh list
        random.shuffle(activities_to_schedule) # Introduce randomness in processing order

        for activity in activities_to_schedule:
            assigned_successfully = False
            possible_assignments = self._get_possible_assignments_for_activity(activity)

            if not possible_assignments:
                self.unassigned_activities.append(activity)
                continue

            # Ant makes a choice based on pheromone and heuristic
            chosen_slot, chosen_room = self.aco.select_next_move(activity, possible_assignments)

            if chosen_slot and chosen_room:
                # Assign the activity for its entire duration
                start_slot_index = self.aco.slots.index(chosen_slot)
                for i in range(activity.duration):
                    current_slot_idx_in_list = start_slot_index + i
                    if current_slot_idx_in_list < len(self.aco.slots):
                        slot_code_for_segment = self.aco.slots[current_slot_idx_in_list]
                        self.timetable[slot_code_for_segment][chosen_room] = activity # Assign activity object
                    else:
                        # Not enough contiguous slots available towards the end of the schedule
                        # This should ideally be caught by _get_possible_assignments_for_activity
                        assigned_successfully = False 
                        self.unassigned_activities.append(activity) # Mark as unassigned if full duration cannot be met
                        # Backtrack or remove partially assigned parts if any were made before this check
                        for j in range(i): # Remove already placed segments of this activity
                            self.timetable[self.aco.slots[start_slot_index+j]][chosen_room] = None
                        break 
                assigned_successfully = True # If loop completed
            
            if not assigned_successfully:
                 if activity not in self.unassigned_activities: # Ensure it's added if not already
                    self.unassigned_activities.append(activity)

        # Evaluate the constructed timetable
        self.fitness = self.aco.evaluator(self.timetable, self.unassigned_activities)
        return self.timetable

    def _get_possible_assignments_for_activity(self, activity):
        """ Find all valid (slot, room) combinations for the start of an activity,
            considering its full duration and hard constraints.
        """
        valid_starting_points = []
        activity_class_size = get_class_size(activity.id, self.aco.groups)
        
        for r_code, room_obj in self.aco.rooms.items():
            if room_obj.size < activity_class_size:
                continue # Skip room if capacity is too small

            for i in range(len(self.aco.slots) - activity.duration + 1):
                start_slot_code = self.aco.slots[i]
                can_place_activity = True
                temp_assignment_block_for_check = {}

                # Check if all segments of the activity can be placed contiguously and without conflict
                for j in range(activity.duration):
                    current_segment_slot_code = self.aco.slots[i+j]
                    
                    # 1. Check if room is already taken by another activity in the ant's current partial timetable
                    if self.timetable[current_segment_slot_code][r_code] is not None:
                        can_place_activity = False
                        break
                    
                    # 2. Check hard constraints (lecturer, group) against the ant's current partial timetable
                    # The check_hard_constraints function will need to be aware of the ant's partial timetable state
                    # We are checking the placement of *this* activity, so current_timetable is the ant's view *before* placing this activity.
                    # For the purpose of this check, imagine adding this segment to an empty block first.
                    temp_segment_assignment = {current_segment_slot_code: {r_code: activity}} 
                    if self.aco.check_hard_constraints(activity, current_segment_slot_code, r_code, self.timetable, temp_segment_assignment, is_placement_check=True) > 0:
                        can_place_activity = False
                        break
                
                if can_place_activity:
                    valid_starting_points.append((start_slot_code, r_code))
                    
        return valid_starting_points

class ACO:
    def __init__(self, activities_dict, slots_list, spaces_dict, lecturers_dict, groups_dict, 
                 n_ants, n_iterations, alpha, beta, evaporation_rate, q0=0.1, initial_pheromone=0.1):
        self.activities = activities_dict
        self.slots = slots_list
        self.rooms = spaces_dict
        self.lecturers = lecturers_dict
        self.groups = groups_dict
        self.n_ants = n_ants
        self.n_iterations = n_iterations
        self.alpha = alpha
        self.beta = beta
        self.evaporation_rate = evaporation_rate
        self.q0 = q0 
        self.initial_pheromone = initial_pheromone
        self.pheromone_trails = {}
        self.best_timetable_so_far = None
        self.best_fitness_so_far = float('inf')
        
        # For tracking convergence and statistics
        self.convergence_data = []
        self.iteration_stats = []
        self.fitness_history = []
        self.best_fitness_history = []
        # print("ACO Initialized") # Debug print

    def initialize_pheromones(self):
        """Initializes pheromone trails for all possible (activity_id, slot_code, room_code) combinations."""
        for activity_id in self.activities.keys():
            for slot_code in self.slots:
                for room_code in self.rooms.keys():
                    self.pheromone_trails[(activity_id, slot_code, room_code)] = self.initial_pheromone

    def run(self):
        """Main loop of the ACO algorithm."""
        print(f"ACO starting with {self.n_iterations} iterations and {self.n_ants} ants per iteration.")
        self.best_timetable_so_far = None
        self.best_fitness_so_far = float('inf')
        best_iteration = -1

        for iteration in range(self.n_iterations):
            ants = [Ant(self) for _ in range(self.n_ants)]
            current_iteration_best_fitness = float('inf')
            current_iteration_best_ant_idx = -1
            iteration_fitness_values = []

            for ant_idx, ant in enumerate(ants):
                ant.construct_solution()
                iteration_fitness_values.append(ant.fitness)
                
                if ant.fitness < self.best_fitness_so_far:
                    self.best_fitness_so_far = ant.fitness
                    self.best_timetable_so_far = {s: r.copy() for s, r in ant.timetable.items()}
                    best_iteration = iteration + 1
                    print(f"    New global best! Iteration {iteration+1}, Ant {ant_idx+1}. Fitness: {self.best_fitness_so_far}, Unassigned: {len(ant.unassigned_activities)}")
                    
                if ant.fitness < current_iteration_best_fitness:
                    current_iteration_best_fitness = ant.fitness
                    current_iteration_best_ant_idx = ant_idx
            
            # Collect statistics for this iteration
            iteration_stats = {
                'iteration': iteration + 1,
                'best_fitness': current_iteration_best_fitness,
                'worst_fitness': max(iteration_fitness_values),
                'mean_fitness': np.mean(iteration_fitness_values),
                'std_fitness': np.std(iteration_fitness_values),
                'median_fitness': np.median(iteration_fitness_values)
            }
            self.iteration_stats.append(iteration_stats)
            self.fitness_history.extend(iteration_fitness_values)
            self.best_fitness_history.append(self.best_fitness_so_far)
            
            self.update_pheromones(ants)
            print(f"Iteration {iteration+1} complete. Iteration best fitness: {current_iteration_best_fitness} (Ant {current_iteration_best_ant_idx+1}). Global best: {self.best_fitness_so_far}")
        
        print("ACO finished.")
        if self.best_timetable_so_far:
            print(f"Final best solution fitness: {self.best_fitness_so_far}")
            print(f"Best solution found at iteration: {best_iteration}")
        else:
            print("No feasible solution found by ACO.")
        return self.best_timetable_so_far, self.best_fitness_so_far, best_iteration

    def update_pheromones(self, ants):
        """Updates pheromone trails: evaporation and deposition."""
        # Evaporation
        for path in self.pheromone_trails:
            self.pheromone_trails[path] *= (1 - self.evaporation_rate)

        # Deposition for the best ant in the iteration or all ants (common variants)
        # Here, let's allow all ants to deposit pheromone proportional to their solution quality.
        for ant in ants:
            if ant.fitness == float('inf') or not hasattr(ant, 'timetable'):
                continue
            
            pheromone_increase = 1.0 / (ant.fitness + 1e-6) # Fitness is cost, so inverse
            processed_activities_for_deposit = set()

            for slot_code_iter, room_assignments_iter in ant.timetable.items():
                for room_code_iter, activity_obj_iter in room_assignments_iter.items():
                    if activity_obj_iter and activity_obj_iter.id not in processed_activities_for_deposit:
                        # Determine the actual starting slot of this activity instance
                        actual_start_slot = slot_code_iter # Default for duration 1
                        is_first_segment = True
                        current_slot_idx = self.slots.index(slot_code_iter)
                        if current_slot_idx > 0: # Check previous slot if not the first slot of the day/week
                           if ant.timetable[self.slots[current_slot_idx-1]].get(room_code_iter) == activity_obj_iter:
                               is_first_segment = False # This is not the starting segment
                        
                        if is_first_segment:
                            path_to_update = (activity_obj_iter.id, actual_start_slot, room_code_iter)
                            if path_to_update in self.pheromone_trails:
                                self.pheromone_trails[path_to_update] += pheromone_increase
                            else:
                                # Path should exist from initialization
                                self.pheromone_trails[path_to_update] = self.initial_pheromone + pheromone_increase
                            # Optional: Bound pheromones (min/max values)
                            # self.pheromone_trails[path_to_update] = max(self.min_pheromone, self.pheromone_trails[path_to_update])
                            # self.pheromone_trails[path_to_update] = min(self.max_pheromone, self.pheromone_trails[path_to_update])
                            processed_activities_for_deposit.add(activity_obj_iter.id)

    def select_next_move(self, activity, possible_assignments):
        """Selects (slot, room) for an activity. `possible_assignments` is list of (slot_code, room_code)."""
        if not possible_assignments:
            return None, None

        if random.random() < self.q0: # ACS Exploitation
            best_value = -1.0
            choice = None
            for slot_c, room_c in possible_assignments:
                pheromone_val = self.pheromone_trails.get((activity.id, slot_c, room_c), self.initial_pheromone)
                heuristic_val = self.calculate_heuristic_value(activity, slot_c, room_c, {})
                current_value = pheromone_val * (heuristic_val ** self.beta) # Alpha often 1 here
                if current_value > best_value:
                    best_value = current_value
                    choice = (slot_c, room_c)
            return choice if choice else random.choice(possible_assignments) # Fallback
        else: # Probabilistic Exploration (Roulette Wheel)
            choices_data = []
            sum_probabilities = 0.0
            for slot_c, room_c in possible_assignments:
                pheromone_val = self.pheromone_trails.get((activity.id, slot_c, room_c), self.initial_pheromone)
                heuristic_val = self.calculate_heuristic_value(activity, slot_c, room_c, {})
                heuristic_val = max(heuristic_val, 1e-5) # Ensure positive heuristic
                prob_val = (pheromone_val ** self.alpha) * (heuristic_val ** self.beta)
                choices_data.append({'slot': slot_c, 'room': room_c, 'prob': prob_val})
                sum_probabilities += prob_val
            
            if sum_probabilities == 0:
                return random.choice(possible_assignments) # If all are equally zero
            
            rand_num = random.random() * sum_probabilities
            cumulative_prob = 0.0
            for data in choices_data:
                cumulative_prob += data['prob']
                if rand_num <= cumulative_prob:
                    return data['slot'], data['room']
            return random.choice(possible_assignments) # Fallback

    def calculate_heuristic_value(self, activity, slot_code, room_code, current_timetable_state_for_heuristic):
        """Calculates heuristic desirability (higher is better)."""
        penalty = 0.0
        activity_class_size = get_class_size(activity.id, self.groups)
        room = self.rooms.get(room_code)
        if not room: return 1e-5 # Room code not found, very low heuristic

        if room.size < activity_class_size:
            penalty += 100.0 
        elif room.size > activity_class_size * 3: # Penalize largely oversized rooms more
            penalty += (room.size - activity_class_size * 2.0) * 0.1

        slot_numeric_part = int(slot_code[-1]) # MON1 -> 1
        if slot_numeric_part > 7: # Prefer earlier slots in a day (e.g., 8th slot)
            penalty += 1.0
        if "FRI" in slot_code and slot_numeric_part > 4: # Penalize Friday afternoon heavily
            penalty += 5.0
        
        # Heuristic is inverse of (1 + penalty)
        heuristic_value = 1.0 / (1.0 + penalty)
        return max(heuristic_value, 1e-5) # Ensure it's a small positive float

    def evaluator(self, timetable, unassigned_activities_list):
        """Evaluates timetable fitness (lower is better)."""
        h_violations = 0.0 # Use float for penalties
        s_penalties = 0.0 # For soft constraints
        h_violations += len(unassigned_activities_list) * 1000.0

        lecturer_usage = {lect_id: set() for lect_id in self.lecturers.keys()}
        group_usage = {group_id: set() for group_id in self.groups.keys()}
        # This map is to check if different activities are assigned to the same room-slot by the ant.
        room_slot_activity_check = {slot: {r_code: None for r_code in self.rooms.keys()} for slot in self.slots}
        processed_acts_eval = set() # To evaluate each distinct activity instance once for multi-slot properties

        for s_code_loop, r_assignments_loop in timetable.items():
            for r_code_loop, act_obj_loop in r_assignments_loop.items():
                if not act_obj_loop or act_obj_loop.id in processed_acts_eval:
                    continue
                
                processed_acts_eval.add(act_obj_loop.id)
                
                # Find the true starting slot of this particular activity instance in the timetable
                actual_start_slot_of_this_instance = ""
                try:
                    # Iterate backwards from current s_code_loop to find where this act_obj_loop started in this room
                    current_loop_slot_idx = self.slots.index(s_code_loop)
                    for check_idx in range(current_loop_slot_idx, -1, -1):
                        slot_to_verify = self.slots[check_idx]
                        if timetable[slot_to_verify].get(r_code_loop) == act_obj_loop:
                            actual_start_slot_of_this_instance = slot_to_verify
                        else:
                            # The previous slot did not have this activity, so actual_start_slot_of_this_instance is correct
                            break 
                    if not actual_start_slot_of_this_instance: # Should have been found if act_obj_loop is valid
                        continue
                    start_slot_idx_for_act_duration = self.slots.index(actual_start_slot_of_this_instance)
                except ValueError: 
                    continue # Should not happen if slots are consistent

                for i in range(act_obj_loop.duration):
                    current_segment_idx_in_slots_list = start_slot_idx_for_act_duration + i
                    if current_segment_idx_in_slots_list >= len(self.slots):
                        h_violations += 500.0 # Activity duration extends beyond available timetable slots
                        break 
                    
                    current_segment_slot_code = self.slots[current_segment_idx_in_slots_list]

                    # Consistency check: is the activity object itself consistent across its duration in this room?
                    if timetable[current_segment_slot_code].get(r_code_loop) != act_obj_loop:
                        h_violations += 250.0 # Inconsistent placement of multi-duration activity segments
                        continue # Skip further checks for this broken segment

                    # Room double-booking check (by different activities)
                    # An activity should occupy its slot exclusively unless it is the same activity (which is okay for multi-duration)
                    activity_in_checker = room_slot_activity_check[current_segment_slot_code][r_code_loop]
                    if activity_in_checker is not None and activity_in_checker.id != act_obj_loop.id:
                        h_violations += 200.0 # Room double-booked by two different activities
                    room_slot_activity_check[current_segment_slot_code][r_code_loop] = act_obj_loop # Mark as occupied by this activity segment

                    # 1. Room Capacity
                    act_size = get_class_size(act_obj_loop.id, self.groups)
                    if self.rooms[r_code_loop].size < act_size:
                        h_violations += 150.0

                    # 2. Lecturer Conflict
                    if act_obj_loop.teacher_id and act_obj_loop.teacher_id in lecturer_usage:
                        if current_segment_slot_code in lecturer_usage[act_obj_loop.teacher_id]:
                            h_violations += 100.0
                        else:
                            lecturer_usage[act_obj_loop.teacher_id].add(current_segment_slot_code)
                    
                    # 3. Student Group Conflict
                    for grp_id in act_obj_loop.group_ids:
                        if grp_id in group_usage:
                            if current_segment_slot_code in group_usage[grp_id]:
                                h_violations += 100.0
                            else:
                                group_usage[grp_id].add(current_segment_slot_code)
        
        # Soft Constraint: Lecturer Workload Balance
        lect_workload_hours = {l_id: 0 for l_id in self.lecturers.keys()}
        unique_acts_for_workload_calc = set()
        for s_data_wl in timetable.values(): 
            for act_wl_obj in s_data_wl.values():
                if act_wl_obj and act_wl_obj.id not in unique_acts_for_workload_calc:
                    if act_wl_obj.teacher_id and act_wl_obj.teacher_id in lect_workload_hours:
                        lect_workload_hours[act_wl_obj.teacher_id] += act_wl_obj.duration
                    unique_acts_for_workload_calc.add(act_wl_obj.id)
        
        non_zero_lecturer_workloads = [w for w in lect_workload_hours.values() if w > 0]
        if len(non_zero_lecturer_workloads) > 1:
            mean_wl = np.mean(non_zero_lecturer_workloads)
            var_wl = np.var(non_zero_lecturer_workloads)
            s_penalties += (var_wl / (mean_wl + 1e-6)) * 0.5 # Weighting for workload balance
            
        return h_violations + s_penalties

    def check_hard_constraints(self, activity, slot_code_segment, room_code_segment, current_ant_partial_timetable, temp_segment, is_placement_check=False):
        """Check hard constraints for a single segment of an activity. Returns violation count."""
        violations = 0
        activity_size = get_class_size(activity.id, self.groups)

        if self.rooms[room_code_segment].size < activity_size: violations += 1
        if is_placement_check and current_ant_partial_timetable[slot_code_segment][room_code_segment] is not None: violations +=1
        
        # Lecturer and Group conflicts against the ant's current timetable state
        if activity.teacher_id:
            for r_iter, act_iter in current_ant_partial_timetable[slot_code_segment].items():
                if act_iter and act_iter.teacher_id == activity.teacher_id and r_iter != room_code_segment:
                    violations +=1; break
        
        for grp_id_check in activity.group_ids:
            for r_iter, act_iter in current_ant_partial_timetable[slot_code_segment].items():
                if act_iter and grp_id_check in act_iter.group_ids and r_iter != room_code_segment:
                    violations +=1; break
            if violations > 0 and any(grp_id_check in act_iter.group_ids for r_iter, act_iter in current_ant_partial_timetable[slot_code_segment].items() if act_iter and grp_id_check in act_iter.group_ids and r_iter != room_code_segment): break
        return violations

if __name__ == '__main__':
    # Create directory structure
    results_dir = create_co_results_structure()
    
    print("--- Initial Data Loaded (Verification) ---")
    if not all([activities_dict, slots, spaces_dict, lecturers_dict, groups_dict]):
        print("ERROR: Critical data dictionary is empty. Check data loading process.")
        exit()
    else:
        print(f"Loaded {len(activities_dict)} activities, {len(slots)} slots, {len(spaces_dict)} rooms, {len(lecturers_dict)} lecturers, {len(groups_dict)} groups.")

    # ACO Parameters
    N_ANTS = 20 
    N_ITERATIONS = 20  # Reduced for testing
    ALPHA = 1.0  # Pheromone importance
    BETA = 3.0   # Heuristic importance
    EVAPORATION_RATE = 0.25 # Rho - how much pheromone evaporates
    Q0 = 0.2 # Probability of best choice (exploitation) vs. probabilistic choice (exploration)
    INITIAL_PHEROMONE = 0.1

    print("\n--- ACO Parameters ---")
    print(f"Ants: {N_ANTS}, Iterations: {N_ITERATIONS}, Alpha: {ALPHA}, Beta: {BETA}, Evaporation: {EVAPORATION_RATE}, Q0: {Q0}")

    aco_scheduler = ACO(
        activities_dict=activities_dict,
        slots_list=slots,
        spaces_dict=spaces_dict,
        lecturers_dict=lecturers_dict,
        groups_dict=groups_dict,
        n_ants=N_ANTS,
        n_iterations=N_ITERATIONS,
        alpha=ALPHA,
        beta=BETA,
        evaporation_rate=EVAPORATION_RATE,
        q0=Q0,
        initial_pheromone=INITIAL_PHEROMONE
    )
    
    aco_scheduler.initialize_pheromones()
    
    print("\n--- Running ACO Scheduler ---")
    best_timetable, best_fitness, convergence_iteration = aco_scheduler.run()

    print("\n--- ACO Final Results ---")
    if best_timetable:
        print(f"Best timetable fitness achieved: {best_fitness}")
        print(f"Convergence speed: {convergence_iteration} iterations")
        
        print("\n" + "="*60)
        print("DETAILED EVALUATION RESULTS")
        print("="*60)
        
        # Evaluate hard constraints
        hard_results = evaluate_hard_constraints(best_timetable)
        total_violations, vacant_rooms, lecturer_conflicts, room_capacity_violations, student_group_conflicts, unassigned_activities = hard_results
        
        # Evaluate soft constraints
        soft_score, soft_components = evaluate_soft_constraints(best_timetable)
        
        print("="*60)
        print("RESEARCH TABLE FORMAT")
        print("="*60)
        
        # Format results for research table
        primary_violations = f"{total_violations} ({lecturer_conflicts}), ({room_capacity_violations}), ({student_group_conflicts})"
        
        print(f"Algorithm: ACO")
        print(f"Hard Constraint Violations: {total_violations}")
        print(f"Primary Violation Types: {primary_violations}")
        print(f"Soft Constraint Score: {soft_score:.3f}")
        print(f"Convergence Speed: {convergence_iteration} iterations")
        print(f"Parameters: α={ALPHA}, β={BETA}, ρ={EVAPORATION_RATE}, Q0={Q0}")
        
        print("\n--- Detailed Breakdown ---")
        print(f"Vacant Rooms: {vacant_rooms}")
        print(f"Lecturer Conflicts: {lecturer_conflicts}")
        print(f"Room Capacity Violations: {room_capacity_violations}")
        print(f"Student Group Conflicts: {student_group_conflicts}")
        print(f"Unassigned Activities: {unassigned_activities}")
        
        # Save results to structured directories
        results_data = {
            "algorithm": "ACO",
            "parameters": {
                "n_ants": N_ANTS,
                "n_iterations": N_ITERATIONS,
                "alpha": ALPHA,
                "beta": BETA,
                "evaporation_rate": EVAPORATION_RATE,
                "q0": Q0
            },
            "results": {
                "hard_constraints": {
                    "total_violations": int(total_violations),
                    "vacant_rooms": int(vacant_rooms),
                    "lecturer_conflicts": int(lecturer_conflicts),
                    "room_capacity_violations": int(room_capacity_violations),
                    "student_group_conflicts": int(student_group_conflicts),
                    "unassigned_activities": int(unassigned_activities)
                },
                "soft_constraints": {
                    "overall_score": float(soft_score),
                    "components": {k: float(v) for k, v in soft_components.items()}
                },
                "convergence_speed": int(convergence_iteration),
                "final_fitness": float(best_fitness),
                "iteration_stats": aco_scheduler.iteration_stats,
                "fitness_history": [float(f) for f in aco_scheduler.fitness_history],
                "best_fitness_history": [float(f) for f in aco_scheduler.best_fitness_history]
            }
        }
        
        try:
            # Create a serializable version of the timetable
            serializable_timetable = {}
            for slot_key, room_data_val in best_timetable.items():
                serializable_timetable[slot_key] = {}
                for room_key, act_obj_val in room_data_val.items():
                    if act_obj_val:
                        serializable_timetable[slot_key][room_key] = {
                            'id': act_obj_val.id,
                            'subject': act_obj_val.subject,
                            'teacher_id': act_obj_val.teacher_id,
                            'group_ids': act_obj_val.group_ids,
                            'duration': act_obj_val.duration
                        }
                    else:
                        serializable_timetable[slot_key][room_key] = None
            
            # Save to results_CO/aco_results/
            aco_results_dir = results_dir / "aco_results"
            
            with open(aco_results_dir / "best_timetable.json", "w") as f_out:
                json.dump(serializable_timetable, f_out, indent=2)
            print(f"\nBest timetable saved to {aco_results_dir}/best_timetable.json")
            
            # Save comprehensive results data
            with open(aco_results_dir / "comprehensive_results.json", "w") as f_results:
                json.dump(results_data, f_results, indent=2)
            print(f"Comprehensive results saved to {aco_results_dir}/comprehensive_results.json")
            
            # Save statistics for visualization
            stats_data = {
                "iteration_stats": aco_scheduler.iteration_stats,
                "convergence_data": {
                    "best_fitness_per_iteration": aco_scheduler.best_fitness_history,
                    "convergence_iteration": convergence_iteration,
                    "final_fitness": float(best_fitness)
                },
                "fitness_distribution": {
                    "all_fitness_values": [float(f) for f in aco_scheduler.fitness_history],
                    "final_iteration_fitness": [float(f) for f in aco_scheduler.fitness_history[-N_ANTS:]]
                }
            }
            
            with open(aco_results_dir / "statistics.json", "w") as f_stats:
                json.dump(stats_data, f_stats, indent=2)
            print(f"Statistics data saved to {aco_results_dir}/statistics.json")
            
            # Generate and save convergence plot
            plt.figure(figsize=(12, 8))
            
            # Plot best fitness over iterations
            plt.subplot(2, 2, 1)
            plt.plot(range(1, len(aco_scheduler.best_fitness_history) + 1), aco_scheduler.best_fitness_history, 'b-', linewidth=2)
            plt.title('ACO Best Fitness Convergence')
            plt.xlabel('Iteration')
            plt.ylabel('Best Fitness')
            plt.grid(True, alpha=0.3)
            
            # Plot mean fitness over iterations
            plt.subplot(2, 2, 2)
            mean_fitness_per_iteration = [stat['mean_fitness'] for stat in aco_scheduler.iteration_stats]
            std_fitness_per_iteration = [stat['std_fitness'] for stat in aco_scheduler.iteration_stats]
            iterations = [stat['iteration'] for stat in aco_scheduler.iteration_stats]
            
            plt.errorbar(iterations, mean_fitness_per_iteration, yerr=std_fitness_per_iteration, 
                        fmt='o-', capsize=3, alpha=0.7)
            plt.title('ACO Mean Fitness with Standard Deviation')
            plt.xlabel('Iteration')
            plt.ylabel('Mean Fitness')
            plt.grid(True, alpha=0.3)
            
            # Plot fitness distribution of final iteration
            plt.subplot(2, 2, 3)
            final_fitness_values = aco_scheduler.fitness_history[-N_ANTS:]
            plt.hist(final_fitness_values, bins=min(15, len(set(final_fitness_values))), alpha=0.7, edgecolor='black')
            plt.title('Final Iteration Fitness Distribution')
            plt.xlabel('Fitness Value')
            plt.ylabel('Frequency')
            plt.grid(True, alpha=0.3)
            
            # Plot convergence speed visualization
            plt.subplot(2, 2, 4)
            plt.axvline(x=convergence_iteration, color='r', linestyle='--', linewidth=2, label=f'Convergence at iteration {convergence_iteration}')
            plt.plot(range(1, len(aco_scheduler.best_fitness_history) + 1), aco_scheduler.best_fitness_history, 'b-', linewidth=2)
            plt.title('ACO Convergence Speed Analysis')
            plt.xlabel('Iteration')
            plt.ylabel('Best Fitness')
            plt.legend()
            plt.grid(True, alpha=0.3)
            
            plt.tight_layout()
            convergence_plot_path = results_dir / "convergence_plots" / "aco_convergence_analysis.png"
            plt.savefig(convergence_plot_path, dpi=300, bbox_inches='tight')
            plt.close()
            print(f"Convergence plots saved to {convergence_plot_path}")
            
        except Exception as e_save:
            print(f"Error saving files: {e_save}")

    else:
        print("No solution was found by the ACO algorithm.")

    print("\n--- Script End ---")