Hello, I am Enzo, a student in data and artificial intelligence.

The Ant Colony Optimization algorithm is a metaheuristic algorithm inspired by the foraging behavior of ants. It is used to solve combinatorial optimization problems.

The algorithm is based on the principle of pheromone deposition by ants on the ground. The more ants pass through a path, the more pheromones are deposited on it. This allows other ants to follow the path more easily.

The algorithm is based on the following principles:
- Construction of solutions
- Local search
- Updating of pheromones

The first step is to define a function to evaluate the quality of the solutions. This function is named \( \text{score} \) and is defined as \( \text{score} : \mathbb{T} \to [0, 1] \) where \( \mathbb{T} \) represents the set of all possible timetables.

The score function is expressed as a weighted sum (average) of various feature functions. Each feature function represents a specific characteristic of the timetable (\( \text{tt} \in \mathbb{T} \)): \( \:\text{score}(\text{tt}) = \sum_{i=1}^n \alpha_i \cdot f_i(\text{tt}) \)

	08:00	08:30	09:00	09:30	10:00	10:30	...	20:00
Monday	Course 1				Course 2		...
Tuesday							...
...							...
Saturday		Course 3					...

Score: 14% {

feature functions: Number of hours for students

1. Penalty function for a day \( d \), based on the number of class hours \( h_d \): \[ \text{penalty}(h_d) = \begin{cases} 1 & \text{if } h_d \leq 8 \\ e^{\text{-}k(h_d \, \text{-} \, 8)}& \text{if } h_d > 8, k \in \mathbb{T}^+ \end{cases} \] We chose \( k = 0.9 \) for this project.

2. Function \(\text{nb_hours_for_students}(tt)\), which uses this penalty for each day in the timetable (TT): \[ \text{nb_hours_for_students}(tt) = \sum_{d \in \text{tt}} \text{penalty}(h_d) / | \text{tt} | \] where \( h_d \) represents the total number of class hours on day \( d \).

Number of hours for teachers

1. Penalty function for a day \( d \) and a teacher \( d \), based on the number of class hours \( h_d \): \[ \text{penalty}(h_{d, t}) = \begin{cases} 1 & \text{if } h_d \leq t.nb\_hours\_by\_day \\ 0 & \text{if } h_d > t.nb\_hours\_by\_day \end{cases} \] 2. Function \(\text{nb_hours_for_teacher}(tt)\), which uses this penalty for each day in the timetable (TT)
and \(teachers_d\) the list of teachers for day \( d \): \[ \text{nb_hours_for_teacher}(tt) = \frac{1}{\left|\:\text{tt}\right|} * \sum_{d \in \text{tt}} \left( \frac{1}{\left|\:teachers_d \right|} * \sum_{t \in teachers_d} \text{penalty}(h_{d, t}) \right) \] where \( h_{d, t} \) represents the total number of class hours on day \( d \) for teacher \( t \).

Size of gaps between hours for students

1. Penalty function for a day \( d \), based on the number of gaps between class hours \( g_d \): \[ \text{penalty_nb_gaps}(g_d) = e^{-\frac{g_d^2}{2 * \sigma^2}} \] Given that each time slot represents 30 minutes from 8:00 to 20:00, there are indeed 24 slots in a day. The maximum of possible gaps is 22 when there is a course at two extreme ends (8:00 and 20:00) and all other slots are empty. \( \sigma \in ]0, 22] \), we choose \( \sigma = 8 \)



2. Penalty function for a day \( d \), and a gap index \( i \) in the day \( d \), for exemple if the gap is between 8:30 and 9:00, the index is 1: \[ \text{penalty_gap_position}(g_{d, i}) = 1 - \frac{abs(i - midday)}{midday} \] where \( midday = \frac{nb\_slots}{2} = 12 \). The idear is to penalize gaps that are far from the middle of the day because they need less operations to be filled.

3. Function \(\text{nb_gaps_for_students}(tt)\), which uses these penalties for each day in the timetable (TT): \[ \text{nb_gaps_for_students}(tt) = \frac{1}{\left|\:\text{tt}\right|} * \sum_{d \in \text{tt}} \left( \beta_1 * \text{penalty_nb_gaps}(g_d) + \frac{\beta_2}{\left|\,g_d\right|} * \sum_{i}^{g_d} \text{penalty_gap_position}(g_{d, i}) \right) \] In this function, \( \beta_1 \) and \( \beta_2 \) are hyperparameters that we set to 0.75 and 0.25 respectively.

Size of gaps between hours for teachers

1. Penalty function for a day \( d \), based on the number of gaps between class hours \( g_d \): \[ \text{penalty_nb_gaps}(g_d) = e^{-\frac{g_d^2}{2 * \sigma^2}} \] Given that each time slot represents 30 minutes from 8:00 to 20:00, there are indeed 24 slots in a day, with up to 22 gaps possible if a class is placed at only two extreme ends (8:00 and 20:00) and all other slots are empty. \( \sigma \in ]0, 22] \), we choose \( \sigma = 8 \)



3. Function \(\text{nb_gaps_for_students}(tt)\), which uses these penalties for each day in the timetable (TT): \[ \text{nb_gaps_for_students}(tt) = \frac{1}{\left|\:\text{tt}\right|} * \sum_{d \in \text{tt}} \text{penalty_nb_gaps}(g_d) \]

Number of hours on Saturday

1. Penalty function for saturday \( d \), based on the number of slots (half hours) \( h_d \): \[ \text{penalty_saturday_hours}(g_d) = e^{-0.3 * h_d} \] I've chosen 0.3 as a hyperparameter to penalize fast the number of hours on saturday.

Size of the lunch break

1. Penalty function for a day \( d \), based on the number of slots (half hours) free between 11:30 and 13:30 \( h_d \): \[ \text{penalty_lunch_break}(g_d) = \frac{1}{e^{-5(h_d - 0.9) + 1}} \] I used a sigmoid function to penalize if the lunch break is smaller than an hour. The hyperparameter are adjusted to fit the problem.

We consider \( \Omega \) as the set of all possible association of (day, hour of beginning, course) for a week.
If we consider \( \text{tt} \in \mathbb{T}_{week} \) and \(\Omega_{tt} = \bigcup_{d \in \text{tt}, h \in \text{tt}_d} \{d, h, tt_{d,h}\} \), then \(\Omega_{tt} \subseteq \Omega\).
It follow that the score function is also applicable to the subset \(\Omega_{tt}\): \( score(tt) = score(\Omega_{tt}) \)

\(\Omega_{i} = \{\alpha_1, \alpha_2, ..., \alpha_n\}\) with \(\alpha_i \in \Omega\)
We define \( P_i \) the probability to choose \( \alpha_i \) and \( \Omega^{\displaystyle \prime} \) the association between know score and \(\alpha_i\) (also named the learning/pheromone table).
In fact, every time we generate a timetable we had the score associated with every \( \alpha_i \) in \( \Omega^{\displaystyle \prime} \). \[ P_i = \gamma * impact + \varepsilon * \Omega^{\displaystyle \prime}_i \] where \( \gamma \) and \( \varepsilon \) are hyperparameters, \( \Omega^{\displaystyle \prime}_i \) is the average score associated with \(\alpha_i\).
\(\varepsilon = 1 - \gamma\) we start the algorithm with \( \gamma = 1 \) and \(\Omega^{\displaystyle \prime}_i = \{\} \). After each iteration, we incrase \( \varepsilon \).
The impact function is determinist and represents how many other \(\alpha \) will be not available if we choose \(\alpha_i\). For exemple if we choose a course on monday at 8:00, we can't choose another course at 8:00 on monday, so we will impact all the other association on monday at 8:00 as well as the association with the same course. The impact is considered more important if an impacted association don't has a lot of other possibilities.

The \(\alpha_i\) selected is the result of a random choice based on the probability distribution \( P \).