## 4 Methodology
### Ant Colony System  
Algorithm 1 lists a single-objective implementation of BACS [7] with concepts from a multi-objective ACS formulation [35]. ```
1:input: Component deployment instance
2:\(G=\emptyset\)
3:\(G=G\cup\{\text{a randomly generated intial solution }\pi^{t}\}\)
4:while termination conditions not satisfied do
5:\(G^{\prime}\gets G\)
6:for\(\text{b}\in G^{\prime}\)do
7:\(I=\text{ACS}(\text{b})\)
8:\(G=\text{UpdateSols}(G,I)\)
9:endfor
10:endwhile
11:OUTPUT:\(G\)
```  
**Algorithm 1** Ant Colony System for Multi-objective Component Deployment  
An initial solution (\(\pi^{t}\)), generated by randomly assigning software components to hardware units (\(\pi_{i}=j\) is equivalent to \(\text{d}(i)=j\), where the \(i^{th}\) software component is assigned to hardware unit \(j\)), is added to set of non-dominated solutions (\(G\)). The main algorithm is then run to a time-limit (line 4). Within this loop, an ACS is conducted on each solution in the set of non-dominated solutions, \(G\), and the output solutions of the ACS are considered for inclusion in \(G\) (lines 6-8). Thus, the complete set of non-dominated solutions is maintained in \(G\) which is output at the end of the algorithm. The procedure of updating solutions in line 8 works as follows. All solutions in the set \(I\) are equal in terms of constraint violations and all of these are non-dominated. These solutions are compared with those in \(G\) and the best (least violating) non-dominated solutions after considering both sets are returned. More formally, a solution \(\pi^{\text{nd}}\) is considered an improvement on the existing solutions if it violates fewer constraints than those solutions: \(v(\pi^{\text{nd}})<v(\pi^{\text{b}})\), \(\forall\pi^{\text{b}}\in G\). In this case, all solutions in \(G\) are removed and \(\pi^{\text{nd}}\) inserted. However, if the violated constraints are equal (\(v(\pi^{\text{nd}})=v(\pi^{\text{b}})\), \(\forall\pi^{\text{b}}\in G\)), then \(\pi^{\text{nd}}\) is considered non-dominated in the set \(G\) if there is no other solution in the set which is an improvement on \(\pi\) when considering both objectives: \(\pi^{\text{nd}}:R(\pi^{\text{nd}})>R(\pi^{\text{nd}})\lor co(\pi^{\text{nd}})< co(\pi^{\text{nd}})\), \(\forall\pi^{\text{b}}\in G\). Algorithm 2 shows the ACS procedure conducted on a single solution b. This is now effectively the ACS procedure in the single objective setting, as detailed in Reference [7]. The pheromone trails are initialised and b is added to the set of best non-dominated solutions \(I\). The main ACS loop executes between lines 3-11 and the terminating criteria include an iteration limit and a time limit. Within this loop, a number of solutions are constructed and added to the set \(S\) (lines 5-7). Each solution is incrementally constructed by assigning software components to hardware units using the pheromone trails. In particular, the solution construction works as follows. A random number \(r\) is chosen in the range \([0,1]\), and compared to pre-defined parameter \(q\). If \(q\leq r\), hardware unit \(k\) is chosen with probability:  
\[P(\pi_{i}=k)=\frac{\tau_{ik}}{\sum_{j\in\mathcal{H}}\tau_{ij}}, \tag{11}\]  
where \(\tau_{ik}\) is the desirability of selecting hardware unit \(k\) for component \(i\). If \(q>r\), hardware unit \(k\) is selected such that it has the highest pheromone value:  
\[k=\operatorname*{argmax}_{j\in\mathcal{H}}\{\tau_{ij}\} \tag{12}\]  
Moreover, each time a hardware unit is chosen for a software component, the ACS local pheromone update applies:  
\[\tau_{ij}=\max\{\tau_{ij}\cdot(1.0-\rho),\tau_{min}\}, \tag{13}\]  
where \(\rho\) is the learning rate and \(\tau_{min}\) is a small constant that ensures that a hardware unit may always have a chance to be selected for a software component. In Line 9, the set of non-dominated solutions, \(I\) is updated with the best non-dominated solutions considering \(S\) and \(I\). The choice of these solutions is carried out exactly as described earlier when discussing Algorithm 1.