# Allocating Students to Industry Placements Using Integer Programming and Ant Colony Optimisation
## 5 Ant Colony Optimisation  
ACO is proven on a number of practical problems [9], and among the ACO implementations, \(\mathcal{M}\)ax-\(\mathcal{M}\)in Ant System (\(\mathcal{M}\)MAS) has been one of the most effective practical ACO variants [34]. Hence, this approach is used as the basis for our ACO implementation for the IBL problem. We also found that the heuristic selection of the ant colony system [35] provides improved intensification; hence, we use this step for the selection of the solution components. Algorithm 1 shows the \(\mathcal{M}\)ax-\(\mathcal{M}\)in Ant System applied to the IBL problem.  
A solution is represented by \(\pi\), which is a vector of placements. The length of \(\pi\) corresponds to the number of students and \(\pi_{i}=j\) means that student \(i\) is allocated to placement \(j\). (Note that this is not an allocation to a company but to a specific placement of a company. This difference is important in the case where a company requires more than one placement.) The input to the algorithm is an instance of the problem. The pheromone trails are initialised (Initialise(\(\mathcal{T}\))), where \(\tau_{ij}=\frac{1}{p_{ij}}\) is the desirability of allocating student \(i\) to placement \(j\).  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Student** & **Company** & \(c_{1}\) & \(c_{2}\) & **Gender** \\ \hline \(s_{1}\) & \(p_{11}=1\) & \(p_{12}=3\) & male \\ \hline \(s_{2}\) & \(p_{21}=2\) & \(p_{22}=1\) & male \\ \hline \(s_{3}\) & \(p_{31}=3\) & \(p_{32}=2\) & female \\ \hline \(r_{c}\) & \(r_{1}=2\) & \(r_{2}=1\) & \\ \hline \(v_{c}\) & \(v_{1}=3\) & \(v_{2}=1\) & \\ \hline \hline \end{tabular}
\end{table}
Table 2: The table of preferences and the number of available placements of companies.  
A number of solutions (\(n_{ants}\)) to the problem are constructed in Lines 4-5. A solution is built incrementally by allocating a student to a placement using the pheromone information (\(\mathsf{AllocStatents}(\mathcal{T})\)). If a company preference for a student is 3 (not desired), the student is not allowed to be allocated to the corresponding placement(s). A placement for a student is selected using one of two rules. First, a random number is generated \(q\in(0,1]\) and compared with the parameter \(q_{0}\). If \(q<q_{0}\), placement \(k\) is chosen for student \(i\) according to:  
\[k=\operatorname*{argmax}_{j\in\mathcal{C}}\tau_{ij}\cdot\eta_{ij} \tag{9}\]  
Otherwise, if \(q\geq q_{0}\), placement \(k\) is chosen probabilistically according to:  
\[P(\pi_{i}=k)=\frac{\tau_{ik}\cdot\eta_{ik}}{\sum_{j\in\mathcal{C}}\tau_{ij} \cdot\eta_{j}} \tag{10}\]  
Here, \(\eta\) is a heuristic factor that biases the selection towards higher preference placements, i.e., \(\eta_{ij}=\frac{1}{p_{ij}}\) for student \(i\) and placement \(j\).  
In Line 7, the iteration best solution is determined as the one with the minimum objective value (Equation (2)). The global best solution (Line 8) is then updated if a new better iteration of the best solution was found. Finally, in Line 9, the pheromone trails are updated in two steps. First, all solution components that are not found in the global best solution have evaporation applied:  
\[\tau_{ij}=\tau_{ij}\cdot(1.0-\rho) \tag{11}\]  
Otherwise, the solutions components are updated with the allocation found in the global best solution. In addition to evaporation, this step additionally includes a reward factor to favour components in the global best solution. The pheromones are updated according to:  
\[\tau_{ij}=\tau_{ij}\cdot(1.0-\rho)+\delta \tag{12}\]  
where \(\delta=Q/f(\pi^{bs})\), \(f(\pi^{bs})\) is the objective value of the global best solution determined according to Equation (2) and \(Q\) is selected such that \(0.01\leq\delta\leq 0.1\). The learning rate, \(\rho\), was chosen to be relatively high at 0.1, and determined on a subset of the instances from the values [0.1, 0.05, 0.01].