Genetic_Algorithm_Scheduling.py

#!/usr/bin/env python
# coding: utf-8

# ## Hard Constraint Evaluation Function
# 
# This function evaluates a timetable to check for violations of hard constraints — rules that must not be broken for the schedule to be valid. It counts different types of violations and prints a summary, helping us understand where the schedule fails.
# 
# ### Parameters:
# - **`timetable`:** A dictionary where each timeslot contains rooms and the activities scheduled in them.
# - **`activities_dict`:** A dictionary of all activities, indexed by activity ID.
# - **`groups_dict`:** A dictionary of student groups, including their sizes.
# - **`spaces_dict`:** A dictionary of rooms, including their capacities.
# 
# ### What the function checks:
# 
# 1. **Vacant Rooms:**  
#    If a room is left empty in a timeslot, it’s counted as a vacant room. 
# 
# 2. **Lecturer Conflicts:**  
#    If the same lecturer is assigned to more than one activity in the same timeslot, that counts as a conflict.
# 
# 3. **Student Group Conflicts:**  
#    If a student group is scheduled for multiple activities in the same timeslot, it creates a conflict. The function uses set intersections to catch these overlaps.
# 
# 4. **Room Capacity Violations:**  
#    The function checks if the total number of students in an activity exceeds the room’s capacity. If it does, that counts as a violation.
# 
# 5. **Unassigned Activities:**  
#    The function also counts how many activities were never assigned to any room or timeslot.
# 
# ### The output:  
# After checking all the constraints, the function prints a summary:  
# - **Vacant Rooms Count** — how many rooms were left empty.  
# - **Lecturer Conflict Violations** — how many times lecturers were double-booked.  
# - **Student Group Conflict Violations** — how many times student groups were double-booked.  
# - **Room Capacity Violations** — how many times room size was insufficient for the assigned activity.  
# - **Unassigned Activity Violations** — how many activities weren’t placed in the timetable.  
# 
# Finally, it adds up all the violations to give a **total hard constraint violation score**. This score gives a quick sense of how well the timetable satisfies the strictest rules. Lower scores are better, meaning fewer conflicts and a more feasible schedule.
# 
# This function is essential for checking the raw feasibility of a schedule before worrying about things like preferences or soft constraints. 
# 

# In[14]:


def evaluate_hard_constraints(timetable, activities_dict, groups_dict, spaces_dict):
    vacant_rooms = []
    vacant_room = 0
    prof_conflicts = 0
    room_size_conflicts = 0
    sub_group_conflicts = 0
    unasigned_activities = len(activities_dict)
    activities_set = set()

    for slot in timetable:
        prof_set = set()
        sub_group_set = set()
        for room in timetable[slot]:
            activity = timetable[slot][room]

            if not isinstance(activity, type(list(activities_dict.values())[0])):  # Ensure it's an Activity object
                vacant_room += 1
                vacant_rooms.append((slot, room))
            else:
                activities_set.add(activity.id)

                # Lecturer Conflict Check
                if activity.teacher_id in prof_set:
                    prof_conflicts += 1
                prof_set.add(activity.teacher_id)

                # Student Group Conflict Check
                sub_group_conflicts += len(
                    set(activity.group_ids).intersection(sub_group_set))

                group_size = 0
                for group_id in activity.group_ids:
                    group_size += groups_dict[group_id].size
                    sub_group_set.add(group_id)

                # Room Capacity Constraint Check
                if group_size > spaces_dict[room].size:
                    room_size_conflicts += 1

    # Unassigned Activity Count
    unasigned_activities -= len(activities_set)

    # Print Results
    print("\n--- Hard Constraint Evaluation Results ---")
    print(f"Vacant Rooms Count: {vacant_room}")
    print(f"Lecturer Conflict Violations: {prof_conflicts}")
    print(f"Student Group Conflict Violations: {sub_group_conflicts}")
    print(f"Room Capacity Violations: {room_size_conflicts}")
    print(f"Unassigned Activity Violations: {unasigned_activities}")

    # Final Hard Constraint Violation Score
    total_violations = prof_conflicts + sub_group_conflicts + room_size_conflicts + unasigned_activities
    print(f"\nTotal Hard Constraint Violations: {total_violations}")


# ## Soft Constraint Evaluation Function
# 
# This function evaluates the **soft constraints** of a timetable — factors that influence schedule quality but can be compromised if necessary. It measures aspects like student and lecturer fatigue, idle time, spread of lectures, and lecturer workload balance. The function then computes an overall score to help us understand how well the schedule performs.
# 
# ### Parameters:
# - **`schedule`:** A dictionary representing the scheduled activities, organized by time slots and room assignments.
# - **`groups_dict`:** A dictionary containing student group details (e.g., group size).
# - **`lecturers_dict`:** A dictionary containing lecturer details.
# - **`slots`:** An ordered list of available time slots.
# 
# ### What the function checks:
# 
# 1. **Student Metrics:**  
#    - **Fatigue:** Number of lectures attended.  
#    - **Idle Time:** Gaps between lectures within the same day.  
#    - **Lecture Spread:** Distribution of lectures across slots (more spread = more scattered, less compact).
# 
# 2. **Lecturer Metrics:**  
#    - **Fatigue:** Number of lectures conducted.  
#    - **Idle Time:** Gaps between lectures.  
#    - **Lecture Spread:** How scattered the lectures are across the slots.  
#    - **Workload Balance:** Variance in workload across lecturers (lower variance = better balance).
# 
# ### How the function works:
# 
# - It loops through each timeslot and room to gather relevant data on activities.  
# - It updates fatigue, spread, and workload metrics directly during this loop.  
# - It calculates idle time by checking gaps between consecutive lectures.  
# - It normalizes all metrics for fair comparison and calculates workload balance using variance.  
# 
# ### Scoring the constraints:
# 
# The function prints individual scores for:  
# - **Student Fatigue Factor**  
# - **Student Idle Time Factor**  
# - **Student Lecture Spread Factor**  
# - **Lecturer Fatigue Factor**  
# - **Lecturer Idle Time Factor**  
# - **Lecturer Lecture Spread Factor**  
# - **Lecturer Workload Balance Factor**  
# 
# Finally, it computes a **weighted final score**. Higher scores indicate better schedule quality, with a balance between minimizing fatigue, idle time, and spread, while maximizing workload balance for lecturers.
# 
# The weights reflect the relative importance of each factor, but these can be adjusted as needed.
# 
# This function is invaluable for refining a feasible schedule into an optimized one that enhances the well-being of both students and lecturers.
# 

# In[15]:


import numpy as np

def evaluate_soft_constraints(schedule, groups_dict, lecturers_dict, slots):
    """
    Evaluates the soft constraints of a given schedule, handling missing (None) activities.
    This function measures:
    - Student group metrics: fatigue, idle time, lecture spread.
    - Lecturer metrics: fatigue, idle time, lecture spread, and workload balance.

    Parameters:
    - schedule (dict): The scheduled activities mapped by time slots and locations.
    - groups_dict (dict): Dictionary of student groups with group IDs as keys.
    - lecturers_dict (dict): Dictionary of lecturers with lecturer IDs as keys.
    - slots (list): Ordered list of available time slots.

    Returns:
    - final_score (float): Computed soft constraint score representing 
      schedule quality based on fatigue, idle time, spread, and workload balance.
    """

    # Initialize student group metrics
    group_fatigue = {g: 0 for g in groups_dict.keys()}
    group_idle_time = {g: 0 for g in groups_dict.keys()}
    group_lecture_spread = {g: 0 for g in groups_dict.keys()}

    # Initialize lecturer metrics
    lecturer_fatigue = {l: 0 for l in lecturers_dict.keys()}
    lecturer_idle_time = {l: 0 for l in lecturers_dict.keys()}
    lecturer_lecture_spread = {l: 0 for l in lecturers_dict.keys()}
    lecturer_workload = {l: 0 for l in lecturers_dict.keys()}

    # Track the lecture slots assigned to each group and lecturer
    group_lecture_slots = {g: [] for g in groups_dict.keys()}
    lecturer_lecture_slots = {l: [] for l in lecturers_dict.keys()}

    # Process the schedule and accumulate lecture-related data
    for slot, rooms in schedule.items():
        for room, activity in rooms.items():
            if activity is None:
                continue  # Skip empty slots (None values)

            # Process student groups
            if not isinstance(activity,Activity):
                continue
            if not isinstance(activity.group_ids,list):
                continue
            for group_id in activity.group_ids:
                if group_id in groups_dict:
                    group_fatigue[group_id] += 1  # Increase fatigue per lecture
                    group_lecture_spread[group_id] += 2  # Increase spread factor
                    group_lecture_slots[group_id].append(slot)  # Store time slot

            # Process lecturers
            lecturer_id = activity.teacher_id
            if lecturer_id in lecturers_dict:
                lecturer_fatigue[lecturer_id] += 1
                lecturer_lecture_spread[lecturer_id] += 2
                lecturer_workload[lecturer_id] += activity.duration  # Add workload
                lecturer_lecture_slots[lecturer_id].append(slot)  # Store time slot

    # Compute idle time for each student group
    for group_id, lectures in group_lecture_slots.items():
        if lectures:
            lecture_indices = sorted([slots.index(s) for s in lectures])
            idle_time = sum(
                (lecture_indices[i + 1] - lecture_indices[i] - 1) for i in range(len(lecture_indices) - 1)
            )
            group_idle_time[group_id] = idle_time / (len(slots) - 1)  # Normalize

    # Compute idle time for each lecturer
    for lecturer_id, lectures in lecturer_lecture_slots.items():
        if lectures:
            lecture_indices = sorted([slots.index(s) for s in lectures])
            idle_time = sum(
                (lecture_indices[i + 1] - lecture_indices[i] - 1) for i in range(len(lecture_indices) - 1)
            )
            lecturer_idle_time[lecturer_id] = idle_time / (len(slots) - 1)  # Normalize

    # Helper function to normalize values within a dictionary
    def normalize(dictionary):
        max_val = max(dictionary.values(), default=1)
        return {k: v / max_val if max_val else 0 for k, v in dictionary.items()}

    # Normalize metrics for fair comparison
    group_fatigue = normalize(group_fatigue)
    group_idle_time = normalize(group_idle_time)
    group_lecture_spread = normalize(group_lecture_spread)
    lecturer_fatigue = normalize(lecturer_fatigue)
    lecturer_idle_time = normalize(lecturer_idle_time)
    lecturer_lecture_spread = normalize(lecturer_lecture_spread)

    # Compute lecturer workload balance
    workload_values = np.array(list(lecturer_workload.values()))
    lecturer_workload_balance = 1  # Default balance
    if len(workload_values) > 1 and np.mean(workload_values) != 0:
        lecturer_workload_balance = max(0, 1 - (np.var(workload_values) / np.mean(workload_values)))

    # Compute the final soft constraint metrics
    student_fatigue_score = np.mean(list(group_fatigue.values()))
    student_idle_time_score = np.mean(list(group_idle_time.values()))
    student_lecture_spread_score = np.mean(list(group_lecture_spread.values()))

    lecturer_fatigue_score = np.mean(list(lecturer_fatigue.values()))
    lecturer_idle_time_score = np.mean(list(lecturer_idle_time.values()))
    lecturer_lecture_spread_score = np.mean(list(lecturer_lecture_spread.values()))

    # Print individual final metric scores
    print("\n--- Soft Constraint Evaluation Results ---")
    print(f"Student Fatigue Factor: {student_fatigue_score:.2f}")
    print(f"Student Idle Time Factor: {student_idle_time_score:.2f}")
    print(f"Student Lecture Spread Factor: {student_lecture_spread_score:.2f}")
    print(f"Lecturer Fatigue Factor: {lecturer_fatigue_score:.2f}")
    print(f"Lecturer Idle Time Factor: {lecturer_idle_time_score:.2f}")
    print(f"Lecturer Lecture Spread Factor: {lecturer_lecture_spread_score:.2f}")
    print(f"Lecturer Workload Balance Factor: {lecturer_workload_balance:.2f}")

    # Compute final soft constraint score based on weighted factors
    final_score = (
        student_fatigue_score * 0.2 +
        (1 - student_idle_time_score) * 0.2 +
        (1 - student_lecture_spread_score) * 0.2 +
        (1 - lecturer_fatigue_score) * 0.1 +
        (1 - lecturer_idle_time_score) * 0.1 +
        (1 - lecturer_lecture_spread_score) * 0.1 +
        lecturer_workload_balance * 0.1
    )

    print(f"\nFinal Soft Constraint Score: {final_score:.2f}")
    #return final_score


# ### Constraint Evaluation Function
# 
# This function evaluates a schedule by checking both **hard** and **soft constraints**:  
# 
# - **Hard Constraints:**  
#   - Room availability and capacity.  
#   - Lecturer and student group conflicts.  
#   - Unassigned activities.  
# 
# - **Soft Constraints:**  
#   - Student fatigue, idle time, and lecture spread.  
#   - Lecturer fatigue, idle time, spread, and workload balance.  
# 
# By running both evaluations, we get a complete view of schedule feasibility and quality, helping us identify and fix violations while optimizing for better resource usage and well-being.  

# In[16]:


# Constraint Evaluation Metrics
def evaluate(schedule, groups_dict, lecturers_dict, activities_dict, spaces_dict, slots):
    # Evaluate Hard Constraints
    evaluate_hard_constraints(schedule, activities_dict, groups_dict, spaces_dict)

    # Evaluate Soft Constraints
    evaluate_soft_constraints(schedule, groups_dict, lecturers_dict, slots)


# # Timetable Data Processing
# 
# This script processes timetable data from a JSON file, structuring it using classes for spaces, groups, activities, periods, and lecturers.
# 
# ### Class Definitions
# 
# - **Space**: Represents a location with a unique code and capacity.  
# - **Group**: Defines a student group with an ID and size.  
# - **Activity**: Represents a subject, assigned teacher, student groups, and duration.  
# - **Period**: Associates an activity with a time slot and space.  
# - **Lecturer**: Stores lecturer details, including ID, name, username, and department.
# 
# ### Data Loading and Processing
# 
# The script reads `sliit_computing_dataset.json` and organizes data into:
# 
# - `spaces_dict`: Maps spaces by code.  
# - `groups_dict`: Maps student groups by ID.  
# - `activities_dict`: Maps activities by code.  
# - `lecturers_dict`: Stores lecturers filtered by role.  
# 
# Each section is processed by iterating over the JSON file and creating class instances.
# 
# ### Time Slot Generation
# 
# A list of time slots is created for Monday to Friday, with eight slots per day.
# 
# ### Data Verification
# 
# The script prints the structured dictionaries to confirm correct data loading, providing a foundation for scheduling and further analysis.
# 

# In[17]:


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 Period:
    def __init__(self, *args):
        self.space = args[0]
        self.slot = args[1]
        self.activity = args[2]

    def __repr__(self):
        return f"Period(space={self.space}, group={self.group}, activity={self.activity})"

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})"



import json

# Load data from JSON file
with open('sliit_computing_dataset.json', 'r') as file:
    data = json.load(file)

# Create dictionaries to store instances
spaces_dict = {}
groups_dict = {}
activities_dict = {}
lecturers_dict = {}
slots = []
# Populate the dictionaries with data from the JSON file
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'])

for activity in data['activities']:
    activities_dict[activity['code']] = Activity(
        activity['code'], activity['subject'], activity['teacher_ids'][0], 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 in range(1, 9):
        slots.append(day+str(id))
# Print the dictionaries to verify
print("spaces_dict=", spaces_dict)
print("groups_dict=", groups_dict)
print("activities_dict=", activities_dict)
print("lecturers_dict=", lecturers_dict)
print("slots=",slots)


# In[18]:


class Period:
    def __init__(self, space, slot, activity=None):
        self.space = space
        self.slot = slot
        self.activity = activity

    def __repr__(self):
        return f"Period(space={self.space}, slot={self.slot}, activity={self.activity})"

slots = ['MON1', 'MON2', 'MON3', 'MON4', 'MON5', 'MON6', 'MON7', 'MON8',
         'TUE1', 'TUE2', 'TUE3', 'TUE4', 'TUE5', 'TUE6', 'TUE7', 'TUE8',
         'WED1', 'WED2', 'WED3', 'WED4', 'WED5', 'WED6', 'WED7', 'WED8',
         'THU1', 'THU2', 'THU3', 'THU4', 'THU5', 'THU6', 'THU7', 'THU8',
         'FRI1', 'FRI2', 'FRI3', 'FRI4', 'FRI5', 'FRI6', 'FRI7', 'FRI8']

spaces = ['LH401', 'LH501', 'LAB501', 'LAB502']

# schedule = {f"{slot}_{space}": Period(space, slot) for slot in slots for space in spaces}

# for key, value in sorted(schedule.items()):
#     print(f"{key}: {value}")
schedule = {slot: {space: None for space in spaces} for slot in slots}


# 
# # NSGA-II: Multi-Objective Genetic Algorithm for Timetable Optimization
# 
# **Overview**  
# This implementation of **NSGA-II** optimizes a timetable scheduling problem by minimizing conflicts such as professor clashes, room capacity violations, and unassigned activities. The timetable is represented as a dictionary mapping slots to room-activity assignments.
# 
# **Inputs and Parameters**  
# - `POPULATION_SIZE`: Number of individuals in the population.  
# - `NUM_GENERATIONS`: Number of evolutionary iterations.  
# - `MUTATION_RATE`: Probability of mutation in offspring.  
# - `CROSSOVER_RATE`: Probability of crossover between parents.  
# - `vacant_rooms`: Stores vacant room slots.
# 
# ---
# 
# ## Functions
# 
# **`evaluator(timetable)`**  
# Evaluates the timetable based on:  
# - Vacant rooms.  
# - Professor conflicts (same professor assigned to multiple activities).  
# - Room size violations.  
# - Subgroup conflicts (overlapping student groups).  
# - Unassigned activities.  
# 
# **Returns:** A tuple `(vacant_room, prof_conflicts, room_size_conflicts, sub_group_conflicts, unasigned_activities)`.
# 
# **`get_classsize(activity: Activity) -> int`**  
# Computes total class size by summing the sizes of associated groups.
# 
# **`evaluate_population(population)`**  
# Computes fitness values for individuals in the population using `evaluator()`.
# 
# **Returns:** List of fitness tuples.
# 
# **`mutate(individual)`**  
# Performs mutation by randomly swapping activities between two slots.
# 
# **`crossover(parent1, parent2)`**  
# Performs crossover by swapping timetable slots between parents.  
# 
# **Returns:** Two new offspring timetables.
# 
# **`fast_nondominated_sort(fitness_values)`**  
# Ranks individuals based on Pareto dominance.
# 
# **Returns:** List of ranked fronts.
# 
# **`dominates(fitness1, fitness2)`**  
# Checks if one fitness tuple dominates another.
# 
# **Returns:** `True` if `fitness1` dominates `fitness2`, otherwise `False`.
# 
# **`calculate_crowding_distance(front, fitness_values)`**  
# Computes crowding distances to maintain diversity.
# 
# **Returns:** List of crowding distances.
# 
# **`select_parents(population, fitness_values)`**  
# Performs tournament selection using Pareto fronts and crowding distance.
# 
# **Returns:** List of selected parents.
# 
# **`generate_initial_population()`**  
# Creates an initial random population of timetables.
# 
# **Returns:** List of randomly initialized timetable dictionaries.
# 
# **`nsga2()`**  
# Main evolutionary loop:
# 1. Initializes the population.
# 2. Evaluates fitness.
# 3. Applies selection, crossover, and mutation.
# 4. Uses non-dominated sorting for diversity.
# 
# **Returns:** The evolved population.
# 
# ---
# 
# ## Running the Algorithm
# The best timetable is selected based on the lowest sum of evaluation metrics:
# 
# ```python
# final_populations = nsga2()
# 
# schedule = {}
# minimum = 1000
# for population in final_populations:
#     if sum(evaluator(population)) < minimum:
#         minimum = sum(evaluator(population))
#         schedule = population
# ```
# 

# #### **Defining the chromosome as slot:{room: Activity}** 

# In[19]:


# Code
import random

POPULATION_SIZE = 50
NUM_GENERATIONS = 100
MUTATION_RATE = 0.1
CROSSOVER_RATE = 0.8


vacant_rooms = []


def evaluator(timetable):
    vacant_room = 0
    prof_conflicts = 0
    room_size_conflicts = 0
    sub_group_conflicts = 0
    unasigned_activities = len(activities_dict)
    activities_set = set()

    for slot in timetable:
        prof_set = set()
        sub_group_set = set()
        for room in timetable[slot]:
            activity = timetable[slot][room]

            if not isinstance(activity, Activity):
                vacant_room += 1
                vacant_rooms.append((slot, room))

            else:
                activities_set.add(activity.id)
                if activity.teacher_id in prof_set:
                    prof_conflicts += 1

                sub_group_conflicts += len(
                    set(activity.group_ids).intersection(sub_group_set))

                group_size = 0
                for group_id in activity.group_ids:
                    group_size += groups_dict[group_id].size
                    sub_group_set.add(group_id)

                if group_size > spaces_dict[room].size:
                    room_size_conflicts += 1
                teacher_id = activity.teacher_id
                prof_set.add(teacher_id)
    unasigned_activities -= len(activities_set)
    return vacant_room, prof_conflicts, room_size_conflicts, sub_group_conflicts, unasigned_activities

def get_classsize(activity: Activity) -> int:
    classsize = 0
    for id in activity.group_ids:
        classsize += groups_dict[id].size
    return classsize


def evaluate_population(population):
    """Evaluate each individual using the provided evaluator function."""
    fitness_values = []
    for timetable in population:
        fitness_values.append(evaluator(timetable))
    return fitness_values


def mutate(individual):
    """Perform mutation by randomly swapping activities in the timetable."""
    slots = list(individual.keys())
    slot1, slot2 = random.sample(slots, 2)
    room1, room2 = random.choice(
        list(individual[slot1])), random.choice(list(individual[slot2]))

    individual[slot1][room1], individual[slot2][room2] = individual[slot2][room2], individual[slot1][room1]


def crossover(parent1, parent2):
    """Perform crossover by swapping time slots between two parents."""
    child1, child2 = parent1.copy(), parent2.copy()
    slots = list(parent1.keys())
    split = random.randint(0, len(slots) - 1)

    for i in range(split, len(slots)):
        child1[slots[i]], child2[slots[i]
                                 ] = parent2[slots[i]], parent1[slots[i]]

    return child1, child2


def fast_nondominated_sort(fitness_values):
    """Perform non-dominated sorting based on the multi-objective fitness values."""
    fronts = [[]]
    S = [[] for _ in range(len(fitness_values))]
    n = [0] * len(fitness_values)
    rank = [0] * len(fitness_values)

    for p in range(len(fitness_values)):
        for q in range(len(fitness_values)):
            if dominates(fitness_values[p], fitness_values[q]):
                S[p].append(q)
            elif dominates(fitness_values[q], fitness_values[p]):
                n[p] += 1
        if n[p] == 0:
            rank[p] = 0
            fronts[0].append(p)

    i = 0
    while fronts[i]:
        next_front = []
        for p in fronts[i]:
            for q in S[p]:
                n[q] -= 1
                if n[q] == 0:
                    rank[q] = i + 1
                    next_front.append(q)
        i += 1
        fronts.append(next_front)

    return fronts[:-1]


def dominates(fitness1, fitness2):
    """Return True if fitness1 dominates fitness2."""
    return all(f1 <= f2 for f1, f2 in zip(fitness1, fitness2)) and any(f1 < f2 for f1, f2 in zip(fitness1, fitness2))


def calculate_crowding_distance(front, fitness_values):
    """Calculate crowding distance for a front."""
    distances = [0] * len(front)
    num_objectives = len(fitness_values[0])

    for m in range(num_objectives):
        front.sort(key=lambda x: fitness_values[x][m])
        distances[0] = distances[-1] = float('inf')

        min_value = fitness_values[front[0]][m]
        max_value = fitness_values[front[-1]][m]
        if max_value == min_value:
            continue

        for i in range(1, len(front) - 1):
            distances[i] += (fitness_values[front[i + 1]][m] -
                             fitness_values[front[i - 1]][m]) / (max_value - min_value)

    return distances


def select_parents(population, fitness_values):
    """Perform tournament selection based on non-dominated sorting and crowding distance."""
    fronts = fast_nondominated_sort(fitness_values)
    selected = []

    for front in fronts:
        if len(selected) + len(front) > POPULATION_SIZE:
            crowding_distances = calculate_crowding_distance(
                front, fitness_values)
            sorted_front = sorted(
                zip(front, crowding_distances), key=lambda x: x[1], reverse=True)
            selected.extend(
                [x[0] for x in sorted_front[:POPULATION_SIZE - len(selected)]])
            break
        else:
            selected.extend(front)

    return [population[i] for i in selected]


def generate_initial_population():
    """Generate an initial population with random timetables."""
    population = []

    for _ in range(POPULATION_SIZE):
        timetable = {}
        activity_slots = {activity.id: []
                          for activity in activities_dict.values()}
        activities_remain = [activity.id for activity in activities_dict.values()
                             for _ in range(activity.duration)]
        for slot in slots:
            timetable[slot] = {}
            for space_id in spaces_dict.keys():
                space = spaces_dict[space_id]
                a_activities = [activity for activity in activities_remain if get_classsize(
                    activities_dict[activity]) <= space.size]
                a_activities = [
                    activity for activity in a_activities if slot not in activity_slots[activity]]
                activity = random.sample(a_activities, 1)[0]
                timetable[slot][space_id] = activities_dict[activity]
                activity_slots[activity].append(slot)

        population.append(timetable)
    return population


def nsga2():
    """Main NSGA-II algorithm loop."""
    population = generate_initial_population()

    for generation in range(NUM_GENERATIONS):
        fitness_values = evaluate_population(population)
        new_population = []

        while len(new_population) < POPULATION_SIZE:
            parent1, parent2 = random.sample(population, 2)
            if random.random() < CROSSOVER_RATE:
                child1, child2 = crossover(parent1, parent2)
            else:
                child1, child2 = parent1.copy(), parent2.copy()

            if random.random() < MUTATION_RATE:
                mutate(child1)
            if random.random() < MUTATION_RATE:
                mutate(child2)

            new_population.extend([child1, child2])

        population = select_parents(
            new_population, evaluate_population(new_population))

    return population


# Run NSGA-II (Dictionary-based)
nsga2_dict_populations = nsga2()

schedule = {}
minimum = 1000
for population in nsga2_dict_populations:
    if sum(evaluator(population))<minimum:
        minimum = sum(evaluator(population))
        schedule = population


# In[20]:


evaluate(schedule,groups_dict, lecturers_dict, activities_dict, spaces_dict,slots)


# 
# ### **Defining the Chromosome as {Activity: (Room, Slot)}**
# 
# **Overview**  
# This approach represents a timetable chromosome as a mapping of activities to assigned rooms and slots. The algorithm optimizes assignments by minimizing conflicts in student schedules, professor availability, and room capacity constraints.
# 
# **Functions**
# 
# **`fitness(solution)`**  
# Evaluates a timetable based on:  
# - Room overbooking (capacity exceeded).  
# - Slot conflicts (students assigned to multiple activities at the same time).  
# - Professor conflicts (same professor assigned to multiple courses in overlapping slots).  
# 
# **Returns:** `(room_overbooking, slot_conflicts, prof_conflicts)`.
# 
# **`get_classsize(activity: Activity) -> int`**  
# Computes the total class size for an activity based on assigned student groups.
# 
# **`create_population(pop_size)`**  
# Generates a random initial population of timetable solutions, ensuring:
# - Activities are assigned to rooms with sufficient capacity.
# - Valid slots are selected considering room and professor availability.
# 
# **Returns:** A list of randomly generated timetable solutions.
# 
# **`crossover(parent1, parent2)`**  
# Performs a single-point crossover on two parent timetables.
# 
# **Returns:** Two offspring solutions.
# 
# **`non_dominated_sorting(population, fitness_values)`**  
# Ranks individuals based on Pareto dominance for multi-objective optimization.
# 
# **Returns:** A list of ranked fronts.
# 
# **`crowding_distance(front, fitness_values)`**  
# Calculates crowding distances to maintain diversity among solutions.
# 
# **Returns:** A list of crowding distances for individuals in the front.
# 
# **`tournament_selection(population, fitness_values)`**  
# Selects parents for crossover using tournament selection based on dominance.
# 
# **Returns:** Index of the selected parent.
# 
# **`mutate(solution)`**  
# Randomly alters a timetable solution by modifying room and slot assignments.
# 
# **Returns:** The mutated solution.
# 
# **`dominates(fit1, fit2)`**  
# Determines if one fitness tuple dominates another.
# 
# **Returns:** `True` if `fit1` dominates `fit2`, otherwise `False`.
# 
# ---
# 
# ## NSGA-II Algorithm
# 
# **`run_nsga2(pop_size=50, generations=200)`**  
# Executes the NSGA-II optimization loop:
# 1. Generates an initial population.
# 2. Evaluates fitness and applies non-dominated sorting.
# 3. Performs selection, crossover, and mutation.
# 4. Maintains diversity using crowding distance.
# 
# **Returns:** The final evolved population.
# 
# **`adapter(solution)`**  
# Converts a chromosome-based solution into a structured timetable format.
# 
# **Returns:** A dictionary-based timetable representation.
# 
# ---
# 
# ## Running the Algorithm
# The best timetable is selected based on the lowest sum of evaluation metrics:
# 
# ```python
# final_populations = run_nsga2()
# 
# schedule = {}
# minimum = 1000
# for population in final_populations:
#     timetable = adapter(population)
#     if sum(evaluator(timetable)) < minimum:
#         minimum = sum(evaluator(timetable))
#         schedule = timetable
# ```
# ```

# In[21]:


import random


def fitness(solution):
    room_overbooking = 0
    slot_conflicts = 0
    prof_conflicts = 0

    slot_assignments = {}
    prof_assignments = {}

    # Evaluate room overbooking and slot conflicts
    for entry in solution:
        course_id, student_group, room_id, valid_slots, professor = entry
        course = activities_dict[course_id]
        room = spaces_dict[room_id]

        # Room overbooking
        if room.size < get_classsize(course):
            room_overbooking += 1

        # Slot conflicts (same student in multiple classes at the same time)
        for slot_id in valid_slots:
            if slot_id not in slot_assignments:
                slot_assignments[slot_id] = []
            slot_assignments[slot_id].append((student_group, course_id))

        # Professor conflicts (same professor teaching multiple courses at the same time)
        if course.teacher_id not in prof_assignments:
            prof_assignments[course.teacher_id] = []
        prof_assignments[course.teacher_id].append(slot_id)

    # Calculate slot conflicts
    for slot_id, assignments in slot_assignments.items():
        student_groups_in_slot = {}
        for student_groups, course_id in assignments:
            for student_group in student_groups:
                if student_group in student_groups_in_slot:
                    slot_conflicts += 1  # Conflict when a student is assigned to two courses at the same time
                else:
                    student_groups_in_slot[student_group] = course_id

    # Calculate professor conflicts
    for professor, assigned_slots in prof_assignments.items():
        if len(assigned_slots) > len(set(assigned_slots)):  # Duplicate slots means conflict
            prof_conflicts += 1

    return room_overbooking, slot_conflicts, prof_conflicts


def get_classsize(activity: Activity) -> int:
    classsize = 0
    for id in activity.group_ids:
        classsize += groups_dict[id].size
    return classsize

# Updated create_population function


def create_population(pop_size):
    population = []
    for _ in range(pop_size):
        solution = []
        room_slot_assignments = {space.code: set()
                                 # Track slots per room
                                 for space in spaces_dict.values()}
        prof_slot_assignments = {prof: set() for prof in set(
            activity.teacher_id for activity in activities_dict.values())}  # Track professor slots

        for activity in activities_dict.values():
            # course = courses[course_id]

            student_groups = activity.group_ids
            rooms = [room for room in spaces_dict.values(
            ) if room.size >= get_classsize(activity)]
            # student_group = course.student  # Get student group
            selected_room = random.choice(rooms)  # Random room

            # Find consecutive slots for the course
            valid_slots = [
                slot for slot in slots if slot not in room_slot_assignments[selected_room.code] and slot not in prof_slot_assignments[activity.teacher_id]]

            if len(valid_slots) >= activity.duration:
                selected_slots = random.sample(valid_slots, activity.duration)
            else:
                selected_slots = random.sample(slots, activity.duration)

            for slot in selected_slots:
                room_slot_assignments[selected_room.code].add(slot)
                prof_slot_assignments[activity.teacher_id].add(slot)

            solution.append(
                (activity.id, student_groups, selected_room.code, selected_slots, activity.teacher_id))

        population.append(solution)
    return population

# Crossover function


def crossover(parent1, parent2):
    crossover_point = random.choice(range(1, len(parent1)))
    child1 = parent1[:crossover_point] + parent2[crossover_point:]
    child2 = parent2[:crossover_point] + parent1[crossover_point:]
    return child1, child2


# NSGA-II selection based on non-dominated sorting and crowding distance
def non_dominated_sorting(population, fitness_values):
    fronts = [[]]
    rank = [0] * len(population)
    domination_count = [0] * len(population)
    dominated_solutions = [[] for _ in range(len(population))]

    for p in range(len(population)):
        for q in range(len(population)):
            if dominates(fitness_values[p], fitness_values[q]):
                dominated_solutions[p].append(q)
            elif dominates(fitness_values[q], fitness_values[p]):
                domination_count[p] += 1

        if domination_count[p] == 0:
            rank[p] = 0
            fronts[0].append(p)

    front_counter = 0
    while len(fronts[front_counter]) > 0:
        next_front = []
        for p in fronts[front_counter]:
            for q in dominated_solutions[p]:
                domination_count[q] -= 1
                if domination_count[q] == 0:
                    rank[q] = front_counter + 1
                    next_front.append(q)
        front_counter += 1
        fronts.append(next_front)

    return fronts


# Crowding distance for maintaining diversity in the population
def crowding_distance(front, fitness_values):
    distance = [0] * len(front)
    if len(front) > 1:  # Only calculate crowding distance if there are at least two individuals in the front
        sorted_by_first = sorted(front, key=lambda x: fitness_values[x][0])
        sorted_by_second = sorted(front, key=lambda x: fitness_values[x][1])

        # Set infinity for boundary individuals
        distance[0] = distance[-1] = float('inf')
        for i in range(1, len(front) - 1):
            distance[i] = (fitness_values[sorted_by_first[i + 1]][0] - fitness_values[sorted_by_first[i - 1]][0]) + \
                          (fitness_values[sorted_by_second[i + 1]][1] -
                           fitness_values[sorted_by_second[i - 1]][1])

    return distance


# Tournament selection for parents
def tournament_selection(population, fitness_values):
    selected_parents = random.sample(list(range(len(population))), 2)
    p1, p2 = selected_parents[0], selected_parents[1]

    if dominates(fitness_values[p1], fitness_values[p2]):
        return p1
    else:
        return p2


def mutate(solution):
    mutation_point = random.randint(0, len(solution) - 1)
    course_id, student_group, _, _, _ = solution[mutation_point]

    new_room = random.choice(list(spaces_dict.values())).code  # Random room
    new_slot = random.choice(slots)  # Random slot

    professor = activities_dict[course_id].teacher_id
    # Update with new room and slot, keep course_id and student_group the same
    solution[mutation_point] = (
        course_id, student_group, new_room, new_slot, professor)
    return solution

# Domination check


def dominates(fit1, fit2):
    return (fit1[0] <= fit2[0] and fit1[1] <= fit2[1] and fit1[2] <= fit2[2]) and \
           (fit1[0] < fit2[0] or fit1[1] < fit2[1] or fit1[2] < fit2[2])


# Run NSGA-II algorithm
def run_nsga2(pop_size=50, generations=200):
    population = create_population(pop_size)
    for generation in range(generations):
        # Evaluate the fitness of the current population
        fitness_values = [fitness(solution) for solution in population]

        # Non-dominated sorting
        fronts = non_dominated_sorting(population, fitness_values)
        new_population = []

        # Iterate through each front and apply crossover and mutation
        for front in fronts:
            distances = crowding_distance(front, fitness_values)
            sorted_front = sorted(
                front, key=lambda x: distances[front.index(x)], reverse=True)

            # Select parents from the sorted front
            while len(new_population) < pop_size and len(sorted_front) > 1:
                parent1 = population[sorted_front[0]]
                parent2 = population[sorted_front[1]]

                # Crossover
                child1, child2 = crossover(parent1, parent2)

                # Mutation
                child1 = mutate(child1)
                child2 = mutate(child2)

                # Add children to the new population
                new_population.append(child1)
                new_population.append(child2)

        # Truncate to maintain population size
        population = new_population[:pop_size]

        # Print the progress
        if generation % 10 == 0:
            print(
                f"Generation {generation}: Population size {len(population)}")

    return population


def adapter(solution):
    timetable = {}
    for slot in slots:
        timetable[slot] = {}
        for space in spaces_dict.keys():
            timetable[slot][space] = ""

    for period in solution:
        time_slots = period[3]
        room = period[2]
        activity_id = period[0]
        if not isinstance(time_slots, list):
            time_slots = [time_slots]
        for aslot in time_slots:
            timetable[aslot][room] = activities_dict[activity_id]
    return timetable


# Running the algorithm
final_populations_chromosome = run_nsga2()

schedule = {}
minimum = 1000
for population in final_populations_chromosome:
    timetable = adapter(population)
    if sum(evaluator(timetable)) < minimum:
        minimum = sum(evaluator(timetable))
        schedule = timetable


# In[22]:


import pprint as pp
pp.pprint(schedule)
evaluate(schedule, groups_dict, lecturers_dict, activities_dict, spaces_dict,slots)


# 
# # MOEA/D: Multi-Objective Evolutionary Algorithm based on Decomposition
# 
# **Overview**  
# This implementation of **MOEA/D** optimizes timetable scheduling by decomposing a multi-objective problem into subproblems solved collaboratively. It assigns activities to time slots and rooms while minimizing scheduling conflicts.
# 
# **Inputs and Parameters**  
# - `POPULATION_SIZE`: Number of individuals in the population.  
# - `NUM_GENERATIONS`: Number of evolutionary iterations.  
# - `MUTATION_RATE`: Probability of mutation.  
# - `CROSSOVER_RATE`: Probability of crossover.  
# - `NUM_OBJECTIVES`: Number of objectives to optimize.  
# - `NUM_WEIGHTS`: Number of weight vectors used for decomposition.  
# 
# ---
# 
# ## Functions
# 
# **`generate_weight_vectors(num_weights, num_objectives)`**  
# Generates weight vectors using the **Dirichlet distribution**, ensuring they sum to 1.
# 
# **`evaluate_population(population)`**  
# Computes fitness values for all individuals in the population using `evaluator()`.
# 
# **Returns:** A list of fitness tuples.
# 
# **`update_ideal_point(fitness_values)`**  
# Updates the **ideal point**, tracking the best objective values found.
# 
# **`scalarizing_function(fitness, weight_vector)`**  
# Applies the **Tchebycheff** decomposition approach to evaluate subproblems.
# 
# **`select_parents_neighborhood(population, fitness_values, neighborhood)`**  
# Selects two parents from a given **neighborhood** for crossover.
# 
# **Returns:** Two selected parents.
# 
# **`crossover(parent1, parent2)`**  
# Performs crossover by swapping timetable slots between parents.
# 
# **Returns:** Two offspring timetables.
# 
# **`mutate(individual)`**  
# Randomly swaps activities between two slots in the timetable.
# 
# **`generate_initial_population()`**  
# Creates an initial random population of timetables.
# 
# **Returns:** A list of randomly initialized timetable solutions.
# 
# ---
# 
# ## MOEA/D Algorithm
# 
# **`moead()`**  
# Executes the MOEA/D optimization process:
# 1. Initializes the population and evaluates fitness.
# 2. Generates weight vectors and **assigns neighborhoods**.
# 3. Selects parents within each neighborhood.
# 4. Applies crossover and mutation.
# 5. Updates the **ideal point** and modifies solutions.
# 
# **Returns:** The final evolved population.
# 
# ---
# 
# ## Running the Algorithm
# The best timetable is selected based on the lowest sum of evaluation metrics:
# 
# ```python
# final_populations = moead()
# 
# schedule = {}
# minimum = 1000
# for population in final_populations:
#     if sum(evaluator(population)) < minimum:
#         minimum = sum(evaluator(population))
#         schedule = population
# ```
# ```

# In[23]:


# Code
import random
import numpy as np
from itertools import combinations_with_replacement

POPULATION_SIZE = 50
NUM_GENERATIONS = 100
MUTATION_RATE = 0.1
CROSSOVER_RATE = 0.8
NUM_OBJECTIVES = 5  # Adjust based on your objectives
NUM_WEIGHTS = POPULATION_SIZE

# Generate weight vectors for decomposition


def generate_weight_vectors(num_weights, num_objectives):
    weight_vectors = []
    for _ in range(num_weights):
        vec = np.random.dirichlet(np.ones(num_objectives), size=1)[
            0]  # Generates valid weights summing to 1
        weight_vectors.append(vec)
    return np.array(weight_vectors)


# Generate weight vectors for 5 objectives
weight_vectors = generate_weight_vectors(NUM_WEIGHTS, NUM_OBJECTIVES)
# Initialize ideal point
ideal_point = np.full(NUM_OBJECTIVES, float('inf'))

# Define functions


def evaluate_population(population):
    """Evaluate each individual using the provided evaluator function."""
    return [evaluator(ind) for ind in population]


def update_ideal_point(fitness_values):
    """Update the ideal point based on the best objective values found."""
    global ideal_point
    for fitness in fitness_values:
        ideal_point = np.minimum(ideal_point, fitness)


def scalarizing_function(fitness, weight_vector):
    """Apply the Tchebycheff approach for decomposition."""
    return max(weight_vector * abs(fitness - ideal_point))


def select_parents_neighborhood(population, fitness_values, neighborhood):
    """Select parents from a given neighborhood."""
    parent1, parent2 = random.sample(neighborhood, 2)
    return population[parent1], population[parent2]


def crossover(parent1, parent2):
    """Perform crossover by swapping time slots between two parents."""
    child1, child2 = parent1.copy(), parent2.copy()
    slots = list(parent1.keys())
    split = random.randint(0, len(slots) - 1)
    for i in range(split, len(slots)):
        child1[slots[i]], child2[slots[i]
                                 ] = parent2[slots[i]], parent1[slots[i]]
    return child1, child2


def mutate(individual):
    """Perform mutation by randomly swapping activities in the timetable."""
    slots = list(individual.keys())
    slot1, slot2 = random.sample(slots, 2)
    room1, room2 = random.choice(
        list(individual[slot1])), random.choice(list(individual[slot2]))
    individual[slot1][room1], individual[slot2][room2] = individual[slot2][room2], individual[slot1][room1]


def generate_initial_population():
    """Generate an initial population with random timetables."""
    population = []
    for _ in range(POPULATION_SIZE):
        timetable = {}
        for slot in slots:
            timetable[slot] = {}
            for space_id in spaces_dict.keys():
                timetable[slot][space_id] = random.choice(
                    list(activities_dict.values()))
        population.append(timetable)
    return population


def moead():
    """Main MOEA/D algorithm loop."""
    global ideal_point
    population = generate_initial_population()
    fitness_values = evaluate_population(population)
    update_ideal_point(fitness_values)

    # Create neighborhoods
    distances = np.zeros((POPULATION_SIZE, POPULATION_SIZE))
    for i in range(POPULATION_SIZE):
        for j in range(POPULATION_SIZE):
            distances[i, j] = np.linalg.norm(
                weight_vectors[i] - weight_vectors[j])
    neighborhoods = [list(np.argsort(distances[i])[:5])
                     for i in range(POPULATION_SIZE)]

    for generation in range(NUM_GENERATIONS):
        for i in range(POPULATION_SIZE):
            parent1, parent2 = select_parents_neighborhood(
                population, fitness_values, neighborhoods[i])

            if random.random() < CROSSOVER_RATE:
                child1, child2 = crossover(parent1, parent2)
            else:
                child1, child2 = parent1.copy(), parent2.copy()

            if random.random() < MUTATION_RATE:
                mutate(child1)
            if random.random() < MUTATION_RATE:
                mutate(child2)

            new_individuals = [child1, child2]
            new_fitness = evaluate_population(new_individuals)
            update_ideal_point(new_fitness)

            for j, new_fit in enumerate(new_fitness):
                scalar_fitness = scalarizing_function(
                    new_fit, weight_vectors[i])
                for k in neighborhoods[i]:
                    if scalar_fitness < scalarizing_function(fitness_values[k], weight_vectors[k]):
                        population[k] = new_individuals[j]
                        fitness_values[k] = new_fit

    return population


# Run MOEA/D
moead_populations = moead()

schedule = {}
minimum = 1000
for population in moead_populations:
    if sum(evaluator(population)) < minimum:
        minimum = sum(evaluator(population))
        schedule = population


# In[24]:


evaluate(schedule,groups_dict, lecturers_dict, activities_dict, spaces_dict,slots)


# 
# # SPEA2: Strength Pareto Evolutionary Algorithm 2
# 
# **Overview**  
# This implementation of **SPEA2** optimizes timetable scheduling by maintaining an **archive** of non-dominated solutions. It selects individuals based on dominance ranking and density estimation while applying genetic operations for improvement.
# 
# **Inputs and Parameters**  
# - `POPULATION_SIZE`: Number of individuals in the population.  
# - `NUM_GENERATIONS`: Number of evolutionary iterations.  
# - `MUTATION_RATE`: Probability of mutation.  
# - `CROSSOVER_RATE`: Probability of crossover.  
# - `NUM_OBJECTIVES`: Number of optimization objectives.  
# - `ARCHIVE_SIZE`: Maximum size of the archive storing non-dominated solutions.
# 
# ---
# 
# ## Functions
# 
# **`generate_weight_vectors(num_weights, num_objectives)`**  
# Generates weight vectors using the **Dirichlet distribution**, ensuring they sum to 1.
# 
# **`evaluate_population(population)`**  
# Computes fitness values for individuals in the population using `evaluator()`.
# 
# **Returns:** List of fitness tuples.
# 
# **`dominates_any(fit, other_fits)`**  
# Checks if a given solution dominates any other in the set.
# 
# **`dominates(fit1, fit2)`**  
# Determines if one fitness value dominates another.
# 
# **`dominance_rank(population, fitness_values)`**  
# Assigns dominance ranks based on Pareto dominance.
# 
# **`density_estimation(population, fitness_values)`**  
# Estimates density by measuring distances between fitness values.
# 
# **`select_parents(population, fitness_values, archive)`**  
# Selects parents for crossover using dominance ranking and density estimation.
# 
# **Returns:** Two selected parents.
# 
# **`crossover(parent1, parent2)`**  
# Performs a **single-point crossover** by swapping parts of two parent timetables.
# 
# **Returns:** Two offspring timetables.
# 
# **`mutate(individual)`**  
# Randomly swaps activities between slots in the timetable.
# 
# **`generate_initial_population()`**  
# Creates a random initial population of timetables.
# 
# **Returns:** List of generated solutions.
# 
# ---
# 
# #### **SPEA2 Algorithm**
# 
# **`spea2()`**  
# Executes the **SPEA2 optimization** loop:
# 1. Generates an initial population and evaluates fitness.
# 2. Maintains an **archive** of non-dominated solutions.
# 3. Uses dominance ranking and density estimation for selection.
# 4. Applies **crossover and mutation** for genetic improvement.
# 5. Updates the population iteratively.
# 
# **Returns:** The evolved population and final archive.
# 
# ---
# 
# ## Running the Algorithm
# The best timetable is selected based on the lowest sum of evaluation metrics:
# 
# ```python
# final_population, final_archive = spea2()
# 
# schedule = {}
# minimum = 1000
# for population in final_population:
#     if sum(evaluator(population)) < minimum:
#         minimum = sum(evaluator(population))
#         schedule = population
# ```
# ```

# In[25]:


# Code
import random
import numpy as np

POPULATION_SIZE = 50
NUM_GENERATIONS = 100
MUTATION_RATE = 0.1
CROSSOVER_RATE = 0.8
NUM_OBJECTIVES = 5  # Adjust based on your objectives
NUM_WEIGHTS = POPULATION_SIZE
ARCHIVE_SIZE = POPULATION_SIZE  # Archive size for storing non-dominated solutions

# Generate weight vectors for decomposition


def generate_weight_vectors(num_weights, num_objectives):
    weight_vectors = []
    for _ in range(num_weights):
        vec = np.random.dirichlet(np.ones(num_objectives), size=1)[
            0]  # Generates valid weights summing to 1
        weight_vectors.append(vec)
    return np.array(weight_vectors)


# Generate weight vectors for 5 objectives
weight_vectors = generate_weight_vectors(NUM_WEIGHTS, NUM_OBJECTIVES)

# Define functions


def evaluate_population(population):
    """Evaluate each individual using the provided evaluator function."""
    return [evaluator(ind) for ind in population]


def dominates_any(fit, other_fits):
    """Check if the individual `fit` dominates any individual in `other_fits`."""
    for other_fit in other_fits:
        if not dominates(fit, other_fit):
            return False
    return True


def dominates(fit1, fit2):
    """Check if individual `fit1` dominates individual `fit2`."""
    return np.all(fit1 <= fit2) and np.any(fit1 < fit2)


def dominance_rank(population, fitness_values):
    """Assign dominance ranks to each individual in the population."""
    ranks = []
    for i, fit1 in enumerate(fitness_values):
        dominated = 0
        for j, fit2 in enumerate(fitness_values):
            if i != j and np.all(fit1 <= fit2) and np.any(fit1 < fit2):
                dominated += 1
        ranks.append(dominated)
    return np.array(ranks)


def density_estimation(population, fitness_values):
    """Estimate the density of each individual based on the distances between them."""
    densities = np.zeros(len(population))

    for i, fit1 in enumerate(fitness_values):
        fit1 = np.array(fit1)  # Convert fitness value to a NumPy array
        distance_sum = 0
        for j, fit2 in enumerate(fitness_values):
            if i != j:
                fit2 = np.array(fit2)  # Convert fitness value to a NumPy array
                distance_sum += np.linalg.norm(fit1 - fit2)
        densities[i] = 1 / (1 + distance_sum)

    return densities


def select_parents(population, fitness_values, archive):
    """Select parents from the population and archive based on fitness and density."""
    combined_population = population + archive
    combined_fitness = fitness_values + [ind['fitness'] for ind in archive]
    ranks = dominance_rank(combined_population, combined_fitness)
    densities = density_estimation(combined_population, combined_fitness)

    fitness = ranks + densities  # Combine rank and density to form fitness
    selected_indices = np.argsort(fitness)[:2]  # Select two parents
    return population[selected_indices[0]], population[selected_indices[1]]


def crossover(parent1, parent2):
    """Perform crossover by swapping parts between two parents."""
    child1, child2 = parent1.copy(), parent2.copy()
    slots = list(parent1.keys())
    split = random.randint(0, len(slots) - 1)
    for i in range(split, len(slots)):
        child1[slots[i]], child2[slots[i]
                                 ] = parent2[slots[i]], parent1[slots[i]]
    return child1, child2


def mutate(individual):
    """Perform mutation by randomly swapping activities in the timetable."""
    slots = list(individual.keys())
    slot1, slot2 = random.sample(slots, 2)
    room1, room2 = random.choice(
        list(individual[slot1])), random.choice(list(individual[slot2]))
    individual[slot1][room1], individual[slot2][room2] = individual[slot2][room2], individual[slot1][room1]


def generate_initial_population():
    """Generate an initial population with random timetables."""
    population = []
    for _ in range(POPULATION_SIZE):
        timetable = {}
        for slot in slots:
            timetable[slot] = {}
            for space_id in spaces_dict.keys():
                timetable[slot][space_id] = random.choice(
                    list(activities_dict.values()))
        population.append(timetable)
    return population


def spea2():
    """Main SPEA2 algorithm loop."""
    population = generate_initial_population()
    archive = []
    fitness_values = evaluate_population(population)

    # Main loop
    for generation in range(NUM_GENERATIONS):
        # Combine population and archive for dominance-based sorting
        combined_population = population + archive
        combined_fitness = fitness_values + [ind['fitness'] for ind in archive]
        ranks = dominance_rank(combined_population, combined_fitness)
        densities = density_estimation(combined_population, combined_fitness)

        fitness = ranks + densities
        sorted_indices = np.argsort(fitness)

        # Create the next population
        new_population = []
        for i in sorted_indices[:POPULATION_SIZE]:
            new_population.append(combined_population[i])

        # Perform crossover and mutation
        for i in range(0, len(new_population), 2):
            parent1, parent2 = new_population[i], new_population[i + 1]
            if random.random() < CROSSOVER_RATE:
                child1, child2 = crossover(parent1, parent2)
            else:
                child1, child2 = parent1.copy(), parent2.copy()

            if random.random() < MUTATION_RATE:
                mutate(child1)
            if random.random() < MUTATION_RATE:
                mutate(child2)

            # Evaluate the new individuals and add to the archive if non-dominated
            new_fitness = evaluate_population([child1, child2])
            for ind, fit in zip([child1, child2], new_fitness):
                if not dominates_any(fit, [archive_ind['fitness'] for archive_ind in archive]):
                    archive.append({'solution': ind, 'fitness': fit})

        population = new_population  # Replace the old population

    return population, archive


# Run SPEA2
spea2_population, spea2_archive = spea2()

schedule = {}
minimum = 1000
for population in spea2_population:
    if sum(evaluator(population)) < minimum:
        minimum = sum(evaluator(population))
        schedule = population


# In[26]:


evaluate(schedule,groups_dict, lecturers_dict, activities_dict, spaces_dict,slots)


# # Results: Pareto Front Visualizations
# 
# This section presents the Pareto fronts obtained from the implemented multi-objective genetic algorithms. The figures below illustrate the trade-offs between objectives for each algorithm, as required for the results section of the paper.
# 
# - **NSGA-II (Chromosome-based):** 3D Pareto front using the objectives from the `fitness` function.
# - **NSGA-II, MOEA/D, SPEA2 (Dictionary-based):** 5D Pareto fronts using the objectives from the `evaluator` function.
# 
# > **Note:** MOEA/D and SPEA2 do not have chromosome-based (3D) Pareto fronts because their implementations use a dictionary-based solution representation and optimize all 5 objectives. Only the chromosome-based NSGA-II uses a 3D objective space.

# In[29]:


# Extract and plot the 3D Pareto front for chromosome-based NSGA-II
try:
    # Use the actual chromosome-based NSGA-II result variable
    pareto_3d = [fitness(population) for population in final_populations_chromosome]
    pareto_3d = np.array(pareto_3d)

    import matplotlib.pyplot as plt
    from mpl_toolkits.mplot3d import Axes3D

    fig = plt.figure(figsize=(8, 6))
    ax = fig.add_subplot(111, projection='3d')
    ax.scatter(pareto_3d[:, 0], pareto_3d[:, 1], pareto_3d[:, 2], c='b', marker='o')
    ax.set_xlabel('Objective 1')
    ax.set_ylabel('Objective 2')
    ax.set_zlabel('Objective 3')
    ax.set_title('NSGA-II (Chromosome-based) 3D Pareto Front')
    plt.show()
except Exception as e:
    print("3D Pareto front for chromosome-based NSGA-II not available:", e)


# In[30]:


# Extract and plot the 5D Pareto fronts for dictionary-based algorithms
algorithms = {
    'NSGA-II (dict)': nsga2_dict_populations,  # Dictionary-based NSGA-II result
    'MOEA/D': moead_populations,              # MOEA/D result
    'SPEA2': spea2_population                 # SPEA2 result
}

import itertools
import matplotlib.pyplot as plt
import pandas as pd

for name, result in algorithms.items():
    try:
        # For dictionary-based algorithms, result is a list of timetables
        # We need to evaluate each timetable to get the 5D fitness values
        pareto_5d = [evaluator(timetable) for timetable in result]
        pareto_5d = np.array(pareto_5d)
        df = pd.DataFrame(pareto_5d, columns=[f'Obj{i+1}' for i in range(5)])

        # Plot all 2D projections
        fig, axes = plt.subplots(1, 5, figsize=(25, 4))
        pairs = list(itertools.combinations(range(5), 2))[:5]
        for i, (x, y) in enumerate(pairs):
            axes[i].scatter(df.iloc[:, x], df.iloc[:, y], alpha=0.7)
            axes[i].set_xlabel(df.columns[x])
            axes[i].set_ylabel(df.columns[y])
            axes[i].set_title(f'{df.columns[x]} vs {df.columns[y]}')
        fig.suptitle(f'{name} 5D Pareto Front (2D Projections)')
        plt.tight_layout()
        plt.show()
    except Exception as e:
        print(f"5D Pareto front for {name} not available:", e)


# ## Why MOEA/D and SPEA2 Do Not Have Chromosome-Based (3D) Pareto Fronts
# 
# MOEA/D and SPEA2 are implemented using a dictionary-based solution representation, which evaluates all 5 objectives using the `evaluator` function. As a result, their native Pareto fronts are 5-dimensional. In contrast, the chromosome-based NSGA-II uses a different representation and only optimizes 3 objectives, resulting in a 3D Pareto front. Therefore, only the dictionary-based algorithms (including dictionary-based NSGA-II) have 5D Pareto fronts, and only the chromosome-based NSGA-II has a 3D Pareto front.

# ## Pareto Front Visualizations for Multi-Objective Genetic Algorithms
# 
# This section presents the native Pareto fronts obtained from each multi-objective genetic algorithm (NSGA-II, MOEA/D, SPEA2). These visualizations help compare the trade-offs achieved by each method across their respective objectives.

# In[ ]:


# 3D Pareto Front for Chromosome-based NSGA-II (3 objectives)
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

# Use the actual chromosome-based NSGA-II result variable
# Each solution has three objectives from the fitness function
pareto_3d = [fitness(population) for population in final_populations_chromosome]
pareto_3d = list(set(pareto_3d))  # Remove duplicates if any

fig = plt.figure(figsize=(8,6))
ax = fig.add_subplot(111, projection='3d')
ax.scatter(
    [p[0] for p in pareto_3d],
    [p[1] for p in pareto_3d],
    [p[2] for p in pareto_3d],
    c='blue', marker='o', label='NSGA-II Chromosome Pareto Front'
)
ax.set_xlabel('Objective 1')
ax.set_ylabel('Objective 2')
ax.set_zlabel('Objective 3')
ax.set_title('3D Pareto Front: Chromosome-based NSGA-II')
ax.legend()
plt.show()


# In[ ]:


# 5D Pareto Fronts for Dictionary-based NSGA-II, MOEA/D, and SPEA2 (5 objectives)
import pandas as pd
import seaborn as sns

# Use the actual result variables from the dictionary-based algorithms
# Each result is a list of timetables that need to be evaluated using the evaluator function
algo_results = {
    "NSGA-II (dict)": nsga2_dict_populations,
    "MOEA/D": moead_populations,
    "SPEA2": spea2_population
}

# For visualization, plot pairwise scatterplots of the 5 objectives (parallel coordinates or pairplot)
for name, result in algo_results.items():
    pareto_5d = [evaluator(timetable) for timetable in result]
    pareto_5d = list(set(pareto_5d))  # Remove duplicates
    objective_names = ['Vacant Rooms', 'Lecturer Conflicts', 'Room Capacity Violations', 'Student Group Conflicts', 'Unassigned Activities']
    df = pd.DataFrame(pareto_5d, columns=objective_names)
    sns.pairplot(df)
    plt.suptitle(f"Pairwise Pareto Fronts: {name}", y=1.02)
    plt.show()


# **Note:**  
# MOEA/D and SPEA2 do not have chromosome-based (3D) Pareto fronts because they use a dictionary-based solution representation and optimize five objectives simultaneously. The chromosome-based NSGA-II, in contrast, optimizes only three objectives, allowing for a 3D Pareto front visualization. The dictionary-based approaches require higher-dimensional (5D) Pareto front analysis, which is visualized here using pairwise projections.